关于迅雷笔试题

只看该作者 · 2012-8-27 17:55

//求解0-n中（包含0，但不包含n）m个不重复随机数的算法.
void knuth(int n, int m)
{
srand( (unsigned)time( NULL ) );
for( int i =
0; i < n; i++)
{
      if( rand()%(n-i) < m)
      {
         cout << i <<
"\t";
         m--;
      }// end if
}//end for

return;
}
不理解点：
1.if( rand()%(n-i) < m)
{
cout << i << "\t";
m--;
}// end if
此处if语句的思路是什么？
个人理解到的：
1）通过m来控制个数。因为题意是求解[0,n-1]的m个不重复的数。
2）rand()%(n-i)即求解的随机数除以(n-i)的余数，此处n-i的值
取为{n,n-1,n-2,...1}.
但串起来还是不太理解此处的思路，望大家指点提示，谢谢！
或者对于求解不重复随机数有没有更好的方法或思路也可以交流。
以前写过，但是比这要复杂很多，这是我见到的最简洁的一种。

只看该作者 · 2012-8-27 18:08

这迅雷的笔试题难度还不小

1万 · 2012-8-27 18:38

由题意m必定小于n，从0至n-1中找出m个随机数，那么这n个数可以分为两组：要求的不重复的随机数（m个）+非要求的随机数（n-m个）；i不断自增，n-i不断自减，所以 rand()%(n-i)最终会为0，而每得出一个要求的不重复的随机数，m自减，所以m最终也为零，所以当一共得带来m个要求数，循环会停止；if判断i是否为随机数的依据是rand()%(n-i)和m相比，可能是大于，也可能是小于，结果是随机的，而每个数符合条件的概率是m/n