动态称球
01 Oct 2017 • Leave Comments问题描述
有N个同规格的球，现发现其中有一个坏了，重量和其它N-1个球有稍微区别。现给一个没有砝码的灵敏天平，请通过最少次的称量，找出坏球，并判别是轻了还是重了。
数学模型
- 给球编号，1,2, … , N.
-
假设需要的最少次数是n，那么N和n之间的关系是：
n = ⌈ log₃(2N+3) ⌉ 或 N = ⌊ (3ⁿ - 3)/2 ⌋ (N >= 4)
- 这里出现两个特别的数字2和3. 2是因为每一个球有两个可能性，即它是坏球且比其它标准球轻，或它是坏球且比其它标准球重。3是因为每次称量会有三种结果，即左边重（右边轻），右边重（左边轻）或平衡。
- 我们说最少次数n，其实不是没次称量都要n次，因为称量过程是随机的，我们没法预测下一次称量的结果。但如果算法合理，最复杂的情况是n次；反之，算法不合理，最复杂情况不低于n次。
- 假设n不变，球数加1，即N+1个球，那么可以保证找出坏球，但不能保证识别出轻重。
称量分析
称球的过程其实可以用决策树或矩阵方程表述。
-
每次称量前，把待称量的球（假设K个，第一次为N）分成三堆，并确保上天平的两堆球数相同，也即：第一堆（左堆）⌈ K/3 ⌉个球，第二堆（右堆）⌈ K/3 ⌉个球，第三堆（未上称）K - 2⌈ K/3 ⌉个球。
这样的划分的结果是，不上天平的那堆球数少。
- 前面说过，每次称量有三种可能，每种可能可以推导出新的信息：
- 左边重：坏球肯定在天平上的两堆里。坏球在左边并比标准球重，或坏球在右边且比标准球轻。
- 右边重：坏球肯定在天平上的两堆里。坏球在左边并比标准球轻，或坏球在右边且比标准球重。
- 平衡：坏球在未上称的第三堆，暂时无法判断轻重。
- 每次称量前，我们需要算出：
-
如何根据上次称量结果，找出本次待称量的是哪些球。
假设上次称量结果为前两种情况（左边重或右边重，坏球在天平上），那么本次待称量的是天平上的球。假设上次称量的球数为K'，那么本次K = 2⌈ K'/3 ⌉. 如果上次称量结果为平衡，那么本次待称量即未上天平的第三堆，K = K' - 2⌈ K'/3 ⌉.
后面会分析到，“实际称量球数是待称量球的一个子集（<= K）”。
-
分堆。如何决定一个编号球被分到哪一堆，或者说每一堆里都有哪些编号球。
决定了本次待称量的球，如何划分这些球才是核心问题，我们在下节讲解。
-
三堆
-
第一次称量没有上次参考。待称量的是所有的N个球。只需按照编号顺序划分为：
堆 球 左 1 ~ ⌈ N/3 ⌉ 右 (⌈ N/3 ⌉ + 1) ~ 2⌈ N/3 ⌉ 否 (2⌈ N/3 ⌉ + 1) ~ N “否”表示未上天平的第三堆。第一次的分堆随意，只需要保证堆的数量即可。下面来考虑更一般的情况。
-
假设本次待称量的球已经确定，这些球除了编号这个属性外，还额外增加了一个新标签，即前面节第二条所述三种推理。那么如何描述新信息呢？
本次待称量的球可以用u、v两个子集合表示，注意这里的u、v集合不是分堆，而是用来辅助分堆。我们也可以说u、v里的球具有u、v标签。
- u里的球，要么是标准球，要么是坏球并且比标准球重。
- v里的球，要么是标准球，要么是坏球并且比标准球轻。
u、v的定义可以反过来，但不影响结果。最简单的u、v集合出现在第一次称量之后：
- 第一次称量左重，则左堆为u，右边堆为v。
- 第一次称量右重，则右堆为u，左边堆为v。
这时| u | = | v | = ⌈ N/3 ⌉. 但更一般情况如下：
- u、v有可能为空集；
- | u | ≠ | v |更常见；
- 经过几轮称量后，堆里会同时含有u、v中的球，这是为了便于排除更多的球。
假设上次称量的三堆如下：
堆 u', v' 数量 左 u₁', v₁' ⌈ K'/3 ⌉ 右 u₂', v₂' ⌈ K'/3 ⌉ 否 v' 余下 K' - 2⌈ K'/3 ⌉ 表格用逗号来分隔u/v集合，便于识别。
- 如果左重，那么u = u₁'，v = v₂'；u₂'、v₁'被排除；
- 如果右重，那么u = u₂'，v = v₁'；u₁'、v₂'被排除；
- 如果平衡，那么u = ∅，v = v' - v₁' - v₂'引入一个标准球（左右堆里全是）。为何这里需要引入标准球？因为本次v' - v₁' - v₂'集合球标签单一，引入标准球寻求更多差异。
轻特别注意如何排除部分“待称量球”，“实际称量球数是待称量球的一个子集（<= K）”。
显然，对于第一次称量没有前次参考，u = v = ∅.
- K = | u | + | v |. 那么把u、v里的球分成三堆呢？
- 把u集合的球平均分配到第一、二堆。如果不够⌈ K/3 ⌉，则
- 从v集合平均往第一、二堆放球到满。
- 把v里余下的球分到第三堆。明显不存在v集合取完后，还没有填完第一、二堆的情况。
至此分球完毕，用表格表示如下：
堆 u, v 数量 左 u₁, v₁ ⌈ K/3 ⌉ 右 u₂, v₂ ⌈ K/3 ⌉ 否 v余下 K - 2⌈ K/3 ⌉ 开始本次称量。
- 引入标准球
- u = ∅，或v = ∅，或 u = v = ∅，此时引入标准球替换一个待称量球，寻取差异。被替换的待称量球放在第三堆。
- 一般发生在上次称量平衡时。但第一次称量时明显u = v = ∅. u = ∅, v ≠ ∅不常见，多出现在| u' | 和 | v' | 非常小时（如< =3）。
- 如果 | u | 或 | v | 非常小（如3），根本不引入标准球。
N = 1、2、3
N <= 3的情况特殊，这里特别说明。
- N = 1，不需要称，坏球肯定就那一个。
- N = 2，没有参考，无法称量，
- N = 3，n = 2。1号球左边，2号球右边，称量一次后用三号球替换2号球。
- 左重，左重，1号坏球并且比标准球重；
- 左重，平衡，2号坏球并且比标准球轻；
- 左重，右重，不可能；
- 平衡，左重，3号坏球并且比标准球轻；
- 平衡，平衡，不可能；
- 平衡，右重，3号坏球并且比标准球重；
- 右重，左重，不可能；
- 右重，平衡，2号球坏并且比标准球重；
- 右重，右重，1号球号并且比标准球轻；
N = 4
- n = ⌈ log₃(2*4+3) ⌉ = 3.
- 第一次称量，如上分析，没有参考，所以简单按编号分堆：
- u' = v' = ∅.
- ⌈ K/3 ⌉ = ⌈ N/3 ⌉ = ⌈ 4/3 ⌉ = 2
堆 u, v 数量 左 1 2 2 右 3 4 2 否 ∅ 0 分析下次称量u、v集合：
- 左重，u = { 1, 2 }, v = { 3, 4 }.
- 右重，u = { 3, 4 }, v = { 1, 2 }.
- 平衡，不可能。
-
第二次称量：
K = | u | + | v | = 4，比较特殊K = K'. ⌈ K/3 ⌉ = ⌈ 4/3 ⌉ = 2
一左重：
堆 u, v 数量 左 1, 3 2 右 2, 4 2 否 ∅ 0 或一右重：
堆 u, v 数量 左 3, 1 2 右 4, 2 2 否 ∅ 0 注意，这次不是按照顺序分堆。逗号左边是u集合，右边是v集合。
根据第一、二次称量，分析下次称量u、v集合，实际有4重情况：
- 一左重，二左重，u = { 1, 2 } ∩ { 1, 3 } = { 1 }，v = { 3, 4 } ∩ { 2, 4 } = { 4 }.
- 一左重，二右重，u = { 1, 2 } ∩ { 2, 4 } = { 2 }，v = { 3, 4 } ∩ { 1, 3 } = { 3 }.
- 一左重，二平衡，不可能。
- 一右重，二左重，u = { 3, 4 } ∩ { 3, 1 } = { 3 }，v = { 1, 2 } ∩ { 4, 2 } = { 2 }.
- 一右重，二平衡，不可能。
- 一右重，二右重，u = { 3, 4 } ∩ { 4, 2 } = { 4 }，v = { 1, 2 } ∩ { 3, 1 } = { 1 }.
第二轮称量后，排除两个球，剩下两个球。
-
第三次称量：
经过第二次称量，u、v cardinality为1, K = 2 < 4属于特殊情况。我们不需要继续称量分析，而是直接引入标准球。被排除的两个球肯定是标准球，随便引入一个替换u、v中的球上天平即可。
堆 u, v 数量 左 1, 1 右 , 4 > 2 1 否 ∅ 0 堆 u, v 数量 左 2, 1 右 , 3 > 1 1 否 ∅ 0 堆 u, v 数量 左 3, 1 右 , 2 > 4 1 否 ∅ 0 堆 u, v 数量 左 4, 1 右 , 1 > 3 1 否 ∅ 0 上表重，分别引入了2、1、4、3标准球作为参考：
- 左重，1是坏球并比标准球重；平衡，4是坏球并比标准球轻；右重不可能。
- 左重，2是坏球并比标准球重；平衡，3是坏球并比标准球轻；右重不可能。
- 左重，3是坏球并比标准球重；平衡，2是坏球并比标准球轻；右重不可能。
- 左重，4是坏球并比标准球重；平衡，1是坏球并比标准球轻；右重不可能。
N = 12
这个过程非常复杂，在纸上演练吧。
