作者eieio (好多目標)
看板puzzle
標題Re: [問題] 猜數字要幾次才猜的到?
時間Mon Jan 10 16:11:47 2011
※ 引述《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
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 68.190.205.96
推 KitWoolsey:WOW!!!! BINGO 01/10 21:42
推 cj6u40:感覺好專業( ̄ー ̄;) 01/14 19:58