1、猜數(shù)問題,猜數(shù)問題是信息學競賽中一種常見的類似博弈的問題。 基本形式：存在一個被猜數(shù)X。每次可以猜一個數(shù)Y，之后會返回X和Y的關系，你要利用返回的信息來猜出X。 本文著重討論的一類猜數(shù)問題是：返回的信息是X和Y的大小關系。,基本的猜數(shù)問題,下面就是一個本文討論范疇內的最基本的猜數(shù)問題： 被猜數(shù)X是1到N范圍內的整數(shù)，每次你可以詢問一個整數(shù)Y和X的大小關系。給出N，請問在最壞情況下至少需要幾次才能保證猜出X。 上題應用大家熟悉的二分的思想可以輕松解決。,上面我們總共耗費了3次詢問。這只是作為一個二分詢問的例子。對于此題，應用二分法，作適當?shù)臄?shù)學分析，就可以得到最少的詢問次數(shù)為：,基本的猜數(shù)問題,

2、設N=7,X=5。應用二分的思想詢問：,1,2,3,4,5,6,7,1.詢問Y=4 2.得到XY 3.詢問Y=6 4.得到XY 5.詢問Y=5 6.得到X=Y,猜出X=5!,問題的提出,作為一類猜數(shù)問題中最基本的形式，固然是非常簡單的。 但很多其他的問題在這個“基本形式”上進行了一些擴充和加強，就變成了非常棘手的問題。 下面就讓我們來實際的看一看這類型的例子：,問題的提出,你和你的同學在網上進行猜數(shù)游戲，基本規(guī)則和普通的猜數(shù)游戲一樣。你猜一個數(shù)Y，他告訴你，Y和他心中所想的數(shù)X的大小關系。你打字速度很快，每1s鐘就可以問一個問題。由于網絡有延遲的，所以你問的問題不能馬上得到回答，而是要經過1s

3、之后才會得到回答。同時你和同學約定，你要盡量避免得到XY的回答。（你可以認為，X是他的考試成績之類的）當你累計得到第K次XY的回答的時候，你就輸了。已知X是1到N之間的整數(shù)?，F(xiàn)在給出N、K，請問最少要多少秒才能保證猜出X。,問題的提出,下面是一個N=6,K=3時的實例：,上面的詢問，總共用了5s。 期間得到了一次XY的回答。K=3沒有超過限制。,Y=3,Y=5,Y=4,Y=4,Y=6,X6,X5,X=4,X3,初步分析,我們現(xiàn)在的問題并不是如何猜，而是在最壞的情況下至少要多少秒才能猜出X來。 本題沿用二分的老思路是行不通的。 可以看出，雖然僅僅是在基本猜數(shù)問題上進行了些許加強，就成了一個非常棘

4、手的問題。 為了解決這個問題，讓我們重新從最原始的猜數(shù)問題開始分析。,1,2,3,當N=3，K=1并且X=3時。,詢問Y=2，必然得到XY回答。,不可以二分！,前面我們是通過二分的方法來解決此題的。至于“二分”這個思路的來源，更多的是源自猜測、及平時做題的經驗。 下面就來系統(tǒng)的分析為什么“二分”是正確的。 通過分析，希望能找到一個更具有普遍性的方法解決前面的題目。 讓我們嘗試用遞推的方法來分析問題。,被猜數(shù)X是1到N范圍內的整數(shù)，每次你可以詢問一個整數(shù)Y和X的大小關系。給出N，請問在最壞情況下至少需要幾次才能保證猜出X。,再看基本猜數(shù)問題,再看基本猜數(shù)問題,設f(i)表示i次詢問最大能夠處理的

