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