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

python的函数调用参数

python函数调用的参数有4种
　　1 Positional Arguments，如func(1,2)
　　2 Keyword Arguments，如func(x=1,y=2)
　　3 Non-keyword Variable Arguments (Tuple)
　　 如args=(1,2)，func(*args)
　　4 Keyword Variable Arguments (Dictionary)

basic tips of python(1)

basic tips:

1、切片符[0:3]指从0－3但是不包括3，类型其它语言的 (i>=0 & i<3)

2、python类中的属性也有类属性和对象属性之分，分别用classname. 以及 objcet.的前缀来调用

3、file初始化的时候可以新建或者打开文件，打开的话要传入'w'参数

4、python的try...expect\try...finally\raise 与delphi的极为相似――基本一样

5、python中有docstrings，用来作为函数、类的注释，用'''Prints the maximum of two numbers'''（3个'）来表示

6、函数体中默认声明的是局部变量，加上global 关键字则是全局的

7、OS模块可以帮助写跨操作系统的程序，同时也提供了操作OS下资源的接口，比如删除文件