青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

S.l.e!ep.¢%

像打了激速一樣,以四倍的速度運轉,開心的工作
簡單、開放、平等的公司文化;尊重個性、自由與個人價值;
posts - 1098, comments - 335, trackbacks - 0, articles - 1
  C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理
2009-03-19 12:42
如何產生不重復的隨機數?最容易想到的方法,是逐個產生這些隨機數,每產生一個,都跟前面的隨機

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

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

面產生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
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲欧美区自拍先锋| 亚洲一区二区三区成人在线视频精品| 亚洲欧美日韩精品在线| 亚洲高清在线视频| 久久精品男女| 一区二区三区在线免费观看| 葵司免费一区二区三区四区五区| 欧美专区日韩专区| 在线欧美福利| 一区二区黄色| 国产在线播放一区二区三区| 久久网站热最新地址| 免费久久99精品国产自| 亚洲日本免费| 亚洲综合日韩中文字幕v在线| 国产在线观看一区| 亚洲电影免费在线观看| 欧美日韩亚洲另类| 久久av在线看| 你懂的国产精品永久在线| 亚洲一区免费视频| 久久久久久久久伊人| 99re66热这里只有精品3直播 | 亚洲免费在线播放| 欧美专区福利在线| 一区二区免费在线播放| 午夜视频一区二区| 日韩午夜在线视频| 亚洲欧美日韩一区二区| 亚洲日本电影在线| 午夜精品亚洲| 亚洲视频在线二区| 久久伊人精品天天| 性xx色xx综合久久久xx| 欧美成人按摩| 久久久久综合| 国产精品爽爽ⅴa在线观看| 卡通动漫国产精品| 国产精一区二区三区| 91久久视频| 在线不卡中文字幕播放| 亚洲主播在线播放| 亚洲午夜激情网站| 欧美国产日韩xxxxx| 久久在线免费观看视频| 国产精品入口66mio| 99亚洲一区二区| 亚洲欧洲日产国产网站| 久久久www免费人成黑人精品| 亚洲欧美久久久| 欧美日韩亚洲一区二区三区四区| 免费在线看成人av| 国产婷婷精品| 性欧美18~19sex高清播放| 亚洲一二三区视频在线观看| 欧美国产欧美亚洲国产日韩mv天天看完整 | 欧美伦理视频网站| 美乳少妇欧美精品| 国产婷婷色一区二区三区在线| 国产精品99久久久久久久久 | 亚洲国产精品国自产拍av秋霞| 午夜激情久久久| 午夜在线视频观看日韩17c| 欧美日韩一二区| 日韩一级黄色av| 亚洲素人在线| 国产精品久久久久9999高清| 夜夜躁日日躁狠狠久久88av| 一本色道久久综合精品竹菊| 欧美日韩精品免费| 亚洲最新合集| 欧美一区二区黄| 国产原创一区二区| 久久尤物视频| 亚洲国产综合在线| 亚洲一区二区三区在线看| 国产精品成人久久久久| 亚洲午夜激情免费视频| 欧美一区二区在线看| 国产在线视频欧美| 久久综合久久美利坚合众国| 欧美激情综合| 亚洲先锋成人| 国产婷婷色一区二区三区四区| 久久久久久久波多野高潮日日 | 亚洲欧美久久| 一区二区三区在线观看国产| 久久影院亚洲| 国产精品99久久久久久久vr| 久久精品成人一区二区三区 | 欧美午夜激情视频| 香蕉av福利精品导航| 你懂的一区二区| 一本色道精品久久一区二区三区 | 欧美激情性爽国产精品17p| 亚洲美女福利视频网站| 久久精品人人| 一区二区三区四区蜜桃| 国产日韩精品一区二区| 欧美1区视频| 午夜精品免费在线| 亚洲高清三级视频| 欧美自拍偷拍| 一区二区三区欧美在线| 国产日韩在线看片| 欧美激情国产高清| 欧美一区二粉嫩精品国产一线天| 91久久在线| 猫咪成人在线观看| 亚洲欧美影音先锋| 亚洲欧洲日韩综合二区| 国产日韩欧美一区在线| 欧美成人免费在线视频| 午夜视频在线观看一区二区三区| 亚洲人成绝费网站色www| 久久久久九九视频| 亚洲一区999| 久久综合影音| 欧美a级一区| 久久福利资源站| 亚洲午夜91| 亚洲免费观看高清完整版在线观看熊| 国产精品午夜视频| 欧美日韩精品综合| 欧美成年人网站| 久久精品在线视频| 亚洲欧美日韩在线不卡| 99视频在线观看一区三区| 欧美福利电影网| 欧美 亚欧 日韩视频在线| 久久九九国产精品| 久久国产精品久久国产精品| 亚洲摸下面视频| 亚洲视频播放| 一二三四社区欧美黄| 99re6这里只有精品| 亚洲人成亚洲人成在线观看| 在线欧美日韩| 亚洲国产视频一区| 一区在线播放视频| 黄色一区二区在线| 国产一区免费视频| 韩国av一区二区三区四区| 国产免费亚洲高清| 国产精品一区二区三区久久久| 国产精品久久久一区二区| 欧美日韩亚洲系列| 国产精品亚洲成人| 国产女主播在线一区二区| 国产伦精品一区二区三区高清| 国产精品久久久久久久久久久久久久| 国产精品久久久久久久久免费桃花| 国产精品成人一区二区三区夜夜夜| 欧美日韩一区二区免费在线观看 | 欧美一区二区啪啪| 久久国产精品99精品国产| 久久gogo国模裸体人体| 久久综合网络一区二区| 美日韩精品免费| 欧美日产国产成人免费图片| 国产精品videossex久久发布| 国产精品视频导航| 韩国一区二区三区美女美女秀| 激情视频一区| 亚洲精品资源| 午夜在线精品偷拍| 免费观看成人鲁鲁鲁鲁鲁视频| 亚洲国产成人av| 一本一本久久a久久精品牛牛影视| 亚洲一区二区三区精品在线观看 | 欧美第一黄色网| 亚洲精品一区中文| 午夜伦理片一区| 欧美成人午夜视频| 国产精品免费看| 亚洲国产欧美一区二区三区同亚洲| 亚洲精品一区在线观看香蕉| 欧美在线视频观看免费网站| 欧美高清视频www夜色资源网| 99re成人精品视频| 久久久www成人免费精品| 欧美日韩免费观看一区二区三区| 国产伦精品一区二区三区照片91| 亚洲国产精品久久| 午夜视频精品| 亚洲国产精品999| 亚洲欧美日韩区| 欧美日韩国产在线播放网站| 国产亚洲欧美日韩日本| av成人老司机| 美女诱惑一区| 亚洲男人天堂2024| 欧美剧在线免费观看网站| 激情久久中文字幕| 午夜老司机精品| 99re亚洲国产精品| 麻豆精品视频在线| 黄色影院成人| 欧美成人一品| 性欧美18~19sex高清播放|