海盗分宝石.ppt

海盗分宝石问题5个海盗抢到了100颗宝石,每一颗都一样的大小和价值连城。他们决定这么分:(1,2,3,4,5),由1号提出分配方案,然后大家5人进行表决,当且仅当超过半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。,再由2号提出分配方案,然后大家4人进行表决,当且仅当超过半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。:每个海盗都是很聪明的人,都能很理智的判断得失,从而做出选择。问题:最后的分配结果如何?海盗的判断原则:,能够成为微软的应聘测试题,也与其求解的巧妙思路有关。分析这个问题时,需要用到递归的思想,即将复杂的问题转化为同一问题的小规模模型。这是很常用的解决问题思路,同时,也是写程序,写算法时所不可或缺的思想。柔送沏椭幂裹奈挑吗枪适淡货懒晚碾患垫曲佯钡这恋工拧俞光瓢耪愤黄堰海盗分宝石海盗分宝石海盗分宝石从后面往前推,将问题规模缩小、简化。如果1-3号海盗都已然由于自己的决策失误没有得到半数以上人的投票,喂了鲨鱼。于是,现在就剩下4号、5号两个海盗。5号海盗必然不会同意4号海盗的任何提议,这样4号的任何提议都不会得到半数以上的通过率。只要4号死了,5号就可以独得所有金币。由于所有的海盗都绝顶聪明,4号海盗必然不会让事态发展到如此地步,所以他至少要保证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)。因