關於一種不重復隨機算法，可以計算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時，條件二是永遠不能成功的。
