香港新浪網 MySinaBlog
軒爸 | 24th Apr 2009 | 一般 | (3003 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... 正期待下一個無聊問題...

 


軒爸 | 17th Apr 2009 | 一般 | (2941 Reads)
電鋸問了一個「無聊問題」, 答案已到其blog回覆. Generic的解, 就寫到這裡來.

問題:
首先, 假設某餐廳有m種食品, 亦有n種餐可供選擇. 每個餐可包含2種或以上的食品. 而買餐的價錢, 就會比散買要平.
問題是, 如果要買一堆食品, 要叫那幾個餐(可重覆)加散買那幾個食品, 才是最便宜呢?
(不過, 先剔除一個情況, 就是就算「部份叫餐」比「全散買」有機會買多了食物, 卻仍然平些.)

解:
第1步, 就是由Worst Case開始, 即是「全散買」.
第2步, 就嘗試合成一個餐, 這裡可以出現n個可能.(因為有n種餐)
第3步, 跟據上面的每個可能, 嘗試把餘下的再合成另一個餐. 這裡可以出現nC2個可能.(因為先組合1號餐再組合2號餐, 和先組合2號餐再組合1號餐, 是一樣的.)
然後, 第4, 5, 6 .... 一直做, 直至不能再組合任何餐.
假設做到第6步就完, 就最多可以出現nC5個可能.
最後, 將這nC5(實際情況會少得多)個可能, 都計個總和, 就知那個組合最平.

然而, 按實際的情況, 是可以做不同的optimization,
就如麥當勞情況, 所有餐也是有薯條, 就算中薯條升級做大薯條, 所加的價錢是一樣的.
就是說, 你可以完全當薯條無到, 因為薯條完全唔影響結果. 你只要記住, 如果你要買4包薯條, 你頂多只做到4個餐就夠了.

可做的optimization, 按實際情況, 還可以有更多更多.


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