其实在一些特殊的情况下，确定最优的问问题策略和最少需要的问题个数并不困难。
考虑这样一个特例：俺心里的神秘数字X的取值范围是S={1，2，…，8}，而且X的概率分布函数是个均匀分布。那么最优的问问题方法就是所谓的“二分法”：每问一个问题要把这个神秘数字的可能范围缩减一半。比如这样的问法：
问题1:把集合{1，2，…，8}分成左右两份，左边的是{1，2，3，4}，右边的是{5，6，7，8}。然后问：你想的数是不是在左边啊？
问题2:根据俺的答案，你可以确定这个神秘数字只剩下四种选择。你再类似地把四种选择分成左右两份，然后问：你想的数是不是在左边啊？
问题3:根据俺的答案，你现在可以确定这个神秘数字只有两种选择，再把它们一个放左边，一个放右边。你再问：你想的数是不是在左边啊？
如此问完三个问题，你一定知道了俺的神秘数字。相信你的直觉也应该告诉你，这就是最优问法！那么在这个例子里，所需的最少问题个数就是3。从咱们用每个问题把猜测空间一切两半的问法，同学们应该也已经认识到，这里得出的最少问题数3正是因为8=2^3，或者说，2=lg8.（本文中所有的对数操作均以2为底数）。
↑返回顶部↑