1、算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社第第10章章 概率算法概率算法 10.1 概概 述述 10.2 舍伍德舍伍德(Sherwood)型概率算法型概率算法10.3 拉斯維加斯拉斯維加斯(Las Vegas)型概率算法型概率算法10.4 蒙特卡羅蒙特卡羅(Monte Carlo)型概率算法型概率算法10.5 實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目隨機(jī)數(shù)發(fā)生器隨機(jī)數(shù)發(fā)生器算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社10.1 概概 述述 10.1.1 概率算法的設(shè)計(jì)思想概率算法的設(shè)計(jì)思想 10.1.2 隨機(jī)數(shù)發(fā)生器隨機(jī)數(shù)發(fā)生器 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社確定性算

2、法算法的每一步都明確指定下一步該如何進(jìn)行，對(duì)于任何合理的輸入，確定性算法都必須給出正確的輸出。概率算法允許算法在執(zhí)行過程中隨機(jī)選擇下一步該如何進(jìn)行，同時(shí)允許結(jié)果以較小的概率出現(xiàn)錯(cuò)誤。以上述錯(cuò)誤為代價(jià)，獲得算法運(yùn)行時(shí)間的大幅減少。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社10.1.1 概率算法的設(shè)計(jì)思想概率算法的設(shè)計(jì)思想 概率算法把概率算法把“對(duì)于所有合理的輸入都必須對(duì)于所有合理的輸入都必須給出正確的輸出給出正確的輸出”這一求解問題的條件放寬，把這一求解問題的條件放寬，把隨機(jī)性隨機(jī)性的選擇注入到算法中，在算法執(zhí)行某些步的選擇注入到算法中，在算法執(zhí)行某些步驟時(shí)，可以隨機(jī)地選擇下一步該

3、如何進(jìn)行，同時(shí)驟時(shí)，可以隨機(jī)地選擇下一步該如何進(jìn)行，同時(shí)允許結(jié)果以允許結(jié)果以較小的概率較小的概率出現(xiàn)錯(cuò)誤，并以此為代價(jià)，出現(xiàn)錯(cuò)誤，并以此為代價(jià)，獲得算法運(yùn)行時(shí)間的大幅度減少。獲得算法運(yùn)行時(shí)間的大幅度減少。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社概率算法的分類概率算法的分類概率算法大致分為四類:數(shù)值概率算法，蒙特卡羅（Monte Carlo）算法，拉斯維加斯（Las Vegas）算法和舍伍德（Sherwood）算法。 數(shù)值概率算法常用于數(shù)值問題的求解。這類算法所得到的往往是近似解。而且近似解的精度隨計(jì)算時(shí)間的增加不斷提高。在許多情況下，要計(jì)算出問題的精確解是不可能或沒有必要的，

4、因此用數(shù)值概率算法可得到相當(dāng)滿意的解。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 舍伍德算法： 很多具有很好的平均運(yùn)行時(shí)間的確定性算法，在最壞的情況下性能很壞。引入隨機(jī)性加以改造，可以消除或減少一般情況和最壞情況的差別。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 拉斯維加斯算法： 要么給出問題的正確答案，要么得不到答案。反復(fù)求解多次，可使失效的概率任意小。 蒙特卡羅算法： 總能得到問題的答案，偶然產(chǎn)生不正確的答案。重復(fù)運(yùn)行，每一次都進(jìn)行隨機(jī)選擇，可使不正確答案的概率變得任意小。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 例如，判斷表達(dá)式例如，判斷

5、表達(dá)式f(x1, x2, , xn)是否恒等于是否恒等于0。概率算法首先生成一個(gè)隨機(jī)概率算法首先生成一個(gè)隨機(jī)n元向量元向量(r1, r2, , rn)，并計(jì)算并計(jì)算f(r1, r2, , rn)的值，如果的值，如果f(r1, r2, , rn)0，則則f(x1, x2, , xn)0；如果；如果f(r1, r2, , rn)0，則或者，則或者f(x1, x2, , xn)恒等于恒等于0，或者是，或者是(r1, r2, , rn)比較特比較特殊，如果這樣重復(fù)幾次，繼續(xù)得到殊，如果這樣重復(fù)幾次，繼續(xù)得到f(r1, r2, , rn)0的結(jié)果，那么就可以得出的結(jié)果，那么就可以得出f(x1, x2,

6、, xn)恒等于恒等于0的結(jié)的結(jié)論，并且測試的隨機(jī)向量越多，這個(gè)結(jié)果出錯(cuò)的可論，并且測試的隨機(jī)向量越多，這個(gè)結(jié)果出錯(cuò)的可能性就越小。能性就越小。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社一般情況下，概率算法具有以下基本特征：一般情況下，概率算法具有以下基本特征：（1）概率算法的輸入包括兩部分，一部分是原）概率算法的輸入包括兩部分，一部分是原問題的輸入，另一部分是一個(gè)供算法進(jìn)行隨機(jī)選問題的輸入，另一部分是一個(gè)供算法進(jìn)行隨機(jī)選擇的擇的隨機(jī)數(shù)序列隨機(jī)數(shù)序列；（2）概率算法在運(yùn)行過程中，包括一處或若干）概率算法在運(yùn)行過程中，包括一處或若干處處隨機(jī)選擇隨機(jī)選擇，根據(jù)隨機(jī)值來決定算法的運(yùn)行；