5、區(qū)間長度。即若N=f(i)，則只需要i次就可以猜出X。 根據上面定義，若f(j)N。且f(j-1)N則可以知道j即為題目所求的至少詢問次數(shù)。 每詢問一個Y，只可能得到三種不同的回答，我們就從這三種不同的回答入手來分析問題。,再看基本猜數(shù)問題,詢問一個值Y。 若回答是X=Y，即游戲馬上中止。 XY時，為了要在剩下的I-1次詢問中得到答案，大于Y的區(qū)域長度不能超過f(i-1)。 XY時，小于Y的區(qū)域長度不能超過f(i-1)。,Y,小于Y的區(qū)域,大于Y的區(qū)域,1,f(i-1),f(i-1),再看基本猜數(shù)問題,上面分析直觀的說明了二分的正確性。 f(i)=2f(i-1)+1 = f(i)=2i-1 應

6、用遞推的方法間接的證明了前面的結論，即最少詢問的次數(shù)為： 更重要的是：對于這類試題來說，上面這種應用遞推的分析問題的方法具有很強的推廣性。,二次分析,通過上面的分析，基本的猜數(shù)問題已經完整的解決了?，F(xiàn)在回到原題的研究。 現(xiàn)在直接分析原題仍然有點困難，注意到原題相比基本猜數(shù)問題有兩個加強： 不妨先把這道題目拆開，分部解決。,1.累計獲得K次XY的答案就游戲結束。 2.本次的回答要在下一個提問之后獲得。,猜數(shù)問題的加強,被猜數(shù)X是1到N范圍內的整數(shù)，每次你可以詢問一個整數(shù)Y和X的大小關系。 附加上條件：累計獲得K次XY的答案就游戲結束。 給出N、K，請問在最壞的情況下至少需要幾次詢問才能保證猜出X

7、。 對于這個問題，可以借鑒前面的經驗，應用遞推的方法來求解。,被猜數(shù)X是1到N范圍內的整數(shù)，每次你可以詢問一個整數(shù)Y和X的大小關系。你要盡量避免詢問比X小的Y值，因為累計獲得K次XY的答案就游戲結束。給出N、K，問在最壞情況下至少需要詢問幾次才能保證猜出X。,猜數(shù)問題的加強,類似的，我們設f(i,j)表示用i次詢問，在累計j次XY的回答就游戲結束的情況下，最大能處理的區(qū)間長度。 如果我們能夠快速求出f，問題也就容易解決了。找到最小的數(shù)Ans，滿足f(Ans,k)N，f(Ans-1,K)Y分別進行討論來構造遞推公式。,猜數(shù)問題的加強,X=Y的情況最簡單,長度為1。 回答為XY，還剩下i-1次機會

8、詢問，并且我們得到了一次“XY”的回答，所以j值減少1，大于Y的區(qū)域長度最多為f(i-1,j-1)。,Y,小于Y的區(qū)域,大于Y的區(qū)域,f(i-1,j),f(i-1,j-1),1,猜數(shù)問題的加強,根據這個遞推式，依次將f全部計算出來，直到存在一個f(Ans,k)N，就結束。所以總時間復雜度為O(AnsK)。 這樣此題就被我們解決了。但是如果我們不是要求詢問次數(shù)，而是希望得到每一步詢問的策略，該怎么辦呢？ 為了讓大家深入理解遞推算法，我們在這里做進一步分析。,猜數(shù)問題的加強,仔細看上圖。事實上詢問的值Y已經提示出來了，Y是第f(i-1,j)+1個可能值。 在還剩下i次詢問，并累計j次XY回答就游戲

9、結束的情況下，若X可能的出現(xiàn)區(qū)間是L,R，則Y=L+f(i-1,j)。 下面是一個簡單的例子：,5f(3,2),7f(3,3),2f(2,1),3f(2,2),4,8,例子,上表是已經計算好的f值。 若N=6，K=2，查上表可以得出需要3次詢問才能保證猜出X。第一次詢問Y=4。 若N=13,K=3，查上表可以得出需要4次詢問才能保證猜出X。第一次詢問Y=8。,1,3,2,1,6,1,3,3,7,4,14,10,j=3,j=2,j=1,無論得到什么回答，都能解決！,被猜數(shù)X是1到N范圍內的整數(shù)，你可以詢問一個整數(shù)Y和X的大小關系。與普通猜數(shù)問題不同，提問的回答要在下一次提問之后才能獲得。給出N，

