算法設(shè)計與分析耿國華第七章

1、第七章第七章 隨機(jī)算法隨機(jī)算法算法設(shè)計與分析算法設(shè)計與分析算法算法設(shè)計與分析設(shè)計與分析主編主編 耿國華耿國華本章內(nèi)容本章內(nèi)容 7 7. .1 1 隨機(jī)算法基礎(chǔ)隨機(jī)算法基礎(chǔ)7.1.1 偽隨機(jī)數(shù)7.1.2 實例分析7.2 7.2 數(shù)值隨機(jī)算法數(shù)值隨機(jī)算法7.3 7.3 舍伍德算法舍伍德算法7.3.1 基本的舍伍德型隨機(jī)算法7.3.2 線性表的快速查找7.4 7.4 拉斯維加斯算法拉斯維加斯算法7.4.1 拉斯維加斯算法的基本思想7.4.2 分班問題7.5 7.5 蒙特卡羅算法蒙特卡羅算法7.5.1 蒙特卡羅算法的基本思想7.5.2 蒙特卡洛算法的基本概念7.5.3 主元素問題7.5.4 素數(shù)測試7

2、.6 7.6 本章小結(jié)本章小結(jié) Chapter7 77.1 隨機(jī)算法基礎(chǔ)隨機(jī)算法基礎(chǔ)7.1.1 7.1.1 偽隨機(jī)數(shù)偽隨機(jī)數(shù)7.1.2 7.1.2 實例分析實例分析 Chapter7 77.1 隨機(jī)算法基礎(chǔ)隨機(jī)算法基礎(chǔ)7.1.1 7.1.1 偽隨機(jī)數(shù)偽隨機(jī)數(shù)例例7-17-1 產(chǎn)生1到25之間的隨機(jī)整數(shù)。 分析：分析：將25個大小形狀相同的小球分別標(biāo)1,2,24,25放入一個袋中，充分?jǐn)嚢瑁瑥闹忻鲆粋€球，這個球上的數(shù)就是得到的隨機(jī)數(shù)。Chapter7 7隨機(jī)數(shù)是由試驗(如摸球或抽簽）產(chǎn)生的隨機(jī)數(shù)，是專門的隨機(jī)試驗的結(jié)果。計算器或計算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù)，計算器或計算機(jī)產(chǎn)生的隨機(jī)數(shù)是通過一個

3、固定的、可以重復(fù)的計算方法產(chǎn)生的，具有周期性(周期很長),具有類似隨機(jī)數(shù)的統(tǒng)計特征，但并不是真正的隨機(jī)數(shù)，故叫偽隨機(jī)數(shù)。這樣的發(fā)生器稱為偽隨機(jī)數(shù)發(fā)生器。 7.1 隨機(jī)算法基礎(chǔ)隨機(jī)算法基礎(chǔ)偽隨機(jī)數(shù)特性偽隨機(jī)數(shù)特性偽隨機(jī)數(shù)應(yīng)具備的特征：l良好的統(tǒng)計分布特征l高效率的偽隨機(jī)序列的生成l偽隨機(jī)數(shù)序列產(chǎn)生的循環(huán)周期足夠大l生成程序可移植性好l偽隨機(jī)數(shù)序列可以重復(fù)生成Chapter7 77.1 隨機(jī)算法基礎(chǔ)隨機(jī)算法基礎(chǔ)線性同余法線性同余法 偽隨機(jī)數(shù)的生成算法很多，例如取中發(fā)，移位法，同余法，線性同余法等，其中線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法。 由線性同余法產(chǎn)生的隨機(jī)序列滿足： Chapter7 7,

4、 2 , 1mod)(10nmcbaadann 其中b為乘數(shù)，b=0；c為增量，c=0；d稱為該隨機(jī)序列的種子dm；m為模數(shù)，m0，m應(yīng)取充分大，因此可取m為機(jī)器大數(shù)，另外應(yīng)取gcd(m,b)=1，因此可取b為一素數(shù)。7.1 隨機(jī)算法基礎(chǔ)隨機(jī)算法基礎(chǔ)7.1.2 7.1.2 實例分析實例分析隨機(jī)數(shù)類隨機(jī)數(shù)類 為了便于設(shè)計隨機(jī)化算法，我們在此建立一個隨機(jī)數(shù)類RandomNumber，由該隨機(jī)數(shù)類給出隨機(jī)數(shù)。該類中包含一個由用戶初始化的種子randSeed，可產(chǎn)生0到n-1之間的隨機(jī)整數(shù)和0，1)之間的隨機(jī)實數(shù)。 Chapter7 77.1 隨機(jī)算法基礎(chǔ)隨機(jī)算法基礎(chǔ)算法算法7.1 7.1 隨機(jī)數(shù)類隨

5、機(jī)數(shù)類 /隨機(jī)數(shù)類const unsigned long maxshort =65536L;const unsigned long multiplier =1194211693L;const unsigned long adder =12345L;class RandomNumber private: unsigned long randSeed; /當(dāng)前種子 public: /構(gòu)造函數(shù)，默認(rèn)值0表示由系統(tǒng)自動產(chǎn)生種子 RandomNumber(unsigned long s=0); /產(chǎn)生0:n-1 之間的隨機(jī)的整數(shù) unsigned short Random(unsigned long n

6、); /該函數(shù)的參數(shù)n16)%n);/生成0,1)之間的隨機(jī)數(shù)double RandomNumber:fRandom(void) return Random(maxshort)/double(maxshort);7.2 數(shù)值隨機(jī)算法數(shù)值隨機(jī)算法數(shù)值隨機(jī)化算法經(jīng)常用于數(shù)值問題的求解。這類算法得到的往往是近似解，且近似解的精度隨計算時間的增加而不斷增高。 例7-3 隨機(jī)投點(diǎn)法計算Pi值 問題描述：將n根飛鏢隨機(jī)投向一正方形的靶子,如圖7-1(a)所示。計算落入此正方形的內(nèi)切圓中的飛鏢數(shù)目k。 (a) (b) 圖7-1 計算值的隨機(jī)投點(diǎn)法Chapter7 77.2 數(shù)值隨機(jī)算法數(shù)值隨機(jī)算法問題分析：

7、假定飛鏢擊中方形靶子任一點(diǎn)的概率相等。設(shè)圓的半徑為r，面積s1= ,方靶面積s2= 。由等概率假設(shè)可知,落入圓中的飛鏢和正方形內(nèi)的飛鏢平均數(shù)目之比為： 。由此可得： 。 這里考慮投入的點(diǎn)在正方形上均勻分布，因而正方形上一個點(diǎn)落在圓上的概率為 ，所以當(dāng)N足夠大時，k與n之比就逼近這一概率，即為 ，因而 。也可以看成如圖7-1（b）所示，在正|x|方形上投入n個點(diǎn)，落到扇形內(nèi)的點(diǎn)數(shù)k， 。從而可應(yīng)用隨機(jī)投點(diǎn)法計算出的近似解，并通過增加投點(diǎn)實驗次數(shù)提高解的精確度。其具體算法如下給出。Chapter7 72r24r4422rrnk4kn224r（r/2）44kn4kn7.2 數(shù)值隨機(jī)算法數(shù)值隨機(jī)算法算

8、法算法7.2 7.2 用隨機(jī)投點(diǎn)法計算用隨機(jī)投點(diǎn)法計算 值值double Darts(int n) static RandomNumber dart;/隨機(jī)數(shù)對象 int k=0;for (int i=1;i =n;i+) double x=dart.fRandom();/產(chǎn)生0,1)之間的隨機(jī)實數(shù) double y=dart.fRandom(); /判斷條件為(x*x+y*y)=1，表示當(dāng)前隨機(jī)處于圓內(nèi) if (x*x+y*y)j,則要找的第k小元素落在子數(shù)組ai+1:r中。由于此時已知道子數(shù)組ap:i中元素均小于要找的第k小元素，因此，要找的ap:r中第k小元素是ai+1:r中的第k-j小

