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