0

该算法应该找到仅使用一角硬币、五分硬币和一分钱就可以对输入金额进行更改的方式数量。我的方法是使用分而治之的策略，通过找出用最大的硬币、一角硬币可以做出改变的方法的数量以及不使用一角硬币做出改变的方法的数量来分割问题。我已经为这个算法编写了一个实现，它可以正确解决来自 1...14 的输入的问题，但是当输入等于或大于 15 时，返回的结果不正确。显然我的算法是错误的，并且想知道需要进行哪些更改来修复代码，以及我的方法是否是一个适当的分而治之的解决方案。

代码如下：

    public static int makeChange(int n) {

        if(n < 0)
            return 0;
        else  {

        int sum = makeChange(n-10) + makeChange(n-5) + 1;

        return sum;
     }
}

非常感谢。

4

2 回答 2

2

暗示：

int nways_10 (int n) {
    int s = 0;
    int d = n / 10;

    for (int i = 0; i <= d; ++i) {
        s += nways_5 (n - 10*i);
    }

    return s;
}

如果需要，您应该了解如何编写nways_5和其他功能。

于 2013-10-21T17:02:14.080 回答
0

您可以从我的回答中获得基本算法：https ://stackoverflow.com/questions/19440228/creating-a-function-that-returns-combinations-of-change/19440582#19440582

你需要修改它而不是输出你应该返回 1，并总结所有的以显示计数

于 2013-10-21T17:09:47.110 回答