Re: [問題] 猜牌的遊戲

[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 等地方

--
要不要把這一大段貼回姿勢佳呢...(思)

--
いああオレたちには見えてるモノがあるbデ きっと誰にも奪われないモノがあるはずさ
け  開口一番一虚一実跳梁跋扈形影相弔yュL羊頭狗肉東奔西走国士無双南柯之夢  歪も
ぶ    　意味がないと思えるコトがある ラPきっとでも意図はそこに必ずある    んの
く  依依恋恋空前絶後疾風怒濤有無相生 ラH急転直下物情騷然愚者一得相思相愛  だが
ろ                    無意味じゃない ラ6あの意図が                        恋た
で  有為転変死生有命蒼天已死黄天當立 !!6五里霧中解散宣言千錯万綜則天去私  のり

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.28.92
推 lighttodie:那要把牌減少到幾張  就可以100％猜對呢？
→ LPH66:三個問題的話只能猜兩張 XD (也就是Hamming(3,2))
→ LPH66:呃  Hamming(3,1) 才對
→ LPH66:就是最簡單的 {1,2}, {1}, {2} 這種問法
→ puzzlez:噗  要貼到知識+ 首先要擔心對方能不能看懂XDDDD
推 lighttodie:如果這樣問 {1},{1},{1}  只有一次謊話  也可以知道吧
→ LPH66:也是可以啊
推 lighttodie:總有一天會要學到....
→ LPH66:這也是我們電資這方面的人才會學吧...(編碼理論的東西)
推 lighttodie:資工也該會學到吧
→ LPH66:對啊  所以我說電資啊 (我自己就是資工的)
→ rofellosx:沒學過...(資工)