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

1、第七章第七章 隨機(jī)算法隨機(jī)算法算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析算法算法設(shè)計(jì)與分析設(shè)計(jì)與分析主編主編 耿國(guó)華耿國(guó)華本章內(nèi)容本章內(nèi)容 7 7. .1 1 隨機(jī)算法基礎(chǔ)隨機(jī)算法基礎(chǔ)7.1.1 偽隨機(jī)數(shù)7.1.2 實(shí)例分析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 分班問(wèn)題7.5 7.5 蒙特卡羅算法蒙特卡羅算法7.5.1 蒙特卡羅算法的基本思想7.5.2 蒙特卡洛算法的基本概念7.5.3 主元素問(wèn)題7.5.4 素?cái)?shù)測(cè)試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 實(shí)例分析實(shí)例分析 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個(gè)大小形狀相同的小球分別標(biāo)1,2,24,25放入一個(gè)袋中，充分?jǐn)嚢瑁瑥闹忻鲆粋€(gè)球，這個(gè)球上的數(shù)就是得到的隨機(jī)數(shù)。Chapter7 7隨機(jī)數(shù)是由試驗(yàn)(如摸球或抽簽）產(chǎn)生的隨機(jī)數(shù)，是專門的隨機(jī)試驗(yàn)的結(jié)果。計(jì)算器或計(jì)算機(jī)上無(wú)法產(chǎn)生真正的隨機(jī)數(shù)，計(jì)算器或計(jì)算機(jī)產(chǎn)生的隨機(jī)數(shù)是通過(guò)一個(gè)

3、固定的、可以重復(fù)的計(jì)算方法產(chǎn)生的，具有周期性(周期很長(zhǎng)),具有類似隨機(jī)數(shù)的統(tǒng)計(jì)特征，但并不是真正的隨機(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)計(jì)分布特征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為一素?cái)?shù)。7.1 隨機(jī)算法基礎(chǔ)隨機(jī)算法基礎(chǔ)7.1.2 7.1.2 實(shí)例分析實(shí)例分析隨機(jī)數(shù)類隨機(jī)數(shù)類 為了便于設(shè)計(jì)隨機(jī)化算法，我們?cè)诖私⒁粋€(gè)隨機(jī)數(shù)類RandomNumber，由該隨機(jī)數(shù)類給出隨機(jī)數(shù)。該類中包含一個(gè)由用戶初始化的種子randSeed，可產(chǎn)生0到n-1之間的隨機(jī)整數(shù)和0，1)之間的隨機(jī)實(shí)數(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)自動(dò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ù)值問(wèn)題的求解。這類算法得到的往往是近似解，且近似解的精度隨計(jì)算時(shí)間的增加而不斷增高。 例7-3 隨機(jī)投點(diǎn)法計(jì)算Pi值 問(wèn)題描述：將n根飛鏢隨機(jī)投向一正方形的靶子,如圖7-1(a)所示。計(jì)算落入此正方形的內(nèi)切圓中的飛鏢數(shù)目k。 (a) (b) 圖7-1 計(jì)算值的隨機(jī)投點(diǎn)法Chapter7 77.2 數(shù)值隨機(jī)算法數(shù)值隨機(jī)算法問(wèn)題分析：

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

8、法算法7.2 7.2 用隨機(jī)投點(diǎn)法計(jì)算用隨機(jī)投點(diǎn)法計(jì)算 值值double Darts(int n) static RandomNumber dart;/隨機(jī)數(shù)對(duì)象 int k=0;for (int i=1;i =n;i+) double x=dart.fRandom();/產(chǎn)生0,1)之間的隨機(jī)實(shí)數(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í)已知道子數(shù)組ap:i中元素均小于要找的第k小元素，因此，要找的ap:r中第k小元素是ai+1:r中的第k-j小

9、元素。Chapter7 77.3 舍伍德算法舍伍德算法對(duì)于選擇問(wèn)題來(lái)說(shuō)，采用擬中位數(shù)作為劃分基準(zhǔn)，可以保證在最壞情況下用線性時(shí)間完成選擇。最壞情況發(fā)生在劃分過(guò)程中產(chǎn)生的兩個(gè)區(qū)域分別包含n-1個(gè)元素和1個(gè)元素的時(shí)候；最好情況是每次劃分所取的基準(zhǔn)都正好為中值，即每次都產(chǎn)生兩個(gè)大小為n/2的區(qū)域。如果只簡(jiǎn)單地用待劃分?jǐn)?shù)組的第一個(gè)元素作為劃分基準(zhǔn)，則算法的平均性能較好，而在最壞情況下卻需要計(jì)算時(shí)間。 Chapter7 7舍伍德型選擇算法以隨機(jī)方式選擇一個(gè)數(shù)組元素作為劃分基準(zhǔn)，既能保證算法的線性時(shí)間平均性能，又能有效避免計(jì)算擬中位數(shù)的問(wèn)題。 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。計(jì)算數(shù)組。計(jì)算數(shù)組a a中的中的第第k k小元素。小元素。問(wèn)題分析：?jiǎn)栴}分析： 1）隨機(jī)選擇一個(gè)數(shù): 15。交換a0 和15，此時(shí)以15作為劃分基準(zhǔn)。 1 5 8 2 5 3 2 3 2）劃分?jǐn)?shù)組：i初始化為0,j初始化為5。i從左向右，直到找到第一個(gè)大于劃分基準(zhǔn)的元素停止，此時(shí)i=4。j從右向左，直到找到第一個(gè)比劃分基準(zhǔn)小的元素，此時(shí)j=5。由于ij。此時(shí)i=5，j=4。低區(qū)子數(shù)組中的元素個(gè)數(shù)5不等于k，交換aj和劃分基準(zhǔn)元素。 3 8 2 5 1 5 3 2 4）低區(qū)子數(shù)組元素的個(gè)數(shù)大于k

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

