基本題
現在甲選定1~15其中一個數字，讓乙來猜，
但甲最多只有一次說謊的機會，請問乙要怎樣來猜比較好
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: arist.m7.ntu.edu.tw
> -------------------------------------------------------------------------- <
作者: KMS (幾何三賤客<K>) 看板: puzzle
標題: Re: 猜數字
時間: Thu Jul 13 11:00:23 2000
※ 引述《arist (這實在是太複雜了)》之銘言：
: ※ 引述《noblesse (小狐狸)》之銘言：
: : 這跟二分逼近好像一樣……
: : 1～7 8～15
: : ↓ ↓
: : 1～3 4～7 8～11 12～15
: : ↓ ↓ ↓ ↓
: : 1 2 3 45 67 89 1011 1213 1415
: : 然後就出來了……
: : 蠻白痴就是了
: 不過這是沒有說謊的情況下
聽說最少要用 7的問題...
假設已用了四個問題得到一個答案(如 1100)
再問前兩位對不對..若回答對..則只前兩位正確
若回答不對則..前兩為有一位是錯的..
再問第一位是否正確及可得到前兩位之答案 (答"是"則是 10 答"否"則是01)
同樣的問題在問後兩位..
用樹枝圖來看就是
11 00
前兩位對否? 否 對 對 否 後兩位對否?
第一位對否 否 11 00 對 否 第三位對否?
10 01 01 01
應為只說謊一次..所有不會出現兩次否的答案..故只要問三的問題
--
即使人的腦袋變得簡單的足以被了解,
人們依舊將愚蠢的無法了解它.
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: laplace.math.ntu.edu.tw
> -------------------------------------------------------------------------- <
作者: JKD (賭神趙三) 看板: puzzle
標題: Re: 猜數字
時間: Thu Jul 13 11:16:59 2000
※ 引述《KMS (幾何三賤客<K>)》之銘言：
: 再問第一位是否正確及可得到前兩位之答案 (答"是"則是 10 答"否"則是01)
你這種做法已經假設甲一定有一個回答是說謊,當甲全部說實話時會誤判.
Hamming code 應該是可以解決這個問題,不過細節我忘了,也沒有書,正在問別
人...
--
★
｜ ╭╮
● ╰╯ ●
｜◥██◤
██ 來! 變個魔術瞧瞧......。 我是妙手宗!
http://crypto.ee.ntu.edu.tw/~magic/PuzzleWorld.html
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: h115.s32.ts30.hinet.net
> -------------------------------------------------------------------------- <
作者: KMS (幾何三賤客<K>) 看板: puzzle
標題: Re: 猜數字
時間: Thu Jul 13 12:57:07 2000
※ 引述《JKD (賭神趙三)》之銘言：
: ※ 引述《KMS (幾何三賤客<K>)》之銘言：
: : 再問第一位是否正確及可得到前兩位之答案 (答"是"則是 10 答"否"則是01)
: 你這種做法已經假設甲一定有一個回答是說謊,當甲全部說實話時會誤判.
: Hamming code 應該是可以解決這個問題,不過細節我忘了,也沒有書,正在問別
: 人...
關於 Hamming code 是可以解決這個問題...不過會令人覺的兜了一圈..
得到答案卻沒什感覺...
考慮將 1-15用進二制表示則可用 1000,0100,0010,0001來表示...
則糾一個錯的 hamming code 為用 1000011 0100101 0010110 0001111
來取代 1000 0100 0010 0001..於是 1-15 各有一個對應的 7 位數
1 = 0001111
2 = 0010110
3 = 0011001
4 = 0100101
5 = 0101010
如此等等...而要問的第n個問題就是你想的數第n的位數是不是 1
如此得到一組 7 位數...在代到下列矩陣...
0 0 0 1 1 1 1
[0 1 1 0 0 1 1] * [ 所得是七位數(直列)]
1 0 1 0 1 0 1
將得到一個 3x1 的矩陣..視其為一三位數..可當其為 0 時表示對方都沒有說謊
當其值為 n (1-7,換回十進制)..則表是第 n 為是錯的...則改正後及可得確解..
--
即使人的腦袋變得簡單的足以被了解,
人們依舊將愚蠢的無法了解它.
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: web03.math.ntu.edu.tw