王國威概率算法作業(yè)

1、中國科學技術大學 計算機科學與技術系SA12011911王國威概率算法作業(yè)Ex1程序代碼如下：public class ex1 public static void main(String args) ex1 ex1sample = new ex1();int i = 1;while (i = 100) double result = ex1sample.dart(1000000 * i); System.out.println( + 10000000 * i + 次運算結果為： + i = i * 10;result);public double dart(int n) int k = 0;

2、for (int i = 0; i n; i+) double x = Math.random(); double y = x;double r = x * x + y * y; if (r = 1)k+;return 4 * k / (double) n;運行截圖如下Ex2代碼如下public class ex2 public double HitorMiss(int n) int k = 0;for (int i = 0; i n; i+) 中國科學技術大學 計算機科學與技術系SA12011911王國威double x = Math.random(); double y = Math.ra

3、ndom(); if (y = f(x)k+;double r1 = k / (double) n; return 4 * r1;public double f(double x) double y = Math.sqrt(1.0 - x * x); return y;主函數(shù)調用部分代碼如下public static void main(String args) ex2 ex2sample = new ex2();int i = 1;while (i = 100) double result = ex2sample.HitorMiss(10000000 * i); System.out.pri

4、ntln( + 10000000 * i + 次運算結果為pi = + result); i = i * 10;運行截圖入下Ex3代碼如下（由于 JAVA 中沒有函數(shù)指針，故用 C+編寫）函數(shù) f 為 x*x+1.0， #include #include #include #include 區(qū)間為 a、b、c、d 取值分別為 1、2、2、5using namespace std;double function(double x) double y = x*x + 1.0; return y;中國科學技術大學 計算機科學與技術系SA12011911王國威double HitorMiss(doub

5、le (*pf)(double ) , int n ,double a,double b, double c, double d)/已經完全考慮了f(x)曲線的各種情況，包括是否穿越x軸、f(x)上下限與x左右極不對應等 int k = 0;srand(time(0);double s = ( b - a ) * ( d - c + fabs( c - 0.0); for (int i = 0; i n; i+)double x = (double)rand() * ( b - a )/ RAND_MAX + a;double y = (double)rand() * ( d - c + fa

6、bs(c-0.0) / RAND_MAX + c - fabs(c-0.0);if (y = (*pf)(x) k+;return s * k / n;voidmain()double a = 1.0; double b = 2.0; double c = 2.0;double d = 5.0; /此時a,b,c,d已經先計算好了，因為c和d的確定很難直/接在程序中通過a和b計算出來for (int i = 1; i = 100; i = i*10)double resulty = HitorMiss(function, i*10000000, a, b, c, d); couti*10000

7、000次計算結果為： ; coutsetprecision(10)resultyendl;system(pause);運行截圖為Ex4證：HitorMiss 算法中的 k 符合二項分布 B(n,I)，期望Ek = nI，方差Var(k) = nI(1 I)， 算法的返回值h = k/n根據(jù)切比雪夫不等式有中國科學技術大學 計算機科學與技術系SA12011911王國威1Pr (|k nI| (1 ) n (1)時，有 (1)，所以有當2(1 )Pr(|h I| ) Pr (|h I| )(1 )= 1 Pr (| | )1= 1 Pr (| | (1 ) 1 即證Ex5 估算整數(shù)集 1n 的大小

8、代碼如下package .ustc.weiking;import importimportjava.util.HashSet; java.util.Random;java.util.Set;publicclass ex5 public int setN(int n) long sum = 0;intfork = 100;(int j = 0; j k; j+) sum += SetCount(n); / 每種情況計算100次取平均intcountSet = (int) (sum /k);returncountSet;publiclong klong SetCount(int n)=

9、 0;Set S = new HashSet(); Random rand = new Random();int a = rand.nextInt(n); do k+;中國科學技術大學 計算機科學與技術系SA12011911王國威S.add(a);a = rand.nextInt(n); while (!S.contains(a);return (long) (2 * k * k /Math.PI);主函數(shù)調用部分如下public static void main(String args) ex5 ex5sample = new ex5();int i = 1;while (i = 100)

10、int result = ex5sample.setN(10000000 System.out.println( + 10000000 * i+ result);i = i * 10;* i);+ 大小的整數(shù)集運算所得集合的勢為算法多次運行結果，并未發(fā)現(xiàn)與 n 的值有特別大的關聯(lián)，可能是數(shù)據(jù)過少或者是隨機函數(shù)并不是真正的隨機造成的結果。同時，計算出的結果偏差較大，估計是因為 n 的值過小，雖然 10 億的集合已經很大，但是因為計算次數(shù)僅為 30000 左右，對于概率算法來說，30000 次左右的計算次數(shù)完全不夠，可能需要更大的計算規(guī)模才能得出較為精確的結果Ex6 分析 dlogRH 的工作原理

11、，指出該算法相應的 u 和 v解：DlogRH 算法描述如下.5.6.7.function DlogRH(g,a,p) r uniform(0, p 2) b c y log, return (y-r) mod (p-1)End function此算法中，第 4 行，c = ba mod p = + ；第 5 行解得的y 滿足 + 。所以有y + ( 1)，因而算法的輸出(y r)mod(p 1)是正確的此算法中，對于給定的 p 有中國科學技術大學 計算機科學與技術系SA12011911王國威u(x, r) = (, ) v(, ) = ( )( 1) = (, ) = log,

12、( )Ex7整體代碼過多，下面只貼出寫出的 Sherwood 算法，只是對算法 B 的尋找最大整數(shù)部分進行隨機化，可得到代碼如下： public int C(int x) int i = head; int max = vali;/隨機化部分，用隨機的步距進行隨機化int step = rand.nextInt(int) Math.sqrt(int) Math.sqrt(n) + 1; for (int j = 1; j = (int) Math.sqrt(n); j += step) int y = valj;if (max y & y = x) i = j;max = y;return s

13、earch(x, i);算法C對算法B的改動部分主要是將原來算法中尋找最大值的步距增大為step，由于step隨機生成，故有一定的隨機性，也減少了迭代步數(shù)本實驗中，由于CPU中高速緩存對順序存取和隨機存取速度的影響，選定輸入規(guī)模為1000000的數(shù)組進行尋找，對不同的類型的序列，不同算法的運行時間如下表所示。下圖為x=1時不同算法在不同類型序列的時間開銷，其余輸入因篇幅中。不在贅述，數(shù)據(jù)寫入表中國科學技術大學 計算機科學與技術系SA12011911王國威由上表中信息計算平均時間和最壞時間可得下表可見，對于不同序列，算法 B 的平均時間明顯優(yōu)于其他算法的時間，算法 C 在算法 B 的方法上進行改

14、動，但是執(zhí)行時間除了在隨機分布序列明顯小于 A 和 D 外，別的都沒有優(yōu)勢，也許是因為改動的方式不太好，將預處理部分從 sqrt(n)復雜度減為 sqrt(sqrt(n)，復雜度降低過多，導致預處理效果不是很好。Ex8證：當放置第 k+1 個皇后時，設總共有 m 個位置是開放的。根據(jù)算法的描述，第 i 個開放位置被選擇當且僅當：發(fā)現(xiàn)第 i 個開放位置時，其被選擇，并且其后的 m-i 個開放位置不被選擇。此概率為1 + 1 11 = = + 1 + 2所以開放位置的選取時等概率的Ex9算法代碼如下 public class ex9 private final HashSet col = new

15、HashSet();序列類型算法 A/s算法 B/s算法 C/s算法 D/s隨機分布序列平均時間最壞時間44243.1588742.19242.43685.6311377.1662589.49825855.442114.147遞增序列平均時間最壞時間1717.1552441.2981609.5762311.1471908.962728.0311015.6831293.615遞減序列平均時間最壞時間1539.6942528.037985.15341784.8271131.1252091.739991.99181256.547序列類型X 值算法 A/s算法 B/s算法 C/s算法 D/s隨機分布序

16、列125000050000075000010000003.30521862.68143569.45467038.12788742.19213.86985.63133.5294851830.6337.7021445.5392007.341835.7522589.4981.68519474.18631946.88935740.10142114.147遞增序列125000050000075000010000002404.82619.0821307.4241813.1532441.2982254.99575.1571183.6261722.9592311.1472719.455682.7461369.

17、392045.182728.0311293.615552.281912.6411082.5961237.282遞減序列125000050000075000010000001347.142624.5191274.7821923.9892528.0371295.314608.9941227.0921784.8279.541465.198702.8491393.4632091.7392.378964.245558.121983.361197.6861256.547中國科學技術大學 計算機科學與技術系SA12011911王國威privateprivate privatefinal HashSetfin

18、al HashSet static Random rand;diag45 = new HashSet();diag135 = new HashSet();public final int nint tryArr = new= 12;intn + 1;public static voidmain(String args) ex9 e = new ex9(); rand = new Random();for (int j = 0; j = e.n; j+) long starttime = System.nanoTime(); for (int i = 0; i 1000; i+) while (

19、!e.QueensLV(j, e.n);System.out.println(stepVages = + j + ,Time : + (System.nanoTime() - starttime) / 1000 / 1E3 + us); /endof /endpublic boolean QueensLV(int stepVegas, int n) col.clear();diag45.clear();diag135.clear();int intintk = 0;j = 0;nb = 0;do nb = 0;for (int i = 1; i 0) k+;tryArrk = j; col.a

20、dd(j);diag45.add(j - k); diag135.add(j + k); while (nb != 0 & k != n);中國科學技術大學 計算機科學與技術系SA12011911王國威return (nb0);部分截圖如下將所有數(shù)據(jù)列在下表中運行時間（s）201918171159.503940.248755.075640.899490.386452.135384.86281.277205.89711128.004881.856709.56611.445489.564418.411351.962250.54197.42721123.056918.692739.905601.58

21、4484.169407.207382.432239.104194.71531116.464878.514745.947633.685470.993427.868345.741235.967190.51141122.193915.307755.142633.06494.273411.801358.58247.987182.2851098.104873.788735.393615.733454.819399.846338.535236.722197.58561111.769850.773770.121618.704483.705390.36347.213243.552182.67671084.83

22、5838.221683.319626.787461.578392.575354.001247.989185.95581092.425904.457752.733565.892457.222405.972339.017251.461195.7191095.827907.294735.499629.636479.147415.504353.212249.705188.746101018.194860.13742.577582.153476.931397.621344.132237.624191.367111074.939892.147763.103605.659467.656430.034345.

23、446244.499203.487121066.624875.629738.715585.176478.756394.89365.673263.488183.018131091.65863.662734.56635.943471.72409.602343.186241.034141034.157912.648693.588627.055482.97416.399358.796151086.154875.12711.642595.48488.128411.185161082.591839.874773.012637.032511.21171102.592912.668705.514603.205

24、181115.382884.697769.298中國科學技術大學 計算機科學與技術系SA12011911王國威可以看出，最優(yōu) stepVegas 在下表中從上述兩表可以看出，最優(yōu) stepVegas 一般為小于 n/2，在算法中 rand 函數(shù)占用的時間過多，可能不是很準確Ex10代碼過長，直接貼在后面。10000 以內的素數(shù)確定性算法和 Miller-Rabin 算法都得到了 1229 個素數(shù)的結果，且經驗證，結果都正確。故Miller-Rabin 算法在此范圍內無誤代碼如下package .ustc.weiking;importimportjava.math.BigIntege

25、r;java.util.Random;publicclass primeprivate Random rand = new Random(); public static void main(String args)prime pr = new prime(); pr.PrintPrimes(); pr.funprime();void PrintPrimes()System.out.print(2t3t);int nint m while= 5;= 2;(n = 10000)if (RepeatMillRab(n, (int) (Math.log(n)System.out.print(n + t); if (m % 10 = 9)System.out.println();m+;/ Math.log(2)201918171615141312最優(yōu)1077856534191112.124870.339201093.06中國科學技術大學 計算機科學與技術系SA12011911王國威n = n + 2;System.out.pr