JAVA 递归找零钱

看了楼上的写法后，不甚满意，于是自己写了一种coinnew 。

这个题目很有意思，相当有意思coinnew 。

加上了比较详细的注释coinnew 。

你试一试coinnew 。

这种方法你能很明显的看出递归的特征coinnew 。

可以随意传要找钱的总数，以及硬币面额可以增加或者减少coinnew 。但是

硬币的面额要由小到大排列coinnew ，就ok

注释加的有点多coinnew 。。看起来有点累赘。不过能容易看。

package file;

import java.util.ArrayList;

import java.util.List;

* 递归得到找钱方案个数

* 思路为：

* 定义待找钱币类型coinnew 。默认从小到大排列。

* 传入参数后，先获得最大的硬币面值coinnew 。通过整除，得到可以有几种找钱情况

* 递归调用找钱，因为排除了最大面额硬币后的可找硬币以余额都发生了变化coinnew 。可以看作一次新的找钱

* 最终得到所有的找钱方案coinnew 。封装到List中返回。

* @version ***.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));

* 通过递归coinnew ，得到所有的方案数量

* author Andy

* date 2010-10-26 下午01:30:06

* @param coinType 可以找给客户的钱币的类型 为int数组

* @param totalMoney 待找钱的数量

* @return

public static List<String> reCoins(int[]coinType , int totalMoney){

//获得最后一个coinnew ，也就是默认为最大的一个钱币类型

int lastCoin = coinType[coinType.length-1];

//通过数组复制获得下一级调用时候的硬币类型

int[] newCoinType = new int[coinType.length-1];

System.arraycopy(coinType, 0, newCoinType, 0, newCoinType.length);

//获得针对当前硬币coinnew ，也就是这个lastCoin 有几种找钱情况

int times = totalMoney/lastCoin;

List<String> resultList = new ArrayList<String>();

//如果当前硬币的面值大于余额coinnew 。但是手中还有更小面值的硬币，则递归调用找钱。

if(times==0&&coinType.length!=0){

List<String> childList = reCoins(newCoinType, totalMoney);

resultList.addAll(childList);

//进行遍历coinnew ，得到带找钱的值

}else{

//最小面值了coinnew ，所以，直接返回值

if(coinType.length==1){

resultList.add(" 1分*"+totalMoney+"个 ");

}else{

//不是最小面值coinnew ，所以，要遍历下

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;

加油coinnew ，java的路 还有很长哦，呵呵