猜數字

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
就是差為等差的數列，這樣當出現“不正確”，也就是大了的情況，此時還需要猜的最多的次數就是兩個數之間所有的數。
因為是猜的數增大的量依次減小，所以剩余還需要猜的數也在變小。