2008-02-17

分硬币问题的递归解法

关键字: 算法
确定将一定数量的钱（以分为单位）转换成两角五分的硬币，一角硬币，五分和一分硬币的方法总数。 
import java.util.Stack;

public class Coin {
    private static int[] coins = {25,10,5,1};
    private static Stack<Integer> roots =new Stack<Integer>();
    
    private static void divide(int num){
        for (int coin : coins){
            if (num - coin >=0 && (roots.size()==0 || coin <= roots.get(roots.size()-1))){
                roots.push(new Integer(coin));
                if (num - coin > 0){
                    divide (num - coin);
                } else {    // Get one
                    for (Integer root: roots){
                        System.out.print (root);
                        System.out.print (" ");
                    }
                    System.out.print ("\n");
                }
                roots.pop();
            }
        }
    }
    
    public static void main(String[] args) {
        Coin.divide(17);
    }
}
评论
metaphy 2008-02-21
运行结果：
10 5 1 1
10 1 1 1 1 1 1 1
5 5 5 1 1
5 5 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
发表评论

您还没有登录，请登录后发表评论

metaphy
搜索本博客
我的相册
E4a25167-de99-3f5d-a292-f4dd7f86392a-thumb
theend
共 10 张
最近加入圈子
存档
最新评论