隨機(jī)數(shù)生成算法的研究

1、.隨機(jī)數(shù)生成算法的研究日期：2006-05-23來源： 作者：字體：大 中 小 張敬新摘要：本文通過流程圖和實(shí)際例程，較詳細(xì)地闡述了隨機(jī)數(shù)生成的算法和具體的程序設(shè)計(jì)，分析了其符合算法特征的特性。關(guān)鍵詞：隨機(jī)數(shù)；算法；算法特征；程序設(shè)計(jì)1 引言在數(shù)據(jù)結(jié)構(gòu)、算法分析與設(shè)計(jì)、科學(xué)模擬等方面都需要用到隨機(jī)數(shù)。由于在數(shù)學(xué)上，整數(shù)是離散型的，實(shí)數(shù)是連續(xù)型的，而在某一具體的工程技術(shù)應(yīng)用中，可能還有數(shù)據(jù)值的范圍性和是否可重復(fù)性的要求。因此，我們就整數(shù)隨機(jī)數(shù)和實(shí)數(shù)隨機(jī)數(shù)，以及它們的數(shù)據(jù)值的范圍性和是否可重復(fù)性，分別對(duì)其算法加以分析和設(shè)計(jì)。以下以Visual Basic 語言為工具，對(duì)整數(shù)隨機(jī)數(shù)生成問題加以闡述，

2、而對(duì)于實(shí)數(shù)隨機(jī)數(shù)生成問題，只要稍加修改就可轉(zhuǎn)化為整數(shù)隨機(jī)數(shù)生成問題。根據(jù)整數(shù)隨機(jī)數(shù)范圍性和是否可重復(fù)性，可分為：(1)某范圍內(nèi)可重復(fù)。(2)某范圍內(nèi)不可重復(fù)。(3)枚舉可重復(fù)。(4)枚舉不可重復(fù)。所謂范圍，是指在兩個(gè)數(shù)n1和n2之間。例如，在100和200之間這個(gè)范圍，那么，只要產(chǎn)生的整數(shù)隨機(jī)數(shù)n滿足100n200，都符合要求。所謂枚舉，是指有限的、已知的、若干個(gè)不連續(xù)的整數(shù)。例如，34、20、123、5、800這5個(gè)整數(shù)就是一種枚舉數(shù)，也就是單獨(dú)可以一個(gè)個(gè)確定下來。2 某范圍內(nèi)可重復(fù)在Visual Basic 語言中，有一個(gè)隨機(jī)數(shù)函數(shù)Rnd。語法：Rnd(number)。參數(shù)number 可

3、選，number 的值決定了 Rnd 生成隨機(jī)數(shù)的方式。Rnd 函數(shù)返回小于 1 但大于或等于 0 的值。如果 number 為Rnd 生成小于零每次都相同的數(shù)字，并將 number 用作種子。大于零序列中的下一個(gè)隨機(jī)數(shù)。等于零最近生成的數(shù)字。未提供序列中的下一個(gè)隨機(jī)數(shù)。在調(diào)用 Rnd 之前，先使用無參數(shù)的 Randomize 語句初始化隨機(jī)數(shù)生成器，該生成器具有一個(gè)基于系統(tǒng)計(jì)時(shí)器的種子。若要生成某給定范圍內(nèi)的隨機(jī)整數(shù)，可使用以下公式：Int(upperbound - lowerbound + 1) * Rnd + lowerbound)這里，upperbound 是此范圍的上限，而 lowe

4、rbound 是范圍的下限。程序流程圖：程序例程：下面是一個(gè)生成10個(gè)1020之間隨機(jī)數(shù)的例子。Private Sub Command1_Click() lowerbound = 10 upperbound = 20 Randomize For i = 1 To 10 random = Int(upperbound - lowerbound + 1) * Rnd + lowerbound) Debug.Print random; Next Debug.PrintEnd Sub運(yùn)行結(jié)果：12 10 20 20 17 17 18 14 12 203 某范圍內(nèi)不可重復(fù)要產(chǎn)生一定范圍內(nèi)不可重復(fù)的隨機(jī)數(shù)

5、，按通常的設(shè)計(jì)是把曾經(jīng)生成的隨機(jī)數(shù)保存起來作為歷史數(shù)據(jù)。產(chǎn)生一個(gè)新的隨機(jī)數(shù)后在歷史數(shù)據(jù)搜索，若找到就重新產(chǎn)生一個(gè)新的再重復(fù)數(shù)據(jù)搜索；否則就認(rèn)為已經(jīng)找到了一個(gè)新的不同隨機(jī)數(shù)。例如，要由計(jì)算機(jī)隨機(jī)產(chǎn)生10個(gè)101200之間互不相同的數(shù)。程序流程圖：程序： Private Sub Command2_Click() Dim random(10) As Integer lowerbound = 101 upperbound = 200 Randomize For i = 1 To 10 Do r = Int(upperbound - lowerbound + 1) * Rnd + lowerbound)

