算法设计与分析 课件 9.4-概率算法 - 蒙特卡罗算法_第1页
算法设计与分析 课件 9.4-概率算法 - 蒙特卡罗算法_第2页
算法设计与分析 课件 9.4-概率算法 - 蒙特卡罗算法_第3页
算法设计与分析 课件 9.4-概率算法 - 蒙特卡罗算法_第4页
算法设计与分析 课件 9.4-概率算法 - 蒙特卡罗算法_第5页
已阅读5页，还剩5页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析概率算法-蒙特卡罗信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版思政：国防--催生新技术的源动力“曼哈顿计划”摩纳哥

蒙特卡罗冯·诺伊曼目标：

求问题的准确解特征：求得的解不一定正确，且无法判定所得解是否肯定正确。设p是0.5到1间的实数。若算法得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且p-1/2是该算法的优势。求得正确解的概率依赖于算法所用时间，时间越多，得到正确解的概率越高此外，若对于同一问题，蒙特卡罗算法不会给出不同的正确解答，则称该蒙特卡罗算法是一致的。应用：数值问题求解

求近似解

近似解精度随计算时间的增加而不断提高。例1：计算

值随机投点法半径为r的圆的外切四边形内投点

defdarts(n):k=0foriinrange(1,n+1):x=random()#在[0，1)内随机选择一个数作为xy=random()#在[0，1)内随机选择一个数作为yifx**2+y**2<=1:k+=1return4*k/n例1：计算

值测试判断题：针对计算Pi值的蒙特卡罗算法实现代码，当n=1000时，独立运行两次程序，会得到一样的结果。A：正确 B：错误例2：计算定积分

设f(x)是[0,1]上的连续函数，且0f(x)1。需要计算的积分为。

假设向单位正方形内随机地投入n个点(xi,yi)。如果有m个点落入积分区域内，则defdarts(n):k=0foriinrange(1,n+1):x=random()#在[0，1)内随机选择一个数作为xy=random()#在[0，1)内随机选择一个数作为yify<=f(x):k+=1returnk/n例2：计算定积分例3：主元素问题

设数组T[1:n]含有n个元素。当|{i|T[i]=x}|>n/2时，称元素x是数组T的主元素。defmajority(t):n=len(t)-1i=randint(1,n)x=t[i]#随机选择数组元素k=0forjinrange(1,n+1):ift[j]==x:k+=1returnk>n/2#k>n/2时t含有主元素返回true时，一定含有主元素，但返回false时，数组未必不含主元素重复调用主元素蒙特卡罗算法boolmajority2(int[]t,intn){if(majority(t,n))returntrue;elsereturnmajority(t,n);}

设p是算法返回true的概率，则算法可将错误率降低到(1-p)2<(1/2)2=1/4。

对于任何的

>0，重复调用算法

log(1/

)

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论