推 LPH66 :允許說一次謊→收到的回答可能有一個 bit 錯誤 12/15 12:50
→ LPH66 :再回想一下你所學到的東西就知道這兩題要怎麼答了 12/15 12:51
不好意思,小弟想請教編碼作業裡的一道題目:
The host has chosen a random integer n from between 1 and 15 and you would
like to guess the number n with the least number of question.
Suppose the answer for each question can
only be either true or false.
(a) Show that 4 questions are enough to find n.
Proof:
Expressing the numbers by nonzero binary codewords,
each of the codewords has 4 digits.
Hence 4 questions are enough to find n.(Q.E.D.)
(b) Show that if the host is allowed to lie once, then 7 questions are
enough to find n.
(c) Write down the 4 questions that you are going to ask in (a).
Answer:
(1) Is the first digit 0 or 1?
(2) Is the second digit 0 or 1?
(3) Is the third digit 0 or 1?
(4) Is the fourth digit 0 or 1?
(d) Write down the 7 questions that you are going to ask in (b).
目前(a)和(c)已經有端倪了(答案已經寫在上面),但不曉得允許說一次謊會有何影響?
懇請各位高手提示,非常感謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.223.244.244