概率算法ppt課件(完整版)
【正文】 的近似解。 } 5 計(jì)算定積分 設(shè) f(x)是 [0， 1]上的連續(xù)函數(shù)，且 0?f(x)?1。從而 。如何選取該方法中的常數(shù) b、 c和 m直接關(guān)系到所產(chǎn)生的隨機(jī)序列的隨機(jī)性能。 線性同余法 是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法。設(shè)落入圓內(nèi)的點(diǎn)數(shù)為 k。 double y=()。在算法的搜索過(guò)程中，假設(shè)第 j步隨機(jī)搜索得到的隨機(jī)搜索點(diǎn)為 xj。當(dāng) s(n)與 tA(n)相比可忽略時(shí)，舍伍德算法可獲得很好的平均性能。i++) { int j=(ni+1)+i。這使得跳躍表可在 O(logn)平均時(shí)間內(nèi)支持關(guān)于有序集的搜索、插入和刪除等運(yùn)算。 11 跳躍表 為了在動(dòng)態(tài)變化中維持跳躍表中附加指針的平衡性，必須使跳躍表中 k級(jí)結(jié)點(diǎn)數(shù)維持在總結(jié)點(diǎn)數(shù)的一定比例范圍內(nèi)。如果 qp，則使新結(jié)點(diǎn)級(jí)別增加 1，直至 q?p。 } 設(shè) p(x)是對(duì)輸入 x調(diào)用拉斯維加斯算法獲得問(wèn)題的一個(gè)解的概率。 stopVegas p s e t 0 5 12 15 整數(shù)因子分解 設(shè) n1是一個(gè)整數(shù)。 return 1。 x=(x*x1)%n。由于 n的最小素因子 p? ，故 Pollard算法可在O(n1/4)時(shí)間內(nèi)找到 n的一個(gè)素因子。 18 蒙特卡羅 (Monte Carlo)算法 對(duì)于一個(gè)一致的 p正確蒙特卡羅算法，要提高獲得正確解的概率，只要執(zhí)行該算法若干次，并選擇出現(xiàn)頻次最高的解即可。 int x=t[i]。次調(diào)用算法 majority int k= (int) ((1/e)/(2))。 20 素?cái)?shù)測(cè)試 Wilson定理 ： 對(duì)于給定的正整數(shù) n，判定 n是一個(gè)素?cái)?shù)的充要條件是 (n1)!? 1(mod n)。amp。 posite=false。 。 result=power(a,n1,n)。amp。 二次探測(cè)定理 ： 如果 p是一個(gè)素?cái)?shù)，且 0xp，則方程 x2?1(mod p)的解為 x=1， p1。i=k。 for (int j=1。 稱上述算法 MC(x)是 偏 y0的算法 。蒙特卡羅算法則在一般情況下可以保證對(duì)問(wèn)題的所有實(shí)例都以高概率給出正確解，但是通常無(wú)法判定一個(gè)具體解是否正確。 // 求 n的非平凡因子 if ((d1) amp。 16 Pollard算法 在開(kāi)始時(shí)選取 0～ n1范圍內(nèi)的隨機(jī)數(shù)，然后遞歸地由 產(chǎn)生無(wú)窮序列 對(duì)于 i=2k，以及 2kj?2k+1，算法計(jì)算出 xjxi與 n的最大公因子 d=gcd(xjxi， n)。 如果 n是一個(gè)合數(shù)，則 n必有一個(gè)非平凡因子 x， 1xn，使得 x可以整除 n。 設(shè) t(x)是算法 obstinate找到具體實(shí)例 x的一個(gè)解所需的平均時(shí)間 ,s(x)和 e(x)分別是算法對(duì)于具體實(shí)例 x求解成功或求解失敗所需的平均時(shí)間，則有： 解此方程可得： ))()())((1()()()( xtxexpxsxpxt ????)()( )(1)()( xexp xpxsxt ???14 n后問(wèn)題 對(duì)于 n后問(wèn)題的任何一個(gè)解而言，每一個(gè)皇后在棋盤上的位置無(wú)任何規(guī)律，不具有系統(tǒng)性，而更象是隨機(jī)放置的。如此產(chǎn)生的新結(jié)點(diǎn)的級(jí)別有可能是一個(gè)很大的數(shù)，甚至遠(yuǎn)遠(yuǎn)超過(guò)表中元素的個(gè)數(shù)。因此，在插入一個(gè)元素時(shí)，以概率 1/2引入一個(gè)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1