7、，根據(jù)隨機(jī)值來決定算法的運(yùn)行；（3）概率算法的結(jié)果不能保證一定是正確的，）概率算法的結(jié)果不能保證一定是正確的，但可以限定其出錯(cuò)概率；但可以限定其出錯(cuò)概率；（4）概率算法在不同的運(yùn)行中，對(duì)于相同的輸）概率算法在不同的運(yùn)行中，對(duì)于相同的輸入實(shí)例可以有不同的結(jié)果，因此，對(duì)于相同的輸入實(shí)例可以有不同的結(jié)果，因此，對(duì)于相同的輸入實(shí)例，概率算法的入實(shí)例，概率算法的執(zhí)行時(shí)間可能不同執(zhí)行時(shí)間可能不同。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 對(duì)于確定性算法，通常分析在平均情況下以對(duì)于確定性算法，通常分析在平均情況下以及最壞情況下的時(shí)間復(fù)雜性。對(duì)于概率算法，通及最壞情況下的時(shí)間復(fù)雜性。對(duì)于概率算

8、法，通常分析在平均情況下以及最壞情況下的常分析在平均情況下以及最壞情況下的期望期望時(shí)間時(shí)間復(fù)雜性，即由概率算法反復(fù)運(yùn)行同一輸入實(shí)例所復(fù)雜性，即由概率算法反復(fù)運(yùn)行同一輸入實(shí)例所得的平均運(yùn)行時(shí)間。得的平均運(yùn)行時(shí)間。 概率算法的時(shí)間性能概率算法的時(shí)間性能v需要強(qiáng)調(diào)的是，需要強(qiáng)調(diào)的是，“隨機(jī)隨機(jī)”并不意味著并不意味著“隨意隨意”。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社10.1.2 隨機(jī)數(shù)發(fā)生器隨機(jī)數(shù)發(fā)生器 目前，在計(jì)算機(jī)上產(chǎn)生隨機(jī)數(shù)還是一個(gè)難題，因?yàn)樵谀壳埃谟?jì)算機(jī)上產(chǎn)生隨機(jī)數(shù)還是一個(gè)難題，因?yàn)樵谠砩希@個(gè)問題只能近似解決。原理上，這個(gè)問題只能近似解決。 計(jì)算機(jī)中產(chǎn)生隨機(jī)數(shù)的方法通

9、常采用線性同余法，產(chǎn)計(jì)算機(jī)中產(chǎn)生隨機(jī)數(shù)的方法通常采用線性同余法，產(chǎn)生的隨機(jī)數(shù)序列為生的隨機(jī)數(shù)序列為a0, a1, , an，滿足：，滿足： （式（式10.1） 其中，其中，b0，c0，m0，dm。d稱為隨機(jī)數(shù)發(fā)生器的稱為隨機(jī)數(shù)發(fā)生器的隨機(jī)種子（隨機(jī)種子（Random Seed），當(dāng)），當(dāng)b、c和和m的值確定后，給定的值確定后，給定一個(gè)隨機(jī)種子，由式一個(gè)隨機(jī)種子，由式10.1產(chǎn)生的隨機(jī)數(shù)序列也就確定了。產(chǎn)生的隨機(jī)數(shù)序列也就確定了。, 2 , 1mod)(10nmcbaadann算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 計(jì)算機(jī)語言提供的隨機(jī)數(shù)發(fā)生器，一般會(huì)輸出一個(gè)分布計(jì)算機(jī)語言提供

10、的隨機(jī)數(shù)發(fā)生器，一般會(huì)輸出一個(gè)分布在開區(qū)間（在開區(qū)間（0, 1）上的隨機(jī)小數(shù)，并且需要一個(gè)隨機(jī)種子，）上的隨機(jī)小數(shù)，并且需要一個(gè)隨機(jī)種子，這個(gè)隨機(jī)種子可以是系統(tǒng)當(dāng)前的日期或時(shí)間。下面給出利用這個(gè)隨機(jī)種子可以是系統(tǒng)當(dāng)前的日期或時(shí)間。下面給出利用C+語言中的隨機(jī)函數(shù)語言中的隨機(jī)函數(shù)rand產(chǎn)生的分布在任意區(qū)間產(chǎn)生的分布在任意區(qū)間a, b上的上的隨機(jī)數(shù)算法。隨機(jī)數(shù)算法。算法10.1隨機(jī)數(shù)發(fā)生器 int Random(int a, int b) return rand( )%(b-a)+a; /rand( )產(chǎn)生(0, 32767)之間的隨機(jī)整數(shù) 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版

11、社10.2 舍伍德舍伍德(Sherwood)型概率算法型概率算法 10.2.1 快速排序快速排序 10.2.2 選擇問題選擇問題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社舍伍德舍伍德(Sherwood)型概率算法型概率算法 分析確定性算法在平均情況下的時(shí)間復(fù)雜性分析確定性算法在平均情況下的時(shí)間復(fù)雜性時(shí)，通常假定算法的輸入實(shí)例滿足某一特定的概時(shí)，通常假定算法的輸入實(shí)例滿足某一特定的概率分布。率分布。 事實(shí)上，很多算法對(duì)于不同的輸入實(shí)例，其事實(shí)上，很多算法對(duì)于不同的輸入實(shí)例，其運(yùn)行時(shí)間差別很大。此時(shí)，可以采用舍伍德型概運(yùn)行時(shí)間差別很大。此時(shí)，可以采用舍伍德型概率算法來消除算法的時(shí)間復(fù)

12、雜性與輸入實(shí)例間的率算法來消除算法的時(shí)間復(fù)雜性與輸入實(shí)例間的這種聯(lián)系。這種聯(lián)系。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法10.2隨機(jī)洗牌 void RandomShuffle(int n, int r ) for (i=0; in; i+) j=Random(0, n-i-1); rirj; /交換ri和rj 如果一個(gè)確定性算法無法直接改造成舍伍德型概率算法，如果一個(gè)確定性算法無法直接改造成舍伍德型概率算法，可借助于隨機(jī)預(yù)處理技術(shù)，即不改變?cè)械拇_定性算法，僅可借助于隨機(jī)預(yù)處理技術(shù)，即不改變?cè)械拇_定性算法，僅對(duì)其輸入

