




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
算法设计与分析概率算法-蒙特卡罗信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025至2030泰国首席技术官蒸馏行业产业运行态势及投资规划深度研究报告
- 河北省石家庄市井陉矿区贾庄镇区贾庄中学2025届化学九年级第一学期期末学业质量监测试题含解析
- 车辆设备研发、采购、检测、认证一体化服务合同
- 学习计划制定与执行
- 氢能源与储能技术的融合发展研究
- 2025至2030二氧化碳数据记录器行业发展研究与产业战略规划分析评估报告
- 新兴工业设计领域:AI技术的行业可行性分析报告
- 教育中创新能力的培养
- 2025至2030塑料鼓行业发展趋势分析与未来投资战略咨询研究报告
- 2025至2030气体洗涤器行业项目调研及市场前景预测评估报告
- DGJ08-81-2015 现有建筑抗震鉴定与加固规程
- 房屋租赁合同范本15篇
- 2025至2030年中国飞行控制器行业市场供需态势及未来趋势研判报告
- 2025年汽车维修工职业资格考试试卷及答案
- 2025至2030年中国锦氨纶汗布市场分析及竞争策略研究报告
- 2025年中小学暑假安全教育主题家长会 课件
- 2025年佛山市南海区图书馆招聘题库带答案分析
- 基于学科核心素养的初中化学单元整体教学设计课题研究的阶段小结基于学科核心素养的初中化学单元整体教学设计研究
- GB/T 4169.19-2006塑料注射模零件第19部分:浇口套
- GB/T 31586.1-2015防护涂料体系对钢结构的防腐蚀保护涂层附着力/内聚力(破坏强度)的评定和验收准则第1部分:拉开法试验
- 领导干部的决策力与执行力
评论
0/150
提交评论