称球问题

Question 1.5: 12 identical marbles with one of different weight. Use a scale to identify it and determine whether is heavy or light.

& Question 1.18. 这个问题的推广版本有:

  • N 个小球中有一个和其他质量不同,用天平最少几次称出并确定偏重偏轻
  • 用天平 m 次最多可以从多少个球中称出唯一的一个次品,并确定偏重偏轻

这个问题知乎上有好多个精彩的解答,比如详细的编码方法,逗比的信息论方法,还有一个从压缩感知的思路去理解该问题的。准确的答案是:

  • 如需知道次品轻重,m 次最多可以称
  • 无需知道轻重,m 次可以称

知乎上使用的是正逆序编码,1 代表天平平衡,0 代表左重右轻,2 代表左轻右重。

另一种编码方法更为直观,0 代表天平平衡,1 代表左重右轻,2 代表左轻右重。这个方法是我从网上搜到的一个名为《用三进制解决小球称量问题》的文章中使用的。文章通俗易懂,并且有着很详细的称法和证明。可惜一直没找到原作者。

由于原文中各种指数的混乱(可能是因为直接复制到word),我编辑了一个网页的版本

文章归档

阅读更多

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注