13、實(shí)例隨機(jī)排列（稱為洗牌）。假設(shè)輸入實(shí)例為整型，對(duì)其輸入實(shí)例隨機(jī)排列（稱為洗牌）。假設(shè)輸入實(shí)例為整型，下面的隨機(jī)洗牌算法可在線性時(shí)間實(shí)現(xiàn)對(duì)輸入實(shí)例的隨機(jī)排下面的隨機(jī)洗牌算法可在線性時(shí)間實(shí)現(xiàn)對(duì)輸入實(shí)例的隨機(jī)排列。列。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 舍伍德型概率算法總能求得問題的一個(gè)解，并且所求得的解總是正確的。但與其相對(duì)應(yīng)的確定性算法相比，舍伍德型概率算法的平均時(shí)間復(fù)雜性沒有改進(jìn)。換言之，舍伍德型概率算法不是避免算法的最壞情況行為，而是設(shè)法消除了算法的不同輸入實(shí)例對(duì)算法時(shí)間性能的影響，對(duì)所有輸入實(shí)例而言，舍伍德型概率算法的運(yùn)行時(shí)間相對(duì)比較均勻，其時(shí)間復(fù)雜性與原有的確定性

14、算法在平均情況下的時(shí)間復(fù)雜性相當(dāng)。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社10.2.1 快速排序快速排序 快速排序算法的關(guān)鍵在于一次劃分中選擇合適快速排序算法的關(guān)鍵在于一次劃分中選擇合適的軸值作為劃分的基準(zhǔn)，如果軸值是序列中最小的軸值作為劃分的基準(zhǔn)，如果軸值是序列中最小（或最大）記錄，則一次劃分后，由軸值分割得到（或最大）記錄，則一次劃分后，由軸值分割得到的兩個(gè)子序列不均衡，使得快速排序的時(shí)間性能降的兩個(gè)子序列不均衡，使得快速排序的時(shí)間性能降低。舍伍德型概率算法在一次劃分之前，根據(jù)隨機(jī)低。舍伍德型概率算法在一次劃分之前，根據(jù)隨機(jī)數(shù)在待劃分序列中隨機(jī)確定一個(gè)記錄作為軸值，并數(shù)在

15、待劃分序列中隨機(jī)確定一個(gè)記錄作為軸值，并把它與第一個(gè)記錄交換，則一次劃分后得到期望均把它與第一個(gè)記錄交換，則一次劃分后得到期望均衡的兩個(gè)子序列，從而使算法的行為不受待排序序衡的兩個(gè)子序列，從而使算法的行為不受待排序序列的不同輸入實(shí)例的影響，使快速排序在最壞情況列的不同輸入實(shí)例的影響，使快速排序在最壞情況下的時(shí)間性能趨近于平均情況的時(shí)間性能。下的時(shí)間性能趨近于平均情況的時(shí)間性能。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社一次劃分結(jié)果一次劃分結(jié)果 6 13 192331 35 28初始鍵值序列初始鍵值序列 6 13 19 23 31 35 58圖圖10.1 一次劃分引入隨機(jī)選擇的示例

16、一次劃分引入隨機(jī)選擇的示例一次劃分結(jié)果一次劃分結(jié)果 613 19 23 31 35 58初始鍵值序列初始鍵值序列 6 13 19 23 31 35 58隨機(jī)選擇一個(gè)隨機(jī)選擇一個(gè) 23 13 19 6 31 35 58記錄與記錄與6交換交換(a) 以最小值以最小值6為軸值，劃分不均衡為軸值，劃分不均衡(b) 隨機(jī)選擇軸值，劃分均衡隨機(jī)選擇軸值，劃分均衡算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法算法10.3隨機(jī)快速排序隨機(jī)快速排序 void QuickSort (int r , int low, int high) if (lowhigh) i=Random(low, high)

17、; rlowri; k=Partition(r, low, high); QuickSort(r, low, k- -1); QuickSort(r, k+1, high); 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 一次劃分算法一次劃分算法Partition與與4.3.2節(jié)中相同。算法節(jié)中相同。算法10.3在最壞情況下的時(shí)間復(fù)雜性仍是在最壞情況下的時(shí)間復(fù)雜性仍是O(n2)，這是由，這是由于隨機(jī)數(shù)發(fā)生器在第于隨機(jī)數(shù)發(fā)生器在第i次隨機(jī)產(chǎn)生的軸值記錄恰好都次隨機(jī)產(chǎn)生的軸值記錄恰好都是序列中第是序列中第i?。ɑ虻谛。ɑ虻趇大）記錄。但是，作為隨機(jī)大）記錄。但是，作為隨機(jī)數(shù)發(fā)生器，這種

18、情況的出現(xiàn)概率是微乎其微的。事數(shù)發(fā)生器，這種情況的出現(xiàn)概率是微乎其微的。事實(shí)上，輸入記錄的任何排列，都不可能出現(xiàn)使算法實(shí)上，輸入記錄的任何排列，都不可能出現(xiàn)使算法行為處于最壞的情況。因此，該算法的期望時(shí)間復(fù)行為處于最壞的情況。因此，該算法的期望時(shí)間復(fù)雜性是雜性是O(nlog2n)。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社10.2.2 選擇問題選擇問題 設(shè)無序序列設(shè)無序序列T=(r1, r2, , rn)，T的第的第k（1kn）小元素定義為小元素定義為T按升序排列后在第按升序排列后在第k個(gè)位置上的元素。個(gè)位置上的元素。給定一個(gè)序列給定一個(gè)序列T和一個(gè)整數(shù)和一個(gè)整數(shù)k，尋找，尋找