9、元素。Chapter7 77.3 舍伍德算法舍伍德算法對于選擇問題來說，采用擬中位數(shù)作為劃分基準(zhǔn)，可以保證在最壞情況下用線性時間完成選擇。最壞情況發(fā)生在劃分過程中產(chǎn)生的兩個區(qū)域分別包含n-1個元素和1個元素的時候；最好情況是每次劃分所取的基準(zhǔn)都正好為中值，即每次都產(chǎn)生兩個大小為n/2的區(qū)域。如果只簡單地用待劃分?jǐn)?shù)組的第一個元素作為劃分基準(zhǔn)，則算法的平均性能較好，而在最壞情況下卻需要計算時間。 Chapter7 7舍伍德型選擇算法以隨機(jī)方式選擇一個數(shù)組元素作為劃分基準(zhǔn)，既能保證算法的線性時間平均性能，又能有效避免計算擬中位數(shù)的問題。 7.3 舍伍德算法舍伍德算法例例7-4 7-4 數(shù)組數(shù)組a6=

10、5 8 2 15 32 3a6=5 8 2 15 32 3，k=3k=3，l=1l=1，r=6r=6。計算數(shù)組。計算數(shù)組a a中的中的第第k k小元素。小元素。問題分析：問題分析： 1）隨機(jī)選擇一個數(shù): 15。交換a0 和15，此時以15作為劃分基準(zhǔn)。 1 5 8 2 5 3 2 3 2）劃分?jǐn)?shù)組：i初始化為0,j初始化為5。i從左向右，直到找到第一個大于劃分基準(zhǔn)的元素停止，此時i=4。j從右向左，直到找到第一個比劃分基準(zhǔn)小的元素，此時j=5。由于ij。此時i=5，j=4。低區(qū)子數(shù)組中的元素個數(shù)5不等于k，交換aj和劃分基準(zhǔn)元素。 3 8 2 5 1 5 3 2 4）低區(qū)子數(shù)組元素的個數(shù)大于k

11、，則第k小元素在低區(qū)子數(shù)組中，改變右邊界，即r=3。此時只需在低區(qū)子數(shù)組中查找。 3 8 2 5 5）重復(fù)步驟1)，得到 5 8 2 3 6）初始化i=0, j=3。重復(fù)步驟2)，此時i=1，j=3。由于ij，交換后的數(shù)組為： 5 3 2 8 重復(fù)步驟3)，此時i=3，j=2。低區(qū)子數(shù)組中的元素個數(shù)3等于k，則結(jié)果為：劃分基準(zhǔn)的值5。Chapter7 77.3 舍伍德算法舍伍德算法3.3.結(jié)合隨機(jī)預(yù)處理技術(shù)結(jié)合隨機(jī)預(yù)處理技術(shù) 上述舍伍德型選擇算法對確定性選擇算法所作的修改簡單且易于實現(xiàn)。有時也會遇到這樣的情況，所給的確定性算法無法直接改造成舍伍德型算法。那么需要借助于隨機(jī)預(yù)處理技術(shù)對原有確定算

