JAVA 递归找零钱
发布网友
发布时间:2022-05-07 04:03
我来回答
共2个回答
热心网友
时间:2023-10-14 20:42
看了楼上的写法后,不甚满意,于是自己写了一种。
这个题目很有意思,相当有意思。
加上了比较详细的注释。
你试一试。
这种方法你能很明显的看出递归的特征。
可以随意传要找钱的总数,以及硬币面额可以增加或者减少。但是
硬币的面额要由小到大排列,就ok
注释加的有点多。。看起来有点累赘。不过能容易看。
package file;
import java.util.ArrayList;
import java.util.List;
/**
* 递归得到找钱方案个数
* 思路为:
* 定义待找钱币类型。默认从小到大排列。
* 传入参数后,先获得最大的硬币面值。通过整除,得到可以有几种找钱情况
* 递归调用找钱,因为排除了最大面额硬币后的可找硬币以余额都发生了变化。可以看作一次新的找钱
* 最终得到所有的找钱方案。封装到List中返回。
* @version TestRePay.java v. 1.0.0 2010-10-26
* @author Andy
*/
public class TestRePay {
public static void main(String[]args){
int i = 150;
int[] coinType = new int[]{1,5,10,25,50};
//调用递归方法
List<String> allResult = reCoins(coinType, i);
System.out.println("找钱方案的个数为:"+allResult.size());
for(int j = 1 ,k = allResult.size(); j<=k;j++ ){
System.out.println(" 第"+j+"种找钱方案为:"+allResult.get(j-1));
}
}
/**
* 通过递归,得到所有的方案数量
* author Andy
* date 2010-10-26 下午01:30:06
* @param coinType 可以找给客户的钱币的类型 为int数组
* @param totalMoney 待找钱的数量
* @return
*/
public static List<String> reCoins(int[]coinType , int totalMoney){
//获得最后一个,也就是默认为最大的一个钱币类型
int lastCoin = coinType[coinType.length-1];
//通过数组复制获得下一级调用时候的硬币类型
int[] newCoinType = new int[coinType.length-1];
System.arraycopy(coinType, 0, newCoinType, 0, newCoinType.length);
//获得针对当前硬币,也就是这个lastCoin 有几种找钱情况
int times = totalMoney/lastCoin;
List<String> resultList = new ArrayList<String>();
//如果当前硬币的面值大于余额。但是手中还有更小面值的硬币,则递归调用找钱。
if(times==0&&coinType.length!=0){
List<String> childList = reCoins(newCoinType, totalMoney);
resultList.addAll(childList);
//进行遍历,得到带找钱的值
}else{
//最小面值了,所以,直接返回值
if(coinType.length==1){
resultList.add(" 1分*"+totalMoney+"个 ");
}else{
//不是最小面值,所以,要遍历下
for(int i=1;i<=times;i++){
List<String> childList = null;
int remainder = totalMoney-lastCoin*i;//新余额
if(remainder != 0){
childList = reCoins(newCoinType, remainder);
for(String r:childList){
r = " "+lastCoin+"分*"+i+"个 " + r;
resultList.add(r);
}
}else{
resultList.add(" "+lastCoin+"分*"+i+"个 ");
}
}
}
}
return resultList;
}
}
加油,java的路 还有很长哦,呵呵
参考资料:手打
热心网友
时间:2023-10-14 20:42
一般都是找最少硬币数的方法,你这里要列出所有的可能,我理解没错吧?解法有很多,我只帮你写了一个,包括输出格式及测试。
import java.util.HashSet;
import java.util.Iterator;
public class MoneyChange {
private HashSet<int[]> allSolutions = new HashSet<int[]>();
private static int[] coins = {1,5,10,25,50};
// @param: amount, currSolution, MaxAvailableCoinIndex
public void computeSolutions(int total, int[] sol, int maxCoin){
if(total < coins[maxCoin])return;
//System.out.println(total+" "+maxCoin);
total -= coins[maxCoin];
sol[maxCoin]++;
if(total == 0){
// System.out.println("++"+allSolutions.size());
allSolutions.add(sol);
}else{
while(maxCoin>=0){
if(total>=coins[maxCoin])
computeSolutions(total, sol.clone(), maxCoin);
maxCoin--;
}
}
}
public void computeSolutions(int total){
if(total == 0)
return;
computeSolutions(total, new int[5], 4);
computeSolutions(total, new int[5], 3);
computeSolutions(total, new int[5], 2);
computeSolutions(total, new int[5], 1);
computeSolutions(total, new int[5], 0);
}
public void showSolutions(){
System.out.println("一共有:"+allSolutions.size()+"种方法");
Iterator it = allSolutions.iterator();
while(it.hasNext()){
int[] a = (int[]) it.next();
//for(int i:a){}
System.out.println("1分:"+a[0]+" "+"5分:"+a[1]+" "+"10分:"+a[2]+" "+"25分:"+a[3]+" "+"50分:"+a[4]);
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
MoneyChange mc = new MoneyChange();
mc.computeSolutions(53);
mc.showSolutions();
}
}