说到算法可能很多人都会和笔者一样有种晦涩艰深望而却步之感（当然对于那些灰常聪明精于算法的童鞋又另当别论）在我们向技术高峰攀登的时候处处都有算法这只传说中的技术老虎的身影有时它还会突然跳出来挑战一下我们脆弱的小心髒但是本篇介绍的这个灰常简单曾经是某对日外包公司的笔试题笔者甚至不知它能不能被称之为算法请不要皱眉看看不会妨碍您阅读的心情的
一问题还原
商场买东西的时候营业员需要找零现在有面额为元元元元元元元角角角分分和分的人民币若干问如何找零才能使现金最优发放（也就是说同一找零金额下找零发放的人民币数量最少）
二经典解法
实现如下
代码
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呢？
