香港新浪網 MySinaBlog
« 上一篇 | 下一篇 »
軒爸 | 24th Apr 2009 | 一般 | (3007 Reads)

小影發起了一個quiz, 公開邀請大家以編程解決「無聊問題」. 小影自己和Jacky都分別寫了程序決這問題. 於留言, 我已為「無聊問題」討論過了, 但以編程討飯吃的, 又豈能齋up. 不過, 概然Jacky已實作了我和Clement T第一個想出來的算法, 我就以另一算法再實作一個.

我的程序, 主要以Tree Search解決問題. 有趣的地方是, 那算法聽起來有少許複雜, 但寫出來卻很簡潔. 不會編程的人只知世上只有兩種程序, 會跑和不會跑的, 就是不明白甚麼叫「elegant」的code. 我想, 這就是個一例子了.

算法上次說了, 今次說說編程技巧吧.
(1) Recursive Function
我的實作, 主要運用了Recursive Function(遞迴函數). 一個function會不斷自己call自己, 或兩個function不斷互call. 凡是能以樹狀形式說明的算法, 多能以Recursive Function解決.



(2) Base Case和Termination Condition
用Recursive Function, 主要要決定Base Case和Termination Condition. 我這程序的Base Case就是「全散叫」清單, 然後不停組合不同套餐, 直至不能再組成其他餐, 就是Termination Condition了. 處理Termination Condition一般要很小心, 因為Recursive Function不像iteration, Termination Condition會寫在特定地方[如:while(!term_condition)]. 而且End Condition一般也不會像iteration那樣直觀.

(3) nCr vs nPr
另一個運用技巧, 就是如何控制Recursive Function跑nCr次而不是nPr次. (效能差很遠的!)
這點嘛, 舉例說明會簡單點. 如果不加控制(即nPr), 若你的最後結果是有3個餐, 這個最佳結果你會計到6次.
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
然而, 我們其實只想要一次就夠了. 要選一個的話, 最易處理的就是[1,2,3]. 所以, 只會我們控制著X1<=X2<=X3<=...<=Xi, 最佳結果就只會出現一次. 以文字來說, 就是若組合到了一個3號餐, 之後程序只會試組4,5,6... 號餐. (註:也是因為這個原因, 我一開始在Constructor替餐編了號.)

(4) 「省得最多」
第4個值得一提的地方, 是全個算法並沒有計算餐的總價, 而是計每次組合後, 可省下多少錢.
所以, 這算法是在找一個「省得最多」的組合, 而不是「最平的組合」. 只計算「省多少」, 在運用Recursive Function時比較方便.

(5) Trace by Stack
最後, 就是如何追蹤Best Case了. Recursive Function是比較難追蹤的, 我就用了一個平時很少會用到的java.util.Stack. 一進入一個Recursive, 就push()一個餐, 離開就pop()一個, 就能簡單追蹤正在試組甚麼餐, 之前又組過了甚麼餐了.

大概就是這樣. 大家若有興趣的話, 歡迎從github.com下載來研究研究.
Hmm... 正期待下一個無聊問題...

 


[1]

這個方法確很優雅!還有這篇文章作導讀,學到很多野呢!nPr 變成 nCr 真是小改變大改善呀

P.S. 可到此看示範:http://mealcalculator.appspot.com/


[引用] | 作者 小影 | 25th Apr 2009 | [舉報垃圾留言]

 

Google 廣告
最新留言
網誌統計
文章總數:45
留言總數:301
引用總數:14
閱讀總數:247380
總瀏覽數:384069
MySinaBlog 精選文章