12、法進(jìn)行改造，但不改變原有的確定性算法，僅對算法的輸入進(jìn)行隨機(jī)洗牌，同樣可以達(dá)到舍伍德算法的效果。例如，對于確定性選擇算法，可以用洗牌算法shuffle將數(shù)組a中元素隨機(jī)排列，然后利用確定性選擇算法來求解。這種處理的效果與舍伍德型算法的效果是相同的。Chapter7 77.3 舍伍德算法舍伍德算法算法算法7.4 7.4 隨機(jī)洗牌算法隨機(jī)洗牌算法templatevoid Shuffle(Type a, int n) static RandomNumber rnd; for (int i=0;i0。設(shè)s(x)和e(x)分別是算法對于具體實例x求解成功或求解失敗所需的平均時間，討論下面的算法： Cha

13、pter7 77.4 拉斯維加斯算法拉斯維加斯算法/反復(fù)調(diào)用拉斯維加斯算法LV(x,y)，直到找到問題的一個解ypublic static void obstinate(Object x, Object y) boolean success = false; while(!success) success=lv(x,y); 由于p(x)0,因此，只要時間足夠，對任何實例x，上述算法obstinate總能找到問題的解。若設(shè)t(x)是算法obstinate找到具體實例x的一個解所需要的平均時間，則有： t(x) = p(x)s(x)+(1-p(x)(e(x)+t(x) 解方程可得： Chapter

14、7 71( )( )( )( )( )p xt xs xe xp x7.4 拉斯維加斯算法拉斯維加斯算法例例7-57-5 標(biāo)識重復(fù)元素算法問題描述：設(shè)有n個元素保存在一維數(shù)組a中，其中有n/2個元素各不相同，而另外n/2個元素值相同，因此，數(shù)組中總共有(n/2)+1種不同的元素值。算法的目標(biāo)是要找出數(shù)組中的重復(fù)元素。問題分析：使用隨機(jī)數(shù)發(fā)生器，它能夠保證從0,n-1個下標(biāo)中選取每個值的概率是相等的，等于1/n。 Chapter7 7 算法的實現(xiàn)十分簡單，它使用隨機(jī)數(shù)發(fā)生器，選擇兩個下標(biāo)i和j，如果i != j,ai = aj,則算法成功終止。但算法也可能在運(yùn)行很長時間后仍不能找到重復(fù)元素，此算

15、法在找到重復(fù)元素前不會終止。此算法如果終止，就一定能得到正確的結(jié)果，因此它是一個拉斯維加斯算法。7.4 拉斯維加斯算法拉斯維加斯算法算法算法7.6 7.6 標(biāo)識重復(fù)元素算法標(biāo)識重復(fù)元素算法int elment(int a,int n,int &x)while(1)RandomNumber rcd;int i = rcd.Random(n);int j = rcd.Random(n);if(i != j)& (ai = aj) /第i，j數(shù)組元素值相等，為重復(fù)元素x = ai;return i;Chapter7 77.4 拉斯維加斯算法拉斯維加斯算法7.4.2 7.4.2 分班問

16、題分班問題 1.1.問題描述問題描述 在學(xué)校管理中常常要進(jìn)行分班，具體做法通常是：新學(xué)期開學(xué)，學(xué)校招收了一批新生，學(xué)生人數(shù)未定（比如100人），男女生未定（如男生57人，女生43人），考試科目有語文、數(shù)學(xué)和總分，對這些學(xué)生進(jìn)行分班（分班數(shù)未定）。其中附加參考條件為：有部分學(xué)生要住校（比如32人），有部分不住校，有些學(xué)生是干部（12人）。Chapter7 77.4 拉斯維加斯算法拉斯維加斯算法要求分班的結(jié)果滿足以下幾個條件：要求分班的結(jié)果滿足以下幾個條件： (1)分班后各個班級總分的平均分差值在02.0間； (2)分班后各班人數(shù)盡量相等，最多相差人，男女生人數(shù)最多相差人； (3)分班后各個班級的

17、各科平均分差值在03.0間； (4)分班后各個班級的住校人數(shù)，班干部人數(shù)最多相差人。 其中，條件(1)和條件(2)必須要滿足，條件(3)和條件(4)最好滿足。 Chapter7 77.4 拉斯維加斯算法拉斯維加斯算法根據(jù)上面列出的數(shù)據(jù)和條件進(jìn)行分班，其方案之一如表7-2所示表7-2 一種滿足條件的分班方案 Chapter7 7班級總?cè)藬?shù)/人男生/人女生/人干部/人住校生/人總平均分/分一班25131239186.12二班25131248187.22三班25121327188.12四班25111438187.907.4 拉斯維加斯算法拉斯維加斯算法2.2.問題分析與解決方案問題分析與解決方案 本

18、題采用拉斯維加斯算法能顯著提高算法的有效性。 通過模擬人工操作，首先初始化：如果有100個人，分4個班，則平均每班要有25人，將男女生分開，隨機(jī)分配再合并成一個班滿足條件(2)，計算年級平均分ave，把各班按平均分分類。Chapter7 77.4 拉斯維加斯算法拉斯維加斯算法3.3.算法分析算法分析 拉斯維加斯算法的一個重要特征是它的隨機(jī)決策可能導(dǎo)致它找不到所需的解。但設(shè)p(x)是此算法對獲得一個問題解的概率，則只要求。故如有足夠多的時間，對任何實例x，拉斯維加斯算法均可出一個解，并且算法平均時間如t(x)=s(x)+(1-p)(x)/p(x)e(x)。因此，只要問題大多數(shù)解是符合要求的，就可

19、以使用拉斯維加斯算法，在采用常規(guī)做法難度超過自身水平甚至在對NP問題搜索時，用它往往效果很好。如果上述方法效率好的話，也可兼顧其它科目分?jǐn)?shù)；效率不好，可以讓程序先運(yùn)行幾分鐘（或調(diào)整n次）后強(qiáng)行退出循環(huán)，看看是否滿意當(dāng)前解。用這個算法測試，運(yùn)氣好時可瞬間求出解，運(yùn)氣差時需要很長一段時間。該算法的運(yùn)行過程幾乎全靠運(yùn)氣，這也是該算法以賭城“拉斯維加斯”來命名的原因。Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法 7.5.1 7.5.1 蒙特卡羅算法的基本思想蒙特卡羅算法的基本思想7.5.2 7.5.2 蒙特卡洛算法的基本概念蒙特卡洛算法的基本概念7.5.3 7.5.3 主元素問題主元素問題 7

