算法設(shè)計(jì)與分析---概率算法試驗(yàn)報(bào)告

1、算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)六概率算法報(bào)告書(shū)姓名指導(dǎo)教師學(xué)號(hào)日 期班級(jí)實(shí)驗(yàn)內(nèi)容使用隨機(jī)方法求解圓周率。使用舍伍德算法求n個(gè)數(shù)中的第k大的數(shù)。試用拉斯維加斯方法求解 8皇后問(wèn)題，能得到正確解嗎？蒙特卡羅算法有何特點(diǎn)？請(qǐng)舉例說(shuō)明。實(shí)驗(yàn)?zāi)康?)熟悉和掌握隨機(jī)化方法2)熟悉和掌握舍伍德算法、拉斯維加斯算法、蒙特卡羅算法以及它們的特點(diǎn)。實(shí)驗(yàn)過(guò)程和步驟1使用隨機(jī)方法求解圓周率解題思路假設(shè)正方形半徑 2r ,圓半徑為r ,故圓的面積為兀*r*r ,正方形面積為 r*r*4。則通過(guò)蒙特卡洛算法，狂跑隨機(jī)數(shù)，在正方形面積內(nèi)拋骰子，若落在圓面積則計(jì)數(shù)。最后通過(guò)落院內(nèi)的計(jì)數(shù)與總數(shù)比值，可以近似為圓面積與正方形面積的比

2、值，之后再乘4,可得兀。程序運(yùn)行情況程序源碼（含注釋?zhuān)?include using namespace std;int n,r;double ans;void init()/printf(input the num of the times, you want to rand(turned out to be the accuracy):n); /scanf(%d,&n);n=100000000;printf(input the range of the circle:n);scanf(%d,&r);printf(n);bool inCircle(int x,int y)if(x*x+y*y=

3、r*r)return true;return false;/statistic = pi*r*r/(4*r*r)void getAns() (int sum=0;for(int i=0;in;i+) (int x=rand()%(r+1);int y=rand()%(r+1); if(inCircle(x,y)sum+;ans=(double)sum/n*4; / 概率void output() (printf(the ans of the pi is %lfn,ans); int main()(srand(unsigned)time(NULL);init();while(1)瘋狂計(jì)算 (ge

4、tAns();output();return 0;2舍伍德算法求第k大的數(shù)解題思路其實(shí)就是普通的快速排序。排序中，講基準(zhǔn)數(shù)從第一個(gè)，改為跑隨機(jī)數(shù)跑出來(lái)的骰子 即可。要處理的三個(gè)地方：.快速排序要會(huì)寫(xiě).當(dāng)前位置大于k則僅對(duì)前部分排序，當(dāng)前位置大于k則僅對(duì)后部分排序，等于k則 返回結(jié)果。.要考慮遞歸時(shí)l=r時(shí)候，要加入判斷機(jī)制。測(cè)試樣例532 3 4 5the ans is 3536 1 3 5the ans is 2程序運(yùn)行情況程序源碼(含注釋)#includeusing namespace std;#define inf 999int n,k;int ans;/答案下標(biāo)int einf;voi

5、d init()(printf(input the n:);scanf(%d,&n);printf(input the k:);scanf(%d,&k);printf(input the array:);for(int i=0;in;i+)scanf(%d,&ei);printf(n);k-;因?yàn)橄聵?biāo)自。始void SWD(int l,int r)/ 舍伍德版二分(if(l=r)/終止條件，舍伍德的時(shí)候還特殊考慮一下(if(l=k)ans=l;return;int t=rand()%(r-l); 產(chǎn)生隨機(jī)數(shù)int pos=l+t;/舍伍德目標(biāo)位置int i=l;int j=r;while(i=

6、j)(while(i=epos)j-;while(i=j&ei=epos)i+;if(i=j)swap(ei,ej);swap(ei,epos);if(i=k)ans=i;else if(ik)SWD(i+1,r);else SWD(l,i-1);void output()(printf(the k th biggest num in the array is %dn,eans);int main()(srand(unsigned)time(NULL);init();SWD(0,n-1);output();return 0;3拉斯維加斯方法求解皇后問(wèn)題解題思路網(wǎng)上的拉斯維加斯算法求 8皇后是結(jié)

7、合了隨機(jī)算法與回溯的特點(diǎn)。我覺(jué)得有了回溯那 還隨機(jī)個(gè)球啊。所以我認(rèn)為的拉斯維加斯算法是，隨機(jī)一個(gè)8皇后的排布方案，然后進(jìn)行檢測(cè)，查看此方案是否是允許的八皇后棋盤(pán)，若不是則重新隨機(jī)，否則輸出結(jié)果。程序運(yùn)行情況程序源碼(含注釋)#includeusing namespace std;int n,r;int queen8;double ans;void init()(printf(beginning the random queens:n);printf(n);bool isLegal()判斷八皇后是否成立(int i,j;for(i=0;i8;i+)/ 行for(j=i+1;j8;j+)(int

8、x1=i;int y1=queeni;int x2=j;int y2=queenj;if(x1=x2|y1=y211abs(y2-y1)=abs(x2-x1)return false;return true;void LSWJS()/隨機(jī)放皇后(while(1)(for(int i=0;i8;i+)queeni=rand()%8;if(isLegal()break;void output()/ 輸出(printf(get an ans!n);for(int i=0;i8;i+)printf(%d ,queeni);printf(nn);for(int i=0;i8;i+)(for(int j=

9、0;j8;j+)if(queeni=j)printf(1 );else printf(0 );printf(n);printf(nDone!n);int main()srand(unsigned)time(NULL);init();LSWJS();output();return 0;4蒙特卡羅算法有何特點(diǎn)蒙特卡羅方法，也稱(chēng)統(tǒng)計(jì)模擬方法，是二十世紀(jì)四十年代中期由于科學(xué)技術(shù)的發(fā)展和電子計(jì)算機(jī)的發(fā)明，而被提出的一種以概率統(tǒng)計(jì)理論為指導(dǎo)的一類(lèi)非常重要的數(shù)值計(jì)算方法。是指使用隨機(jī)數(shù)(或更常見(jiàn)的偽隨機(jī)數(shù))來(lái)解決很多計(jì)算問(wèn)題 的方法。與它對(duì)應(yīng)的是確定性算法。 TOC o 1-5 h z 蒙特卡羅算法的特點(diǎn)一一 采樣越多，越近似最優(yōu)解。以及與采樣數(shù)目有一定關(guān)系，以及是隨機(jī)算法，故并不一定是最優(yōu)解，但一定是可行解。拉斯維加斯算法的特點(diǎn)一一采樣越多，越有機(jī)會(huì)找到最優(yōu)解。舉例說(shuō)明：就比如第一題求圓周率。雖然說(shuō)系統(tǒng)的隨機(jī)數(shù)是偽隨機(jī)數(shù)，但是我們也可以發(fā)現(xiàn)，使用蒙特卡洛算法出現(xiàn)了幾個(gè)情況：1)半徑不能亂選，因?yàn)檫x擇的半徑是整數(shù)，隨機(jī)數(shù)的選取也是整數(shù)，