Given 12 coins, identify the special one in three weighings(转)

Occam's razor states a preference for simple theories. "Accept the simplest explanation that fits the data".

转自：http://www.mitbbs.com/article_t/JobHunting/31710895.html

12 coins. One of them is heavier or lighter than the rest.
Identify this coin and whether it is heavier or lighter in three weighings.

In general, given N coins, at least how many times are needed to identify this coin and whether it is heavier or lighter ?
关键就是每次称都有三种结果：左边重，右边重，两边一样重。那理论上N次操作后可以用3^N种状态。那么12个球也就需要3次就够了。而3次最大可以称27球。
每次操作的关键就是让三种结果的概率尽可能相等。

这种题最简单的解法就是逆推。
最后一步你肯定是要确定特殊硬币在某三个硬币之间（这样才能一次找出），然后前两步自然就是找出这三个硬币。
12个硬币组合方式也就那么多，自然就会分成四拨，每拨三个。四拨三个随便拿两拨称，不一样就说明特殊硬币不在剩下的两拨里面。在剩下两拨里面随便拿一拨（肯定不含特殊硬币）跟最开始选择的两拨里重的那拨称（轻的同理）。如果不一样，说明特殊硬币重了，且在最开始两拨里重的那拨里面。然后一次称重就可找出。如果一样，就说明特殊硬币轻了，且在最开始两拨里轻的那拨里面。同样一次称重可找出。
如果第一次称重重量一样，说明特殊硬币在剩余两拨里面，同理可得。
Given 8 coins, how to identify the heavier one in 2 weighing?
123, 456, 78
if 123 > 456
    then weigh any two from 123, find the heavier one
else if 456 > 123
    do same as above
else
    weigh 78, find the heavier one