19、T的第的第k小元素的小元素的問題稱為選擇問題。特別地，將尋找第問題稱為選擇問題。特別地，將尋找第n/2小元素的小元素的問題稱為中值問題。問題稱為中值問題。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 考慮快速排序中的劃分過程，選定一個(gè)軸值將考慮快速排序中的劃分過程，選定一個(gè)軸值將序列序列rirj進(jìn)行劃分，使得比軸值小的元素都位于軸進(jìn)行劃分，使得比軸值小的元素都位于軸值的左側(cè)，比軸值大的元素都位于軸值的右側(cè)，假值的左側(cè)，比軸值大的元素都位于軸值的右側(cè)，假定軸值的最終位置是定軸值的最終位置是s，則：，則：（1）若）若k=s，則，則rs就是第就是第k小元素；小元素；（2）若）若ks，則第

20、，則第k小元素一定在序列小元素一定在序列rs+1rj中；中； ri rk rs-1 rs rs+1 rj 均均rs 軸值軸值 均均rs 查找這里查找這里 ri rs-1 rs rs+1 rk rj 均均rs 軸值軸值 均均rs 查找這里查找這里 (a) 若若ks，則，則rk在軸值的后面在軸值的后面算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 舍伍德型概率算法在一次劃分之前，根據(jù)隨機(jī)數(shù)在待劃舍伍德型概率算法在一次劃分之前，根據(jù)隨機(jī)數(shù)在待劃分序列中隨機(jī)確定一個(gè)記錄作為軸值，并把它與第一個(gè)記錄分序列中隨機(jī)確定一個(gè)記錄作為軸值，并把它與第一個(gè)記錄交換，則一次劃分后得到期望均衡的兩個(gè)子序列，

21、使得選擇交換，則一次劃分后得到期望均衡的兩個(gè)子序列，使得選擇問題在最壞情況下的時(shí)間性能趨近于平均情況的時(shí)間性能。問題在最壞情況下的時(shí)間性能趨近于平均情況的時(shí)間性能。算法算法10.4選擇問題選擇問題 int Select(int r , int low, int high, int k) if (high-lows) return Select(r, low, s-1, k); /在前半部分繼續(xù)查找在前半部分繼續(xù)查找 else return Select(r, s+1, high, k); /在后半部分繼續(xù)查找在后半部分繼續(xù)查找 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社10.3

22、10.3 拉斯維加斯拉斯維加斯(Las Vegas)(Las Vegas)型概率算法型概率算法 10.3.1 10.3.1 八皇后問題八皇后問題10.3.2 10.3.2 整數(shù)因子分解問題整數(shù)因子分解問題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社拉斯維加斯拉斯維加斯(Las Vegas)(Las Vegas)型概率算法型概率算法 拉斯維加斯型概率算法不時(shí)地做出可能導(dǎo)致拉斯維加斯型概率算法不時(shí)地做出可能導(dǎo)致算法陷入僵局的選擇，并且算法能夠檢測是否陷算法陷入僵局的選擇，并且算法能夠檢測是否陷入僵局，如果是，算法就承認(rèn)失敗。這種行為對(duì)入僵局，如果是，算法就承認(rèn)失敗。這種行為對(duì)于一個(gè)確定

23、性算法是不能接受的，因?yàn)檫@意味著于一個(gè)確定性算法是不能接受的，因?yàn)檫@意味著它不能解決相應(yīng)的問題實(shí)例。但是，拉斯維加斯它不能解決相應(yīng)的問題實(shí)例。但是，拉斯維加斯型概率算法的隨機(jī)特性可以接受失敗，只要這種型概率算法的隨機(jī)特性可以接受失敗，只要這種行為出現(xiàn)的概率不占多數(shù)。當(dāng)出現(xiàn)失敗時(shí)，只要行為出現(xiàn)的概率不占多數(shù)。當(dāng)出現(xiàn)失敗時(shí)，只要在相同的輸入實(shí)例上再次運(yùn)行概率算法，就又有在相同的輸入實(shí)例上再次運(yùn)行概率算法，就又有成功的可能。成功的可能。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 拉斯維加斯型概率算法的一個(gè)顯著特征是，它拉斯維加斯型概率算法的一個(gè)顯著特征是，它所做的隨機(jī)性選擇有可能導(dǎo)致算

24、法找不到問題的解，所做的隨機(jī)性選擇有可能導(dǎo)致算法找不到問題的解，即算法運(yùn)行一次，或者得到一個(gè)正確的解，或者無即算法運(yùn)行一次，或者得到一個(gè)正確的解，或者無解。因此，需要對(duì)同解。因此，需要對(duì)同一輸入實(shí)例反復(fù)多次運(yùn)行算法，一輸入實(shí)例反復(fù)多次運(yùn)行算法，直到成功地獲得問題的解。直到成功地獲得問題的解。 由于拉斯維加斯型概率算法有時(shí)運(yùn)行成功，有由于拉斯維加斯型概率算法有時(shí)運(yùn)行成功，有時(shí)運(yùn)行失敗，因此，通常拉斯維加斯型概率算法的時(shí)運(yùn)行失敗，因此，通常拉斯維加斯型概率算法的返回類型為返回類型為boolbool，并且有兩個(gè)參數(shù)：一個(gè)是算法的，并且有兩個(gè)參數(shù)：一個(gè)是算法的輸入，另一個(gè)是當(dāng)算法運(yùn)行成功時(shí)保存問題的解

