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

1、中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系SA12011911王國(guó)威概率算法作業(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 + 次運(yùn)算結(jié)果為： + 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;運(yùn)行截圖如下Ex2代碼如下public class ex2 public double HitorMiss(int n) int k = 0;for (int i = 0; i n; i+) 中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系SA12011911王國(guó)威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ù)調(diào)用部分代碼如下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 + 次運(yùn)算結(jié)果為pi = + result); i = i * 10;運(yùn)行截圖入下Ex3代碼如下（由于 JAVA 中沒(méi)有函數(shù)指針，故用 C+編寫(xiě)）函數(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;中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系SA12011911王國(guó)威double HitorMiss(doub

5、le (*pf)(double ) , int n ,double a,double b, double c, double d)/已經(jīng)完全考慮了f(x)曲線的各種情況，包括是否穿越x軸、f(x)上下限與x左右極不對(duì)應(yīng)等 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; /此時(shí)a,b,c,d已經(jīng)先計(jì)算好了，因?yàn)閏和d的確定很難直/接在程序中通過(guò)a和b計(jì)算出來(lái)for (int i = 1; i = 100; i = i*10)double resulty = HitorMiss(function, i*10000000, a, b, c, d); couti*10000

7、000次計(jì)算結(jié)果為： ; coutsetprecision(10)resultyendl;system(pause);運(yùn)行截圖為Ex4證：HitorMiss 算法中的 k 符合二項(xiàng)分布 B(n,I)，期望Ek = nI，方差Var(k) = nI(1 I)， 算法的返回值h = k/n根據(jù)切比雪夫不等式有中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系SA12011911王國(guó)威1Pr (|k nI| (1 ) n (1)時(shí)，有 (1)，所以有當(dāng)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); / 每種情況計(jì)算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+;中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系SA12011911王國(guó)威S.add(a);a = rand.nextInt(n); while (!S.contains(a);return (long) (2 * k * k /Math.PI);主函數(shù)調(diào)用部分如下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ù)集運(yùn)算所得集合的勢(shì)為算法多次運(yùn)行結(jié)果，并未發(fā)現(xiàn)與 n 的值有特別大的關(guān)聯(lián)，可能是數(shù)據(jù)過(guò)少或者是隨機(jī)函數(shù)并不是真正的隨機(jī)造成的結(jié)果。同時(shí)，計(jì)算出的結(jié)果偏差較大，估計(jì)是因?yàn)?n 的值過(guò)小，雖然 10 億的集合已經(jīng)很大，但是因?yàn)橛?jì)算次數(shù)僅為 30000 左右，對(duì)于概率算法來(lái)說(shuō)，30000 次左右的計(jì)算次數(shù)完全不夠，可能需要更大的計(jì)算規(guī)模才能得出較為精確的結(jié)果Ex6 分析 dlogRH 的工作原理

11、，指出該算法相應(yīng)的 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)是正確的此算法中，對(duì)于給定的 p 有中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系SA12011911王國(guó)威u(x, r) = (, ) v(, ) = ( )( 1) = (, ) = log,

12、( )Ex7整體代碼過(guò)多，下面只貼出寫(xiě)出的 Sherwood 算法，只是對(duì)算法 B 的尋找最大整數(shù)部分進(jìn)行隨機(jī)化，可得到代碼如下： public int C(int x) int i = head; int max = vali;/隨機(jī)化部分，用隨機(jī)的步距進(jìn)行隨機(jī)化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對(duì)算法B的改動(dòng)部分主要是將原來(lái)算法中尋找最大值的步距增大為step，由于step隨機(jī)生成，故有一定的隨機(jī)性，也減少了迭代步數(shù)本實(shí)驗(yàn)中，由于CPU中高速緩存對(duì)順序存取和隨機(jī)存取速度的影響，選定輸入規(guī)模為1000000的數(shù)組進(jìn)行尋找，對(duì)不同的類型的序列，不同算法的運(yùn)行時(shí)間如下表所示。下圖為x=1時(shí)不同算法在不同類型序列的時(shí)間開(kāi)銷，其余輸入因篇幅中。不在贅述，數(shù)據(jù)寫(xiě)入表中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系SA12011911王國(guó)威由上表中信息計(jì)算平均時(shí)間和最壞時(shí)間可得下表可見(jiàn)，對(duì)于不同序列，算法 B 的平均時(shí)間明顯優(yōu)于其他算法的時(shí)間，算法 C 在算法 B 的方法上進(jìn)行改

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

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

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中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系SA12011911王國(guó)威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);中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系SA12011911王國(guó)威return (nb0);部分截圖如下將所有數(shù)據(jù)列在下表中運(yùn)行時(shí)間（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中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系SA12011911王國(guó)威可以看出，最優(yōu) stepVegas 在下表中從上述兩表可以看出，最優(yōu) stepVegas 一般為小于 n/2，在算法中 rand 函數(shù)占用的時(shí)間過(guò)多，可能不是很準(zhǔn)確Ex10代碼過(guò)長(zhǎng)，直接貼在后面。10000 以內(nèi)的素?cái)?shù)確定性算法和 Miller-Rabin 算法都得到了 1229 個(gè)素?cái)?shù)的結(jié)果，且經(jīng)驗(yàn)證，結(jié)果都正確。故Miller-Rabin 算法在此范圍內(nèi)無(wú)誤代碼如下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中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系SA12011911王國(guó)威n = n + 2;System.out.pr