/** * 题目描述： * 第一题：人民币分为（1,5,10,20,50,100）的金额，若交易金额为19，收银（50），找零（20+10+1）交易所需人民币张数为4. * 或者收银（10+5+1+1+1+1）交易所需人民币张数为6.输入交易金额n,输出交易所需最少人民币数量 * @author young * */ public class MoneyNumberLeast { private static int[] moneyArrays = {100, 50, 20, 10, 5, 1}; private static int[] moneyNumber = new int[100]; static { //初始化获得1-99交易额的最少人民币数量 for(int i = 1; i < 100; i ++) { moneyNumber[i] = getMinNumberOfMoney(i); } } /** * n元进行分解，最少需要的人民币的数量 * @param n * @return */ public static int getMoneyNumber(int n) { int sum = 0; for(int i = 0; i < moneyArrays.length; i ++) { int number = n / moneyArrays[i]; sum += number; n = n % moneyArrays[i]; } return sum; } /** * 输入金额为n,返回最少的人民币数量 * @param n在1-99之间 * @return */ public static int getMinNumberOfMoney(int n) { if(n < 1 || n > 99) return -1; //第一种情况：直接支付不找零 int sum1 = getMoneyNumber(n); //第二种情况，支付，找零 int i = moneyArrays.length - 1; while(n / moneyArrays[i] != 0) { i--; } int sum2 = getMoneyNumber(moneyArrays[i] - n) + 1; return Math.min(sum1, sum2); } public static int getMinNumber(int n) { //100以内的人民币数量 int numberother = 0; //100元的人民币数量 int number100 = n / 100; n = n % 100; if(n > 0) { numberother = moneyNumber[n]; } return number100 + numberother; } }