java - 递归方法找出兑换 5 欧元纸币的所有方法？

Question

我遇到了一个问题，要找到所有可能的组合来兑换 5 欧元纸币。我编写了一个程序，但未能得出正确数量的组合。

我的方法受到以下启发:

500可以分为200、200和100。200可以分为100和100。100可以分为50和50。

写完代码后，我意识到 100 也可以分为 5 个 20。这是我知道的错误，但我不知道如何使用我的方法修复。

我的方法是递归方法，如下所示，它只是检查第一个数字并相应地除以它。

这是我尝试过的:

public class Q1 {

    public static int counter;

    public static void main(String[] args) {

        divide(500);
        System.out.println(counter);

    }

    private static void divide(int x) {


        System.out.println("Dividing " + x);


        if(x == 1) {
            return;
        }

        counter++;

        int length = String.valueOf(x).length();

        int fd = Integer.parseInt(Integer.toString(x).substring(0, 1));
        String zeros;

        if(fd != 1) {
            zeros = Integer.toString(x).substring(1, length);
        }else {
            zeros = Integer.toString(x).substring(1, length-1);
        }


        if(fd == 5) {
            divide(Integer.parseInt(2 + "" + zeros));
            divide(Integer.parseInt(2 + "" + zeros));
            divide(Integer.parseInt(1 + "" + zeros));
        }else if(fd == 2) {
            divide(Integer.parseInt(1 + "" + zeros));
            divide(Integer.parseInt(1 + "" + zeros));
        }else if(fd == 1) {
            divide(Integer.parseInt(5 + "" + zeros));
            divide(Integer.parseInt(5 + "" + zeros));
        }


    }

}

例如使用上面的程序会失败

10 = 2 + 2 + 2 + 2 + 2

我知道已经存在的工作解决方案 like this one但如果可能的话，我想保持我的方法。

使用该程序找出 500 美分的组合，结果有 388 种，其中正确答案是 6295435。有件事告诉我，除了上面的示例之外，我还忘记了其他东西。

Answer 1

以下是有关为什么您得到错误号码的一些提示:

确定所有可能性的正确方法

<小时/>

为了简单起见，尝试拆分 5 而不是 500。请注意，有 4 种可能性，即 5 =

1. 5
2. 2 + 2 + 1
3. 2 + 1 + 1 + 1
4. 1 + 1 + 1 + 1 + 1

现在尝试除以 10 而不是 500。请注意，这可以分为 11 种不同的方式:10 =

1. 10
2. 5 + 5
3. 5 + 2 + 2 + 1
4. 5 + 2 + 1 + 1 + 1
5. 5 + 1 + 1 + 1 + 1 + 1
6. 2 + 2 + 2 + 2 + 2
7. 2 + 2 + 2 + 2 + 1 + 1
8. 2 + 2 + 2 + 1 + 1 + 1 + 1
9. 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
10. 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
11. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

该解决方案遵循以下模式:你要分割的数字x已经是一个答案。通过将这些数字之一拆分为尽可能多的下一个最大数字，将最小数字的数量减少 1。总是忽略那些。如果只剩下一个(和多个)数字，则将 x 拆分为尽可能多的下一个最小数字并继续。

例如，x = 10。则: 10 是最小的数 -> 将其拆分为 5 + 5 -> 5 是最小的数 -> 将其拆分为 2 + 2 + 1 -> 2 是最小的数字，因为 1 被忽略 -> 将其分割为 1 + 1 -> 我们有另一个 2，将其分割为 1 + 1 (这等于解 5 + 1 + 1 + 1 + 1 所以现在我们有 5 作为除 1 之外只有一个数字。下一个最小的数字是 2)-> 将 x=10 拆分为 2 + 2 + 2 + 2 + 2 -> 2 是最小的数字；将其分成 1 + 1 -> 我们还有另外 2 ...

这可以通过递归方法来完成。

代码中出现的问题

<小时/>

您的代码对除 10 的示例的作用如下:

1. 10 分为 5 + 5
2. 前 5 分为 2 + 2 + 1
3. 这两者之一除以 1 + 1
4. 另外两个分为1+1
5. 现在，除以 5 + 5 后的第二个 5 被除以 2 + 2 + 1
6. 其中一个除以 1 + 1
7. 另外两项分为1+1

给它 7 种可能性的总分。尝试将这 7 种可能性映射到上面的 11 种，您数到 10 =

• 10次
• 5 + 5 一次
• 5 + 2 + 2 + 1 两次
• 5 + 2 + 1 + 1 + 1 两次
• 5 + 1 + 1 + 1 + 1 + 1 两次

并且缺少其他 6 个选项。

<小时/>

因此假设这个问题可以通过这样的方法来解决:

10 = 5 + 5 -> 评估前 5 个，然后评估第二个 5

是错误的，因为在这两种情况下，这都会导致 10 = 5 + 5 的计算，仅计算最终 10 的分布中至少包含一个 5 的选项(多次计算，而没有 5 的分布是未评估)。

<小时/>

另一个错误是，代码表示 1 不可能分布，而实际存在 1 (1 = 1)。另外，这个问题不清楚

• x 可以等于所有可能的整数吗？ -> 代码中的 4 不会分解为 2 + 2
• 1 + 1 + 2 与 1 + 2 + 1 和 2 + 1 + 1 是不同的解吗？

(我还没有资格在评论中提出这个问题)。

<小时/>

只有进行一些重大更改才能保留递归方法。上面提到了一种可能的方法。