10、問最壞情況下需要多少次詢問才能猜出X。,由基本的猜數(shù)問題。 附加上條件：本次的回答要在下一個提問之后獲得。 本題最大的難點是：當詢問了一個值Y之后，下一次詢問之前我們得不到任何的訊息，必須盲目的再詢問一個值Y。 其實本題仍然可以用遞推的思想解決。,猜數(shù)問題的加強2,Y,小于Y的區(qū)域,大于Y的區(qū)域,到底將Y選在哪一邊呢？,Y,Y,猜數(shù)問題的加強2,我們設f(i)表示i次詢問能夠處理的區(qū)間最大的長度。 則可以知道若f(ans)N，f(ans-1)N則可知Ans即為所求的最少的詢問次數(shù)。 由于沒有其他條件的限制，大于Y和小于Y兩個區(qū)域是等價的。不妨設我們將Y詢問在了小于Y的區(qū)域：,猜數(shù)問題的加強2,

11、我們先詢問Y，然后再詢問Y。這時才能得到關于Y的回答。 若XY，則關于Y的詢問被浪費了。還剩下i-2次詢問機會。大于Y的區(qū)域的最大為f(i-2)。 若XY，則Y的詢問沒有被浪費，還剩下i-1次詢問機會。小于Y的區(qū)域最大為f(i-1)。,Y,小于Y的區(qū)域,小于Y的區(qū)域,Y,大于Y的區(qū)域,原問題的解決,上題的時間復雜度是O(Ans)。 至此兩個加強問題，已經被分別解決。 有了解決這兩個基礎問題的過程，再回來看原問題就比較容易了。,被猜數(shù)X是1到N范圍內的整數(shù)，你可以詢問一個整數(shù)Y和X的大小關系。與普通猜數(shù)問題不同，提問的回答要在下一次提問之后才能獲得。你要盡量避免詢問比X小的Y值，因為累計獲得K次

12、XY的答案就游戲結束。給出N、K，問在最壞情況下至少需要詢問幾次才能保證猜出X。,原問題的解決,設f(i,j)表示用i次詢問，在累計j次獲得XY的回答就游戲結束的情況下，最大能處理的區(qū)間長度。 先詢問Y，再Y。將Y詢問在小于Y的區(qū)域。 若XY，則Y的詢問浪費了，詢問次數(shù)減二，且會獲得兩次XY的回答，j值減二，所以大于Y的區(qū)域最長為f(i-2,j-2)。 若XY的回答，所以j不變。小于Y的區(qū)域最長為f(i-1,j)。,Y,小于Y的區(qū)域,小于Y的區(qū)域,Y,大于Y的區(qū)域,原問題的解決,做上面的分析之后是不是就足夠了呢？ 注意到由于有了另一個限制條件，使得小于Y的區(qū)域和大于Y的區(qū)域不再等價，我們必須討論Y詢問在大于Y的區(qū)域時的情況。 將Y詢問在大于Y的區(qū)域。 若XY的回答，j值不變。小于Y的區(qū)域最長長度為f(i-2,j)。 若XY，詢問次數(shù)減少1。得到了XY的回答，j減少1。大于Y的區(qū)域最長為f(i-1,j-1)。,Y,大于Y的區(qū)域,大于Y的區(qū)域,Y,小于Y的區(qū)域,原問題的解決,綜合上面，可以得出動態(tài)規(guī)劃公式： 邊界條件為：,原問題的解決,算法的框架就是利用得出的動態(tài)規(guī)劃轉移公式，依次計算f值。直到有一個Ans滿足f(ans,k)N,f(ans-1,k)N。則所求的最少次數(shù)為Ans。 這個算法的總時間復雜度為O(