微软经典面试题--海盗分宝石

[柳柳]

９７　０　１　０　２

回溯分析：

当１号２号３号都死了，只留下４号５号时．４号达到最大利益，可以独占100颗，５号反对也没用．ＴＨＵＳ，５号希望３号能活着 .

当１号２号都死了，留下３号４号５号时．３号达到最大利益，可以独占９９颗，只要给５号一颗，就有了２：１投票数．而４号就两手空空,ＴＨＵＳ，4号希望2号能活着 .

如果只有１号死了，２号分配，那么２号利益最大．２号知道３号基于自己的最大利益不可能给自己投票，则只能拉拢４号或者5号．可以给４号一颗或者５号一颗，自己独占9９．此时，３号两手空空，ＴＨＵＳ，３号希望１号能活着 .

这样，１号来分配，只要拉拢３号和５号就可以了．给３号一颗，给５号两颗．因为按前面的分析，５号不管怎么样最多只能拿一颗，此时１号给他两颗他当然会举双手双脚赞同．

因此，我的答案是：９７　０　１　０　２


这题让我想起二叉树，呵呵～

 

[ODOD]

postulate 只剩下 4,5
4决定分配
4-100 5-0
4分配的心态
(半数算通过 结果一定会通过 所以4拿全部)
4同意 5不同意
1:1(当且仅当半数和超过 半数的人同意时，按照他的提案进行分配)
分配通过

postulate 3,4,5
3决定分配
3-99 4-0 5-1
3分配的心态
(4一定不会同意3的方案 因为下一次分配4将得到100 所以不给4 给5一颗 5一定知道如果否决3 下次5什么都得不到)
3同意 4不同意 5同意
2:1(当且仅当半数和超过 半数的人同意时，按照他的提案进行分配)
分配通过

postulate 2,3,4,5
2决定分配
2-99 3-0 4-0 5-1
2分配的心态
(3一定不会同意2的方案 因为下次分配3将得到98 所以不给3 4会考虑否决掉2和3 4就可以拿掉全部100颗 4也会考虑到如果否决2 下次4什么都拿不到 因此4很矛盾 但4还是会否决2 所以什么都不用给他 给5一颗 5下次也有机会拿到1颗 如果5和2没有仇 5会选同意)
2同意 3不同意 4不同意 5同意
2:2(当且仅当半数和超过 半数的人同意时，按照他的提案进行分配)
分配通过

以次类推就可以啦

 

[ODOD]

98 0 0 1 1 或者 98 0 1 0 1

 

[镇加东]

98 0 0 1 1 是有问题的,至少不能保证自己不死
这种分法是要拉4,5的票,但是不见得行
如果我是4,我一样可以否掉1,
然后2上台,2需要拉一个,显然不会拉3
那么只能找4或5
如果找5,必需要给5两颗,而找4,只要一颗就够了
所以对4来说,无论否决还是支持1,自己都是一颗
那么,如果我要想看活人喂鲨鱼的话...

 

[镇加东]

最初由 柳柳 发布
９７　０　１　０　２

回溯分析：

当１号２号３号都死了，只留下４号５号时．４号达到最大利益，可以独占100颗，５号反对也没用．ＴＨＵＳ，５号希望３号能活着 .

当１号２号都死了，留下３号４号５号时．３号达到最大利益，可以独占９９颗，只要给５号一颗，就有了２：１投票数．而４号就两手空空,ＴＨＵＳ，4号希望2号能活着 .

如果只有１号死了，２号分配，那么２号利益最大．２号知道３号基于自己的最大利益不可能给自己投票，则只能拉拢４号或者5号．可以给４号一颗或者５号一颗，自己独占9９．此时，３号两手空空，ＴＨＵＳ，３号希望１号能活着 .

这样，１号来分配，只要拉拢３号和５号就可以了．给３号一颗，给５号两颗．因为按前面的分析，５号不管怎么样最多只能拿一颗，此时１号给他两颗他当然会举双手双脚赞同．

因此，我的答案是：９７　０　１　０　２


这题让我想起二叉树，呵呵～

2是不会给5的,要给就是两颗,因为3会给5至少一颗

所以1给5一颗足够

还是我的98 0 1 0 1 分法好

 

[柳柳]

最初由 T.I.C. 发布


2是不会给5的,要给就是两颗,因为3会给5至少一颗

所以1给5一颗足够

还是我的98 0 1 0 1 分法好

２号为什么不可能给5号？
还是97 0 1 0 2比较保险～

 

[镇加东]

最初由 柳柳 发布


２号为什么不可能给5号？
还是97 0 1 0 2比较保险～

2上台之后,如果只给5号一颗,
对5来说,支持或否决2的结果是一样的
5否了2, 让3上台
3也会给5一颗
所以2至少要给5两颗

但是对4来说,3上台他一颗都没有,
2只要给他一颗就足够了
2的最佳方案是99-0-1-0

 

[FloatingPoint]

20 20 20 20 20

 

[小吱]

最初由 任天翔 发布
微软经典面试题

Yada,Yada

haha,haha

 

[DickStrong]

最初由 大漠张三 发布



no

4 won't vote against any proposals. in fact 4 will vote for 2 if 2 give him one dimond

5 won't vote for anybody that gives him one dimond, in fact he will vote against 2 if 2 gives him one dimond

and you don't have to be a computer scientist to figure this out, you just need to pass grade 3

what do you mean 5 won't vote for anybody that gives him one diamond?

think about when 3,4,5 are left and 3 propose 99-0-1, what would be the vote? it has to be YNY.

which grade 3 did you pass?

 

[大漠张三]

最初由 DickStrong 发布

5 will get 0 if 1,2,3 all die, so he will vote for any proposal from 1,2,3 that gives him at least 1 diamonds.

That's the simplest, you geeks figure out the rest.

you said 5 will vote for anyone who gives him 1 diamond


i was just saying you are wrong, 5 won't vote for anyone who gives him a diamond

 

[DickStrong]

最初由 大漠张三 发布



you said 5 will vote for anyone who gives him 1 diamond


i was just saying you are wrong, 5 won't vote for anyone who gives him a diamond

you don't have to emphasize what i said, i know it.

you only need to provide explanation (which is lacking) why you think i am wrong