生成不重复的随机数

前天(周三)的方法课结束前,照例大家争先恐后地争抢下周课文献的阅读权,因为如果不负责做某篇文献的summary,就必须提交一个对所有文献的response。换言之,如果负责做某篇文献的summary就基本上可以偷懒掉其他的文献了(当然仍要提防课上被提问到其他文献的内容),在这个激励下,每只手高举,每双眼睛充满着渴望,于是老师常常不知如何选择。这周Brooke干脆说了句:“要是有人会写个随机分配每周文献的程序就好了。” 我当时就打算试试,因为似乎只要用生成伪随机数的函数即可。
 
晚上先查了一下书,书上的例子是用time函数取当前的系统时钟做seed,再用rand函数生成伪随机数。依样画葫芦,居然编译没通过,提示是头文件的问题。于是重写了一个"hello world"做测试,错误依旧。怒了,上网找了些VC6.0基础教程之类的东西看了看,似乎没问题呀。折腾了好久,不知怎么编译就通过了,靠。
 
程序运行后发现有个问题:因为是就这学期剩下的所有文献进行随机分配,所以同一个人可能在同一周做1篇以上的文献的summary,这是不合课堂要求的。于是必须进行修正:每周的每篇文献应该是随机分配给某个人做summary的,而且每个人每周要做summary的文献不得大于1。这个问题相当于“洗牌问题”,可以用“洗牌算法”解决。
 
实际上每周的文献数n是恒小于全部人数m(实际为11人)的,故问题的实质是针对某一周的文献数n,从m个数中随机抽取n个数,并且这n个数是不重复的。最简单的算法是所谓的“打乱重排法”:
(1)先从原m个数中随机抽取1个数作为新数列的第一个数n[1];
(2)再从剩下的m-1个数中随机抽取1个数作为新数列的第二个数n[2];
(3)依次操作,直至原m个数中的最后一个数变成新数列的最后一个数n[m];
(4)取新数列的前n个数,这就构成了"从原m个数中随机抽取出来的且互不相等的n个数“。
 
 

About Hongwei Xu

I'm a social demographer, a single-child, a husband, and a father.
This entry was posted in 未分类. Bookmark the permalink.

3 条 生成不重复的随机数 的回复

  1. Unknown说道:

    很不错!支持一下。。。。哈。。。哈。另外,我家举行的MSN Space的空间评选活动(已经有1989人报名),今天是最后一天,看好啦!——最后一天!想参加的朋友赶快来报名。如果认为我是在“做广告”的朋友就不要来了。

  2. hou说道:

    牛~~~

  3. Hongwei说道:

    呵呵,雕虫罢了

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s