概率算法ppt課件-閱讀頁(yè)
2025-05-16 02:28本頁(yè)面
【正文】 了試除而得到范圍在 1～ x2的任一整數(shù)的因子分割。如果 d是 n的非平凡因子，則實(shí)現(xiàn)對(duì) n的一次分割，算法輸出 n的因子 d。 // 初始化隨機(jī)數(shù) int i=1,k=2。 // 隨機(jī)整數(shù) while (true) { i++。 int d=gcd(yx,n)。amp。 if (i==k) { y=x。} } } 對(duì) Pollard算法更深入的分析可知，執(zhí)行算法的 while循環(huán)約 次后， Pollard算法會(huì)輸出 n的一個(gè)因子 p。 np17 蒙特卡羅 (Monte Carlo)算法 ?在實(shí)際應(yīng)用中常會(huì)遇到一些問(wèn)題，不論采用確定性算法或概率算法都無(wú)法保證每次都能得到正確的解答。 ?設(shè) p是一個(gè)實(shí)數(shù)，且 1/2p1。 ?如果對(duì)于同一實(shí)例，蒙特卡羅算法不會(huì)給出 2個(gè)不同的正確解答，則稱該蒙特卡羅算法是 一致的 。這類算法的計(jì)算時(shí)間復(fù)雜性通常由問(wèn)題的實(shí)例規(guī)模以及錯(cuò)誤解可接受概率的函數(shù)來(lái)描述。 如果重復(fù)調(diào)用一個(gè)一致的 (1/2+?)正確的蒙特卡羅算法 2m1次，得到正確解的概率至少為 1?，其中， mii mimi ??????4)41()41(221 2210????????????? ???對(duì)于一個(gè)解所給問(wèn)題的蒙特卡羅算法 MC(x)，如果存在問(wèn)題實(shí)例的子集 X使得： (1)當(dāng) x?X時(shí)， MC(x)返回的解是正確的； (2)當(dāng) x?X時(shí)，正確解是 y0，但 MC(x)返回的解未必是 y0。 重復(fù)調(diào)用一個(gè)一致的， p正確偏 y0蒙特卡羅算法 k次，可得到一個(gè) O(1(1p)k)正確的蒙特卡羅算法，且所得算法仍是一個(gè)一致的偏 y0蒙特卡羅算法。當(dāng) |{i|T[i]=x}|n/2時(shí)，稱元素 x是數(shù)組 T的主元素。 int i=(n)+1。 // 隨機(jī)選擇數(shù)組元素 int k=0。j=n。 return (kn/2)。 249。 for (int i=1。i++) if (majority(t,n)) return true。 } 對(duì)于任何給定的 ?0，算法majorityMC重復(fù)調(diào)用 ?log(1/?)? 次算法 majority。算法 majorityMC所需的計(jì)算時(shí)間顯然是 O(nlog(1/ ?))。 費(fèi)爾馬小定理 ： 如果 p是一個(gè)素?cái)?shù)，且 0ap，則 ap1(mod p)。 private static int power(int a, int p, int n) {// 計(jì)算 ap mod n，并實(shí)施對(duì) n的二次探測(cè) int x, result。 else { x=power(a,p/2,n)。 // 二次探測(cè) if ((result==1)amp。(x!=1)amp。(x!=n1)) posite=true。 } return result。 int a, result。 a=(n3)+2。 if (posite||(result!=1)) return false。 } 算法 prime是一個(gè)偏假 3/4正確的蒙特卡羅算法。這是一個(gè)很保守的估計(jì)，實(shí)際使用的效果要好得
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1