最新公告
  • 欢迎您光临极客文库,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 今天和大家分享的是身边同学在今日头条二面期间遇到的一道很有意思的面试题,面试题目大概如下:

    5个人去一个海岛寻宝,最后一共找到了100枚金币。他们约定了一个分配方案,如下:五个海盗按照抽签的顺序依次提出方案,某一个人提出方案之后,剩余存活的人投票表决:方案需要获得超过半数人的认可之后才能被通过,否则方案提出者将会被扔进大海喂鲨鱼,某一个方案被通过后游戏就结束。注:每个人的投票都是在追求自己利益的最大化:保证自己不会被喂鲨鱼的前提下,尽量使自己分到更多的金币。

    题目的意思应该很清楚了,五个人依次按照抽签顺序给出自己的分配方案,如果某个方案没有获得通过,那么该方案的提出者就会被扔进大海喂鲨鱼;如果方案通过了,游戏就结束了。问题是:你认为第几个提出方案的存活概率最大,以及ta要如何提出方案才能最大概率存活,并且尽量是自己获得多的金币呢?存活的那个人最多可以获得多少金币?

    在往下看之前,不防先停下来想一想:如果你遇到了这道题,你的会怎样思考呢?


    提出方案的人要想存活下去就必须让自己的方案被大多数人接受,也就是ta必须要争取某些票或者放弃一些票。那么方案提出者如何做出决策呢?ta应该争取哪些人的票?或是又该放弃哪些人的票呢?到这里可以停下来想一想哦。

    方案提出者要想争取到某个人的票就必须知道在ta的方案提出之前那个人能分到的最大金币数量,在不损害那个人利益的前提下才能争取到某个人的投票。也就是方案提出者要尽量去获取其他人在自己提出方案之前可能获得的金币数量,然后尽可能去争取一些人的投票、以及放弃一些人的票。那么如何得知其他人的最大的利益呢?

    如果方案提出者不能获取到这个信息的话,这题基本无解了。因为方案提出者不能确定ta提出的方案能被哪些人接受,也就是生死存活全靠掷骰子了…..

    如果从前往后推测其他人可能的最大利益,会陷入死循环:第一个人做决定前得知道第2,3,4,5个人的决定,从前往后是无法推出任何答案的,所以可以考虑尝试从后往前推测其余人可能的最大利益。在得知其余人的最大利益之后,就能得知自己的方案能够得到哪些人的支持,问题也就迎刃而解了。到这里可以先停下来,尝试从后往前给出你的推测和答案哦~



    01

    从后往前逆向给出解题过程

    从后往前推,假设1~3号提出方案后都没被接收,也就是1,2,3都喂了鲨鱼,只剩下4号和5号。这时4号知道5号一定会投反对票,让4号喂鲨鱼(这时5号只能获得自己的一票,没有超过人数的一半),然后5号独吞金币。所以4号要想活命,必须不能让3号喂鲨鱼,也就是4号必定会支持3号。

    3号也能明白4号一定会支持自己,所以当剩下3,4,5三个人的时候,三号提出的方案会是:100,0,0。即3号独吞掉100个金币,但3号依旧可以获得自己和4号的的票,获得了超过一半的票数。

    2号推测得知3号的方案之后,会尝试为自己争取更多的票数,在2,3,4,5存活的时候,2号提出分配方案:98,0,1,1。这种分配方案下,4号,5号分到的金币比之前的0枚金币要多,所以4号和5号一定会支持2号,在加上2号自己的票,2号的这种分配方案可以得到3票的支持,超过存活人数一半的票数。



    1号的知2号的分配方案之后,必然不会让自己喂鲨鱼啊。1号会尝试去争取超过一半的票数,即1号在保证自己不会被喂鲨鱼的前提下尽量让自己得到更多的金币。1号可以有以下两种方案:97,0,1,2,0或97,0,1,0,2。1号的这种方案可以获得3票(超过一半的票数):自己、三号和四号或者5号的支持。

    到这里问题就彻底明朗了,看到问题的第一眼可能会感觉无从下手,或者随便蒙一个答案,亦或是以为第一个提出方案的人最容易被喂鲨鱼。细细分析后得知:第一个提出方案的人才是最后的赢家。
    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 一道很有意思的今日头条面试题

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    极客文库
    程序员的加油站

    Leave a Reply

    Hi, 如果你对这款模板有疑问,可以跟我联系哦!

    联系发布者

    Leave a Reply

    Hi, 如果你对这款模板有疑问,可以跟我联系哦!

    联系发布者
    • 99会员总数(位)
    • 3629资源总数(个)
    • 44本周发布(个)
    • 0 今日发布(个)
    • 105稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多