硬币方法中的递归方法

Question

对于这个问题，我必须编写一个方法，当用户以便士为单位输入金额时，我必须以字符串格式输出所有可能的 10 美分、5 分硬币和 1 美分硬币组合。我只能使用递归，不能使用任何类型的循环或集合（即数组、列表、堆栈等）。这段代码应该可以工作，但由于某种原因它没有输出所有组合，它缺少：“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));


    }
}

输出：

以美分输入金额： 17 可以通过以下方式更改此金额： 1d, 1n, 2p 1d, 0n, 7p 0d, 2n, 7p 0d, 1n, 12p 0d, 0n, 17p

Answer 1

如果您使用 37 美分作为测试用例，您的问题会更加明显。你从来没有任何例子超过两个镍币，因为你先转移到角钱上，再也没有回来。您只能通过额外的 if (countn...) 步骤来弥补这一点，但我不太理解。

而不是让 waysHelper return 一个字符串，您应该传入一个字符串列表（或者只将一个作为成员变量），并且每次调用 waysHelper 都会将一些字符串添加到列表中。如果您还没有完成列表，您可以在一个大字符串中构建它，但您必须小心，因为那样您必须 return 它，捕获每个修改后的版本，并始终传递它。使用列表，您将其传入，您调用的方法可以修改它。

递归执行此操作而不是使用循环的整个想法有点愚蠢，但请注意尾递归和循环本质上是同一件事。你可以利用这一点。

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
    }
}

Answer 2

相信大家对问题的分解思路大致是正确的。我是这样看你的解释的：

将起始便士转换为可能的最大面额硬币组合（即，对于 17，则为 1d、1n、2p）
将 "largest denomination combination" 分解成每个较小硬币的组合，以确定所有可能的组合（即将一角硬币分解成 2 个镍币，每个镍币分解成 5 个便士）

第一部分是你的 waysHelper，第二部分是你的 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;
        }
    }
}

硬币方法中的递归方法

Recursive Method in a Coins Method

java

methods

recursion

recursive-query