支払う硬貨の組合せの数の問題をJavaで解いてみた。

　支払う硬貨の組合せの数の問題をJavaで解いてみました。(^_^;
　もともと思いつくままに作った自作の遅い再帰版をアルゴリズム辞典の「小銭の払い方」のところを参考にして改良しました。(^_^;
　定数MとCoinのところを変えるだけで簡単に他の問題も解くことが出来ます。
P.S.
　問題がリンク切れのようなので、問題の概要を思い出して付けておきます。それから、この問題は「両替問題」とも呼ばれているようです。(^_^;

　次のお札または硬貨を使って3000円を支払う方法は何通りあるか。
(1)10円,50円,100円
(2)10円,50円,100円,500円
(3)10円,50円,100円,500円,1000円

●Payment01.java

/*
 * Payment01.java
 * 
 */

class Payment01 {
    static final int M = 3000;
    static final int[] Coin = {10,50,100,500,1000}; // 昇順ソート && M%Coin[0]==0
    static final int N = Coin.length;
    
    static long payCoin(int n, long s) {
        if (s%Coin[0]!=0) return -1;
        if (n< 0) return 0;
        if (n==0) return 1;
        
        long r=0, m=s/Coin[n], t=s;
        for(int i=0; i<=m; i++, t-=Coin[n]){
            if (n==1) {
                r+=1+m;
                break;
            } else if (n==2) { // 省略可
                r+=(1+s/Coin[1]-s/Coin[2])*(1+s/Coin[2]);
                break;
            } else
                r+=payCoin(n-1,t);
        }
        return r;
    }
    
    public static void main(String[] args) {
        long tm=System.nanoTime();  // Timer Start
        for(int i=2; i< N; i++)
            System.out.println( payCoin(i,M) );
        tm=System.nanoTime()-tm;    // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

●実行結果

961
2492
3506
Runtime : 0.001 [sec]

P.S.
　最近(2016/09/05頃)、Google アナリティクスで人気のようなので、payCoin()関数をちょっと改良してみました。(^_^;

    static long payCoin(int n, long s) {
        if (s%Coin[0]!=0) return -1;
        if (n< 0) return 0;
        if (n==0) return 1;
        
        long r = 0, m = s/Coin[n], t = s;
        for(int i=0; i<=m; i++, t-=Coin[n]){
            switch (n) {
                case 1:
                    return r+(1+m);
                case 2: // 省略可
                    return r+(1+m)*(1-m+s/Coin[1]);
                default:
                    r+=payCoin(n-1,t);
            }
        }
        return r;
    }