如何高效产生m个n范围内的不重复随机数(m<=n)
发布网友
共1个回答
热心网友
如何产生不重复的随机数？最容易想到的方法，是逐个产生这些随机数，每产生一个，都跟前面的随机数比较，如果重复，就重新产生。这是个很笨的方法，且比较次数呈线性增长，越往后次数越多。其实这些比较是多余的，完全可以不进行比较，只要反过来，按顺序产生这些数，但随机产生它们的位置。例如下面产生100个100以内不重复随机数的代码：int a[100];
for(i=99; i>=1; --i) swap(a[i], a[rand()%i]);上面这段代码只需要遍历一次就可以产生这100个不重复的随机数，它是如何做到的呢？首先第二行按顺序用0到99填满整个数组；第三行，是随机产生从0到m-2个数组下标，把这个下标的元素值跟m-1下标的元素值交换，一直进行到下标为1的元素。因此它只需要遍历一次就能产生全部的随机数。 网上看到上述的方法：从生成随机数的角度出发这个方法确实很好，很快，但是仔细琢磨一番就知道：应该改为a[rand()%(i+1)],因为每一个数字i都有出现在i位置上的概率，要是总是将其交换出去，就会改变每个数字在每个位置上出现的概率。 第二，这个题目给出的是m个n以内的不重复的随机数，但是程序给出的是n个n以内的不重复的随机数，所以只需要输出a[n]的前m项，当m
