使用递归的Java硬币找零问题——不工作

Question

我的程序是错误的，因为赚 2 英镑的方法肯定不止 2 种。

public class TwoPounds

{

    private static int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};

    private static int amount;

    private static int count;

    public TwoPounds()

    {

        amount = 2;

        count = 0;

    }

    public static void main(String[] args)

    {

        TwoPounds run = new TwoPounds();

        count = run.combos(amount);

        run.printOut();

    }

    public int combos(int amountIn)

    {       

        if (amountIn == 0)

        {

            return 1;

        }

        if (amountIn < 0)

        {

            return 0;

        }

        int combosCount = 0;

        for(int i = 0; i < coins.length; i++)

        {

            System.out.println("amountIn now is " + amountIn);

            combosCount += combos(amountIn - coins[i]);

        }

        return combosCount;

    }

    public void printOut()

    {

        System.out.println("\n\n\n");

        System.out.println("There are " + count + " ways can 2 pounds be made, "

            + "using any number of coins");

        System.out.println("\n\n\n");

    }

 }

输出：

There are 2 ways can 2 pounds be made, using any number of coins

Answer 1

您的coins单位是美分（或便士，因为我猜您使用的是英镑），所以既然您使用amountIn - coins[i]它们进行表演，这意味着您的金额也是美分/便士。因此，将您的金额更改为：amount&nbsp;=&nbsp;200;值得花点时间考虑一下变量命名，以及它如何帮助识别甚至完全避免这个问题。术语“amount”和“amountIn”是不明确的。文字中没有任何暗示单位的内容。因此，养成使变量名称尽可能具体且明确的习惯 - 并在适当的情况下包含单位。例如，如果变量被称为“amountInPounds”，那么在写入时错误会变得更加明显amountInPounds - coins[i]现在，在更新到 之前amount = 200;，请注意：1) 将会有大量结果（200 便士、198 便士+2p），这将需要一些时间来迭代一次一便士，加上2）您的代码当前编写为遍历每个离散的有序组合 - 例如，它将进行计数：198“1分”+1“2分”197“1分”+1“2分”+1“1分”196“1分”+1“2分”+2“1分”195“1分”+1“2分”+3“1分”等同样，执行时间太多了。你想要的是不要for(int i = 0; i < coins.length; i++)每次都从零开始，而是添加一个额外的参数combos- 所以像这样：public int combos (int amountIn, int startCoin){&nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; // blah ... existing code ... blah&nbsp; &nbsp; for(int i = startCoin; i < coins.length; i++)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("amountIn now is " + amountIn);&nbsp; &nbsp; &nbsp; &nbsp; combosCount += combos(amountIn - coins[i], i);&nbsp; &nbsp; }最后，正如我之前所说，200 会产生很大的数字，您实际上无法确认其正确性，因此请从可以检查的少量数字开始。

Answer 2

该算法允许使用多个相同面额的硬币，因此有 2 种方法可以赚 2 英镑：{1, 1}{2}