c语言中的随机函数分析与生成m个不重复随机数算法比较

1、c 语言中的随机函数分析与生成 m 个不重复随机数算法比较(转)C+&STL 2008-12-19 18:04:45 阅读134 评论0字号：大中小订阅一说起随机函数，恐怕又有人说这是老生长谈了一般很多人都形成了自己的固定格式，因为随机数用处比较大，用的时候比较多，拿过来就用了。但是新手不这么干，他们总是抱有疑惑，我就是一个新手， 而且较菜为了让跟我一样的菜鸟看明白，我会尽量的说得让高手们不屑一顾（：由于可能内容太多可能会分篇，大家见谅麻烦了比如所随机数，因为函数嘛，总会是确定的，确定的算法就会生成确定的结果。各种编程语言返回的随机数（确切地说是伪随机数）实际上都是根据递推公式计算的一组数值，

2、当序列足够长，这组数c 的标准函数库提供一随机数生成器ran（stdlib.hRAND_MAX之间均匀分布的伪随机整数（RAND_MAX 3276732767）。例如：#include #include void main()for(int i=0;i10;i+) printf(%dn,rand();0RAND_MAX之间的等概率随机数列了。但是如果你第二次运行的时候会发现输出结果仍和第一次一样。：（原来rand（）生成伪随机数 时需要一个种子（计算伪随机序列的初始数值）才行，如果种子相同就会得到相同的序列结果（这就是函数的好处 “优点”列并对数据进行处理；解密时，再利用种子数生成一个伪随机序

