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

《算法设计与分析》实验报告实验六概率算法报告书姓名指导教师学号日期班级实验内容1）使用随机方法求解圆周率。2）使用舍伍德算法求n个数中的第k大的数。3）试用拉斯维加斯方法求解8皇后问题，能得到正确解吗？4）蒙特卡罗算法有何特点？请举例说明。实验目的1）熟悉和掌握随机化方法2）熟悉和掌握舍伍德算法、拉斯维加斯算法、蒙特卡罗算法以及它们的特点。实验过程和步骤1使用随机方法求解圆周率1.1解题思路假设正方形半径2r，圆半径为r，故圆的面积为π*r*r，正方形面积为r*r*4。则通过蒙特卡洛算法，狂跑随机数，在正方形面积内抛骰子，若落在圆面积则计数。最后通过落院内的计数与总数比值，可以近似为圆面积与正方形面积的比值，之后再乘4，可得π。1.2程序运行情况1.3程序源码（含注释）#includebits/stdc++.husingnamespacestd;intn,r;doubleans;voidinit(){//printf(inputthenumofthetimes,youwanttorand(turnedouttobetheaccuracy):\n);//scanf(%d,&n);n=100000000;printf(inputtherangeofthecircle:\n);scanf(%d,&r);printf(--------------------\n);}boolinCircle(intx,inty){if(x*x+y*y=r*r)returntrue;returnfalse;}//statistic=pi*r*r/(4*r*r)voidgetAns(){intsum=0;for(inti=0;in;i++){intx=rand()%(r+1);inty=rand()%(r+1);if(inCircle(x,y))sum++;}ans=(double)sum/n*4;//概率}voidoutput(){printf(theansofthepiis%lf\n,ans);}intmain(){srand((unsigned)time(NULL));init();while(1)//疯狂计算{getAns();output();}return0;}2舍伍德算法求第k大的数2.1解题思路其实就是普通的快速排序。排序中，讲基准数从第一个，改为跑随机数跑出来的骰子即可。要处理的三个地方：1.快速排序要会写2.当前位置大于k则仅对前部分排序，当前位置大于k则仅对后部分排序，等于k则返回结果。3.要考虑递归时l==r时候，要加入判断机制。2.2测试样例5312345theansis35326135theansis22.3程序运行情况2.4程序源码（含注释）#includebits/stdc++.husingnamespacestd;#defineinf999intn,k;intans;//答案下标inte[inf];voidinit(){printf(inputthen:);scanf(%d,&n);printf(inputthek:);scanf(%d,&k);printf(inputthearray:);for(inti=0;in;i++)scanf(%d,&e[i]);printf(-----------\n);k--;//因为下标自0始}voidSWD(intl,intr)//舍伍德版二分{if(l==r)//终止条件，舍伍德的时候还特殊考虑一下{if(l==k)ans=l;return;}intt=rand()%(r-l);//产生随机数intpos=l+t;//舍伍德目标位置inti=l;intj=r;while(i=j){while(i=j&&e[j]=e[pos])j--;while(i=j&&e[i]=e[pos])i++;if(i=j)swap(e[i],e[j]);}swap(e[i],e[pos]);if(i==k)ans=i;elseif(ik)SWD(i+1,r);elseSWD(l,i-1);}voidoutput(){printf(thekthbiggestnuminthearrayis%d\n,e[ans]);}intmain(){srand((unsigned)time(NULL));init();SWD(0,n-1);output();return0;}3拉斯维加斯方法求解8皇后问题3.1解题思路网上的拉斯维加斯算法求8皇后是结合了随机算法与回溯的特点。我觉得有了回溯那还随机个球啊。所以我认为的拉斯维加斯算法是，随机一个8皇后的排布方案，然后进行检测，查看此方案是否是允许的八皇后棋盘，若不是则重新随机，否则输出结果。3.2程序运行情况3.3程序源码（含注释）#includebits/stdc++.husingnamespacestd;intn,r;intqueen[8];doubleans;voidinit(){printf(beginningtherandomqueens:\n);printf(--------------------\n);}boolisLegal()//判断八皇后是否成立{inti,j;for(i=0;i8;i++)//行for(j=i+1;j8;j++){intx1=i;inty1=queen[i];intx2=j;inty2=queen[j];if(x1==x2||y1==y2||abs(y2-y1)==abs(x2-x1))returnfalse;}returntrue;}voidLSWJS()//随机放皇后{while(1){for(inti=0;i8;i++)queen[i]=rand()%8;if(isLegal())break;}}voidoutput()//输出{printf(getanans!\n);for(inti=0;i8;i++)printf(%d,queen[i]);printf(\n\n);for(inti=0;i8;i++){for(intj=0;j8;j++)if(queen[i]==j)printf(1);elseprintf(0);printf(\n);}printf(\nDone!\n);}intmain(){srand((unsigned)time(NULL));init();LSWJS();output();return0;}4蒙特卡罗算法有何特点蒙特·卡罗方法，也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。与它对应的是确定性算法。蒙特卡罗算法的特点——采样越多，越近似最优解。以及与采样数目有一定关系，以及是随机算法，故并不一定是最优解，但一定是可行解。拉斯维加斯算法的特点——采样越多，越有机会找到最优解。举例说明：就比如第一题求圆周率。虽然说系统的随机数是伪随机数，但是我们也可以发现，使用蒙特卡洛算法出现了几个情况：1）半径不能乱选，因为选择的半径是整数，随机数的选取也是整数，就会产生误差。我将半径设置为了RAND_MAX,程序的运算结果的精度一下就提高上来了。2）随机采样的次数不能少，要大。因为随机次数少的话，随机带来的干扰太大，有效性实在太低了。3）不管再怎么调整参数，随机性依然很大。我们可以看到每一次随机的结果都是不一样的，有差异。而这也是随机算法的特点所在。