猜數字要幾次才猜的到? - 拼圖

※ 引述《KitWoolsey (貓)》之銘言：
: Let n be a positive integer, and x an unknown non-negative integer less than
: n.
: Suppose you may ask questions of the form "Is x less than t?",
: where t is an arbitrary integer,
: but the answer to each question will be told only after
: you ask another question (i. e., the answers are delayed by one question;
: note that the last question will not be answered at all). How large may n be
: so that you can still guarantee to determine x with only 30 questions?
: 令N為一正整數, x是一比n小的非負整數.
: 假設你可以提問如" x是否比t小?" 這種類型的問題 , t是多少由你自己決定.
: 但是對方的回答會在你問下一問題之後回答----也就是回答會"延遲"一題才答出
: (也就是說 你問的最後一個問題根本就不會被回答XD)
: 那麼假如你問30個問題就保證可以知道x是多少,n的最大值是多少?
我的答案是費氏數列 F_31 = 1,346,269，希望沒錯。

假設問 k 次可以處理到 n=f(k)，那麼第一個問題應該是問是否 x<f(k-1)，
第二個問題則是先假設 x<f(k-1)，並問出相應的問題。當第一個問題的答案是
yes 時，因為第二個問題已經問對了，所以剛好可以處理。當第一個問題是答案
是 no 時，第二個問題失去價值。剩下 k-2 次機會，只能處理 f(k-2) 個數字
。因此 f(k) = f(k-1) + f(k-2)。接下來是看起始的數列：

次數 max n 問題
0 1 n=1 就只能是 x=0，不用問
1 1 any，問了也沒用
2 2 x<1? any
3 3 x<2? x<1? any
4 5 x<3? x<2? (x<1? or x<4?) any
上面第三個問題要根據第一個問題的答案來問，就可以知道最後答案。

這個數列是平移了一項的費氏數列。所以得到答案為 F_31。下面是檢查可以
問 5 次時，如何利用上面的答案來構造要問的問題：

次數 max n 問題
5 8 x<5? x<3? ？

這裡接下去的狀況是這樣：如果 x<5，那麼我們花掉了一次提問，也把範圍縮到
0-4，是問四次可以搞定的範圍，而且我們也問了 x<3? 這個問四次搞定 0-4
時所需要的第一個問題，因此就直接把問四次的計畫整個搬來。

如果 x<5 的回答是 no，那麼 x<3? 這個問題的答案我們不需要再去聽了，沒有
任何幫助。我們剩下三次提問，就把問三次的計畫，從 0-2 平移到 5-7 即可。

次數 max n 問題
5 8 x<5? x<3? (if x<5) x<2? (x<1? or x<4?) any
(if x>=5) x<7? x<6? any

--
If I don't know I don't know, I think I know
If I don't know I know, I think I don't know
── R. D. Laing

--