算法设计与分析---概率算法试验报告

1、算法设计与分析实验报告实验六概率算法报告书姓名指导教师学号日 期班级实验内容使用随机方法求解圆周率。使用舍伍德算法求n个数中的第k大的数。试用拉斯维加斯方法求解 8皇后问题，能得到正确解吗？蒙特卡罗算法有何特点？请举例说明。实验目的1)熟悉和掌握随机化方法2)熟悉和掌握舍伍德算法、拉斯维加斯算法、蒙特卡罗算法以及它们的特点。实验过程和步骤1使用随机方法求解圆周率解题思路假设正方形半径 2r ,圆半径为r ,故圆的面积为兀*r*r ,正方形面积为 r*r*4。则通过蒙特卡洛算法，狂跑随机数，在正方形面积内抛骰子，若落在圆面积则计数。最后通过落院内的计数与总数比值，可以近似为圆面积与正方形面积的比

2、值，之后再乘4,可得兀。程序运行情况程序源码（含注释）#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)疯狂计算 (ge

4、tAns();output();return 0;2舍伍德算法求第k大的数解题思路其实就是普通的快速排序。排序中，讲基准数从第一个，改为跑随机数跑出来的骰子 即可。要处理的三个地方：.快速排序要会写.当前位置大于k则仅对前部分排序，当前位置大于k则仅对后部分排序，等于k则 返回结果。.要考虑递归时l=r时候，要加入判断机制。测试样例532 3 4 5the ans is 3536 1 3 5the ans is 2程序运行情况程序源码(含注释)#includeusing namespace std;#define inf 999int n,k;int ans;/答案下标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-;因为下标自。始void SWD(int l,int r)/ 舍伍德版二分(if(l=r)/终止条件，舍伍德的时候还特殊考虑一下(if(l=k)ans=l;return;int t=rand()%(r-l); 产生随机数int pos=l+t;/舍伍德目标位置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拉斯维加斯方法求解皇后问题解题思路网上的拉斯维加斯算法求 8皇后是结

7、合了随机算法与回溯的特点。我觉得有了回溯那 还随机个球啊。所以我认为的拉斯维加斯算法是，随机一个8皇后的排布方案，然后进行检测，查看此方案是否是允许的八皇后棋盘，若不是则重新随机，否则输出结果。程序运行情况程序源码(含注释)#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()/随机放皇后(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蒙特卡罗算法有何特点蒙特卡罗方法，也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数(或更常见的伪随机数)来解决很多计算问题 的方法。与它对应的是确定性算法。 TOC o 1-5 h z 蒙特卡罗算法的特点一一 采样越多，越近似最优解。以及与采样数目有一定关系，以及是随机算法，故并不一定是最优解，但一定是可行解。拉斯维加斯算法的特点一一采样越多，越有机会找到最优解。举例说明：就比如第一题求圆周率。虽然说系统的随机数是伪随机数，但是我们也可以发现，使用蒙特卡洛算法出现了几个情况：1)半径不能乱选，因为选择的半径是整数，随机数的选取也是整数，