/********************************************\
|????歡迎轉載, 但請保留作者姓名和原文鏈接, 祝您進步并共勉!???? |
\********************************************/

非“偽”隨機數的生成

作者: Jerry Cat
時間: 2006/05/16
鏈接:? http://www.shnenglu.com/jerysun0818/archive/2006/05/16/7232.html

問題的來由 - "隨機取m個數（在1到n的范圍之內），（m <= n)，要求m個數沒有重復。有沒有
什么好的算法，時間復雜度和空間復雜度都很好"

----------------------------------------------------------------
方案一:
取隨機數可以用C++標準的rand，至于M個不重復，你可以用std::set來解決，把取道的隨機數
插入到set里面，set的size() == m就可以了, 具體可以這樣:

#include <set>
#include <stdlib.h>

int main()
{
?? std::set<int> s;
?? while(1)
?? {
????? int r = rand() % n;
????? s.insert(r);
????? if(s.size() == m)
????? {
???????? break;
????? }
?? }
}

?由于set底層實現是紅黑樹，插入復雜度是對數級的^_^

----------------------------------------------------------------
方案二:
#include <iostream>
#include <cstdlib>????? //用于rand()和srand()函數
#include <ctime>??????? //設置不同的隨機數

using namespace std;

int main (){
??? srand( time( 0 ) );??? //調用不重復的隨機數函數
??? unsigned i;
??? for ( int n = 0; n++ < 10; )
??? {
??????? i = rand() ;??????? //對i 賦系統的隨機數
??????? cout << " The NO." << n << "is : " << i << endl;
??? }

??? return 0;
}

1. C++標準函數庫提供一隨機數生成器rand，返回0－RAND_MAX之間均勻分布的偽隨機整數。 RAND_MAX
?? 必須至少為32767。rand()函數不接受參數，默認以1為種子（即起始值）。

?? 隨機數生成器總是以相同的種子開始，所以形成的偽隨機數列也相同。失去了隨機意義。

2. C++中另一函數srand（），可以指定不同的數（無符號整數變元）為種子。但是如果種子相同，偽
?? 隨機數列也相同。－－一個辦法是讓用戶輸入種子，但是仍然不理想。

3. 比較理想的是用變化的數，比如時間來作為隨機數生成器的種子。
?? 在 頭文件ctime中時間庫包含time函數，它可以返回一個表示時間、日期、月和年的數值使用如
?? 下調用可將該值設為rand的種子
?? srand(static_cast<unsigned>(time(static_cast<time_t*>(NULL))));

4. 但, srand()并不是說使隨機數都不一樣,它只是使取隨機數的種子隨著時間而改變:)
?? So, 還是方案一好!