海盗分宝石面试题的头脑风暴

逆推的思考
服务器君一共花费了175.010 ms进行了4次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

有个面试题,是这样的:

五个海盗得到100颗钻石,颗颗价值连城。这五个海盗非常聪明,都想自己得到钻石最多。因而他们设计了个规则,根据抽签后的顺序, 每个人提出个分配方案,如果有半数以上(不包括半数)的人表决通过,则按这个方案执行,否则提出方案的人要被扔到海里喂鱼。下一个人开始提方案,以此类推。

问:如果你是抽到第一个提方案的人,你该提出什么样的钻石分配方案保住你的小命,并且自己获得钻石尽可能得多?

这类博弈论的问题不能采用一般的常识去做,比如均分的方案根本不可行,大家如果把你否决,剩余的人可以均分得更多呢。这里可以使用逆推的方案。

假设按抽签的顺序, 要提方案的人依次为1, 2, 3, 4, 5。

如果只剩下4和5, 除非把宝石全给5, 否则5肯定不会同意, 这样4的提议就不能通过, 就面临喂鱼的结果。因此4绝对不允许自己来分配宝石。

接着,如果有3,4和5,5必然不会同意,因为主要把3干掉,剩下的宝石其实就是他的了。这里主要争取4的支持,如果能给他一颗,也不错了,所以当3提议的时候,最好的分配方案是——3: 99, 4: 1, 5: 0.

依次类推,如果有2, 3, 4, 5呢?3肯定不会同意了,所以要争取剩下的两个人。可以给4两颗, 给5一颗, 这样对它们来说已经比3的方案多了,还是会投赞成票的。分配方案: 2: 97, 3: 0, 4: 2, 5: 1。

最后到1了,2是不会投赞成票的,所以主要是取得3,4,5其中的两个人的支持就可以了。这时候可以给3一颗,给5两颗,这样对他们两个来说,已经比2的方案好了,他们肯定投赞成票。

因而对一来说,最好的分配方案是—— 1: 97, 2: 0, 3: 1, 4: 0, 5:2。

本文地址:http://www.nowamagic.net/librarys/veda/detail/1833,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1833

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《编程之美:微软技术面试心得》 《编程之美》小组 (作者)

《编程之美:微软技术面试心得》是一本让人着迷的书!阅读起来。有些题目的内容会引起强烈的共鸣,尤其是那些自己非常熟悉并且又深知解答的题目;也有一些题目让我异常惊诧,原来除了我所知道的解答思路之外,还有更好的解答以及更深层次的原因。还有一些题目是从来没想到过的。阅读过程是一次愉快的享受,也是脑细胞持续活跃的过程。

更多计算机宝库...