4

再帰を使用して、特定の金額を作るためのコインの最小量を見つけようとしています。必要なコインの最小量をリストできるコードがありますが、ソリューションを考え出すために使用されたコインを出力する方法を見つけることができないようです。同様の例を検索して見つけましたが、これに適切に適用できないようです。

これが私がこれまでに持っているものです：

import java.util.*;

public class Coins{

    public static int findMinCoins(int[] currency, int amount) {
        int i, j, min, tempSolution;

        min = amount;

        for (i = 0; i < currency.length; i++) {
            if (currency[i] == amount) {
                return 1;
            }
        }

        for (j = 1; j <= (amount / 2); j++) {
            tempSolution = findMinCoins(currency, j) + findMinCoins(currency, amount - j);
            if (tempSolution < min) {
                min = tempSolution;
            }
        }
        return min;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] USA =
        {1, 5, 10, 25, 50};
        System.out.println("Please enter an integer amount.");
        int amount = in.nextInt();
        int minCoins = findMinCoins(USA, amount);
        System.out.println("The minimum number of coins to make " + amount + " in United States currency is " + minCoins + ".");
        System.out.println("The coins used were:");
        /*Print coins used to find minCoins.*/
        in.close();
    }
}

これまでに実行されたコードの例:

Please enter an integer amount.
17
The minimum number of coins to make 17 in United States currency is 4.
The coins used were:

これを行う方法について誰かが私に洞察を与えることができれば、それは大歓迎です。

4

5 に答える 5

0

あなたが提供するコードでは、数値1またはmin再帰関数によって返されます。この方法に沿って、コインのリストを取得する 1 つの方法は、戻り変数を変更してコインとカウントの両方を含めることです。

一般的なアイデアの例を次に示します。Javaでのプログラミングについては知らないので、実装はあなたに任せます。

if (currency[i] == amount){
    return [1,i];

...

temp1 = findMinCoins(currency,j);
temp2 = findMinCoins(currency,amount - j);

if(temp1[0] + temp2[0] < min[0]){
    min = [temp1[0] + temp2[0]] concatenated with temp1[1..] and temp2[1..]
于 2015-10-19T03:02:13.600 に答える
0

これは再帰コードです (動作していますが、修正が必要です ...)。アイデアは、すべてのコイン {1,5,10,25,50} を渡して配列し、左から右に (配列の最後まで) 再帰的に呼び出すことです。

ノート ：

出力に小さなバグがあります

数値は、プリミティブ int ではなく、1 要素の配列として渡されます。(これは、すべての再帰呼び出しを通してその値を保持する参照型を持つことです:

public class coins {

    public static void main(String[] args) {
        // arrays of coin types
        int[] coinTypes = { 0, 1, 5, 10, 25, 50 };
        // arrays are references, so changing them
        // inside the recursive function will 'really' change
        int[] price = {11}; // sample input
        tryBigger(price, coinTypes, 0);
    }

    // tries to see if higher coin is possible by passing array
    // of coin types and recursively call until the end of array
    public static void tryBigger(int[] price, int[] theCoins, int index) {
        if (index < theCoins.length-1){
            // until last element
            if (price[0] > theCoins[index]){
                tryBigger(price, theCoins, ++index);
            }
        }
        // find amount of this coin
        int thisCoin = price[0]/theCoins[index];
        // remove the amount already got before
        price[0] = price[0] - thisCoin*theCoins[index];
        System.out.println(thisCoin + " coins of " + theCoins[index]);
        return;

    }
}
于 2015-10-18T21:00:28.450 に答える