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

　前回、Javaで作った支払う硬貨の組合せの数を求めるプログラムのpayCoin()メソッドを使って、「Ｈ２３　開成中学校　算数　３番」の問題を解いてみました。(^_^;
　ただし、扱う数が小さいのでプログラムの省略可能部分は省略してみました。

●Payment02.java

/*
 * Payment02.java
 * 
 */

class Payment02 {
    static final int M = 170;// 0 1  2  3  4
    static final int[] Coin = { 1,5,10,50,100};  // 昇順ソート && 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
                r+=payCoin(n-1,t);
        }
        return r;
    }
    
    public static void main(String[] args) {
        long tm=System.nanoTime();  // Timer Start
        
        int m, min, max;
        System.out.println("(1) 10野くん : "+payCoin(2,70)+"通り");
        System.out.println("    50川くん : "+payCoin(3,70)+"通り");
        System.out.println("(2) "+payCoin(4,M)+"通り");  // M=170
        for(max=m=M; payCoin(4,m)!=875; m++);
        for(min=m;   payCoin(4,m)==875; max=m++);
        System.out.println("(3) "+payCoin(3,min)+"通り");
        System.out.println("    最小 : "+ min+"円");
        System.out.println("    最大 : "+ max+"円");
        
        tm=System.nanoTime()-tm;    // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

●実行結果

(1) 10野くん : 64通り
    50川くん : 73通り
(2) 639通り
(3) 750通り
    最小 : 190円
    最大 : 194円
Runtime : 0.003 [sec]

Javaによるはじめてのアルゴリズム入門

Javaによるアルゴリズム事典

明解Javaによるアルゴリズムとデータ構造

定本Javaプログラマのためのアルゴリズムとデータ構造