20、.5.4 7.5.4 素數(shù)測試素數(shù)測試Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法7.5.1 7.5.1 蒙特卡羅算法的基本思想蒙特卡羅算法的基本思想 蒙特卡洛方法所解決的問題主要有兩類： （1）確定性的數(shù)學(xué)問題：如計算多重積分、求逆矩陣、解線性方程組、解積分方程、偏微分方程等。解決方法：間接模擬方法。建立相關(guān)問題的概率模型；對模型進(jìn)行隨機(jī)抽樣；用隨機(jī)抽樣的算術(shù)平均值作為近似估計值。 （2）隨機(jī)性問題：如原子核物理問題、運(yùn)籌學(xué)中的優(yōu)化問題、隨機(jī)服務(wù)系統(tǒng)中的排隊問題、動物的生態(tài)競爭和傳染病的蔓延等。解決方法：一般情況下都采用直接模擬方法。即根據(jù)實際物理情況的概率法則，用計算機(jī)進(jìn)行抽樣檢驗

21、。 Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法蒙特卡洛方法解題的一般步驟：蒙特卡洛方法解題的一般步驟： （1）建模：對求解的問題建立簡單而又便于實現(xiàn)的概率統(tǒng)計模型 ，使所求的解恰好是所建立的的概率分布或數(shù)學(xué)期望； （2）改進(jìn)模型：根據(jù)概率統(tǒng)計模型的特點(diǎn)和計算實踐的需要，盡量改進(jìn)模型，以便減少方差和降低費(fèi)用，提高計算效率； （3）模擬試驗：建立對隨機(jī)變量的抽樣方法，其中包括建立偽隨機(jī)數(shù)的方法和建立對所遇到的分布產(chǎn)生隨即變量的隨機(jī)抽樣方法； （4）求解：給出獲得所求解的統(tǒng)計估計值及其方差或標(biāo)準(zhǔn)誤差的方法。 Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法蒙特卡洛方法的特點(diǎn)：蒙特卡洛方

