面试(54)
问题描述:
设rand(s,t)返回[s,t]之间的随机小数,利用该函数在一个半径为R的圆内找随机n个点,并给出时间复杂度分析。
在半径为R的圆内找随机的n个点,既然是找点,那么就需要为其建立坐标系,如果建立平面直角坐标系,以圆心为原点,建立半径为R的圆的直角坐标系。要使随机的点在圆内,则必须使其所找的点 point 的x,y坐标的绝对值小于R,问题转化为:随机的找n个圆内的点,使其x,y坐标的绝对值均小于R。这里以x为例, 首先 x 应满足 -R&= x &= R; &y同理。这样产生的点均在以圆心为中心,边长为2R的正放形内,需要另外判断其距离R的值。本文介绍采用极坐标的形式,建立圆的极坐标系,则圆内的任意一点满足&P(ρ,θ)(用ρ表示线段OP的长度,θ表示从Ox到OP的角度angle),此时问题转化为:找一点,使其到圆心的距离OP大于等于0
小于R,极角大于等于0 小于360,则OP=rand(0, R) ,当 OP== R 时重新寻找,angle = rand(0,360) ,当angle==360时,重新寻找。每找到一个点p,将其与之前所找到的所有点进行比较,若重合,则继续寻找,否则将其加入到已找到的点集合中,直到找到n个点。
存放点的数据结构
typedef struct Point{
算法流程:
for( i= i &0; i--)
& &产生 p.r = rand(0,R),且p.r != R
& &产生 p.rangle = rand(0,360) ,且 p.rangle != 360
& &遍历所有产生的点,若 p 已经存在,则重新生成该点
& &否则将其加入到产生的点集合中
生成第n个点,需要先遍历前n-1个点,时间复杂度为O(n),故生成n个点的时间复杂度为O(n^2)
参考知识库
* 以上用户言论只代表其个人观点,不代表CSDN网站的观点或立场
访问:89826次
积分:1817
积分:1817
排名:第17892名
原创:84篇
转载:78篇
(2)(1)(4)(1)(1)(20)(43)(9)(2)(2)(7)(24)(26)(20)