猜數(shù)字

252725

這個好難

239583

漲知識了

257406

當(dāng)不提示時，猜數(shù)范圍為n時，就需要逐個數(shù)猜，最倒霉的情況為n，即至少n次。當(dāng)有提示時，假設(shè)猜的數(shù)是范圍n的第k個，猜小時則問題轉(zhuǎn)化為范圍為k-1的有提示猜數(shù)，猜大時則變?yōu)榉秶鸀閚-k的無提示猜數(shù)，即另外需要n-k次。容易看出，根據(jù)猜數(shù)的不同，猜小次數(shù)減少時，猜大次數(shù)增多；猜小次數(shù)增多時，猜大次數(shù)減少。保證猜對的至少次數(shù)取決于猜小次數(shù)和猜大次數(shù)兩者間最大的一方，因此要使猜的次數(shù)盡可能少，則需要使猜小和猜大兩種情況下的次數(shù)相等或盡可能接近。不妨用f(n)來表示范圍為n的有提示猜數(shù)保證猜對至少需要的次數(shù)，則根據(jù)前面的分析可得遞推公式：
f(n)=f(k-1)+1, 其中1≤k≤n且f(k-1)-(n-k)的絕對值最小，而初始的f(1)=1，即只有一個數(shù)時只需要一次，而根據(jù)遞推公式將n=1代入可得f(0)=0。遞推公式可以變形為f(n+1+f(n))=f(n)+1, k=n+1，f(n)具有單調(diào)非遞減性
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，計(jì)算易得k=88, |f(88-1)-(100-88)|=0
總而言之，至少14次保證猜對，第一次猜88

260526

猜14次保證能猜到，第一個數(shù)猜14，如果一直是小了的話，那么依次猜
27  39  50  60  69  77  84  90  95  99
就是差為等差的數(shù)列，這樣當(dāng)出現(xiàn)“不正確”，也就是大了的情況，此時還需要猜的最多的次數(shù)就是兩個數(shù)之間所有的數(shù)。
因?yàn)槭遣碌臄?shù)增大的量依次減小，所以剩余還需要猜的數(shù)也在變小。