找零算法

說到算法，可能很多人都會和筆者一樣有種晦澀艱深望而卻步之感（當然對于那些灰常聰明精于算法的童鞋又另當别論）。在我們向技術高峰攀登的時候，處處都有算法這隻傳說中的技術老虎的身影，有時它還會突然跳出來挑戰一下我們脆弱的小心髒。但是本篇介紹的這個灰常簡單，曾經是某對日外包公司的筆試題。筆者甚至不知它能不能被稱之為“算法”，請不要皺眉，看看不會妨礙您閱讀的心情的。

一、問題還原

商場買東西的時候，營業員需要找零。現在有面額為100元、50元、20元、10元、5元、2元、1元、5角、2角、1角，5分，2分和1分的人民币若幹，問，如何找零才能使現金最優發放（也就是說同一找零金額下，找零發放的人民币數量最少）。

二、經典解法

實作如下：

代碼

如你所看到的那樣，簡單的加減法就可以算出來。這實際上就是我們小時候數學課上做過的按照面額的從大到小進行“窮舉”。

當然你可能會說加減沒有乘除來的快，我們稍作改進：

其實這就是一個簡單數學問題的計算機語言（c#）描述而已（當然，您可能已經看出來了，上面的兩段小程式寫得一點也不OO。有心的讀者也可以練練手試試看寫一下對找零算法的OO改進版，期待指教），以前我們都是用c語言來描述的。說到這裡，筆者不無沉重地又在腦袋裡浮現起大學求學階段某秃頂老頭教算法和資料結構的課堂。當年某老人每次開始上課必然堅持來5分鐘演講，興緻勃勃地細說自己是如何依靠聰明才智和刻苦努力成功解決和征服算法的，說的好像天下所有算法都經過他老人家之手一樣。同學們紛紛感歎，自戀的人常有，而像老頭這麼一上課就自戀的人不常有。通常老頭的課上不到15分鐘，台下就會有大面積異兆出現，比如交頭接耳自說自話的，化蝶去見周公的，恩愛有加打情罵俏的......有時在他和藹的逼視下，講台下會适當有所收斂。總之一句話，你無法形容老頭的課是多麼的優秀。學院計系和資訊系很多人都灰常慶幸地表示，上他老人家的課，他們得到了充足的休息和睡眠，是以下一學年，他們奮不顧身毅然決然地選擇重修老頭的課......時光匆匆，曆曆在目。農曆虎年要到了，但是什麼時候筆者才敢對算法大聲說“I老虎U”呢？

ps：這應該是今年春節前的最後一篇，來年筆者會力争多寫部落格，多記錄自己的開發心得，和大家共同提高。衷心恭祝各位部落格園園友們在新的一年裡一帆風順，一往無前，百尺竿頭更進一步，一如既往的健康快樂。

本文轉自JeffWong部落格園部落格，原文連結：http://www.cnblogs.com/jeffwongishandsome/archive/2010/02/07/1652257.html，如需轉載請自行聯系原作者