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

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

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

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

4、rbound 是范圍的下限。程序流程圖：程序例程：下面是一個生成10個1020之間隨機數(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運行結(jié)果：12 10 20 20 17 17 18 14 12 203 某范圍內(nèi)不可重復要產(chǎn)生一定范圍內(nèi)不可重復的隨機數(shù)

5、，按通常的設(shè)計是把曾經(jīng)生成的隨機數(shù)保存起來作為歷史數(shù)據(jù)。產(chǎn)生一個新的隨機數(shù)后在歷史數(shù)據(jù)搜索，若找到就重新產(chǎn)生一個新的再重復數(shù)據(jù)搜索；否則就認為已經(jīng)找到了一個新的不同隨機數(shù)。例如，要由計算機隨機產(chǎn)生10個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運行結(jié)果：199 174 147 126 120 190 192 146 122 111粗看起來，上面的程序似乎沒有什么問題，在執(zhí)行過程中程序也能夠通過。但，仔細分析我們就會發(fā)現(xiàn)問題出在一個新產(chǎn)生的隨機數(shù)是否已經(jīng)存在的判定上。既然是隨機數(shù)，那么從數(shù)學的角度來說在概率上，每次產(chǎn)生的隨機數(shù) r就有可能相同，盡管這種

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

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

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

10、都不會一樣，這樣，就保證了算法的確定性、有效性、有窮性。程序流程圖：程序： 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運行結(jié)果：195 153 148 183 149 101 137 172 126 1104 枚舉可重復這種隨機數(shù)的生成比較簡單，只要把各個枚舉數(shù)放入一個數(shù)組中保存起來，然后隨機生成數(shù)組的下標，最后取出對應下標下的數(shù)組的值即可。流程圖和程序可參考前面的論述。5 枚舉不可重復首先把各個枚舉數(shù)放入一個數(shù)組中保