猜数字

252725

这个好难

239583

涨知识了

257406

当不提示时，猜数范围为n时，就需要逐个数猜，最倒霉的情况为n，即至少n次。当有提示时，假设猜的数是范围n的第k个，猜小时则问题转化为范围为k-1的有提示猜数，猜大时则变为范围为n-k的无提示猜数，即另外需要n-k次。容易看出，根据猜数的不同，猜小次数减少时，猜大次数增多；猜小次数增多时，猜大次数减少。保证猜对的至少次数取决于猜小次数和猜大次数两者间最大的一方，因此要使猜的次数尽可能少，则需要使猜小和猜大两种情况下的次数相等或尽可能接近。不妨用f(n)来表示范围为n的有提示猜数保证猜对至少需要的次数，则根据前面的分析可得递推公式：
f(n)=f(k-1)+1, 其中1≤k≤n且f(k-1)-(n-k)的绝对值最小，而初始的f(1)=1，即只有一个数时只需要一次，而根据递推公式将n=1代入可得f(0)=0。递推公式可以变形为f(n+1+f(n))=f(n)+1, k=n+1，f(n)具有单调非递减性
f(0)=0
f(1)=1
f(3)=2, k=2
f(6)=3, k=4
f(10)=4, k=7
f(15)=5, k=11
f(21)=6, k=16
f(28)=7, k=22
f(36)=8, k=29
f(45)=9, k=37
f(55)=10, k=46
f(66)=11, k=56
f(78)=12, k=67
f(91)=13, k=79
f(105)=14, k=92
100在91和105之间，因此f(100)=14，计算易得k=88, |f(88-1)-(100-88)|=0
总而言之，至少14次保证猜对，第一次猜88

260526

猜14次保证能猜到，第一个数猜14，如果一直是小了的话，那么依次猜
27  39  50  60  69  77  84  90  95  99
就是差为等差的数列，这样当出现“不正确”，也就是大了的情况，此时还需要猜的最多的次数就是两个数之间所有的数。
因为是猜的数增大的量依次减小，所以剩余还需要猜的数也在变小。