找零算法

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

　　一問題還原

　　商場買東西的時候營業員需要找零現在有面額為元元元元元元元角角角分分和分的人民幣若干問如何找零才能使現金最優發放（也就是說同一找零金額下找零發放的人民幣數量最少）

　　二經典解法

　　實現如下

　　代碼

　　class Program

　　{

　　//人民幣面額

　　private static decimal[] moneyArr = new decimal[] { M M M M M M M M M M M M M };

　　//存各種面額的人民幣發放份數

　　private static int[] moneyCountList = null;

　　static void Main(string[] args)

　　{

　　decimal currentMoney = M;

　　int[] moneyCount = Calculate(currentMoney);

　　ConsoleWriteLine(當前需找零金額{}￥ currentMoney);

　　for (int i = ; i < moneyCountLength; i++)

　　ConsoleWriteLine(面額{}￥ 共 {} 張 moneyArr[i] moneyCount[i]);

　　ConsoleReadLine();

　　}

　　/// <summary>

　　/// 計算發放金額數

　　/// </summary>

　　/// <param name=money></param>

　　/// <returns></returns>

　　static int[] Calculate(decimal money)

　　{

　　moneyCountList = new int[] { };

　　int tmpMoney = NumHelper(money);

　　while (tmpMoney > )

　　{

　　for (int i = ; i < moneyArrLength; i++)

　　{

　　if (tmpMoney >= NumHelper(moneyArr[i]))

　　{

　　tmpMoney = NumHelper(moneyArr[i]); //減去一份發放的面額

　　moneyCountList[i] += ;//對應的發送份數+

　　break;

　　}

　　}

　　}

　　return moneyCountList;

　　}

　　/// <summary>

　　/// 將金錢轉換成整數處理

　　/// </summary>

　　/// <param name=money></param>

　　/// <returns></returns>

　　static int NumHelper(decimal money)

　　{

　　return ConvertToInt(money * );

　　}

　　}

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

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

　　代碼

　　class Program

　　{

　　//人民幣面額

　　private static decimal[] moneyArr = new decimal[] { M M M M M M M M M M M M M };

　　//存各種面額的人民幣發放份數

　　private static int[] moneyCountList = null;

　　static void Main(string[] args)

　　{

　　decimal currentMoney = M;

　　int[] moneyCount = Calculate(currentMoney);

　　ConsoleWriteLine(當前需找零金額{}￥ currentMoney);

　　for (int i = ; i < moneyCountLength; i++)

　　ConsoleWriteLine(面額{}￥ 共 {} 張 moneyArr[i] moneyCount[i]);

　　ConsoleReadLine();

　　}

　　/// <summary>

　　/// 計算發放金額數

　　/// </summary>

　　/// <param name=money></param>

　　/// <returns></returns>

　　static int[] Calculate(decimal money)

　　{

　　moneyCountList = new int[] { };

　　int tmpMoney = NumHelper(money);

　　while (tmpMoney > )

　　{

　　for (int i = ; i < moneyArrLength; i++)

　　{

　　if (tmpMoney >= NumHelper(moneyArr[i]))

　　{

　　int result = tmpMoney / NumHelper(moneyArr[i]); //直接除比一條一條減算的快

　　moneyCountList[i] = result;//對應的發送份數

　　tmpMoney = tmpMoney % NumHelper(moneyArr[i]); //余數

　　break;

　　}

　　}

　　}

　　return moneyCountList;

　　}

　　/// <summary>

　　/// 將金錢轉換成整數處理

　　/// </summary>

　　/// <param name=money></param>

　　/// <returns></returns>

　　static int NumHelper(decimal money)

　　{

　　return ConvertToInt(money * );

　　}

　　}

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

From:http://tw.wingwit.com/Article/program/net/201311/13853.html