隨機(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ù)，以及它們的

2、數(shù)據(jù)值的范圍性和是否可重復(fù)性，分別對其算法加以分析和設(shè)計(jì)。以下以Visual Basic 語言為工具，對整數(shù)隨機(jī)數(shù)生成問題加以闡述，而對于實(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è)確定下

3、來。 2        某范圍內(nèi)可重復(fù)在Visual Basic 語言中，有一個(gè)隨機(jī)數(shù)函數(shù)Rnd。語法：Rnd(number)。參數(shù)number 可選，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è)

4、基于系統(tǒng)計(jì)時(shí)器的種子。若要生成某給定范圍內(nèi)的隨機(jī)整數(shù)，可使用以下公式：Int(upperbound - lowerbound + 1) * Rnd + lowerbound)這里，upperbound 是此范圍的上限，而 lowerbound 是范圍的下限。程序流程圖：程序例程：下面是一個(gè)生成10個(gè)1020之間隨機(jī)數(shù)的例子。Private Sub Command1_Click()    lowerbound = 10    upperbound = 20    Randomize  &

5、#160; 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

6、0; 17  18  14  12  203        某范圍內(nèi)不可重復(fù)要產(chǎn)生一定范圍內(nèi)不可重復(fù)的隨機(jī)數(shù)，按通常的設(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  low

7、erbound = 101  upperbound = 200       Randomize  For i = 1 To 10    Do      r = Int(upperbound - lowerbound + 1) * Rnd + lowerbound)      yes = 0      For j = 1 To i - 1 

8、       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 

9、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就有可能相同，盡管這種可能性很小，但確是一個(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的工作就變得不確定了。從算法的角度來講，在理論上，

10、程序失去了有窮性、有效性和確定性。什么是算法？通常人們將算法定義為一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列。一個(gè)算法應(yīng)當(dāng)具有以下特征：(1)輸入：一個(gè)算法必須有0個(gè)或多個(gè)輸入。它們是算法開始運(yùn)算前給予算法的量。這些輸入取自于特定的對象的集合。它們可以使用輸入語句由外部提供，也可以使用置初值語句或賦值語句在算法內(nèi)提供。(2)輸出：一個(gè)算法應(yīng)有1個(gè)或多個(gè)輸出，輸出的量是算法計(jì)算的結(jié)果。(3)確定性：算法的每一步都應(yīng)確切地、無歧義地定義。對于每一種情況，需要執(zhí)行的動(dòng)作都應(yīng)嚴(yán)格地、清晰地規(guī)定。(4)有窮性：一個(gè)算法無論在什么情況下，都應(yīng)在執(zhí)行有窮步后結(jié)束。(5)有效性：算法中每一

11、條運(yùn)算都必須是足夠基本的。就是說，它們原則上都能精確地執(zhí)行，甚至人們只用紙和筆做有限次運(yùn)算就能完成。一般來說，我們所編寫的程序都是在特定算法基礎(chǔ)上設(shè)計(jì)出來的，程序常常與算法是相互對應(yīng)的，在沒有特殊的情況下，程序也應(yīng)當(dāng)具有以上五個(gè)特征。但，也有一些程序在設(shè)計(jì)中，人們由于疏忽會(huì)想當(dāng)然地認(rèn)為，程序只要編寫出來一般都會(huì)自然地符合算法的五個(gè)特征，這是應(yīng)當(dāng)引為注意的。那么，應(yīng)該如何對其進(jìn)行改進(jìn)，使其符合算法的五個(gè)特征呢？仍然以上述由計(jì)算機(jī)隨機(jī)產(chǎn)生10個(gè)101200之間互不相同的數(shù)為例進(jìn)行闡述。首先，把要產(chǎn)生的所有數(shù)放到一個(gè)數(shù)組a中。令upperbound 是此范圍的上限，而 lowerbound 是范圍的

12、下限。第二，每次隨機(jī)生成數(shù)組a的一個(gè)下標(biāo)subscript，然后取出它所對應(yīng)的數(shù)據(jù)，將數(shù)組a的最后一個(gè)數(shù)放到下標(biāo)subscript的位置，同時(shí)將數(shù)組a長度減1。盡管前若干次生成的下標(biāo)subscript隨機(jī)數(shù)有可能相同，但，因?yàn)槊恳淮味及炎詈笠粋€(gè)數(shù)填到取出的位置，因此，相同下標(biāo)subscript對應(yīng)的數(shù)卻絕不會(huì)相同，每一次取出的數(shù)都不會(huì)一樣，這樣，就保證了算法的確定性、有效性、有窮性。程序流程圖：程序： Private Sub Command3_Click()  Dim a(10), b(100) As Integer  lowerbound = 101  uppe

13、rbound = 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(sub

14、script)    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ù)的生成比較簡單，只要把各個(gè)枚舉數(shù)放入一個(gè)數(shù)組中保存起來，然后隨機(jī)生成數(shù)組的下標(biāo)，最后取出對應(yīng)下標(biāo)下的數(shù)組的值即可。流程圖和程序可參考前面的論述。5