3、列并对加密数据进行还原。这样，对于不知道种子数的人要想解密就需要多费些事了。当然，这种完全相同的序列对于你来说是非常糟糕的。要解决这个问题，需要在每次产生随机序列前，先指定不同的种子，这样计算出来的随机序列就不会完全相同了。srand()用来设置rand()产生随机数时的随机数种子。在调用rand()函数产生随机数前，必须先利用srand() 设好随机数种子（seed）, rand()1（有人说默认是0，困惑中）1 ，进 rand()(C random，可是random 函数ANSI Crandomgcc,vcsrand的选择是不是接近随机（不存在 完全随机Windows9x/NTFreeCe

4、ll就允许用户指定种子数，这样用户如果一次游戏没有成功，下次还可以以同样的发牌结果再玩一次。但我们还是喜欢系统自动生成最 简单的方法就是利用系统时间了（几乎所有的人都这么做），因为时间的数值随时间变化而变化，运行两 次，一般不会出现前一次和后一次相同的局面，time(NULL)会返回一个表示当前系统时间的整数（它在time.htime()197011日到现在的秒数，有的说是unix元年，不知道这 两个是不是一天:（ ，另外有的嫌麻烦会写作time（0）。我们这么来写：srand(srand(unsigned)time(NULL);#include #include #includevoid m

5、ain()srand(int)time(0); for(int x=0;x10;x+)printf(%dn,(rand();据说如果软件一直开两天，种子会有 1/(60*60*24)个可能会重复，虽说这对于一般人已经绝对足够了，但纵然人不舒服，于是我在网上开到有这么写的：#include #include #include #includevoid main(void)int i; unsigned int seedVal; struct timeb timeBuf;ftime(&timeBuf); seedVal=(unsigned int)timeBuf.time&0 xFFFF)+(un

6、signed int)timeBlitm) (unsigned int)timeBlitm);srand(unsigned int)seedVal); for(i=0;i10;+i)printf(%6dn,rand();（下面是关于它的解释，但我也不是太明白，引用过来大家分析一下）“ 上面的程序先是调用_ftime()来检查当前时间，并把它的值存入结构成员timeBuf.time 197011_ftime()之后，在结构timeBuf的成员millitm中还存入了当前DOS中这个数字实际上是以百分之一秒来计算的。然后，把毫秒数和秒seedVal的取值范围，并进一步加强它

7、的随机性，但上例用的逻辑运算就已经足够了。”看下面代码：void main()for(int i=0;i100000;i+)printf（%dn,rand();为什么总是生成一个数？因为此程序产生一个随机数之前，都调用一次 srand，而由于计算机运行很快，所以每用time 得到的时间都是一样的（time 的时间精度较低，只有 55ms）。这样相当于使用同一个种子产生随机序列，所以产生的随机数总是相同的。把 srand 放在循环外看看：srand( (unsigned)time( NULL ) ); for(int i=0;i100000;i+)问题解决了：）既然生成的是 0RAND_MAX

8、之间均匀分布的随机整数（我们姑且把以上方法生成的是理想的随机数 吧那么要生成0-x 之间(包括0 不包括的随机数就把改成 rand()/(double)RAND_MAX*x 要生成x-y 之间（包括x 不包括y）的就是 rand()/(double)RAND_MAX*(y-x)+x了。但是如果要生0-10之间的整数很多人会这么写：#include #include #includevoid main()srand(int)time(0); for(int x=0;x10;x+) printf(%dn,(rand()%10);x-y 的就是 rand()%(y-x)+x?懂一点概率的就知道这样写

9、，会使得到的数列分布不均的，但是大家确实都喜欢这么写x （一些游戏目标,rand(). 当主角在地图上走的时候动不动冒出三两小兵挑衅兼找死.01，当变量=随机取得的数时，小兵出现），这样写足够了下面再讨论生成 m 个小于n 的不重复随机数的算法本人认为算法结构很重要，但语句结构也很重要，所以我喜欢一个算法给出多个语句结构最容易想到的傻瓜算法，逐个产生这些随机数，每产生一个，都跟前面的随机数比较，如果重复，就重新产生：算法一（1）for(j = 0; j m; j+) a:aj = rand() % n; for(i=0;ij;i+)if(ai=aj)goto a;goto goto 可以直接转

10、译，而且循环goto 可以break continue 语句使这些结构实现成为可能，后来发现goto 的使用会造成维护和调试的许多麻烦，所以循环逐渐代替了goto 了，如果用 goto 还会被认为编程修养不好言归正题，把它的 goto 去掉： 算法一（2）srand(unsigned)time(NULL);j=0;while (jm)aj = rand() % n ; for(i=0;ij;i+)if(ai=aj) break; if(ij)continue;j+但是后来都建议用 for 循环，这样可以使循环条件跟紧凑： 算法一（3）srand(unsigned)time(NULL); for

11、(j=0;jm;j+)aj=rand()%n; for(i=0;ij;i+)if(ai=aj)i=-1;aj=rand()%n;但这是个很笨的方法，且比较次数呈线性增长，越往后次数越多另一个想法是生成一个就把它从中去掉，就可以实现不重复了：算法二（1）for (i=0;in;i+)ai=i+1;for(i=0;im;i+)j=rand()%(n-i);bi=aj;for (k=j;kn-i-2;k+) ak=ak+1;b是生成的随机数列这样做也太麻烦了，生成的直接做个标记不就行了？ 算法三（1-1）i=rand()%m; ai=1;b0=i;for(j=1;jm;j+)for (i=rand(

12、)%m;ai=1;i=rand()%m); bj=i;ai=1;写紧凑一些吧，直接： 算 法 三 （1-2） for(j=0;jm;j+)for (i=rand()%m;ai=1;i=rand()%m); bj=i;ai=1;但是我看到了更简洁的：intn=某值； intan=0；for (i=1;i=n;i+)while(ax=rand()%n);ax=i;这个无循环体的 while 保证 am是初始化的 0 状态。这生成了n 个，我们只取m 个，这太浪费了，结合一下：int n=某值，m=int an=0,bmfor (i=1;i=n;i+)while(ax=rand()%n);bi=x;ax=1;但是总叫人不舒服，对这种算法谁有更好的写法呢？这种算法越到后面，遇到已使用过的元素的可能性越高，重复次数就越多，但是当m 较小时还是很好的：） 这都不太让人满意么？看看下面这个：算法四（1）for (i=0;i0;i-)w=rand()%i;t=ai; ai=aw; aw=t;0 n 0 n-2 个数组下标，把这个下标的元素值跟n-1 下标的元素值交换，一直进1 的元素。因此它只需要遍历一次就能产生全部的随机数。但这样会生成 n 个小于n 的随机数，我们只要m 个，再加两句：for(i=0;im;i+) bi=ai;b是生成的随机数列m 和n 算法四（2）f