一路迅雷笔试题引发的思考？2012-8-25

一道迅雷笔试题引发的思考？2012-8-25

//求解0-n中（包含0，但不包含n）m个不重复随机数的算法.

C/C++ code

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}.
但串起来还是不太理解此处的思路，望大家指点提示，谢谢！
或者对于求解不重复随机数有没有更好的方法或思路也可以交流。
以前写过，但是比这要复杂很多，这是我见到的最简洁的一种。

[解决办法]
由题意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
。。。不知道这样理解对不对
[解决办法]
因为lz你问了 所以我才给出解答

这是你的问题
不理解点：
1.if( rand()%(n-i) < m)
{
cout << i << "\t";
m--;
}// end if
此处if语句的思路是什么？

我的思路就是解答

结果你又问我要代码......
那我只能ctrl+c +v

查看更多 下一篇