概率算法ppt課件-資料下載頁(yè)
2025-05-01 02:28本頁(yè)面
【正文】 /2時(shí)，稱元素 x是數(shù)組 T的主元素。 public static boolean majority(int[]t, int n) {// 判定主元素的蒙特卡羅算法 rnd = new Random()。 int i=(n)+1。 int x=t[i]。 // 隨機(jī)選擇數(shù)組元素 int k=0。 for (int j=1。j=n。j++) if (t[j]==x) k++。 return (kn/2)。 // kn/2 時(shí) t含有主元素 } public static boolean majorityMC(int[]t, int n, double e) {// 重復(fù) 233。 249。次調(diào)用算法 majority int k= (int) ((1/e)/(2))。 for (int i=1。i=k。i++) if (majority(t,n)) return true。 return false。 } 對(duì)于任何給定的 ?0，算法majorityMC重復(fù)調(diào)用 ?log(1/?)? 次算法 majority。它是一個(gè)偏真蒙特卡羅算法，且其錯(cuò)誤概率小于 ?。算法 majorityMC所需的計(jì)算時(shí)間顯然是 O(nlog(1/ ?))。 20 素?cái)?shù)測(cè)試 Wilson定理 ： 對(duì)于給定的正整數(shù) n，判定 n是一個(gè)素?cái)?shù)的充要條件是 (n1)!? 1(mod n)。 費(fèi)爾馬小定理 ： 如果 p是一個(gè)素?cái)?shù)，且 0ap，則 ap1(mod p)。 二次探測(cè)定理 ： 如果 p是一個(gè)素?cái)?shù)，且 0xp，則方程 x2?1(mod p)的解為 x=1， p1。 private static int power(int a, int p, int n) {// 計(jì)算 ap mod n，并實(shí)施對(duì) n的二次探測(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)amp。amp。(x!=1)amp。amp。(x!=n1)) posite=true。 if ((p%2)==1) // p是奇數(shù) result=(result*a)%n。 } return result。} public static boolean prime(int n) {// 素?cái)?shù)測(cè)試的蒙特卡羅算法 rnd = new Random()。 int a, result。 posite=false。 a=(n3)+2。 result=power(a,n1,n)。 if (posite||(result!=1)) return false。 else return true。 } 算法 prime是一個(gè)偏假 3/4正確的蒙特卡羅算法。通過(guò)多次重復(fù)調(diào)用錯(cuò)誤概率不超過(guò) (1/4)k。這是一個(gè)很保守的估計(jì)，實(shí)際使用的效果要好得多。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1