第四百七十一章 二分法的效率（1/1）

在这个例子中有个现象也值得注意一下：不管俺心里想的是个什么数字，使用二分法所需的问题数字都是3，一个完全确定，毫无随机性的数字。

这个特例显然可以推广：如果神秘数字x的概率分布函数是在2^k种可能性上的均匀分布，那么“二十个问题”游戏的最优策略可以通过二分法实现；在这种策略下，不论神秘数字是什么，问出它所需要的问题数都是k，因此所需要的平均问题数也是k。同学们请用红笔圈下这个结论（小心别把手机触摸屏划坏了），咱么晚点要用到这个结论。

当然，这个二分法只适合于这样的特例，当神秘数字的可能性总数不是2的多少次方的时候，或者当神秘数字的分布不均匀的时候，这种问法显然不是最优的。这个问题任意形式的最优解法曾让一个叫大卫·霍夫曼（davidhuffman）的年轻学生在1951年一夜成名。不过，那已经是在香农提出信息论三年之后了。