版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、海盗分宝石问题,5个海盗抢到了100颗宝石,每一颗都一样的大小和价值连城。 他们决定这么分: 1.抽签决定自己的号码(1,2,3,4,5) 2.首先,由1号提出分配方案,然后大家5人进行表决,当且仅当超过半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。 3.如果1号死后,再由2号提出分配方案,然后大家4人进行表决,当且仅当超过半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。 4.以此类推 条件: 每个海盗都是很聪明的人,都能很理智的判断得失,从而做出选择。 问题: 最后的分配结果如何? 海盗的判断原则: 1.保命 2.尽量多得宝石 3.尽量多杀人,海盗分宝石,这个问
2、题之所以成为经典博弈问题,能够成为微软的应聘测试题,也与其求解的巧妙思路有关。 分析这个问题时,需要用到递归的思想,即将复杂的问题转化为同一问题的小规模模型。 这是很常用的解决问题思路,同时,也是写程序,写算法时所不可或缺的思想。,海盗分宝石,从后面往前推,将问题规模缩小、简化。,如果1-3号海盗都已然由于自己的决策失误没有得到半数以上人的投票,喂了鲨鱼。于是,现在就剩下4号、5号两个海盗。,5号海盗必然不会同意4号海盗的任何提议,这样4号的任何提议都不会得到半数以上的通过率。只要4号死了,5号就可以独得所有金币。,由于所有的海盗都绝顶聪明,4号海盗必然不会让事态发展到如此地步,所以他至少要保
3、证3号的存活。,海盗分宝石,所以,将问题向回推,若1、2号海盗死掉,只剩下3号提议时,他完全可以提出(100,0,0)的方案,由于4号必须保证3号的存活,所以即使他不能得到一枚金币也会同意3号的提议。,这样3号的提议因得到两人的同意而通过。,将问题继续向回推,当只有1号死掉而2-5号海盗还在,由2号提议时,他只要保证4号5号有一个金币的收益,即(98,0,1,1)的方案,这样就可以使4号5号获得的收益比2号死掉而由3号提议时获得的多,因此,4号5号会同意2号的如此提议。,海盗分宝石,于是,我们已经接近最初的问题了,即1号提议时的情况。一号通过聪明的海盗头脑分析出,当自己死掉时,2号的策略将会是怎样。,因此一号的提议只要让两个人的收益大于2号的提议时的收益,即可得到通过。而当1号死后2号的提议为(98,0,1,1)。,因此,1号可以选择让3号和4号,或者3号和5号拥有更多的收益,而不顾及另外两个人的想法。,于是他可以提出(97,0,1,2,0)或者(97,0,1,0,2)这样,他的方案便会得到自己以及另外两人的同意而得到通过。,海盗分宝石,在解决这个问题的过程当中,我们采用了递归的手段,找到一个复杂的问题最本源的性质,并且在这个本源的基础上层层“加壳”,逐步分析,最终解决问题。 这便是递归的主要思想,将一个复
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025-2026学年安徽合肥七中高二上第一次月考数学试卷含答案
- 2026-2027学年上学期单元测试九年级数学真题卷及答案解析
- 2025韩语TOPIK初级听力历年真题及答案
- 2025焊工操作证焊接基础每日一练及答案
- 2025安全生产负责人安全生产法律法规易错题及答案
- 2025保安员安全防范章节练习题及答案
- 港口油品储罐建设方案
- 确认某客户订阅服务到期续费的通知函(7篇范文)
- 绿色建材选购与施工指导手册
- 工业生产线操作与质量控制岗位绩效考核表
- 2026浙江宁波市宁海县国有企业招聘考试参考题库及答案解析
- 2026年中国抗体药物市场现状调研分析及前景预测报告
- 2026消防宣传月培训课件(含火灾案例)
- 箱涵工程施工及验收标准
- GB 48147.1-2026矿山隐蔽致灾因素普查规范第1部分:总则
- Unity3D游戏开发PPT完整全套教学课件
- 主持人妆 主持人妆基础
- 2023年台州市黄岩区不动产登记中心事业单位工作人员招聘笔试题库及答案
- GB/T 10708.1-2000往复运动橡胶密封圈结构尺寸系列第1部分:单向密封橡胶密封圈
- 2022年吉林省吉林祥云信息技术有限公司招聘笔试试题及答案解析
- 影视短片创作三课件
评论
0/150
提交评论