初次游玩心得-引言部分

初次游玩心得

一、 引言

如果只告诉你四位数的高于目标值或者低于目标值，通过合理规划，理论上“至少几次可以保证猜到”这个数？

先说结论，至少14次可以保证猜到。

1.推导过程为

我们以二分法为例，0000至9999 共有10000个数字。

我们选择5000为第一个数，结果可能为低于目标值（排除5000个数），高于目标值（排除4999个数）。因为我们在计算“至少几次可以保证猜到”，所以我们假设每一次排除的数都少一些。就是说结果假设为5000高于目标值。

以此继续推演，第二个数为2500，结果假设为2500高于目标值。第三个数为1250，结果假设为1250高于目标值。第四个数为625，结果假设为625高于目标值。第五个数为312，结果假设为312高于目标值（此时，不论高于或低于，排除数量都为312）。第六个数为156，结果假设为156高于目标值。第七个数为78，结果假设为78高于目标值。第八个数为39，结果假设为39高于目标值。第九个数为19，结果假设为19高于目标值（此时，不论高于或低于，排除数量都为19）。第10个数为9，结果假设为9高于目标值（此时，不论高于或低于，排除数量都为9）。第11个数为4，结果假设为4高于目标值（此时，不论高于或低于，排除数量都为4）。第12个数为2，结果假设为2高于目标值。第13个数为1，结果假设为1高于目标值。在第14次可以得到结果为0。

2.总结归纳

据此，我们不难得到，如果只告诉一个数高于目标值或者低于目标值，要至少13次可以保证猜到0至n中的目标值，n最大为8190，

推导中的数字节点分别为0,1,3,7,15,31,63,127,255,511,1023,2047,4095

此题目的通项表述为：如果只告诉一个数高于目标值或者低于目标值，要至少a次可以保证猜到0至n中的目标值，n最大为2^a-2。

进一步精确表述为：如果每次只返回测试数高于/低于/等于目标值，要猜到m至n中的目标值，若2^（a-1）-2＜（m-n）≤2^a-2，则至少a次可以保证猜到（m，n，目标值，测试数，a均为整数）。

我们可以分别带入

① m=0,n=10000,a=14 ②m=0,n=8190,a=13 检验一下。