javaの再帰関数を用いるプログラミング

質問

1セント，10セント，25セントのコインを好きな枚数使う事ができる．
1234セントを支払う時最低何枚で払うことが出来るか？再帰関数を用いて現実的な速度で動くプログラムをjavaを使って作ってください！
どうぞ宜しくお願いします！

回答No.1

noname#6248 · ベストアンサー

この問題文の場合、金額が多い方から使う方が枚数が少ないので
以下の再帰関数で大丈夫です。
use(int,int)と言う関数が自分自身を呼ぶので再帰関数と呼ばれます。
以下をコピーしPain.javaという名前で保存してコンパイルしてみてください。

もしも、使用するコインが25、15、12、1の時、払う金額が24の時は
12+12が最低枚数ですが、
15+1+1+1+1+1+1+1+1+1を返してしまうのが難点ですけどね。
そういう場合も加味しての再帰関数は・・・少し待ってください。

public class Pain{
public static void main(String[] args){
int payMoney = 1234;// 支払う金額
int useMoney = 0;// 支払った枚数
useMoney=use(payMoney,useMoney);// 支払った枚数
System.out.println("支払った枚数："+useMoney);
}

//last:残り支払い useCoinそれまで使った枚数、return 支払った枚数
public int use(int last,int useCoin){
int coin[]={25,10,1};// 使用するコイン(金額が多い順に記述)
if(last == 0){
return useCoin;//0なのでそれまで使った枚数を返す
}
for(int i=0;i<coin.length;i++)
if(last >= coin[i]){
//使用するコイン決定
last=last-coin[i];
useCoin=useCoin+1;
return use(last,useCoin);//再起処理
}
}
return -1;//支払不可能なので-1を返す
}
}

回答No.2

akinori_s

#1 C_ranさんのソースを参考に少し修正してみました。
useCoin関数では割り算で一気にそのコインが何枚必要か取得しているけど
これやっちゃうと再起の意味があまりなくなっちゃうのかな...
ま、参考まで。

public class Pain{
　private static int COINS[] = {
　　25,10,1
　};
　public static void main(String[] args){
　　int payMoney = 1234;　　// 支払う金額
　　int useMoney = 0;　　　// 支払った枚数
　　useMoney=useCoin(payMoney,0);// 支払った枚数
　　System.out.println("支払った枚数："+useMoney);
　}

　public static int useCoin(int money,int coinIndex){
　　if(money <= 0){
　　　return -1;
　　}
　　if((coinIndex < 0) || (coinIndex >= COINS.length)){
　　　return -1;
　　}
　　int useMoney = (int)(money / COINS[coinIndex]);
　　System.out.println(""+COINS[coinIndex]+"セント:"+useMoney+"枚");
　　int lastMoney = money - (useMoney * COINS[coinIndex]);
　　if(lastMoney > 0){
　　　int lastCoins = useCoin(lastMoney,coinIndex+1);
　　　if(lastCoins > 0){
　　　　lastMoney += lastCoins;
　　　}
　　}
　　return lastMoney;
　}
}