确实有点老了
找个一个比较全的题目答案
据说这是微软公司的面试题。题目还可以作一些微小的变动，但是答案就完全不一样啦 。。注：半数以上是包括半数的。
情况一、（原题）有五个聪明强盗编号为1、2、3、4、5号，要分100颗珠宝，首先由1号 提出分配方案，如有半数以上的人通过，就按他的方案分配，反之则出局不参加分配， 依此类推到最后。问：1号要怎样提出一个方案，能确保得到半数以上的人通过，且分到 最大量的珠宝？
答案是98－0－1－0－1，
情况二：将"半数以上"改为"超过半数"，其余不变
简解：只剩下4、5的时候，无论4提什么方案，5都会反对，4一无所有。3必须找一个支 持者，当然是4了，所以3的方案是99－1－0（跟上题的99－0－1不同吧？），倒推知， 2会贿赂4和5，方案应该是97－0－2－1；再倒推到1，易知，1会贿赂3和5，方案应是97 －0－1－0－2。
情况三：将"出局"改为"处死"，其余不变。
简解：只剩下4、5的时候，无论4提什么方案，5都会反对，4将会被杀死。显然，自己的 小命是比珠宝珍贵的，所以3提的任何建议，4都会赞成。所以3的建议可以是100－0－0 。倒推到2，他只需贿赂一个人就行了。他的方案可以是99－0－1－0或者99－0�D0－1； 1需要贿赂两个人，可能有人会说："根据2的方案，对应的1的方案会是98－0－1－0－1
或者98－0－1－1－0。" 可能也有人会说："1在提建议的时候，会想到如果自己被kill 掉了，2提的建议有可能使4得好处，也有可能使5得好处呀，1为稳妥起见，打算在保证 拉拢了3的同时，也把4和5都一起贿赂吧？"对于第一种说法，我不否定，但是应该指出 考虑得不全，而第二种说法就是彻底错误的啦！因为这样做的话1分得的珠宝数目不是最
大的了。我们要考虑到这几个海盗都是很聪明的，包括4和5。如果1被kill了，2可能提 出的两种方案能且只能使4、5两人中的一人受益，至于谁受益，还得取决于2提哪一种方 案。如果等到1被杀了，2的方案一定了，4、5中总有一个人是一文不名的。4和5必然会 考虑到这一点，早得当然早安心嘛，所以当1提的建议只要能使4、5中的一个人受益，那
个人必然会欣然赞成。我们解这道题时注意到这一点，结果就明朗了：1可以贿赂3、4， 也能贿赂3、5，也能贿赂4、5。最后答案是98－0－1－1－0或者98－0－1－0－1或者98 －0－0－1－1。
情况四：将"半数以上"改为"超过半数"，将"出局"改为"处死"，其余不变。
简解：同3题最初分析一样，强盗3提的方案是100－0－0，加进2时情况就有所不同了， 这时2需要贿赂两个人才能使通过率过半。所以2的方案是98－0－1－1。易知，1的方案 应是97－0－1－2－0或者97－0－1－0－2。
|
版主
论坛用户
论坛用户
论坛用户
论坛用户
论坛: 茶余饭后 标题: 极度郁闷中……