西西文学网 > 玄幻奇幻小说 > 数学心 > 第四百七十一章 二分法的效率

第四百七十一章 二分法的效率

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

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

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