找零算法

说到算法，可能很多人都会和笔者一样有种晦涩艰深望而却步之感（当然对于那些灰常聪明精于算法的童鞋又另当别论）。在我们向技术高峰攀登的时候，处处都有算法这只传说中的技术老虎的身影，有时它还会突然跳出来挑战一下我们脆弱的小心脏。但是本篇介绍的这个灰常简单，曾经是某对日外包公司的笔试题。笔者甚至不知它能不能被称之为“算法”，请不要皱眉，看看不会妨碍您阅读的心情的。

　　一、问题还原

　　商场买东西的时候，营业员需要找零。现在有面额为100元、50元、20元、10元、5元、2元、1元、5角、2角、1角，5分，2分和1分的人民币若干，问，如何找零才能使现金最优发放（也就是说同一找零金额下，找零发放的人民币数量最少）。

　　二、经典解法

　　实现如下：

　　代码

　　class Program

　　{

　　//人民币面额

　　private static decimal[] moneyArr = new decimal[] { 100M, 50M, 20M, 10M, 5M, 2M, 1M, 0.5M, 0.2M, 0.1M, 0.05M, 0.02M, 0.01M };

　　//存各种面额的人民币发放份数

　　private static int[] moneyCountList = null;

　　static void Main(string[] args)

　　{

　　decimal currentMoney = 188.88M;

　　int[] moneyCount = Calculate(currentMoney);

　　Console.WriteLine("当前需找零金额：{0}￥", currentMoney);

　　for (int i = 0; i < moneyCount.Length; i++)

　　Console.WriteLine("面额{0}￥ 共 {1} 张", moneyArr[i], moneyCount[i]);

　　Console.ReadLine();

　　}

　　/// <summary>

　　/// 计算发放金额数

　　/// </summary>

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

　　/// <returns></returns>

　　static int[] Calculate(decimal money)

　　{

　　moneyCountList = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

　　int tmpMoney = NumHelper(money);

　　while (tmpMoney > 0)

　　{

　　for (int i = 0; i < moneyArr.Length; i++)

　　{

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

　　{

　　tmpMoney -= NumHelper(moneyArr[i]); //减去一份发放的面额

　　moneyCountList[i] += 1;//对应的发送份数+1

　　break;

　　}

　　}

　　}

　　return moneyCountList;

　　}

　　/// <summary>

　　/// 将金钱转换成整数处理

　　/// </summary>

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

　　/// <returns></returns>

　　static int NumHelper(decimal money)

　　{

　　return Convert.ToInt32(money * 100);

　　}

　　}

♡ 点赞 0

☆ 收藏 0

留言区（共0条）