25、。輸入，另一個(gè)是當(dāng)算法運(yùn)行成功時(shí)保存問題的解。當(dāng)算法運(yùn)行失敗時(shí)，可對(duì)同一輸入實(shí)例再次運(yùn)行，當(dāng)算法運(yùn)行失敗時(shí)，可對(duì)同一輸入實(shí)例再次運(yùn)行，直到成功地獲得問題的解。直到成功地獲得問題的解。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社拉斯維加斯型概率算法的一般形式拉斯維加斯型概率算法的一般形式void Obstinate(input x, solution y) success=false; while (!success) success=LV(x, y);算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 設(shè)設(shè)p(x)是對(duì)輸

26、入實(shí)例是對(duì)輸入實(shí)例x調(diào)用拉斯維加斯型概率調(diào)用拉斯維加斯型概率算法獲得問題的一個(gè)解的概率，則一個(gè)正確的拉斯算法獲得問題的一個(gè)解的概率，則一個(gè)正確的拉斯維加斯型概率算法應(yīng)該對(duì)于所有的輸入實(shí)例維加斯型概率算法應(yīng)該對(duì)于所有的輸入實(shí)例x均有均有p(x)0。在更強(qiáng)的意義下，要求存在一個(gè)正的常數(shù)。在更強(qiáng)的意義下，要求存在一個(gè)正的常數(shù)，使得對(duì)于所有的輸入實(shí)例，使得對(duì)于所有的輸入實(shí)例x均有均有p(x)。由于。由于p(x)，所以，只要有足夠的時(shí)間，對(duì)任何輸入實(shí)，所以，只要有足夠的時(shí)間，對(duì)任何輸入實(shí)例例x，拉斯維加斯型概率算法總能找到問題的一個(gè)，拉斯維加斯型概率算法總能找到問題的一個(gè)解。換言之，拉斯維加斯型概率算法

27、找到正確解的解。換言之，拉斯維加斯型概率算法找到正確解的概率隨著計(jì)算時(shí)間的增加而提高。概率隨著計(jì)算時(shí)間的增加而提高。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社10.3.1 八皇后問題八皇后問題 八皇后問題是在八皇后問題是在88的棋盤上擺放八個(gè)皇后，的棋盤上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。一行、同一列或同一斜線上。 對(duì)于八皇后問題的任何一個(gè)解而言，每一個(gè)皇對(duì)于八皇后問題的任何一個(gè)解而言，每一個(gè)皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更像

28、是隨機(jī)放置的。由此想到拉斯維加斯型概率算更像是隨機(jī)放置的。由此想到拉斯維加斯型概率算法：在棋盤上相繼的各行中隨機(jī)地放置皇后，并使法：在棋盤上相繼的各行中隨機(jī)地放置皇后，并使新放置的皇后與已放置的皇后互不攻擊，直至八個(gè)新放置的皇后與已放置的皇后互不攻擊，直至八個(gè)皇后均已相容地放置好，或下一個(gè)皇后沒有可放置皇后均已相容地放置好，或下一個(gè)皇后沒有可放置的位置。的位置。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 由于棋盤的每一行上可以而且必須放置一個(gè)皇后，所由于棋盤的每一行上可以而且必須放置一個(gè)皇后，所以八皇后問題的可能解用一個(gè)向量以八皇后問題的可能解用一個(gè)向量X=(x1, x2, ,

29、 x8)表示，表示，其中，其中，1xi8并且并且1i8，即第，即第i個(gè)皇后放置在第個(gè)皇后放置在第i行第行第xi列上。列上。由于兩個(gè)皇后不能位于同一列上，所以，解向量由于兩個(gè)皇后不能位于同一列上，所以，解向量X必須滿必須滿足約束條件：足約束條件： xixj （式（式10.2） 若兩個(gè)皇后擺放的位置分別是若兩個(gè)皇后擺放的位置分別是(i, xi)和和(j, xj)，在棋盤上，在棋盤上斜率為斜率為-1的斜線上，滿足條件的斜線上，滿足條件i-j= xi-xj，在棋盤上斜率為，在棋盤上斜率為1的斜線上，滿足條件的斜線上，滿足條件ij= xixj，綜合兩種情況，由于兩，綜合兩種情況，由于兩個(gè)皇后不能位于同一

30、斜線上，所以，解向量個(gè)皇后不能位于同一斜線上，所以，解向量X必須滿足約必須滿足約束條件：束條件： |i-xi|j-xj| （式（式10.3） 滿足式滿足式10.2和式和式10.3的向量的向量X=(x1, x2, , xi)表示已放置表示已放置的的i個(gè)皇后（個(gè)皇后（1i8）互不攻擊，也就是不發(fā)生沖突。）互不攻擊，也就是不發(fā)生沖突。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法算法10.5八皇后問題八皇后問題 1. 將數(shù)組將數(shù)組x8初始化為初始化為0；試探次數(shù)；試探次數(shù)count初始化為初始化為0； 2for (i=1; i=8; i+) 2.1 產(chǎn)生一個(gè)產(chǎn)生一個(gè)1, 8 的隨機(jī)數(shù)

31、的隨機(jī)數(shù)j； 2.2 count=count+1，進(jìn)行第，進(jìn)行第count次試探；次試探； 2.3 若皇后若皇后i放置在位置放置在位置j不發(fā)生沖突，不發(fā)生沖突， 則則xi=j；count=0；轉(zhuǎn)步驟；轉(zhuǎn)步驟2放置下一個(gè)皇后；放置下一個(gè)皇后； 2.4 若若(count= =8)，則無法放置皇后，則無法放置皇后i，算法運(yùn)行失?。?，算法運(yùn)行失敗； 否則，轉(zhuǎn)步驟否則，轉(zhuǎn)步驟2.1重新放置皇后重新放置皇后i； 3. 將元素將元素x1x8作為八皇后問題的一個(gè)解輸出；作為八皇后問題的一個(gè)解輸出； 拉斯維加斯型概率算法通過反復(fù)調(diào)用算法拉斯維加斯型概率算法通過反復(fù)調(diào)用算法10.5，直至得到八皇后問題的一個(gè)解。直