12、法進(jìn)行改造，但不改變?cè)械拇_定性算法，僅對(duì)算法的輸入進(jìn)行隨機(jī)洗牌，同樣可以達(dá)到舍伍德算法的效果。例如，對(duì)于確定性選擇算法，可以用洗牌算法shuffle將數(shù)組a中元素隨機(jī)排列，然后利用確定性選擇算法來(lái)求解。這種處理的效果與舍伍德型算法的效果是相同的。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)分別是算法對(duì)于具體實(shí)例x求解成功或求解失敗所需的平均時(shí)間，討論下面的算法： Cha

13、pter7 77.4 拉斯維加斯算法拉斯維加斯算法/反復(fù)調(diào)用拉斯維加斯算法LV(x,y)，直到找到問(wèn)題的一個(gè)解ypublic static void obstinate(Object x, Object y) boolean success = false; while(!success) success=lv(x,y); 由于p(x)0,因此，只要時(shí)間足夠，對(duì)任何實(shí)例x，上述算法obstinate總能找到問(wèn)題的解。若設(shè)t(x)是算法obstinate找到具體實(shí)例x的一個(gè)解所需要的平均時(shí)間，則有： 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)識(shí)重復(fù)元素算法問(wèn)題描述：設(shè)有n個(gè)元素保存在一維數(shù)組a中，其中有n/2個(gè)元素各不相同，而另外n/2個(gè)元素值相同，因此，數(shù)組中總共有(n/2)+1種不同的元素值。算法的目標(biāo)是要找出數(shù)組中的重復(fù)元素。問(wèn)題分析：使用隨機(jī)數(shù)發(fā)生器，它能夠保證從0,n-1個(gè)下標(biāo)中選取每個(gè)值的概率是相等的，等于1/n。 Chapter7 7 算法的實(shí)現(xiàn)十分簡(jiǎn)單，它使用隨機(jī)數(shù)發(fā)生器，選擇兩個(gè)下標(biāo)i和j，如果i != j,ai = aj,則算法成功終止。但算法也可能在運(yùn)行很長(zhǎng)時(shí)間后仍不能找到重復(fù)元素，此算

15、法在找到重復(fù)元素前不會(huì)終止。此算法如果終止，就一定能得到正確的結(jié)果，因此它是一個(gè)拉斯維加斯算法。7.4 拉斯維加斯算法拉斯維加斯算法算法算法7.6 7.6 標(biāo)識(shí)重復(fù)元素算法標(biāo)識(shí)重復(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 分班問(wèn)

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

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

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

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

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

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

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

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

24、）返回的解總是正確的。 （2）yy0 時(shí)，當(dāng)xX時(shí)，y是正確的。xX時(shí)，y是錯(cuò)誤的。因?yàn)榇藭r(shí)的正確解是y0。由于算法是P正確的，所以發(fā)生這種錯(cuò)誤的概率不超過(guò)1-p。Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法7.5.3 7.5.3 主元素問(wèn)題主元素問(wèn)題 設(shè)T1:n是一個(gè)含有n個(gè)元素的數(shù)組。當(dāng)|i|Ti=x|n/2時(shí)，稱元素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 時(shí)T含有主元素 Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法 對(duì)于任何給定的0，下面算法majorityMC重復(fù)調(diào)用次算法majority。它是一個(gè)偏真的蒙特卡羅算法，且錯(cuò)誤概率小于。算法算法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 素?cái)?shù)測(cè)試素?cái)?shù)測(cè)試 素?cái)?shù)的研究有相當(dāng)長(zhǎng)的歷史，近代密碼學(xué)使得素?cái)?shù)被重新重視起來(lái)，賦予了新的意義。判定一個(gè)整數(shù)是不是素?cái)?shù)

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

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

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

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)馬小定理只是素?cái)?shù)判斷的一個(gè)必要條件，而不是充分條件。所以滿足定理的整數(shù)n未必全是素?cái)?shù)。有些合數(shù)也滿足費(fèi)爾馬小定理的條件，這些合數(shù)被稱為Carmicheal數(shù)，前三個(gè)Carmicheal數(shù)是561，105，1729。Carmicheal數(shù)是非常少的。在1100000000的整數(shù)中，只有255個(gè)Carmicheal數(shù)。Chapter7 77.5 蒙特卡羅算法蒙特卡羅算法

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

32、次探測(cè) int x, result; if (p=0) result=1; else x=power(a,p/2,n); / 遞歸計(jì)算 result=(x*x)%n; / 二次探測(cè) 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)/ 素?cái)?shù)測(cè)試的蒙特卡羅算法 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)用算法的蒙