近日論壇解謎游戲多了猜數(shù)字，出于求知的目的，花了一點(diǎn)時間（大部分時間打游戲去了）考慮了一下猜數(shù)字的解法，基于程序設(shè)計來探求解法的可行性以及在x次內(nèi)猜出數(shù)字的數(shù)學(xué)期望。寫在前面，本貼所有內(nèi)容和結(jié)論僅供交流學(xué)習(xí)，不建議通過本貼內(nèi)容作弊，關(guān)于代碼的一部分內(nèi)容我也會封在另一個文件里避免有人用來進(jìn)行作弊。
一·算法設(shè)計
由于在考慮算法的時候，我點(diǎn)開了中階的猜數(shù)字，進(jìn)不了其他階的猜數(shù)字，所以本貼的解法以中階的規(guī)則為基礎(chǔ)。等到有空了會考慮設(shè)計一下高階的解法。
托中階的福，沒有重復(fù)數(shù)字，因此所有數(shù)字都是完全等價的，我們只需要將 5040 種可能的數(shù)字看作一個解的集合，通過一次次地猜測來縮小這個解集，最后可以把解集鎖定在一個，那么這個解就是答案的數(shù)字。
猜數(shù)字的結(jié)果一共有 (0,0),(0,1),(0,2),(0,3),(0,4),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1),(2,2),(3,0),(4,0) 14 種可能，要判斷猜哪個數(shù)可以將解集縮到最小，只需要遍歷 5040 個可能，將每個可能所對應(yīng)的 14 種可能結(jié)果所得到的縮小解集大小加權(quán)求和，即最后的解集期望。我們只需要挑選其中解空間最小的一個，就是我們下一個要猜的數(shù)字。
二·代碼實(shí)現(xiàn)
本人基于 python 實(shí)現(xiàn)該功能。
首先需要解決的是輸入一個猜的數(shù)字，通過與答案的計算得到 xAxB 的結(jié)果。
A是數(shù)字和位置都正確，那么我們只需要把兩個數(shù)字看作向量，向量相減后求結(jié)果為 0 的維數(shù)即可。
B是數(shù)字正確位置不正確，萬幸沒有重復(fù)數(shù)字，只需要把兩個數(shù)字看作集合，求出交集大小即為正確的數(shù)字個數(shù)，減去A就是B了
然后需要一個函數(shù)得出最能縮小解空間的解，按照算法設(shè)計中的步驟操作即可。這里按理說應(yīng)該每次都遍歷完整的 5040 種可能，但是由于我需要多次計算來得到統(tǒng)計結(jié)果，所以擅自將遍歷的范圍縮小到解空間內(nèi)，不知道是否會對計算的最壞情況下最少次數(shù)產(chǎn)生影響，在嚴(yán)格意義下該代碼非最優(yōu)解法。
同時需要一個函數(shù)幫助縮小解空間，只需要遍歷解空間，將 xAxB 與結(jié)果不符的剔除即可
最后再加點(diǎn)細(xì)節(jié)以實(shí)現(xiàn)一個從生成隨機(jī)數(shù)，記錄猜數(shù)過程到輸出猜數(shù)結(jié)果的最終猜數(shù)函數(shù)
將猜數(shù)函數(shù)循環(huán)調(diào)用以得到統(tǒng)計學(xué)結(jié)論
三·問題與優(yōu)化
由于第一次猜數(shù)時需要在全集內(nèi)進(jìn)行遍歷，較為消耗時間，考慮到猜數(shù)結(jié)果的可能較少，以及第一次猜數(shù)時所有數(shù)等價，我固定第一次猜的數(shù)為 0123 ，將所有結(jié)果對應(yīng)的最優(yōu)縮小數(shù)以及所對應(yīng)的縮小后的解空間打表，省去了第一次猜數(shù)計算的時間，大大降低了時間復(fù)雜度。
將猜數(shù)的范圍限制在解空間內(nèi)是一個潛在的隱患，是否存在影響仍需要嚴(yán)格的數(shù)學(xué)證明，可惜我懶
優(yōu)化后的最終代碼部分見附圖
四·統(tǒng)計結(jié)果
其實(shí)我本來跑了兩千多組數(shù)據(jù)，但是跑完了發(fā)現(xiàn)加權(quán)的部分寫了一點(diǎn)點(diǎn)Bug，天亮了又來不及重跑，只能草草跑 1000 組意思一下。考慮到猜數(shù)字次數(shù)的結(jié)果基本小于10，1000次應(yīng)該能得到一定意義的統(tǒng)計學(xué)結(jié)果。
| 猜數(shù)次數(shù) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | 出現(xiàn)次數(shù) | 0 | 4 | 20 | 118 | 416 | 385 | 57 |
期望約為 5.329 次，方差約為 0.739，最大值為 7 次
測試結(jié)果見附件
五·總結(jié)
實(shí)際上只需要遍歷整個解空間的 5040 組數(shù)據(jù)就可以得到完整的解情況，但是我懶得跑了，隨便隨機(jī)跑了1000組統(tǒng)計一下看看結(jié)果。
從結(jié)果上看該算法平均需要 5 次左右得出正確的數(shù)字，且大部分的次數(shù)分布集中在期望附近，邊緣的次數(shù)分布較少。即使在最壞情況下也只需要猜測 7 次即可得出正確數(shù)字（未數(shù)學(xué)證明）。
高階的數(shù)字組合存在重復(fù)數(shù)字，解空間大了一個數(shù)量級，同時由于重復(fù)數(shù)字的存在 xAxB 的計算方式也需要重新設(shè)計，凌晨寫了一下下還是放棄了，有空再繼續(xù)寫。
——————————————————————————————————————————————————————————————
補(bǔ)充：
花了幾個小時把 5040 種跑完了，出現(xiàn)了兩個 8 次猜測，目前不知道是重視縮小期望而忽略極值的原因還是因?yàn)闉榱丝s小時間而把猜的范圍限制在解空間的原因。
結(jié)果如下
| 猜數(shù)次數(shù) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | 出現(xiàn)次數(shù) | 1 | 13 | 108 | 638 | 2061 | 1925 | 292 | 2 |
期望為 5.321 方差為 0.577
期望和方差都更小了 |