32、至得到八皇后問題的一個(gè)解。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 如果將上述隨機(jī)放置策略與回溯法相結(jié)合，則會(huì)獲如果將上述隨機(jī)放置策略與回溯法相結(jié)合，則會(huì)獲得更好的效果?？梢韵仍谄灞P的若干行中隨機(jī)地放置相得更好的效果?？梢韵仍谄灞P的若干行中隨機(jī)地放置相容的皇后，然后在其他行中用回溯法繼續(xù)放置，直至找容的皇后，然后在其他行中用回溯法繼續(xù)放置，直至找到一個(gè)解或宣告失敗。到一個(gè)解或宣告失敗。 在棋盤中隨機(jī)放置的皇后越多，回溯法搜索所需的在棋盤中隨機(jī)放置的皇后越多，回溯法搜索所需的時(shí)間就越少，但失敗的概率也就越大。時(shí)間就越少，但失敗的概率也就越大。 例如八皇后問題，隨機(jī)地放置兩個(gè)皇后再

33、采用回溯例如八皇后問題，隨機(jī)地放置兩個(gè)皇后再采用回溯法比完全采用回溯法快大約兩倍；隨機(jī)地放置三個(gè)皇后法比完全采用回溯法快大約兩倍；隨機(jī)地放置三個(gè)皇后再采用回溯法比完全采用回溯法快大約一倍；而所有的再采用回溯法比完全采用回溯法快大約一倍；而所有的皇后都隨機(jī)放置比完全采用回溯法慢大約一倍?；屎蠖茧S機(jī)放置比完全采用回溯法慢大約一倍。 很容易解釋這個(gè)現(xiàn)象：不能忽略產(chǎn)生隨機(jī)數(shù)所需的很容易解釋這個(gè)現(xiàn)象：不能忽略產(chǎn)生隨機(jī)數(shù)所需的時(shí)間，當(dāng)隨機(jī)放置所有的皇后時(shí)，八皇后問題的求解大時(shí)間，當(dāng)隨機(jī)放置所有的皇后時(shí)，八皇后問題的求解大約有約有70%的時(shí)間都用在了產(chǎn)生隨機(jī)數(shù)上。的時(shí)間都用在了產(chǎn)生隨機(jī)數(shù)上。 算法設(shè)計(jì)與分析

34、算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社10.3.2 整數(shù)因子分解問題整數(shù)因子分解問題 設(shè)設(shè)n是正整數(shù)且是正整數(shù)且n1，整數(shù)，整數(shù)n的因子分解問題是找的因子分解問題是找出出n的如下形式的惟一分解式：的如下形式的惟一分解式： 其中，其中，p1p2pk是素?cái)?shù)，是素?cái)?shù)，m1, m2, , mk是正整數(shù)。是正整數(shù)。如果如果n是一個(gè)合數(shù)，則是一個(gè)合數(shù)，則n必有一個(gè)非平凡因子必有一個(gè)非平凡因子m（1mn），使得），使得m可以整除可以整除n。給定一個(gè)合數(shù)。給定一個(gè)合數(shù)n，求，求n的一的一個(gè)非平凡因子的問題稱為整數(shù)因子劃分問題。個(gè)非平凡因子的問題稱為整數(shù)因子劃分問題。 kmkmmpppn2121對(duì)于合數(shù)n，

35、n一定存在不大于sqrt(n)的素因子； 1和n都是n的平凡因子，其他因子稱為非平凡因子； 最小非平凡因子一定是素?cái)?shù)。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 整數(shù)因子分解問題可以歸結(jié)為整數(shù)因子整數(shù)因子分解問題可以歸結(jié)為整數(shù)因子劃分和素?cái)?shù)測試：假設(shè)對(duì)整數(shù)劃分和素?cái)?shù)測試：假設(shè)對(duì)整數(shù)n進(jìn)行因子分進(jìn)行因子分解，首先進(jìn)行素?cái)?shù)測試，如果解，首先進(jìn)行素?cái)?shù)測試，如果n是素?cái)?shù)，則是素?cái)?shù)，則分解完成；否則，再進(jìn)行因子劃分，找到分解完成；否則，再進(jìn)行因子劃分，找到n的一個(gè)非平凡因子的一個(gè)非平凡因子m，并遞歸地對(duì)，并遞歸地對(duì)m和和n/m進(jìn)進(jìn)行因子分解。行因子分解。 下面討論整數(shù)因子劃分問題。下面討

36、論整數(shù)因子劃分問題。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 對(duì)一個(gè)正整數(shù)對(duì)一個(gè)正整數(shù)n進(jìn)行因子劃分的最自然的想法進(jìn)行因子劃分的最自然的想法是試除，它可以找到是試除，它可以找到n的最小素?cái)?shù)因子。的最小素?cái)?shù)因子。算法算法10. .5整數(shù)因子劃分整數(shù)因子劃分 int Factor(int n) i =sqrt(n); for (m=2; m1) return d; /若若y- -x與與n存在最大公約數(shù)存在最大公約數(shù)d，則，則d即為即為n的非平凡因子的非平凡因子 if (i= =k) y=x; k*=2; 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 算法算法Pollar

