Рекурсивный метод в методе монет

Question

Для этого вопроса мне нужно написать метод, при котором, когда пользователь вкладывает денежную сумму в копейки, я должен выводить все возможные комбинации с копейками, никелями и копейками в формате String. Я могу использовать только рекурсию и никакой тип циклов или коллекций (т.е. массивы, списки, стеки и т. Д. c). Этот код должен работать, но по какой-то причине он не выводит все комбинации, в нем отсутствуют: «0d 3n 7p» и «0d 0n 17p».

package Assignement02;

public class Coins {

    public static String ways (int money) {

        System.out.println("Enter an amount in cents:");
        System.out.println(money);
        System.out.println("This amount can be changed in the following ways:");

        if(money == 0) {

            return "there are no ways to change that amount";

        } else {

            return waysHelper(0, 0, 0, money);
        }


    }

    public static String waysHelper(int countd, int countn, int countp, int money) {


        if(money >= 10) {

            countd++;
            return waysHelper(countd, countn, countp, money - 10);

        } else if (money >= 5) {

            countn++;
            return waysHelper(countd, countn, countp, money - 5);

        } else {


                String s = " " + countd + "d, " + countn + "n, " + money + "p";
                int orig = 10*countd + 5*countn + money;
               return counterHelper(orig, countd, countn, money, s);


            }
        }

    public static String counterHelper(int money, int countd, int countn, int countp, String s) {

        if(countp == money) {

            s = s + s + "\n " + countd + "d, " + countn + "n, " + countp + "p";
        }

        if(countd > 0) {

            if(countn > 0) {

                countn--;
                countp = countp + 5;
                s = s + "\n " + countd + "d, " + countn + "n, " + countp + "p";
                counterHelper(money, countd, countn, countp, s);
            }

            countd--;
            countn = countn + 2;
            s = s + "\n " + countd + "d, " + countn + "n, " + countp + "p";
            counterHelper(money, countd, countn, countp, s);

        } 

        if(countn > 0) {

            countn--;
            countp = countp + 5;
            s = s + "\n " + countd + "d, " + countn + "n, " + countp + "p";
            counterHelper(money, countd, countn, countp, s);

        }

        if(countn > 0) {

            countn--;
            countp = countp + 5;
            s = s + "\n " + countd + "d, " + countn + "n, " + countp + "p";
            counterHelper(money, countd, countn, countp, s);

        }

        return s;
    }



    public static void main(String[] args) {

        System.out.print(ways(17));


    }
}

Выход:

Enter сумма в центах: 17 Эта сумма может быть изменена следующими способами: 1d, 1n, 2p 1d, 0n, 7p 0d, 2n, 7p 0d, 1n, 12p 0d, 0n, 17p

Answer 1

Я полагаю, что у вас есть правильное представление о проблеме. Вот как я понимаю вашу интерпретацию:

1. Преобразование начальных пенни в наибольшую возможную комбинацию монет из монет (т.е. для 17 это будет 1d, 1n, 2p)
2. Разбить эта «самая большая комбинация достоинства» в каждой комбинации меньших монет, чтобы определить все возможные комбинации (то есть разбить каждый цент на 2 никеля, а каждый никель на 5 копеек)

* 1008 первая часть, а ваш counterHelper - вторая.

Найдите мое решение ниже с комментариями:

public class Coins {

    public static void main(String[] args) {
        System.out.print(findAllCoinCombinationsForPennies(17));
    }

    public static String findAllCoinCombinationsForPennies(int money) {
        System.out.println("Enter an amount in cents:");
        System.out.println(money);
        System.out.println("This amount can be changed in the following ways:");
        if(money <= 0) {
            return "there are no ways to change that amount";
        } else {
            return findAllCoinCombinations(0, 0, money);
        }
    }

    // break down the initial amount into the largest coinage to start (i.e. 17 pennies will be 1d, 1n, 2p)
    private static String findAllCoinCombinations(int dimes, int nickels, int pennies) {
        if(pennies >= 10) {
            // we can still convert pennies to another dime
            return findAllCoinCombinations(dimes + 1, nickels, pennies - 10);
        } else if (pennies >= 5) {
            // we can still convert pennies to another nickel
            return findAllCoinCombinations(dimes, nickels + 1, pennies - 5);
        } else {
            // base case where we have the largest coins (can't convert pennies to any more dimes or nickels)
            return findCoinCombinationsFor(dimes, nickels, pennies, "");
        }
    }

    // find all combinations of coins recursively
    private static String findCoinCombinationsFor(int dimes, int nickels, int pennies, String output) {
        // each call is another combination of coins, add that combination to our result output
        output += "\n " + dimes + "d, " + nickels + "n, " + pennies + "p";
        if (dimes > 0) {
            // if we have dimes, break the dime down into 2 nickels
            return findCoinCombinationsFor( dimes - 1, nickels + 2, pennies, output);
        } else if (nickels > 0) {
            // if we have nickels break each nickel down into 5 pennies
            return findCoinCombinationsFor( dimes, nickels - 1, pennies + 5, output);
        } else {
            // we have no more dimes or nickels, return the accumulated output
            return output;
        }
    }
}

Answer 2

Ваша проблема была бы более очевидной, если бы вы использовали 37 центов в качестве тестового примера. У вас никогда не будет примеров с более чем двумя никелями, потому что вы сначала переключаетесь на десять центов и никогда не возвращаетесь. Вы восполняете это только дополнительными шагами if (countn ...), и я не совсем понимаю.

Вместо того, чтобы wayHelper возвращал String, вы должны передать список строк (или просто иметь его в качестве переменной-члена), и каждый вызов wayHelper будет добавлять некоторые в список. Если вы еще не создали списки, вы можете собрать их в большую строку, но вы должны быть осторожны, потому что тогда вы должны возвращать их, захватывать каждую модифицированную версию и всегда передавать ее. Со списком вы передаете его, и метод, который вы вызываете, может его изменить.

Сама идея сделать это рекурсивно, а не использовать al oop немного глупо, но обратите внимание, что хвостовая рекурсия и циклы по сути одно и то же. Вы можете воспользоваться этим.

import java.util.ArrayList;
import java.util.List;

public class MoneyChangers {
    public static void main(String[] args) {
        List<String> results = new ArrayList<>();
        getCombos(results, 28, 0);
        System.out.println(results);
    }

    public static void getCombos(List<String> results, int target, int dimesCount) {
        int pennies = target - 10 * dimesCount;
        if (pennies < 0) {
            return;
        }
        getCombosForDimesFixed(results, target, dimesCount, 0);

        // This is tail recursion, which is really just a loop.  Do it again with one more dime.
        getCombos(results, target, dimesCount+1);
    }

    private static void getCombosForDimesFixed(List<String> results, int target, int dimesCount, int nickelsCount) {
        int pennies = target - 10 * dimesCount - 5 * nickelsCount;
        if (pennies < 0) {
            return;
        }
        results.add("\n" + dimesCount + "d, " + nickelsCount + "n, " + pennies + "p");
        getCombosForDimesFixed(results, target, dimesCount, nickelsCount+1);   // tail recursion again
    }
}