用递归方法找出所有方法来更改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

我知道像这样的工作解决方案已经存在，但如果可能的话，我希望保持我的方法。

使用该程序找出500美分的组合结果388种方式，其中正确答案为6295435。有些东西告诉我，除了上面的例子，我忘记了其他的东西。

Answer 1

以下是一些关于为什么你会得到错误号码的提示：

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

1. 5

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

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

此解决方案遵循以下模式：要拆分的数字x已经是答案。通过将其中一个数字拆分为尽可能多的次大数字，将最低数字的数量减少1。总是忽略那些。如果只剩下一个（或多个）数字，请将x拆分为尽可能多的下一个最低数字，然后继续。

例如，x=10。那么：10是最低的数字-

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

使用除以10的示例编写的代码如下：

1. 10分为5分
2. 前5项分为2 1
3. 其中一个分为11个
4. 另外两个被分成11个
5. 现在，第二个5分为5分为2 1
6. 其中一个分为11个
7. 另外两个被分为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 -

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

另一个错误是，代码说在实际存在1（1=1）的情况下，不可能存在1的分布。此外，这个问题还不清楚

• x能等于所有可能的整数吗-

（我还没有名声在评论中问这个问题）。

保留递归方法只能通过一些重大更改来完成。一种可能的方法如上所述。