/********************************************\
|????歡迎轉(zhuǎn)載, 但請(qǐng)保留作者姓名和原文鏈接, 祝您進(jìn)步并共勉!???? |
\********************************************/

非“偽”隨機(jī)數(shù)的生成

作者: Jerry Cat
時(shí)間: 2006/05/16
鏈接:? http://m.shnenglu.com/jerysun0818/archive/2006/05/16/7232.html

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

----------------------------------------------------------------
方案一:
取隨機(jī)數(shù)可以用C++標(biāo)準(zhǔn)的rand，至于M個(gè)不重復(fù)，你可以用std::set來解決，把取道的隨機(jī)數(shù)
插入到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底層實(shí)現(xiàn)是紅黑樹，插入復(fù)雜度是對(duì)數(shù)級(jí)的^_^

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

using namespace std;

int main (){
??? srand( time( 0 ) );??? //調(diào)用不重復(fù)的隨機(jī)數(shù)函數(shù)
??? unsigned i;
??? for ( int n = 0; n++ < 10; )
??? {
??????? i = rand() ;??????? //對(duì)i 賦系統(tǒng)的隨機(jī)數(shù)
??????? cout << " The NO." << n << "is : " << i << endl;
??? }

??? return 0;
}

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

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

2. C++中另一函數(shù)srand（），可以指定不同的數(shù)（無符號(hào)整數(shù)變?cè)榉N子。但是如果種子相同，偽
?? 隨機(jī)數(shù)列也相同。－－一個(gè)辦法是讓用戶輸入種子，但是仍然不理想。

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

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