前情提要： 關于猜數字解法的討論（以中階規則為例）
由于月亮對初階的最優次數究竟是不是5次產生了疑問，我抽了周一早八的時間寫了個初階猜數字的算法，并且跑了一下。萬萬沒想到，寫代碼半小時，跑代碼……我從早八下課早上十點跑到了今天凌晨五點半 心疼電腦。甚至我連 Gal 測評都沒更新。
有一些中階帖子里提到的內容我可能會略過不講，感興趣的請看前情提要。
一·算法設計
這次的問題針對的是初階規則，與中階不同的是，初階規則是有重復數字的，由于只有 0-5，即一共有 6^4=1296 種組合。我們只需要將 1296 種可能的數字看作一個解的集合，通過一次次地猜測來縮小這個解集，最后可以把解集鎖定在一個，那么這個解就是答案的數字。
猜數字的結果一共有 (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 種可能，要判斷猜哪個數可以將解集縮到最小，只需要遍歷 1296 個可能。在這里和中階帖子里出現了算法設計的分歧，在選擇猜數的策略上，中階我們選擇的是解集大小的期望重視，也就是說最后會傾向于解決問題的期望步數最少，另外有一個相近的算法是步數期望型，即不是進行直接加權平均而是對解集大小取對數（即需要縮小的步數）再加權平均。這兩種方法會傾向于多次猜數字下的平均步數更少。而月亮的疑惑是最壞情況下的最少步數，所以我們改變策略，選出十四種可能里最大的一種可能，也就對應最壞情況。之后在遍歷的所有解集數字里找出最壞情況下解集最小的一個，也就是最壞情況下的最優猜數。在這種情況下，可能平均步數不是最少，但盡量保證了考慮最壞情況。
二·代碼實現
上次是用 python 實現的，這次考慮到性能的差距于是寫了下 c++。
首先和上次的區別是因為存在可重復數字，所以不能用上次的向量來取巧，采用了遍歷映射到數組來計數，具體可以參考leetcode 299.猜數字游戲
然后需要一個函數得出最能縮小解空間的解，按照算法設計中的步驟進行三層循環即可，上次為了省事只在解集內取猜數結果爆了兩次最優解以外的情況，這次不敢偷懶了（結果時間幾何倍數增長 ）
需要一個函數幫助縮小解空間，只需要遍歷解空間，將 xAxB 與結果不符的剔除即可，這個函數不變
最后只需要從“0000”循環檢驗到“5555”統計最終結果即可。
三·問題與優化
采用了和中階相同的優化方法，先跑一遍找出全集中的最優第一次猜數“0011”（評估相同取靠前的數），將所有結果對應的最優縮小數以及所對應的縮小后的解空間打表，省去了第一次猜數計算的時間，大大降低了時間復雜度。
將猜數的范圍限制在解空間內是一個潛在的隱患，是否存在影響仍需要嚴格的數學證明，可惜我懶這次沒有這個隱患了，但是我的電腦有隱患了，跑了整整一天。
優化后的最終代碼部分見附圖
四·統計結果
| 猜數次數 | 1 | 2 | 3 | 4 | 5 | | 出現次數 | 1 | 6 | 25 | 239 | 1025 |
期望約為 4.76 次，方差約為 0.26，最大值為 5 次
測試結果見附件
五·總結
遍歷了整個可能的解空間，證明了在最壞情況重視的策略下，可以做到 5 次之內猜出數字。
期望在 4.76 次，1296 次里有超過 1000 次是在5次的情況下猜出來的，可見該策略考慮的較為極端，也因此面對最壞情況得到的結果與普通情況也較為平均。
高階在有重復的情況下還多了數字，比初階大了一個數量級左右，初階我跑了一天，高階？不可能去做了。 |
