Re: [問題] 猜牌的遊戲

看板puzzle作者andan (Everything)時間15年前 (2010/10/21 01:24)推噓3(3推 0噓 9→)

留言12則, 3人參與討論串5/6 (看更多)

七次的確也是最佳解了給個簡易版的證明概念假設六次可以表示我們要創作出6位元的0-1字串兩兩距離不能是0 or 2 算一下就會發現 0個1的共1組 1個1的最多只能放1組 2個1的最多只能有3組 3個1的最多也3組 4個1的最多也3組 5個1的最多1組 6個1的總共就1組全部加起來才13組~ 其中還有很多互斥的組, 比如選了0個1的就不能選2個1....etc 所以13組是不可能的! 因此七次的確是最佳解~ ※ 引述《LPH66 (-858993460)》之銘言： : 原題目恕刪 : 這裡提供一個問七次可以保證猜中的問法 : (同樣限定恰說謊一次) : 這七個問題是: 分別詢問是否出現在下列集合當中 : {A,3,4,6,8,T,K} : {A,2,5,6,8,J,Q} : {8,9,T,J,Q,K} : {A,2,4,7,9,T,Q} : {4,5,6,7,Q,K} : {2,3,6,7,T,J} : {A,3,5,7,9,J,K} : 這些問題有個特性: : 對任何兩個數字至少有三個問題兩者恰出現其中之一 : 因此對任何一個數字恰錯一題的答案對其他數字至少錯兩題 : 所以只要一個一個對答案對過去恰錯一題的數字就是它了 : --- : 這題目和所謂的容錯/糾正碼有關 : 如果把在七個問題裡回答是或否標記成 1 或 0 的話 : 這便是要我們尋找一個編碼使得它能夠發現且修正單一 bit 的錯誤 : 上面給的答案使用的是 Hamming(7,4) 編碼 : http://en.wikipedia.org/wiki/Hamming(7,4) : 它使用 7 bits 來編碼 4 bits 的資訊 : 使得當這 7 bits 中有不多於 1 bit 的錯誤時能夠發現並修正它 : 這個題目範圍是 1 ~ 13 正好是 4 bits 的資訊 : 所以套用這個編碼就成了這個答案了 : (仔細看的話, 第 3,5,6,7 四個問題組合起來正好是各數字的二進位 : 也就是正好是 Hamming(7,4) 當中的資料位) : 使用 Hamming 編碼能夠以 2^m-1 bits 來編碼 2^m - m - 1 bits 的訊息 : 以發現且修正單一 bit 的錯誤 : 這類型的編碼通常是在通訊理論上使用減少通道雜訊影響傳輸正確性 : 其中一種很常用的編碼 Reed-Solomon 編碼 (比 Hamming 更強它能修正更多 bit) : 廣泛使用在諸如 RAID 6, QR code, DVD/藍光光碟, WiMAX 等地方 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.193.20.2

推

ACGfans

10/21 01:51, , 1^F

10/21 01:51, 1^F

→

ACGfans

10/21 01:52, , 2^F

10/21 01:52, 2^F

→

ACGfans

10/21 01:54, , 3^F

10/21 01:54, 3^F