yangff
2016-11-14 20:32:42 +08:00
在需要知道轻重的情况下（称之前不知道） N 硬币问题 (N>=3 下有意义)
1. 用{Untested, Standard, Heavy, Light}表示状态
2. 每次称重 Balance(x,y,z) 可能得到 3 种结果， x == y, x > y, x < y ；也就是将 x, y 中的硬币归入 Heavy, Light 或者 Standard ，而 z 在 x>y 或者 x<y 时归入 Standard
3. 如果当前的状态是{0, ?, a, b}，那么， x 次称量最多可以在 3^x 个球中找到假的，策略是显然的。不妨设 a > b, 反之亦然。如果 a 足够大，能按照 3^(x-1)每堆，划分出至少两堆，取其中两堆作比较，如果平衡，则在余数堆(<=3^(x-1))中，并且还是{0, ?, a ’ ,b ’}的状态。如果不平衡，则在其中某堆中，数量为 3^(x-1)。而如果 a 不够大，则在两侧按个数平分轻重球，并让每侧总数为 3^(x-1)。平衡则剩下的(<=3^(x-1))得到结果，反之则确定在某一堆中，状态依旧是{0, ?, a, b}.
4. 而一开始我们的状态是{N, 0, 0, 0}, 但是我们更关注一次三分之后的结果
5. F(x)表示 x 次称重能得从{F(x), 0, 0, 0}个硬币中分辨出结果
6. 考虑第一次称重时使用的某个划分得到的结果，可能秤得 {0, A, B, B}， {A, 2B, 0, 0}，也就是， F(x) = A + 2B, 对于不平衡的前者结果，套用 4. 中结论
7. 其中，情况{0, A, B, B}也就是 Max{2B} = 3^(x-1)考虑到取整
8. 2 * [Max{B}] = 3^(x-1) – 1
9. 而第二种情况之后，和 6. 中情况不同的是我们有了标准硬币
10. 考虑这次称重时，把这 X 个币分成三部分，但是拿去称量的，除了(X/3, X/3 + 1)，分别再在天平两边放(0, 1)个标准球，这时候去称量
11. 如果平衡了，那一次就排除掉 2X/3+1 个硬币，反之，多加的那个标准硬币去掉，也变成 X/3 的情况。
12. 也就是说，此时我们可以比正常情况下多分辨一个硬币也就是， F(x) + 1
13. 因而， Max{A} = F(x – 1) + 1
14. F(x) = 3^(x-1) – 1+ F(x – 1) + 1 = 3^(x-1) + F(x – 1), F(3) = 12
15. F(x) = (3^x-3)/2
在不需要知道轻重的情况下 F(x) = (3^x-1)/2 证明类似。