12个金币的问题

http://www.iteye.com/post/475217

现在有12个金币,其中一个有质量问题(或重或轻),还有一个无砝码的天平,让你称三次怎么样找到那个有质量问题的金币?

这个题目是比较经典的智力题，俺记得第一次解这个题目是学二叉树的时候，俺当时死活要跟二叉树联系起来，汗

一种解法：

第一个量重比较是 4 对 4

考虑以下两个可能：

A) 左边比较重
B) 两边一样重

若是 A)，那么假的金币就在天秤上，即是说余下的金币全都是真的，为了方便，把金币命名如下：

H1, H2, H3, H4, L1, L2, L3, L4, R1, R2, R3, R4

当中 H1, H2, H3, H4 是在重的一端的金币； L1, L2, L3, L4 是在轻的一端的金币；而 R1, R2, R3, R4 就是余下的真金币。在这情形下，有两个可能性：假的金币较重而且是 H1, H2, H3, H4 的其中一个；或者假的金币较轻而且是 L1, L2, L3, L4 的其中一个

第二个量重比较是这样的：

H1,H2,L1,L2 对 H3,L3,R1,R2

有 3 个可能性：

C) 左边较重
D) 右边较重
E) 两边一样重

若是 C)，那么假金币只可能是 H1, H2 或 L3 ，最后的量重是 H1 对 H2，就可以得出答案了

若是 D)，那么假金币只可能是 L1, L2 或 H3，最后的量重是 L1 对 L2，就可以得出答案了

若是 E)，那么假金币只可能是 H4 或 L4，最后的量重是 H4 对 R1，就可以得出答案了

到此 A) 这个可能是完成了

现在处理 B)，这时天秤上的金币都是真的，假的金币就在余下的金币內，以以下方法把金币命名：

R1, R2, R3, R4, R5, R6, R7, R8, U1, U2, U3, U4

当中 R 是真的金币，U 是余下的金币。

第二次量重是这样的：

R1, R2, R3 对 U1, U2, U3

有两个可能：

F) 左边较轻
G) 两边一样重

若是 F)，那么假金币就是较轻的，而且是在 U1, U2, U3 之中。最后比较 U1 和 U2 就知道答案了。

若是 G)，那么 U4 就是假金币但还未知道这个金币是较重还是较轻，只需把它和其中一个真金币比较一下就知道了。