Fwd: 关于称小球的解法

---------- Forwarded message ----------
From: 王莆中 <wangpuzhong@gmail.com>
Date: 2008/9/23
Subject: 关于称小球的解法
To: 宋庆浪gmail <songsql@gmail.com>, 张朋元 <shangdinizaina@gmail.com>, 杨政gmail <leony66@gmail.com>, 潘永杰gmail <hbdl506@gmail.com>

还记得网上流传的一个微软的面试题吗――给12个一模一样的小球，中间有一个重量比其它的小球稍重，用一个天平需要至少称几次才能找出那个小球？
结果当然是3，这个不多说。

昨天在一个邮件列表上看到有人讨论这个问题，然后还扯出香农的信息论和熵理论。一时好奇就看了一下，结果当时以为是想清楚了，还和老大吹了牛逼，但是后来想想发现我理解错了。今天终于想通了，给大家汇报一下。

首先，来看看12球这个集合中总熵为多少。
熵的计算公式：

在这个题目里，12个球中任意一个小球的重量稍重都是有可能的，视为等概率，则n=12，Pi = 1/12，Hs=log(12)。在这里，log代表以2为底的对数函数。那么，根据信息论的解释，每一次称天平都在减少不确定性（也就是每称一次就越接近目标一次），不确定性的减少意味着熵的减少。当熵减少到0的时候，就是找出小球的时候。

假如一堆球分成三份的话，那么称一次可以找到是哪一堆的重量稍重，也就是说每称一次天平，获得的信息量为 -1/3log(1/3)-1/3log(1/3)-1/3log(1/3)=log3

那么，假设最少要称N次，有N*log3>=log12，即 3的N次方>=12，显然，N=3的时候满足条件。

如果题目换一种出法：给一个天平让你称3次，最多可以在多少个小球中找到那个稍微重一点的？
由刚刚的结论得出――如果称三次的话，最多可以从3的3次方=27个小球中找到目标。

当然，这种解法只给出了一个底值，但是不知道具体步骤。
over