集訓(xùn)隊(duì)2002ulam的游戲及編碼

東北育才學(xué)校俞瑋Ulam的游戲和編碼63Ulam的游戲12457有n個(gè)數(shù)字。其中有一個(gè)與其他的不同，是游戲者所選定的。你可以提出“這個(gè)數(shù)字在集合X中嗎？”這樣的問(wèn)題。你能收到的答案只有“是”或“否”。可能會(huì)有一個(gè)錯(cuò)誤的回答，但不多于一個(gè)。用盡可能少的提問(wèn)次數(shù)求出這個(gè)選定的數(shù)字。原型題目及解法同樣是n個(gè)數(shù)字，選定一個(gè)。問(wèn)題的方式也是一樣。但回答中不包含錯(cuò)誤。解答：使用二分法。logn次提問(wèn)。每次把可能為選定數(shù)字的那些數(shù)字分成盡可能相等的兩個(gè)部分。以其中一個(gè)部分作為問(wèn)題中的X。按照回答，去掉不可能為選

定數(shù)字的數(shù)字。結(jié)果為最后剩下的一個(gè)數(shù)字。二分法還是篩選法我們的二分法只是一種比較貪心的篩法。讓算法在最壞的情況下篩去的數(shù)字最多。二分，按錯(cuò)誤分類(lèi)原理：平分的不是數(shù)量。平均分的為選定數(shù)字的可能性。兩個(gè)部分包含選定數(shù)字的可能性是相等的。實(shí)現(xiàn)：對(duì)于每個(gè)數(shù)字，找出回答錯(cuò)誤幾次后，它才可能為選定數(shù)字。按照該次數(shù)，對(duì)數(shù)字進(jìn)行分類(lèi)。每一類(lèi)中的數(shù)字可能為選定數(shù)字的可能性都是相等的。盡可能平均分每一類(lèi)的數(shù)字，并各取一部分作為問(wèn)題中的X。圖一：一個(gè)操作實(shí)例圖中的兩列分別代表兩類(lèi)，所對(duì)應(yīng)的列上非空白的部分屬于該類(lèi)。陰影部分被判定為不包含選定數(shù)字的一部分。72456138二分法的次數(shù)估計(jì)第一類(lèi)中的數(shù)字在k次提問(wèn)后的數(shù)目：n/2k個(gè)方格。第二類(lèi)中的數(shù)字在k次提問(wèn)后的數(shù)目：設(shè)為f(k)。可知f(k)=f(k-1)/2+n/2k。f(k)=kn/2k。當(dāng)?shù)谝欢?lèi)中的數(shù)字只有一個(gè)時(shí)，即確定了答案：f(k)+n/2k≤1。2k≥kn+n。新的方法—編碼篩選法的限制：結(jié)果的保存。對(duì)上一次結(jié)果的依賴。邊界條件的處理。新的編碼方法：為每一數(shù)字賦一確定的二進(jìn)制編碼。第i個(gè)問(wèn)題編碼第i位為1。結(jié)果編碼：Y1，N0。答案：編碼與結(jié)果編碼一樣的數(shù)字。圖二：編碼的例子對(duì)于每次的回答，我們?cè)谙鄳?yīng)的列中把對(duì)應(yīng)的答案都標(biāo)記為高亮。一行均為高亮的數(shù)字和結(jié)果編碼一樣的數(shù)字。1234567821312345678213YYN12345678213110110錯(cuò)誤與糾錯(cuò)碼錯(cuò)誤：m次回答中有一個(gè)錯(cuò)誤n位編碼中有一個(gè)錯(cuò)誤。對(duì)不同的回答編碼對(duì)不同的錯(cuò)誤編碼。糾錯(cuò)碼的設(shè)計(jì)：使用奇偶校驗(yàn)碼，糾錯(cuò)碼為其他編碼的二進(jìn)制加法和。一位編碼的錯(cuò)誤將會(huì)導(dǎo)致所有相關(guān)等式的不成立。假設(shè)非糾錯(cuò)碼位是正確的，找出“錯(cuò)誤”的糾錯(cuò)碼位。如果沒(méi)有，那么沒(méi)有錯(cuò)誤。如果只有一個(gè)，錯(cuò)誤的是糾錯(cuò)碼位。如果有多個(gè)，錯(cuò)誤的是對(duì)應(yīng)的非糾錯(cuò)碼位。圖三：糾錯(cuò)碼的構(gòu)造m=logn=4，所以由2km+k+1知k即糾錯(cuò)碼的位數(shù)至少為3。X5X6X7X1X2X3X4X4X4X3X2X1===??????X5X6X7X5X6X7X1X2X3X4X7X6X5X5X6X7X1X2X3X4X4X4X3X2X1X7X6X5圖四：糾錯(cuò)碼與實(shí)際問(wèn)題的對(duì)應(yīng)對(duì)編碼的異或運(yùn)算等價(jià)于對(duì)問(wèn)題本身的異或。以X5=X2X3X4

為例。X5X2X3X4=??有關(guān)問(wèn)題次數(shù)的一些結(jié)果二分法的次數(shù)：2k≥kn+n的最小解k。編碼方法的次數(shù)：除去必需的m位有效信息外，每個(gè)錯(cuò)誤對(duì)應(yīng)一個(gè)糾錯(cuò)碼：2k-m≥k+1。所有的可能性每個(gè)至少對(duì)應(yīng)一個(gè)不同的編碼：2k≥2m(k+1)。結(jié)果：滿足不等式2k-m≥k+1的最小解k。兩者的比較：m=logn，2k≥kn+n2k≥k2m+2m2k-m≥k+1。擴(kuò)展1：更多錯(cuò)誤時(shí)的解法在此情況下，編碼方法的擴(kuò)展是很困難的。對(duì)于二分法的擴(kuò)展：加入更多的分類(lèi)，最多k個(gè)錯(cuò)誤的時(shí)候分為k+1類(lèi)。平分每一類(lèi)。72456138擴(kuò)展2：更多的回答，稱(chēng)球問(wèn)題篩選方法需要保存更多的元素。編