`
moxiaomomo
  • 浏览: 44165 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

关于三个囚犯分汤,是否有更多妙计

 
阅读更多
题目:
一间囚房里关押着两个犯人。每天监狱都会为这间囚房提供一罐汤,让这两个犯人自己来分。起初,这两个人经常会发生争执,因为他们总是有人认为对方的汤比自己的多。后来他们找到了一个两全其美的办法:一个人分汤,让另一个人先选。于是争端就这么解决了。
可是,现在这间囚房里又加进来一个新犯人,现在是三个人来分汤。必须寻找一个新的方法来维持他们之间的和平,该怎么办呢?

当初接触到这道题的时候,思维开始有点乱。但是后来慢慢想清楚了。
其实这种问题可以扩展到大规模的问题,加入有四个囚犯呢?五个呢?
如果是这样的话,就可以想到一种很经典的解法,那就是相似递归。

我们可以想到,最后分汤的情景只剩下两个人,那样的话就回到了题目最开始说的两个人分汤的公平解决方法了。

不过规则可以稍微改一下,
就是选一个人将汤分成n碗(n为还没喝汤的囚犯),剩下的人挑出一碗汤给当前分汤的人喝;
剩下的犯人再把汤混起来,按上一步的规则再次分汤;
如此重复直到最后剩一个人为止。

貌似这种效率不高,不知有无更妙的方法?有更好的办法时再继续更新。
0
2
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics