老师出的题目。会的来。
来源:百度知道 编辑:UC知道 时间:2024/06/07 20:38:47
第三个分的,应该是只要后面两个反对。也要被推下河
微软的面试题目吧?
用逆推假设法解决5个海盗分100个宝石的难题。无论怎么分,都无外呼以下5种条件。我们分别假设一下就可以逆推出1号海盗的分配方案。
第一,剩下1个海盗的时候,假设其他海盗全部死掉,只剩5号的时候,毫无疑问100个宝石就归他了
第二,剩下2个海盗的时候,这时候4号海盗无论怎么分,5号也不会同意,除非自己一个不拿,但即使这样,如果5号希望他死,也仍然不会同意。因此这时候2号无论怎么分都面临喂鲨鱼的境地。
第三,剩下3个海盗的时候,这时候3号海盗只要得到4,5号海盗中一个人的支持就可以,显然5号这时候是无法买通的,因为在这种剩下3个的情况下,5号希望他们都死,自己能够独吞,而4号只要得到1个宝石就可以同意,因为4号如果不同意,4号自己在剩下2个人的时候,就什么也得不到,因此这时3号的方案就是,自己99个,4号1个,5号0个。
第四,剩下4个海盗的时候,2号需要赢得其他3个人中2个人的支持就可以了,显然3号再这种情况下是无法买通的,因为这时候最希望2号死的就是3号,如果2号死了,3号就可以按照自己的方案得到99个宝石,因此2号只能争取4号和5号的支持,因为在上面3号的分配方案中,5号什么也得不到,因此只要给5号1个宝石就可以了,为了保证4号可以支持自己,需要多给4号1个宝石,也就是给4号2个宝石,因为如果给4号1个宝石,那么2号的死活对4号就无所谓,反正3号的分配方案也可以给4号1个宝石。因此,2号的分配方案就是自己97个,3号0个,4号2个,5号1个。
第五,5个海盗全在,这也是这道题的答案了。这时候1号海盗需要得到其余4人中2个人的支持,首先2号是无法买通的,因为1号死了,2号就可以按照自己的方案得到97个宝石,2号现在最希望1号死,所以这时候要放弃2号,不给2号。3号只用1个宝石就可以收买,因为在2号的分配方案中3号什么也得不到,4号和5号理论上是都可以收买的,但为了自己利益最大化,只要收买一个就可以了,那么收买谁的成本更低呢?4号在2号的分配方案中已经可以得到2个宝石了,让他必然同意这个方案,则需要再多给4号一个宝石,也就是给4号3个宝石才行,而5号在2号的分配方案中只能得到1个宝石,目前只要给他2个宝石,他就会