一、前言
24點游戲是一個常見游戲,出題者給出4個整數,要求答題者在指定時間內給出一個四則運算的表達式,恰好用上這這個整數各一次,計算結果為24,超出時間為輸。
二、分析
用計算機來算這個題,搜索速度當然有很大優勢,我編程喜歡考慮通用一點,不限制輸入數量和結果數,甚至不限制運算符數量。這樣組合數就很大,如果輸入數比較多,則搜索時間會非常長。
我用兩個方法來提高搜索速度:一、是大家都能考慮到的重復搜索問題,比如1,2,3和2,3,1所有的組合情況是相同的,我只搜索使用遞增序的數組,則可以降低一個組合數的數量級別;二、使用動態規劃中的備忘錄方法,比如你計算出2和3所有可能的計算結果,則他們與4結合的時候,要用到,與1結合的時候,也要用到,使用備忘錄,可以只計算一次,大大降低運算復雜度。
三、設計
整體設計:分別設計4個類:游戲、表達式、運算、分數,各司其責,結構清晰,易于擴展。
標簽:
上傳時間:
2014-01-13
上傳用戶:zhangyigenius