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

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

csdn上看到的一帖子 http://topic.csdn.net/u/20120825/20/6171393d-15ea-4a50-ba30-78d1d24974e3.html，是关于一种不重复随机算法，可以计算0 ~ n中不重复的m个数。

#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)很让人不解。帖子的楼主啰嗦了一大堆，于是我干脆自己分析一下。

一、如何不重复

这里取出发生的代码是

 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的情况，所以上面的假设一定成立。

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

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时，条件二是永远不能成功的。

总结：从复杂度看，此算法 <= O(n)，性能很好。不过有人怀疑它的可随机性，这需要更强的数学证明，目前我还做不到。