S.l.e!ep.￠%

如何產(chǎn)生不重復(fù)的隨機(jī)數(shù)？最容易想到的方法，是逐個產(chǎn)生這些隨機(jī)數(shù)，每產(chǎn)生一個，都跟前面的隨機(jī)

數(shù)比較，如果重復(fù)，就重新產(chǎn)生。這是個很笨的方法，且比較次數(shù)呈線性增長，越往后次數(shù)越多。其實(shí)這些

比較是多余的，完全可以不進(jìn)行比較，只要反過來，按順序產(chǎn)生這些數(shù)，但隨機(jī)產(chǎn)生它們的位置。例如下

面產(chǎn)生100個100以內(nèi)不重復(fù)隨機(jī)數(shù)的代碼：

int a[100];
for(i=0; i<=99; ++i) a[i]=i;
for(i=99; i>=1; --i) swap(a[i], a[rand()%i]);

上面這段代碼只需要遍歷一次就可以產(chǎn)生這100個不重復(fù)的隨機(jī)數(shù)，它是如何做到的呢？首先第二行按順

序用0到99填滿整個數(shù)組；第三行，是隨機(jī)產(chǎn)生從0到m-2個數(shù)組下標(biāo)，把這個下標(biāo)的元素值跟m-1下標(biāo)的元

素值交換，一直進(jìn)行到下標(biāo)為1的元素。因此它只需要遍歷一次就能產(chǎn)生全部的隨機(jī)數(shù)。

??????? 再看下面的代碼，原理跟上面例子相似，但效率比上面的差點(diǎn)，但仍不失為一個好方法：

int a[100]={0};
int i, m;
for(i=1; i<=99; ++i)
{
??????? while(a[m=rand()%100]);
??????? a[m] = i;
}

這段代碼也是隨機(jī)產(chǎn)生位置，但它預(yù)先把整個數(shù)組初始化為0，然后隨機(jī)產(chǎn)生其中一個位置，如果該元素

值為0，表示這個位置還沒有被使用過，就把i賦予它；否則，就重新隨機(jī)產(chǎn)生另一個位置，直到整個數(shù)組

被填滿。這個方法，越到后面，遇到已使用過的元素的可能性越高，重復(fù)次數(shù)就越多，這是不及第一個方

法的地方，但總的來說，效率還是不錯的。

===================================================================================

1.產(chǎn)生一個隨機(jī)數(shù)(從0到32767)
?? srand((unsigned) time(NULL)); //為了提高不重復(fù)的概率
?? rand(); //產(chǎn)生隨機(jī)數(shù)

2.產(chǎn)生從m到n的隨機(jī)數(shù)(包括m,不包括n)
?? srand((unsigned) time(NULL)); //為了提高不重復(fù)的概率
?? rand()%(n - m + 1) + m;??????????????? //使用時將m和n換為具體數(shù)即可

==================================================================================

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

----------------------------------------------------------------
方案一:
取隨機(jī)數(shù)可以用C++標(biāo)準(zhǔn)的rand，至于M個不重復(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ù)雜度是對數(shù)級的^_^

----------------------------------------------------------------
方案二:
#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() ;??????? //對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ù)（無符號整數(shù)變元）為種子。但是如果種子相同，偽
?? 隨機(jī)數(shù)列也相同。－－一個辦法是讓用戶輸入種子，但是仍然不理想。

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

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

===============================================================================

生成無重復(fù)的隨機(jī)數(shù),注意,是不重復(fù)的序列.
?? 通常的生成隨機(jī)數(shù)的做法是不考慮重復(fù)的,因?yàn)榧词怪貜?fù)也屬于概率意義上的正常情況.但某些情況下需要不重復(fù)的隨機(jī)數(shù)據(jù),怎么辦呢?
?? 我想從大方向上來說,應(yīng)該只有兩個方法.要么犧牲時間要么犧牲空間.講得不對或不完整,大家一定要指出來啊,謝謝.

??????????????????????????? =---------------來源CSDN

