称球问题很久了,华为和微软都出过。
我想大概是想考察一个人对信息量的敏感程度。
例如题:现有n个外观一样的小球,其中有一个小球的重量与众不同
(不知其轻重或者说知道轻或者重),请问最少称多少次一定可以将这个不同的球找出。
天平称重,有两个托盘比较轻重,加上托盘外面,也就是每次称重有3个结果,
就是ln3/ln2比特信息。n个球要知道其中一个不同的球,如果知道那个不同重量的球
是轻还是重,找出来的话那就是n个结果中的一种,就是有ln
/ln2比特信息,
如果不知道轻重,找出来就是2n(n个球中的一个,轻或者重,所以是2n)个结果中的一种,
那就是ln(2n)/ln2比特信息。
假设我们要称k次,根据信息理论,那显然两种情况就分别有:
(1) k*ln3/ln2>=ln
/ln2, 解得k>=ln
/ln3
(2) k*ln3/ln2>=ln(2n)/ln2 (k>1) 解得k>=ln(2n)/ln3
这是得到下限,可以很轻易证明满足条件的最小正整数k就是所求。
比如称3次知道轻重可以从3^3=27个球中找出不同的球出来,
如果不知道轻重就只能从(3^3-1)/2=13个球中找出不同的球出来。
具体称法就不说了,其实真的理解了信息论里面的那不等式的等式
成立条件就知道称法了,也就是要保证每次称的信息含量ln3/ln2。
可以看看相关的一个帖子:http://dell1.cn99.com/thbbs/GreatTurn.AIX/00000042.htm。