声明:摘自牛客输出随机数:从0...n-1中等概率随机输出m个不重复的数字,并且假设n远大于m
knuth(int n, int m)
{
srand((unsigned int)time(0));
for (int i = 0; i < n; i++) {
if (rand () % (n - i) < m) {
cout << i << endl;
m--;
}
}
}
由这个for循环循环n次,且在满足条件时才输出i,可知,输出m个不同值的要求已满足,因为每次输出的都是i值,而i值每次都是不一样的,m--保证了程序在输出了m个值后就停止循环。
在i=0时,rand()%(n-i)的取值范围为0到n-1,共n个数,此时要输出0只需要rand()%(n-i)小于m,故i=0被输出的概率为m/n;
在i=1时,rand()%(n-i)的取值范围为0到n-2,共n-1个数,若i=0没有被输出,则m--未被执行,此时i=1被输出的概率为m/(n-1),若i=0已经被输出了,则m变为m-1,此时i=1被输出的概率为(m-1)/(n-1);由概率论的知识,可知此时i=1被输出的概率为
P=(1-m/n)*(m/(n-1))+m/n*((m-1)/(n-1))=m/n;以此类推,可知每个数被输出的概率都为m/n