1. 猜数字游戏
A 写下一个数 
，其取值范围为 ![x\in [1,n]](https://math.jianshu.com/math?formula=x%5Cin%20%5B1%2Cn%5D)
，B 来猜这个数字是多少，A 会告诉 B 猜的数字比 大了还是小了，问 B 最少猜多少次可以猜出这个数字？
把 看作一个随机数，他的取值范围是![[1,n]](https://math.jianshu.com/math?formula=%5B1%2Cn%5D)
，B 第一次任意猜一个数，猜中的概率是 %20%3D%20%5Cfrac%7B1%7D%7Bn%7D)
。利用数学中的熵的定义，B 猜中的熵是
![S_{x\in[1,n]} = -\Sigma_{x\in[1,n]}{P(x)\log_2 P(x)} = \log_2 n](https://math.jianshu.com/math?formula=S_%7Bx%5Cin%5B1%2Cn%5D%7D%20%3D%20-%5CSigma_%7Bx%5Cin%5B1%2Cn%5D%7D%7BP(x)%5Clog_2%20P(x)%7D%20%3D%20%5Clog_2%20n)
假如 B 第一次猜的数是 
，则 ![P(x\in[1,y]) = \frac{y}{n}](https://math.jianshu.com/math?formula=P(x%5Cin%5B1%2Cy%5D)%20%3D%20%5Cfrac%7By%7D%7Bn%7D)
，![P(x\in(y,n]) = \frac{n-y}{n}](https://math.jianshu.com/math?formula=P(x%5Cin(y%2Cn%5D)%20%3D%20%5Cfrac%7Bn-y%7D%7Bn%7D)
, 则 条件熵(给定条件下的熵)为 ![S_1 = P(x\in[1,y])S_{x\in[1,y]} + P(x\in(y,n])S_{x\in[y,n]}\\ =\frac{y}{n} \log_2 y +\frac{n-y}{n}\log_2 (n-y)](https://math.jianshu.com/math?formula=S_1%20%3D%20P(x%5Cin%5B1%2Cy%5D)S_%7Bx%5Cin%5B1%2Cy%5D%7D%20%2B%20P(x%5Cin(y%2Cn%5D)S_%7Bx%5Cin%5By%2Cn%5D%7D%5C%5C%20%3D%5Cfrac%7By%7D%7Bn%7D%20%5Clog_2%20y%20%2B%5Cfrac%7Bn-y%7D%7Bn%7D%5Clog_2%20(n-y))
求 取何值时，熵最小？
所以每次都猜一个区间的中间值是最优的选择。由于 A 会告诉 B 两种状态，因此 B 只需要猜 
就可以猜出 A 给定的数。n 代表可取的状态数，2 代表给定信息的个数
2. 排序问题
有 
个互不相等的数，需要通过多少次比较才可以将这些数从小到大排序？
比较两个数 
的大小有两种状态，所以对数的底应取为 2，n 个数排序的方式，即可取的状态数为 
，所以需要比较 %5Crceil)
次。
3. 猜球问题
有 n 个球，其中有一个球与其他 n-1 个球的重量不一样，现在有一个天平，问需要称多少次可以找出这个球？
天平有三种状态，故对数的底应为3，n 个球要么重了要么轻了，故有 2n 中状态数，所以需要称 (
) 次可以找出这个球。
