24小时热门版块排行榜    

CyRhmU.jpeg
查看: 874  |  回复: 21
当前主题已经存档。
当前只显示满足指定条件的回帖,点击这里查看本话题的所有回帖

ms98

[交流] 【讨论】出个算法题大家松松脑筋

大家都知道很多语言都能产生(伪)随机数,为了不涉及到具体语言,我们假设函数Rand能产生1-100间的随机数。既然是随机,那么不保证不重复。例如,产生的数字为5,62,33,5...虽然每个数字都是随机的,但是有重复。
现在问题是,要得到70个随机数,其范围都在1-100之间,但是不允许重复。大家会如何设计该算法?
(我知道答案,但不是自己想出来的,感觉很巧妙,大家也想想吧,挺有意思)
回复此楼
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

dellus

木虫 (职业作家)

★ ★
小木虫(金币+0.5):给个红包,谢谢回帖交流
wangen994(金币+1,VIP+0):谢谢交流,你的方法确实有点麻烦 6-20 10:31
来试下
第一个数由Rand直接生成
接下来从剩于99个中随机取出,先求该数在99个数的队列中的位置: M=(99-1)*Rand/100+1,然后读出该数,(跳过已取出数即可)
再取第三数的位置: M=(98-1)*Rand/100+1
...
循环70次

感觉有点繁琐,期待答案
岂能尽如人意,但求无愧于心。
3楼2009-06-20 05:32:39
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 22 个回答

woshilsh

荣誉版主 (职业作家)

优秀版主

★ ★
小木虫(金币+0.5):给个红包,谢谢回帖交流
wangen994(金币+1,VIP+0):谢谢交流 6-20 10:31
产生的时候,发生重复就删除,继续生成?

巧妙的办法还真没,没仔细想过,呵呵,楼下继续
[center][url=http://www.91cool.net/][img]http://id.91cool.net/sign/?name=小木虫印&say=各位版主辛苦了![/img][/url][/center]
2楼2009-06-20 01:09:57
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

studyhae

木虫 (正式写手)


小木虫(金币+0.5):给个红包,谢谢回帖交流
重复了就重新随机呀,呵呵
4楼2009-06-20 07:55:12
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

dellus

木虫 (职业作家)

★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖交流
wangen994(金币+2,VIP+0):谢谢交流,哈哈 6-20 16:06
引用回帖:
Originally posted by dellus at 2009-6-20 05:32:
来试下
第一个数由Rand直接生成
接下来从剩于99个中随机取出,先求该数在99个数的队列中的位置: M=(99-1)*Rand/100+1,然后读出该数,(跳过已取出数即可)
再取第三数的位置: M=(98-1)*Rand/100+1
...
...

补充一下
采用数组G存放1-100
假设进行到某一步时存在N个未被选的数,选到其中第M个(M<=N),取出G(M),然后将G(M)赋值为最后一个数G(N),这样下一步数组中前N-1个数都是未被选到的,同样可以直接取出G(M')。

这样的优点有二:
1) Rand只要运行70次
2) 不需要判断取到的随机数是否重复
岂能尽如人意,但求无愧于心。
5楼2009-06-20 08:38:34
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
普通表情 高级回复(可上传附件)
信息提示
请填处理意见