22、法的特點(diǎn)： （1）蒙特卡洛方法及其程序結(jié)構(gòu)簡單，但計算量大； （2）收斂的概率性和收斂速度與問題維數(shù)無關(guān)，模擬結(jié)果具有隨機(jī)性； （3）蒙特卡洛方法的適應(yīng)性很強(qiáng)。 Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法7.5.2 7.5.2 蒙特卡羅算法的基本概念蒙特卡羅算法的基本概念 設(shè)p是一個實數(shù)，且1/2p1。若一個蒙特卡羅算法對于問題的任意實例得到正確解的概率不小于p，則稱該蒙特卡羅算法是p正確的。且稱p-1/2是該算法的優(yōu)勢。 若對于同一實例，蒙特卡羅算法不會給出兩個不同的正確解答，則稱該蒙特卡羅算法是一致的。 對于一個一致的p正確蒙特卡羅算法，要提高獲得正確解的概率，只要執(zhí)行該算法若干

23、次，并選擇出現(xiàn)頻率次數(shù)最高的解即可。 Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法7.5.2 7.5.2 蒙特卡羅算法的基本概念蒙特卡羅算法的基本概念 在一般情況下，設(shè)和是兩個正實數(shù)，且+0.5，可以放松到p0。Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法2 2、偏、偏y0y0算法算法 對于一個解所給問題的蒙特卡羅算法MC(x)，如果存在問題實例的子集X使得： (1)當(dāng)xX時，MC(x)返回的解是正確的； (2)當(dāng)xX時，正確解是y0，但MC(x)返回的解未必是y0。 稱上述算法MC(x)是偏y0的算法。 MC(x)返回的解為y0。以下討論兩種情況： （1）y=y0時，MC（x

24、）返回的解總是正確的。 （2）yy0 時，當(dāng)xX時，y是正確的。xX時，y是錯誤的。因為此時的正確解是y0。由于算法是P正確的，所以發(fā)生這種錯誤的概率不超過1-p。Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法7.5.3 7.5.3 主元素問題主元素問題 設(shè)T1:n是一個含有n個元素的數(shù)組。當(dāng)|i|Ti=x|n/2時，稱元素x是數(shù)組T的主元素。下面的Majority算法判定所給定數(shù)組T是否含有主元素。算法算法7.8 Majority算法RandomNumber rnd；templatebool Majority(Type *T, int n)/ 判定主元素的蒙特卡羅算法 int i=rn