6、 yes = 0 For j = 1 To i - 1 If r = random(j) Then yes = 1: Exit For Next Loop While yes = 1 random(i) = r Debug.Print r; Next Debug.PrintEnd Sub運(yùn)行結(jié)果：199 174 147 126 120 190 192 146 122 111粗看起來，上面的程序似乎沒有什么問題，在執(zhí)行過程中程序也能夠通過。但，仔細(xì)分析我們就會(huì)發(fā)現(xiàn)問題出在一個(gè)新產(chǎn)生的隨機(jī)數(shù)是否已經(jīng)存在的判定上。既然是隨機(jī)數(shù)，那么從數(shù)學(xué)的角度來說在概率上，每次產(chǎn)生的隨機(jī)數(shù) r就有可能相同，盡管這種

7、可能性很小，但確是一個(gè)邏輯性與正確性的問題。因此，每次產(chǎn)生的新的隨機(jī)數(shù)r都有可能是數(shù)組random的前i-1個(gè)數(shù)中的某一個(gè)，也就是說程序在運(yùn)行過程中由此可能會(huì)導(dǎo)致死循環(huán)，那么，能否找到一個(gè)不在數(shù)組random中的隨機(jī)數(shù)r的工作就變得不確定了。從算法的角度來講，在理論上，程序失去了有窮性、有效性和確定性。什么是算法？通常人們將算法定義為一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列。一個(gè)算法應(yīng)當(dāng)具有以下特征：(1)輸入：一個(gè)算法必須有0個(gè)或多個(gè)輸入。它們是算法開始運(yùn)算前給予算法的量。這些輸入取自于特定的對(duì)象的集合。它們可以使用輸入語句由外部提供，也可以使用置初值語句或賦值語句在算

8、法內(nèi)提供。(2)輸出：一個(gè)算法應(yīng)有1個(gè)或多個(gè)輸出，輸出的量是算法計(jì)算的結(jié)果。(3)確定性：算法的每一步都應(yīng)確切地、無歧義地定義。對(duì)于每一種情況，需要執(zhí)行的動(dòng)作都應(yīng)嚴(yán)格地、清晰地規(guī)定。(4)有窮性：一個(gè)算法無論在什么情況下，都應(yīng)在執(zhí)行有窮步后結(jié)束。(5)有效性：算法中每一條運(yùn)算都必須是足夠基本的。就是說，它們?cè)瓌t上都能精確地執(zhí)行，甚至人們只用紙和筆做有限次運(yùn)算就能完成。一般來說，我們所編寫的程序都是在特定算法基礎(chǔ)上設(shè)計(jì)出來的，程序常常與算法是相互對(duì)應(yīng)的，在沒有特殊的情況下，程序也應(yīng)當(dāng)具有以上五個(gè)特征。但，也有一些程序在設(shè)計(jì)中，人們由于疏忽會(huì)想當(dāng)然地認(rèn)為，程序只要編寫出來一般都會(huì)自然地符合算法的五

9、個(gè)特征，這是應(yīng)當(dāng)引為注意的。那么，應(yīng)該如何對(duì)其進(jìn)行改進(jìn)，使其符合算法的五個(gè)特征呢？仍然以上述由計(jì)算機(jī)隨機(jī)產(chǎn)生10個(gè)101200之間互不相同的數(shù)為例進(jìn)行闡述。首先，把要產(chǎn)生的所有數(shù)放到一個(gè)數(shù)組a中。令upperbound 是此范圍的上限，而 lowerbound 是范圍的下限。第二，每次隨機(jī)生成數(shù)組a的一個(gè)下標(biāo)subscript，然后取出它所對(duì)應(yīng)的數(shù)據(jù)，將數(shù)組a的最后一個(gè)數(shù)放到下標(biāo)subscript的位置，同時(shí)將數(shù)組a長(zhǎng)度減1。盡管前若干次生成的下標(biāo)subscript隨機(jī)數(shù)有可能相同，但，因?yàn)槊恳淮味及炎詈笠粋€(gè)數(shù)填到取出的位置，因此，相同下標(biāo)subscript對(duì)應(yīng)的數(shù)卻絕不會(huì)相同，每一次取出的數(shù)

10、都不會(huì)一樣，這樣，就保證了算法的確定性、有效性、有窮性。程序流程圖：程序： Private Sub Command3_Click() Dim a(10), b(100) As Integer lowerbound = 101 upperbound = 200 For i = 1 To upperbound - lowerbound + 1 b(i) = lowerbound + i - 1 Next Randomize length = upperbound - lowerbound + 1 For i = 1 To 10 subscript = Int(length * Rnd + 1) r = b(subscript) b(script) = b(length) length = length - i a(i) = r Debug.Print a(i); Next Debug.PrintEnd Sub運(yùn)行結(jié)果：195 153 148 183 149 101 137 172 126 1104 枚舉可重復(fù)這種隨機(jī)數(shù)的生成比較簡(jiǎn)單，只要把各個(gè)枚舉數(shù)放入一個(gè)數(shù)組中保存起來，然后隨機(jī)生成數(shù)組的下標(biāo)，最后取出對(duì)應(yīng)下標(biāo)下的數(shù)組的值即可。流程圖和程序可參考前面的論述。5 枚舉不可重復(fù)首先把各個(gè)枚舉數(shù)放入一個(gè)數(shù)組中保