从9枚硬币中找出假币

Question

只是在这里遇到了这个简单的算法，从相同的称重硬币列表中找到奇数硬币（重达重）。

我可以理解，如果我们一次拿3个硬币，那么最小称重次数只有两个。

我是怎么找到答案的？

我人工试了一下一次称4套硬币，一次称3套硬币，一次称两个硬币，一次称一个硬币。

当然，只有当我们一次拿3个硬币时，最少的步数(两步)才是可以达到的。

问题是，你怎么知道我们必须拿3个硬币？

我只是想知道如何解决这个难题，而不是做所有可能的组合，然后把答案说成2。

1 http://en.wikipedia.org/wiki/Balance_puzzle

Answer 1

基本情况是这样的：

你怎么知道我们应该一次拿三枚硬币？

方法:

1. 首先找到基本案例

在这里，基本情况是找到最大数量的硬币，您可以从中一次称重找到假币。你可以拿两到三枚硬币，从中可以找到假币。因此，最大值（二，三）= 三。

因此，这种方法的基本情况是每次取三个硬币来分配可用的硬币。

2.广义公式为3^n-3=（X*2），其中X为可用硬币数量，n为所需称重数量。（请记住n应该铺地板而不是天花板）。

考虑X=9个球。3^n=21并且n最高为2。

因此，判断最小称重次数的算法类似于：

algo_Min_Weight[int num_Balls]
{
   return log base 3 ([num_Balls * 2] + 3);
}

Answer 2

它可以在信息论的基础上得到严格的证明，这是一门非常漂亮的学科，它为计算机科学奠定了基础。

大卫·麦凯那些精彩的讲座中有一个证据。（抱歉，但不记得是哪一个了：可能是前五个中的一个）。

Answer 3

在每一次称重中，正好会发生三种不同的事情，因此使用两种称重，你只能看到九种不同的整体情况。因此，每次称重时，您需要确保消除至少三分之二（剩余）的可能性。保证每边称重三枚硬币就能做到这一点。每边称重四枚硬币可能会消除八枚硬币，但也可能只消除五枚。