25、d.Random(n)+1; Type x=Ti; / 隨機(jī)選擇數(shù)組元素 int k=0; for (int j=1;jn/2); / kn/2 時T含有主元素 Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法 對于任何給定的0，下面算法majorityMC重復(fù)調(diào)用次算法majority。它是一個偏真的蒙特卡羅算法，且錯誤概率小于。算法算法7.97.9 MajorityMC算法templatebool MajorityMC(Type *T, int n, double e)/ 重復(fù)調(diào)用算法Majority算法log(1/) 次 k=ceil(log(1/e)/log2.0); for (i

26、nt i=1;i=k;i+) if (Majority(T,n) return true; return false; Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法算法算法7.107.10 Majority2算法templatebool majority2(Type T, int n) if(majority(t,n) return true; elsereturn majority(t,n); Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法7.5.4 7.5.4 素數(shù)測試素數(shù)測試 素數(shù)的研究有相當(dāng)長的歷史，近代密碼學(xué)使得素數(shù)被重新重視起來，賦予了新的意義。判定一個整數(shù)是不是素數(shù)

27、，一直是個大難題，所以Wilson定理就顯得尤為珍貴。 Wilson Wilson定理定理 正整數(shù)n1，則n是一個素數(shù)當(dāng)且僅當(dāng)(n-1)!-1(modn)。 證明：如果(n-1)!-1(modn)成立，則說明n與1、2、.、(n-1)這些小于n的所有整數(shù)互素，所以n一定是素數(shù)。 假設(shè)n是一個素數(shù)，如果n=2顯然成立，故下面我們不妨假設(shè)n是一個奇素數(shù)。對于所有A=1,2,.n-1中的正整數(shù)x，x與A中的整數(shù)的乘積除以n的余數(shù)也跑遍A，所以都能找到唯一一個A中的y使得xy1(modn)。也就是說我們把A的數(shù)作了兩兩配對，每一對的乘積除以n的余數(shù)都是1。當(dāng)然其中有些數(shù)x是自己和自己配對，這樣的x必須

28、滿足，由于n為素數(shù)，所以n必然可以整除(x-1)或(x+1)，只能有x=1或(n-1)，即只有兩個數(shù)1和(n-1)是自己和自己配對，因此(n-1)!(n-1)-1(modn)。 Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法 算法算法7.117.11 Prime算法bool Prime(unsigned int n)/ 素數(shù)測試的蒙特卡羅算法 RandomNumber rnd; int m=floor(sqrt(double (n); unsigned int a=rnd.Random(m-2)+2; return (n%a!=0); 當(dāng)算法返回false時可以幸運(yùn)的找到n的一個非平凡因

29、子，因此可以肯定n是一個合數(shù)。但是對上述算法Prime來說，即使是一個合數(shù)，算法仍以高概率返回true。而且，當(dāng)n增大時，情況會變得更糟。Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法 1 1、費(fèi)爾馬小定理、費(fèi)爾馬小定理 費(fèi)爾馬小定理：如果p是一個素數(shù)，且0a1,a1,a2,a3,a4,am為m個整數(shù)，若在這m個數(shù)中任取2個整數(shù)對m不同余，則這m個整數(shù)對m構(gòu)成完全剩余系。引理3設(shè)m是一個整數(shù)，且m1，b是一個整數(shù)且(m,b)=1。如果a1,a2,a3,a4,am是模m的一個完全剩余系，則ba1,ba2,ba3,ba4,bam也構(gòu)成模m的一個完全剩余系。引理4. 如果a,b,c,d是四個整

30、數(shù)，且ab(mod m),cd(mod m),則有acbd(mod m)證明：由題設(shè)得acbc(mod m),bcbd(mod m)，由模運(yùn)算的傳遞性可得acbd(mod m)Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法 費(fèi)馬小定理只是素數(shù)判斷的一個必要條件，而不是充分條件。所以滿足定理的整數(shù)n未必全是素數(shù)。有些合數(shù)也滿足費(fèi)爾馬小定理的條件，這些合數(shù)被稱為Carmicheal數(shù)，前三個Carmicheal數(shù)是561，105，1729。Carmicheal數(shù)是非常少的。在1100000000的整數(shù)中，只有255個Carmicheal數(shù)。Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法

31、 2 2、二次探測定理、二次探測定理 為了彌補(bǔ)費(fèi)爾馬小定理的不足，需要引入二次探測定理。對上述算法做進(jìn)一步改進(jìn)，以避免將Carmicheal數(shù)當(dāng)做素數(shù)。 二次探測定理：二次探測定理：如果p是一個素數(shù)，且0 xp，則方程x21(mod p)的解為x=1，p-1。 利用二次探測定理?？梢栽诶觅M(fèi)馬小定理計算的過程中得到的整數(shù)n進(jìn)行二次探測。如果違背二次探測定理則表示不是素數(shù)。Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法 算法算法7.127.12 power算法private static int power(int a, int p, int n)/ 計算 ap mod n，并實施對n的二

32、次探測 int x, result; if (p=0) result=1; else x=power(a,p/2,n); / 遞歸計算 result=(x*x)%n; / 二次探測 if (result=1)&(x!=1)&(x!=n-1) composite=true; if (p%2)=1) / p是奇數(shù) result=(result*a)%n; return result; Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法 算法算法7.137.13 蒙特卡羅Prime算法public static boolean prime(int n)/ 素數(shù)測試的蒙特卡羅算法 rnd = new Random(); int a, result; composite=false; a=rnd.random(n-3)+2; /1an-1 result=power(a,n-1,n); if (composite|(result!=1) return false; else return true; Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法 算法算法7.147.14 蒙特卡羅PrimeMC算法bool PrimeMC(unsigned int n,unsigned int k)/重復(fù)k次調(diào)用算法的蒙