微软面试“12小球区分”问题的解答方法（熊猫版）

peterch

微软面试“12小球区分”问题的解答方法（熊猫版）（原创的哦）
微软面试有一个道题：有12个小球，其中有一个小球的质量与其他11个标准小球的质量不同。给你一个天平，利用这个天平称3次，找到这个不同的小球，请描述解题方法。

熊猫给出的解答方法虽然不一定是最好的，但一定是可行的，解题方法如下（括号中为思想过程、解题原因及一些必要的前提、假设、说明，看时可以省略）：
01/（说明）（12个小球编号为1到12，以方便区分）
02/（因为）（把12个小球分2组称，一定不能在3次之内找出那个不同的小球，至于为什么不能分2组，熊猫这里不给出分析过程。就像常说的那样：“显然”，需要分3组来称，^_^）
03/[方法步1] 把12个球分3组，既1到4为一组，5到8为一组，其他9到12为一组。
04/[方法步2] “1到4组”与“5到8组”在天平上第一次称。
05/[可能结果1-] 结果有2种：天平平（对应可能结果1-1）和天平不平（对应可能结果1-2），分别讨论。
06/[可能结果1-1] “1到4组”与“5到8组”的天平平。
07/（因为）（由这个结果可知，不同的小球在“9到12组”中）
08/[方法步3] 9号球与10号球在天平上第二次称。
09/[可能结果1-1-] 结果有2种：天平平（对应可能结果1-1-1）和天平不平（对应可能结果1-1-2），分别讨论。
10/[可能结果1-1-1] 9号球与10号球的天平平。
11/（因为）（由这个结果可知，不同小球在11号球和12号球中）
12/（因为）（已经可以证明9号球、10号球一定是标准小球）
13/[方法步4] 9号球与11号球在天平上第三次称。
14/[可能结果1-1-1-] 结果有2种：天平平（对应可能结果1-1-1-1）和天平不平（对应可能结果1-1-1-2），分别讨论。
15/[可能结果1-1-1-1] 9号球与11号球的天平平。
16/（因为）（由这个结果可知，不同小球在12号球中）
17/[找到不同小球] 为12号球。
18/[可能结果1-1-1-2] 9号球与11号球的天平不平。
19/（因为）（由这个结果可知，不同小球在11号球中）
20/（因为）（前面已经证明9号球为标准小球）
21/[找到不同小球] 为11号球。
22/[可能结果1-1-2] 9号球与10号球的天平不平。
23/（因为）（由这个结果可知，不同小球在9号球和10号球中）
24/（因为）（已经可以证明11号球、12号球一定是标准小球）
25/[方法步4] 11号球与9号球在天平上第三次称。
26/[可能结果1-1-2-] 结果有2种：天平平（对应可能结果1-1-2-1）和天平不平（对应可能结果1-1-2-2），分别讨论。
27/[可能结果1-1-2-1] 11号球与9号球的天平平。
28/（因为）（由这个结果可知，不同小球在10号球中）
29/[找到不同小球] 为10号球。
30/[可能结果1-1-2-2] 11号球与9号球的天平不平。
31/（因为）（由这个结果可知，不同小球在9号球中）
32/（因为）（前面已经证明11号球为标准小球）
33/[找到不同小球] 为9号球。
34/[可能结果1-2] “1到4组”与“5到8组”的天平不平。
35/[可能结果1-2-] 结果有2种：“1到4组”重（对应可能结果1-2-1），“5到8组”重（对应可能结果1-2-2），分别讨论。
36/[可能结果1-2-1] “1到4组”重。
37/（因为）（“9到12组”一定都是标准小球，这里可以使用它们中任意一个作为标准小球）
38/（提示）（下面这个分组的分法是关键，至于原因，熊猫在下面论证）
39/[方法步3]（提示）（没错，到这种情况时，只进行了2步，只用过1次天平）
“1号5号6号”与“2号7号9号”在天平上第二次称。
40/[可能结果1-2-1-] 结果有3种：天平平（对应可能结果1-2-1-1）、“1号5号6号”重（对应可能结果1-2-1-2）、“2号7号9号”重（对应可能结果1-2-1-3）。
41/[可能结果1-2-1-1] “1号5号6号”与“2号7号9号”的天平平。
42/（因为）（不同球在3号、4号、8号中）
43/[方法步4] “3号”与“4号” 在天平上第三次称。
44/[可能结果1-2-1-1-] 有3种，天平平（对应可能结果1-2-1-1-1）、“3号”重（对应可能结果1-2-1-1-2）、“4号”重（对应可能结果1-2-1-1-3）
45/[可能结果1-2-1-1-1] “3号”与“4号”天平平。
46/[找到不同小球] 为8号球。
47/（因为）（“[可能结果1-2-1-1-2] ‘3号’重” 和 “[可能结果1-2-1-1-3] ‘4号’重” 之中，可以知道不同小球在3号和4号中，“5到8组”也都是标准小球；又因为“[可能结果1-2-1] ‘1到4组’重”的前提，知道不同小球是比标准小球重的小球）
48/[找到不同小球] 3号与4号球中重的球为不同小球。
49/[可能结果1-2-1-2] “1号5号6号”重。
50/（因为）（在“[可能结果1-2-1] ‘1到4组’重”的前提下，只有1号7号没有改变位置，因此不同球在1号7号中。）
51/[方法步4] 1号7号利用天平第三次称。（利用一个标准球，很容易就找到哪个是不同的小球）
52/[找到不同小球] 不同小球在1号或7号中，（这个步骤省了，不写了）。
53/[可能结果1-2-1-3] “2号7号9号”重。
54/（因为）（在“ [可能结果1-2-1] ‘1到4组’重” 前提下，只有2号5号6号改变位置了，因此不同球在2号5号6号中。）
55/[方法步4] “5号”与“6号” 在天平上第三次称。
56/[可能结果1-2-1-3-]结果有3种：天平平（对应可能结果1-2-1-3-1）、“5号”重（对应可能结果1-2-1-3-2）、“6号”重（对应可能结果1-2-1-3-3）
57/[可能结果1-2-1-3-1] “5号”与“6号”天平平。
58/[找到不同小球] 为2号球。
59/（因为）（在“[可能结果1-2-1-3-2] ‘5号’重”和“[可能结果1-2-1-3-3] ‘6号’重”前提下，不同小球一定在5号和6号之中，因此“1到4组”也都是标准小球；又因为“[可能结果1-2-1] ‘1到4组’重”的前提，知道不同小球是比标准小球轻的小球）
60/[找到不同小球] 5号与6号球中轻的球为不同小球。
61/[可能结果1-2-2] “5到8组”重。
62/（因为）（这种情况与“[可能结果1-2-1] ‘1到4组’重” 基本相同，使用相同的方法就可以找出不同小球，这里就不写出了）
63/解题完毕。
64/^_^

后记：感谢我的室友Mindy，是他不懈的刨根问底，使我有动力写完这么多文字，而且是多少有点罗嗦的文字。



本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/15316/showart_125431.html