37、d中的中的while循環(huán)執(zhí)行約循環(huán)執(zhí)行約 次后，次后，會(huì)得到會(huì)得到n的一個(gè)素?cái)?shù)因子的一個(gè)素?cái)?shù)因子p。由于。由于n的最小素?cái)?shù)的最小素?cái)?shù)因子因子 ，故算法，故算法Pollard可在可在O(n1/4)的時(shí)間的時(shí)間內(nèi)找到內(nèi)找到n的一個(gè)素?cái)?shù)因子。的一個(gè)素?cái)?shù)因子。 pnp 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社10.4 蒙特卡羅蒙特卡羅(Monte Carlo)型概率算法型概率算法10.4.1 主元素問題主元素問題10.4.2 素?cái)?shù)測試問題素?cái)?shù)測試問題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社蒙特卡羅（蒙特卡羅（Monte Carlo）算法）算法 蒙特卡羅算法總能得到問題的

38、答案。偶然產(chǎn)生不正確的答案。p：正確解的概率，1/2p1，稱算法是p正確的，優(yōu)勢(shì)為p-1/2。運(yùn)行同一實(shí)例兩次，不會(huì)給出兩個(gè)不同的正確答案，稱算法是一致的。重復(fù)運(yùn)行一致的p正確的算法，每一次運(yùn)行都獨(dú)立地進(jìn)行隨機(jī)選擇，可使產(chǎn)生不正確答案的概率變得任意小。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社10.4.1 主元素問題主元素問題 設(shè)設(shè)Tn是一個(gè)含有是一個(gè)含有n個(gè)元素的數(shù)組，個(gè)元素的數(shù)組，x是數(shù)組是數(shù)組T的的一個(gè)元素，如果數(shù)組中有一半以上的元素與一個(gè)元素，如果數(shù)組中有一半以上的元素與x相同，相同，則稱元素則稱元素x是數(shù)組是數(shù)組T的主元素（的主元素（Major Element）。）。

39、例如，在數(shù)組例如，在數(shù)組T7=3, 2, 3, 2, 3, 3, 5中，元素中，元素3就是就是主元素。主元素。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 蒙特卡羅型概率算法求解主元素問題可以隨機(jī)蒙特卡羅型概率算法求解主元素問題可以隨機(jī)地選擇數(shù)組中的一個(gè)元素地選擇數(shù)組中的一個(gè)元素Ti進(jìn)行統(tǒng)計(jì)，如果該元進(jìn)行統(tǒng)計(jì)，如果該元素出現(xiàn)的次數(shù)大于素出現(xiàn)的次數(shù)大于n/2，則該元素就是數(shù)組的主元，則該元素就是數(shù)組的主元素，算法返回素，算法返回true；否則隨機(jī)選擇的這個(gè)元素；否則隨機(jī)選擇的這個(gè)元素Ti不是主元素，算法返回不是主元素，算法返回false。此時(shí)，數(shù)組中可能有。此時(shí)，數(shù)組中可能有主元素

40、也可能沒有主元素。如果數(shù)組中存在主元素，主元素也可能沒有主元素。如果數(shù)組中存在主元素，則非主元素的個(gè)數(shù)小于則非主元素的個(gè)數(shù)小于n/2。因此，算法將以大于。因此，算法將以大于1/2的概率返回的概率返回true，以小于，以小于1/2的概率返回的概率返回false，這說明算法出現(xiàn)錯(cuò)誤的概率小于這說明算法出現(xiàn)錯(cuò)誤的概率小于1/2。如果連續(xù)運(yùn)。如果連續(xù)運(yùn)行算法行算法k次，算法返回次，算法返回false的概率將減少為的概率將減少為2-k，則，則算法發(fā)生錯(cuò)誤的概率為算法發(fā)生錯(cuò)誤的概率為2-k。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法算法10.8主元素問題主元素問題 bool Majori

41、ty(int T , int n) i=Random(0, n- -1); x=Ti; /隨機(jī)選擇一個(gè)數(shù)組元素隨機(jī)選擇一個(gè)數(shù)組元素 k=0; for (j=0; jn/2) / kn/2時(shí)含有主元素為時(shí)含有主元素為Ti return true; else return false; bool MajorityMC(int T , int n, double e) k=log(1/e)/log(2); for (i=1; i0，算法，算法MajorityMC重復(fù)重復(fù)調(diào)用調(diào)用 log2(1/ ) 次算法次算法Majority，其錯(cuò)誤概率小于其錯(cuò)誤概率小于 ，時(shí)間復(fù)雜性顯然是，時(shí)間復(fù)雜性顯然是O(n

42、log2(1/ )。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社10.4.2 素?cái)?shù)測試問題素?cái)?shù)測試問題 測試一個(gè)整數(shù)測試一個(gè)整數(shù)n是否是素?cái)?shù)，最簡單的方法是把是否是素?cái)?shù)，最簡單的方法是把這個(gè)數(shù)除以這個(gè)數(shù)除以2 的數(shù)，如果余數(shù)為的數(shù)，如果余數(shù)為0，則，則n是是一個(gè)合數(shù)，否則，一個(gè)合數(shù)，否則，n就是一個(gè)素?cái)?shù)。就是一個(gè)素?cái)?shù)。 算法算法10. .9素?cái)?shù)測試素?cái)?shù)測試 bool Factor(int n) i =sqrt(n); for (m=2; m=i; m+) if (n % m= =0) return false; return true; /如果找不到一個(gè)因子，則如果找不到一個(gè)因子，

