猜数字最优策略计算器

猜数字游戏的最优策略是二分查找：每次猜当前区间的中点，根据大了或小了的提示排除一半可能性。100 个数最坏情况只需 ⌈log₂100⌉ = 7 次，100 万个数也只要 20 次。这就是信息论的威力：每次猜测获得恰好 1 比特信息（是/否），而 n 个可能性包含 log₂n 比特的不确定性，所以次数下界就是 ⌈log₂n⌉——二分法达到了这个理论极限，不存在更快的策略。

实战操作以 1-100 为例：猜 50，小了就猜 75，大了就猜 25，每次把区间砍半。7 次之内必中，平均 5.8 次。如果猜的人不诚实（中途换数字），二分法会在第 7 次抓到矛盾——区间收敛为空即证明对方作弊。这个游戏是理解二分查找、信息熵和算法下界的最佳入口，也是面试常见题的玩具版。

二分查找的数学最优性由信息论严格保证。每次猜测获得 1 比特信息（是/否），n 个可能性包含 ⌈log₂n⌉ 比特不确定性，任何策略的最坏情况次数下界就是 ⌈log₂n⌉。二分法达到这个下界，因此是 minimax 最优——不存在最坏情况更少的策略。平均次数 ≈ log₂n − 1 + 1/ln2 ≈ log₂n − 0.44，因为大多数猜测提前命中（几何分布的期望修正）。

「带成本猜测」的变体引入决策论。若每次猜测成本 c、命中奖励 r，期望收益 = r × P(命中) − c × E(次数)。二分法最小化 E(次数)，但非均匀先验下（如「对方更可能选 7」），贝叶斯二分法按概率质量分割而非数值中点，期望次数可再降 15-20%。「撒谎者版本」（对方最多说一次谎）需要纠错码：重复编码 + 多数表决，次数增加 ⌈log₂⌈log₂n⌉⌉，100 个数约需 11 次。

二分法的历史映射了计算思维的演进。1946 年 Mauchly 首次在 ENIAC 上实现；1962 年 Bottenbruch 发现「几乎正确的二分查找」边界条件 bug（mid = (low+high)/2 在 low+high 溢出时错误），这个 bug 在 Java 标准库潜伏 9 年才修复。现代变体：三分查找（每次排除 1/3，常数因子更差但缓存友好）、插值查找（均匀分布下 O(log log n)）、指数查找（无界序列先倍增定位区间）。