一道迅雷笔试题引发的思考？—— 不重复随机算法

关于一种不重复随机算法，可以计算0 ~ n中不重复的m个数。

[cpp] 
#include <iostream> 
#include <stdlib.h> 
using namespace std; 
 
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; 
} 
 
int main() 
{ 
    knuth(10, 5); 
    return 0; 
} 
常见的算法有2种：

1、用一个大小为n的数组，随机取出一个，把该位置标为已取，防止下次重复取出；重复m次。缺点是当m接近n时，最后重复取出的概率很大。

2、包0 ~ n放在数组中，通过一些方法打乱顺序（比如交换法），然后取出前m个即可。

而上面的方法看起来很神奇，特别是 if ( rand() %(n-i) < m)很让人不解。帖子的楼主啰嗦了一大堆，于是我干脆自己分析一下。

一、如何不重复

这里取出发生的代码是

[cpp] 
cout << i << "/t"; 
 i 在for循环中，每次加1。因此可以保证每次cout都没有重复。
二、如何保证m次

rand() % (n-i) 的结果是从 [0, n-i]中随机取出一个，当n-i < m时，则if判断肯定能成功！m每次判断成功后都减一，所以这个判断肯定可以成功m次。而i最小值是0，所以当n > m时，肯定会出现某时刻 n - i < m的情况，所以上面的假设一定成立。

其实上面的算法可以再改一改

[cpp] 
void knuth(int n, int m) 
{ 
    srand( (unsigned)time( NULL ) ); 
    for( int i = 0; i < n && m; i++) 
    { 
        if( rand()%(n-i) < m) 
        { 
            cout << i << "/t"; 
            m--; 
        }// end if 
    }//end for 
    return; 
} 
因为当m等于0时，条件二是永远不能成功的。