题目描述
假设n远大于m，编程实现从0到n-1中随机等概率的输出m个不重复的数。
void 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值，总共满足条件的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个数，此时如果0已经输出了，则m已经自减，此时为m-1，则i=1被输出的概率为(m-1)/(n-1)；如果0没有被输出，则m未自减，此时，i=1被输出的概率为m/(n-1)。此时，i=1被输出的概率为(1-m/n)x(m/(n-1))+m/nx(m-1)/(n-1)=m/n。 依次类推，每个数被输出的概率都是m/n。
转自：http://blog.csdn.net/u010296036/article/details/70036924
