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