UC知道猜数字（谁能帮我理解下面的含义。。）
来源：百度知道 编辑：UC知道 时间：2024/05/21 02:46:08
猜数字
我们先来玩一个猜数字游戏：我心里默念一个1~64之间的数，你来猜（你只能问答案是“是”或“否”的问题）。为了保证不论在什么情况下都能以尽量少的次数猜中，你应该采取什么策略呢？很显然，二分。先是猜是不是位于1~32之间，排除掉一半可能性，然后对区间继续二分。这种策略能够保证无论数字怎么跟你捉迷藏，都能在log_2{n}次以内猜中。用算法的术语来说就是它的下界是最好的。
我们再来回顾一下这个游戏所蕴含的本质：为什么这种策略具有最优下界？答案也很简单，这个策略是平衡的。反之如果策略不是平衡的，比如问是不是在1~10之间，那么一旦发现不是在1~10之间的话就会剩下比N/2更多的可能性需要去考察了。
我们先来玩一个猜数字游戏：我心里默念一个1~64之间的数，你来猜（你只能问答案是“是”或“否”的问题）。为了保证不论在什么情况下都能以尽量少的次数猜中，你应该采取什么策略呢？很显然，二分。先是猜是不是位于1~32之间，排除掉一半可能性，然后对区间继续二分。这种策略能够保证无论数字怎么跟你捉迷藏，都能在log_2{n}次以内猜中。用算法的术语来说就是它的下界是最好的。
我们再来回顾一下这个游戏所蕴含的本质：为什么这种策略具有最优下界？答案也很简单，这个策略是平衡的。反之如果策略不是平衡的，比如问是不是在1~10之间，那么一旦发现不是在1~10之间的话就会剩下比N/2更多的可能性需要去考察了。
简单地说，就是先确定数字的所在区间，然后不断缩小范围，最终确定那个数字，如果只是乱猜的话，会有更多的可能
用2分法可以保证在6次之内找到，而其他方法比如里面说的1~10的方法，则可能需要7次以上的尝试
即在判断的时候，采用均分的方法能够最快速地把答案所在区间缩小到能得到答案
以上
用黄金分割法更好
就是2进制，从高位到低位一位一位地猜，保证恰好6次猜出。
其他方法可能会有7次甚至更多次才猜出的情况。