43、則n是素?cái)?shù)是素?cái)?shù) n算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 算法算法10.9的時(shí)間復(fù)雜性是的時(shí)間復(fù)雜性是O( )。對(duì)于一個(gè)正。對(duì)于一個(gè)正整數(shù)整數(shù)n，其位數(shù)為，其位數(shù)為 ，則算法，則算法Factor的時(shí)間復(fù)雜性是的時(shí)間復(fù)雜性是O(10m/2)，因此，這個(gè)算法的時(shí)間因此，這個(gè)算法的時(shí)間復(fù)雜性是指數(shù)階的。復(fù)雜性是指數(shù)階的。費(fèi)爾馬定理費(fèi)爾馬定理 如果如果n是一個(gè)素?cái)?shù)，是一個(gè)素?cái)?shù)，a為正整數(shù)且為正整數(shù)且0an，則，則an-1 mod n1。 費(fèi)爾馬定理表明，如果存在一個(gè)小于費(fèi)爾馬定理表明，如果存在一個(gè)小于n的正的正整數(shù)整數(shù)a，使得，使得an-1 mod n1，則，則n肯定不是素?cái)?shù)?？隙?/p>

44、不是素?cái)?shù)。n) 1(log10nm算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 費(fèi)爾馬定理只是素?cái)?shù)判定的一個(gè)必要條件，有些費(fèi)爾馬定理只是素?cái)?shù)判定的一個(gè)必要條件，有些合數(shù)也滿足費(fèi)爾馬定理，這些合數(shù)被稱作合數(shù)也滿足費(fèi)爾馬定理，這些合數(shù)被稱作Carmichael數(shù)。數(shù)。Carmichael數(shù)是非常少的，在數(shù)是非常少的，在1100,000,000范范圍內(nèi)的整數(shù)中，只有圍內(nèi)的整數(shù)中，只有255個(gè)個(gè)Carmichael數(shù)。為了提高數(shù)。為了提高素?cái)?shù)測試的準(zhǔn)確性，可以多次隨機(jī)選取小于素?cái)?shù)測試的準(zhǔn)確性，可以多次隨機(jī)選取小于n的正整的正整數(shù)數(shù)a，重復(fù)計(jì)算，重復(fù)計(jì)算dan-1 mod n來判定來判定n是

45、否是素?cái)?shù)。是否是素?cái)?shù)。例如，對(duì)于例如，對(duì)于341，取，取a=3，則，則3340 mod 34156，從而，從而判定判定341不是素?cái)?shù)。不是素?cái)?shù)。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法算法10.10Fermat測試測試int ExpMod(int n) /計(jì)算計(jì)算an-1 mod n a=Random(2, n- -1); /產(chǎn)生產(chǎn)生2, n- -1之間的一個(gè)隨機(jī)整數(shù)之間的一個(gè)隨機(jī)整數(shù) b=1; for (i=1; i=n- -1; i+) b=(b*a) % n; return b;bool Prime1(int n) if (ExpMod(n)= =1) return

46、true; /可能是素?cái)?shù)或可能是素?cái)?shù)或Carmichael數(shù)數(shù) else return false; /一定不是素?cái)?shù)一定不是素?cái)?shù)算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 算法算法Prime1返回返回false時(shí)，整數(shù)時(shí)，整數(shù)n一定是一個(gè)合一定是一個(gè)合數(shù)，數(shù)，如果算法如果算法Prime1返回返回true，說明正整數(shù)，說明正整數(shù)n可能可能是素?cái)?shù)，還可能是是素?cái)?shù)，還可能是Carmichael數(shù)。但是，這個(gè)簡數(shù)。但是，這個(gè)簡單的測試卻很少給出錯(cuò)誤的結(jié)果。當(dāng)一個(gè)合數(shù)單的測試卻很少給出錯(cuò)誤的結(jié)果。當(dāng)一個(gè)合數(shù)n對(duì)對(duì)于整數(shù)于整數(shù)a滿足費(fèi)爾馬定理時(shí)，稱整數(shù)滿足費(fèi)爾馬定理時(shí)，稱整數(shù)a為合數(shù)為合數(shù)n

47、的偽的偽證據(jù)（證據(jù)（Pseudowitness）。所以，只有在選取到一）。所以，只有在選取到一個(gè)偽證據(jù)時(shí)，個(gè)偽證據(jù)時(shí)，F(xiàn)ermat測試的結(jié)論才是錯(cuò)誤的。測試的結(jié)論才是錯(cuò)誤的。 幸運(yùn)的是偽證據(jù)相當(dāng)少。在小于幸運(yùn)的是偽證據(jù)相當(dāng)少。在小于1000的的332個(gè)個(gè)合數(shù)中只有合數(shù)中只有5個(gè)沒有偽證據(jù)，超過一半的合數(shù)只有個(gè)沒有偽證據(jù)，超過一半的合數(shù)只有兩個(gè)偽證據(jù)，超過兩個(gè)偽證據(jù)，超過15個(gè)偽證據(jù)的合數(shù)不超過個(gè)偽證據(jù)的合數(shù)不超過160個(gè)。個(gè)。如果考慮更大的數(shù)，這個(gè)概率會(huì)更小。如果考慮更大的數(shù)，這個(gè)概率會(huì)更小。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社但是，有些合數(shù)的偽證據(jù)比例相當(dāng)高，在小于但是，有些合數(shù)的偽證據(jù)比例相當(dāng)高，在小于1000的合數(shù)中，的合數(shù)中，情況最壞的是情況最壞的是561，它有，它有318個(gè)偽證據(jù)。最壞的一個(gè)例子是一個(gè)偽證據(jù)。最壞的一個(gè)例子是一個(gè)個(gè)15位的合數(shù)位的合數(shù)651,693,055,693,681，它以大于，它以大于99.965的概的概率返回率返回