说到算法,可能很多人都会和笔者一样有种晦涩艰深望而却步之感(当然对于那些灰常聪明精于算法的童鞋又另当别论)。在我们向技术高峰攀登的时候,处处都有算法这只传说中的技术老虎的身影,有时它还会突然跳出来挑战一下我们脆弱的小心脏。但是本篇介绍的这个灰常简单,曾经是某对日外包公司的笔试题。笔者甚至不知它能不能被称之为“算法”,请不要皱眉,看看不会妨碍您阅读的心情的。 一、问题还原 商场买东西的时候,营业员需要找零。现在有面额为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); } }
|