S.l.e!ep.￠%

數比較，如果重復，就重新產生。這是個很笨的方法，且比較次數呈線性增長，越往后次數越多。其實這些

比較是多余的，完全可以不進行比較，只要反過來，按順序產生這些數，但隨機產生它們的位置。例如下

面產生100個100以內不重復隨機數的代碼：

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

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

序用0到99填滿整個數組；第三行，是隨機產生從0到m-2個數組下標，把這個下標的元素值跟m-1下標的元

素值交換，一直進行到下標為1的元素。因此它只需要遍歷一次就能產生全部的隨機數。

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

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

這段代碼也是隨機產生位置，但它預先把整個數組初始化為0，然后隨機產生其中一個位置，如果該元素

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

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

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

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

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

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

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

問題的來由 - "隨機取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, 還是方案一好!

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

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

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

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

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

1fori ← 1to length[a]
2???doj ← random() //隨機產生一個a數組的下標
3?????? exchange a[i]←→a[j]//交換a[i]與a[j]
4

當范圍數組與目標數組的大小非常接近時,上述算法非常有效,建議采用.

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

1lower ← 101
2upper ← 200
3fori ← 1to upper-lower+1
4????dob[i]=lower+i-1
5fori←1to length[a]
6????dosubscript =(int)(length[b]*Rnd +lower)//隨機產生b數組的一個下標,Rnd產生0~1隨機數
7??????? temp ← b[subscript]
8??????? b[subscript] ← b[length[b]]
9??????? length[b]--;
10??????? a[i]=temp;
11