1、猜數(shù)（guess）解題報告湖南 周戈林摘要 算法篩法時間復(fù)雜度O(C10L)空間復(fù)雜度O(L)問題簡述現(xiàn)有一個未知的長度為L的數(shù)，它的每一位都不相同。程序的目的是把這個未知數(shù)猜出來。它猜的方法是把一些長度為L的每一位都不相同的數(shù)提交給庫，庫則以整數(shù)P和Q來回答程序。其中P表示所猜的數(shù)與被猜的數(shù)有幾個對應(yīng)數(shù)位上的數(shù)字是相同的，Q表示所猜的數(shù)與被猜的數(shù)有幾個數(shù)字是相同的。我們的目標是使猜的次數(shù)盡量少。同時值得注意的是，被猜的數(shù)是完全隨機生成的。分析先看看人會怎么來猜這個數(shù)。最開始什么信息都不知道，只好胡亂試一個數(shù)。如果碰巧猜中了就結(jié)束，否則再試另外一個數(shù)，直到猜中了為止。這中間有個很重要的優(yōu)化：根

2、據(jù)以前猜數(shù)得到的反饋值，我們可以知道某個數(shù)有沒有可能是被猜的數(shù)，如果某個數(shù)不可能是那個數(shù)，當然就不必猜它。用人腦實現(xiàn)這種猜數(shù)策略，就得到最一種簡單的篩算法。每次猜數(shù)前都利用搜索搜出一些有可能為待猜數(shù)的數(shù)，然后從中隨機選擇一個試猜，如果猜中就結(jié)束，否則繼續(xù)上述過程。什么才叫有可能為待猜數(shù)呢？就是說如果這個數(shù)為待猜數(shù)，與之前庫返回的信息就不會互相矛盾，對應(yīng)的P, Q值就會相同。現(xiàn)在的問題就是如何搜索以及確定搜出的待測試數(shù)數(shù)目。基本的搜索框架肯定是直接搜索每一位上的數(shù)字。但是對于L=10這種數(shù)據(jù)硬搜是非常慢的，因此我們要進行剪枝。剪枝一：如果某個已測試數(shù)的P, Q值小于跟當前搜出的位數(shù)對比的P, Q

3、值，那么就可以剪枝。剪枝二：如果某個已測試數(shù)的P, Q值大于跟當前搜出的位數(shù)對比的P, Q值加上剩下的位數(shù)，那么就可以剪枝。加上兩條剪枝，另外再把每次搜數(shù)的數(shù)量控制為不超過10個 L較小時可以適當多一些。，就可以保證在時限內(nèi)出解。表1是測試結(jié)果 L較小時可以適當多一些。 測試環(huán)境為P42.5GHz, 256MB內(nèi)存。表 SEQ 表格 * ARABIC 1數(shù)據(jù)編號用時平均次數(shù) 前面的用時表示標準數(shù)據(jù)用時。這里的平均次數(shù)表示猜測1000個隨機產(chǎn)生的長度與對應(yīng)文件相同的數(shù)需要詢問的平均次數(shù)。Good值guess1.in0.05s5.25times5.30timesguess2.in0.05s5.30

4、times5.30timesguess3.in0.16s5.49times5.50timesguess4.in0.42s5.95times6.00timesguess5.in0.22s6.64times6.70timesguess6.in0.08s7.53times8.00timesguess7.in0.25s8.61times9.50timesguess8.in1.36s9.89times10.50timesguess9.in0.38s11.00times100.00timesguess10.in5.50s同上12.00times從表1可以看出我們的算法足以在時限內(nèi)出解，并且平均詢問次數(shù)都在

5、Good值的范圍內(nèi)。但是當L=2,3,4,5,6的時候平均詢問次數(shù)與Good值非常接近，對于只有100個數(shù)的數(shù)據(jù)容易超過Good值而導(dǎo)致失分，因此我們要對詢問進行一些優(yōu)化。假定我們現(xiàn)在搜得了一些待測試數(shù)，那么挑哪個去測試效果會比較好呢？我們希望用這個數(shù)測試之后在最壞情況下能刪除盡量多的待測試數(shù)。我們定義待測試數(shù)集合為S，設(shè)函數(shù)fi, j和gi, j表示兩個待測試數(shù)i, j進行對比得到的P和Q值。那么令，公式 SEQ 公式 * ARABIC 1第i個待測試數(shù)的選擇價值就是。公式 SEQ 公式 * ARABIC 2value值實際上就是統(tǒng)計P,Q值的方差，我們在value值最小的待測試數(shù)中隨機選擇

6、一個進行測試。每次計算所有的value值需要O(m2)時間，其中m是待測試數(shù)個數(shù)。當m很大時，計算value值需要非常長的時間，并且數(shù)太多時這樣計算的value值不具有代表性，因此我們只在m200的情況下才使用這種方法選數(shù)，其他情況下仍然隨機選數(shù)。優(yōu)化后的算法運行結(jié)果如表2：表2數(shù)據(jù)編號用時平均次數(shù)Good值guess1.in-5.35times5.30timesguess2.in-5.11times5.30timesguess3.in-5.32times5.50timesguess4.in-5.78times6.00timesguess5.in-6.43times6.70timesguess6.in-7.38times8.00timesguess7.in-8.52times9.50timesguess8.in-9.68times10.50timesguess9.in-10.87times100.00timesguess10.in-同上12.00times絕大多數(shù)情況下的詢問次數(shù)都有了明顯的減少，但是當L=2時的平均次數(shù)反而增加了！這是因為這時P,Q值的情況太少，所以當L=2