使用递归的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 = 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)

{       

    // blah ... existing code ... blah

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

    {

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

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

    }

最后，正如我之前所说，200 会产生很大的数字，您实际上无法确认其正确性，因此请从可以检查的少量数字开始。

Answer 2

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

1. {1, 1}

2. {2}