??注意,下面均以在101~200的范圍內(nèi)(設(shè)為b[100],它實(shí)際上是附加空間),從中產(chǎn)生10個不重復(fù)的隨機(jī)數(shù)(設(shè)為a[10]).
??
一.犧牲時間為代價
?? 這種方法不需要附加空間b數(shù)組.
?? 要產(chǎn)生一定范圍內(nèi)不可重復(fù)的隨機(jī)數(shù)，把曾經(jīng)生成的隨機(jī)數(shù)保存起來作為歷史數(shù)據(jù)。產(chǎn)生一個新的隨機(jī)數(shù)后在歷史數(shù)據(jù)搜索，若找到就重新產(chǎn)生一個新的再重復(fù)數(shù)據(jù)搜索；否則就認(rèn)為已經(jīng)找到了一個新的不同隨機(jī)數(shù)。
?? 可以預(yù)見,每個新產(chǎn)生的隨機(jī)數(shù)都要與前面所有的數(shù)比較.若重復(fù),舍棄,再產(chǎn)生;否則,產(chǎn)生下一個.平均耗時n的平方量級.
?? 粗看起來，上面的程序似乎沒有什么問題，在執(zhí)行過程中程序也能夠通過。但，仔細(xì)分析我們就會發(fā)現(xiàn)問題出在一個新產(chǎn)生的隨機(jī)數(shù)是否已經(jīng)存在的判定上。既然是隨機(jī)數(shù)，那么從數(shù)學(xué)的角度來說在概率上，每次產(chǎn)生的隨機(jī)數(shù) r就有可能相同，盡管這種可能性很小，但確是一個邏輯性與正確性的問題。因此，每次產(chǎn)生的新的隨機(jī)數(shù)r都有可能是數(shù)組random的前i-1個數(shù)中的某一個，也就是說程序在運(yùn)行過程中由此可能會導(dǎo)致死循環(huán)!
??? 有人可能會爭辯說,這種概率很小嘛,幾乎為零.的確,但我要問,算法的五大特性是什么,其中兩大特性就是:確定性和有窮性.
??? 所以,怎么解決?犧牲空間.(稍后介紹)

二.犧牲空間為代價
?? 以下方法需要附加空間b數(shù)組.
?? (1)將范圍數(shù)組b[100](b[i]=100+i,不妨設(shè)數(shù)組下標(biāo)從1開始)的每個元素設(shè)置一個標(biāo)志位flag.初始均為flag=0;若某元素被選入到a數(shù)組中,則flag=1;顯然,以后再選到重復(fù)元素可以立刻判定是否已選.這不正是以空間換時間嗎?
?? 但是仍然有一個很嚴(yán)重的問題,在小規(guī)模輸入下,無疑它的表現(xiàn)是不錯的.但現(xiàn)在舉一個失敗的例子.
?? 在1~65536之間,選擇65500個不重復(fù)的隨機(jī)數(shù).看看后面的隨機(jī)數(shù),比如第65500個數(shù)(最后一個),它要在剩下的36個數(shù)中選擇才會有flag=0(根本不知道這36個數(shù)是什么);哼哼,概率36/65536.越到后面,隨機(jī)數(shù)越難產(chǎn)生,空間也換不了時間.
?? 改進(jìn):先在1~65536之間隨機(jī)選取36個數(shù),刪除.將剩下的65500個數(shù)依次賦值給a[65500],然后打亂順序即可,如下偽碼:

當(dāng)范圍數(shù)組與目標(biāo)數(shù)組的大小非常接近時,上述算法非常有效,建議采用.

(2)問題的最終解決.
?? 仍以最開始的那個例子來說,初始數(shù)組b[i]=100+i,a數(shù)組空.
?? 每次隨機(jī)生成數(shù)組b的一個下標(biāo)subscript，然后取出它所對應(yīng)的數(shù)據(jù)a[subscript],記下來.然后將數(shù)組b的最后一個數(shù)b[length]放到下標(biāo)subscript的位置，同時將數(shù)組a長度減1。盡管前若干次生成的下標(biāo)subscript隨機(jī)數(shù)有可能相同，但，因?yàn)槊恳淮味及炎詈笠粋€數(shù)填到取出的位置，因此，相同下標(biāo)subscript對應(yīng)的數(shù)卻絕不會相同，每一次取出的數(shù)都不會一樣，這樣，就保證了算法的確定性、有效性、有窮性.
偽碼算法如下: