计算硬币数

Question

问:我需要付给某人49英镑‘假币’.我有面值为1,2,3,4和5的硬币，我最多可以支付15枚硬币。让我们有M的支付方式吧。找到M的最后3位数字。

所以我用javascript写了一个解决方案：

​

function pay() {
var waysOfPaying= 0;
for (e = 0; e < 10; e++) {
    for (d = 0; d < 13; d++) {
        for (c = 0; c < 16; c++) {
            for (b = 0; b < 16; b++) {
                for (a = 0; a < 16; a++) {
                    if ((a + b + c + d + e <= 15) && (a + (2 * b) + (3 * c) + (4 * d) + (5 * e) == 49)) {
                        waysOfPaying++;
                        }
                    }
                }
            }
        }
    }
    return waysOfPaying % 1000 ;
}

我的代码给出的答案是333，但是正确的答案是714。我做错什么了？

Answer 1

你的算法是面向每一个硬币的价值。问题是，它失去了秩序的重要性:它发现9枚硬币的价值为5，加上1枚硬币的价值为4的总和为49。但它忽略了这样一个事实:8枚硬币的价值为5，1枚硬币的价值为4，另外5枚硬币的价值加起来为49枚。

最初的问题是从一个空间移动到另一个空间，建立一个移动到50平方的轨迹。专注于您所在的位置，而不是跳转值。想想每个空间的决定：-你在第50空间吗？如果是这样的话，你找到一个有效的线索，数一数。-你是经过49号广场了，还是已经走了15步才到这里？如果是的话，这条路就结束了，没有必要再跳下去了。-如果没有，你可以做5个可能的动作:跳转1，2，3，4或5空格。每一次之后，再次评估你的位置。

提示:使用递归函数模拟空间上的操作。

Answer 2

这个问题也在cs.stackexchange上发布。我在此补充一份我的答覆：

19305

我会用动态规划来解决这个问题。不管怎么说，你的代码在我看来没问题。你仔细考虑所有的选项，数一数满足条件的选项。

我运行了你的脚本，我看到选项的数量正好是333。如果这是真正的答案，那么为什么在问题中你被要求给出最后三个数字呢？

我认为，也许你需要数一数，并考虑内部秩序。

例如: 5,5,5,5,5,5,5,5,5,4将作为一种选择，4,5,5,5,5,5,5,5,5,5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5，5

在这种情况下，选项的数量会高得多，询问最后三个数字是有意义的。

通过计算满足条件的每个元组(a、b、c、d、e)的排列数(注意有相同的元素)，您可以轻松地将代码更改为问题的这个版本。它将比仔细研究所有选项更有效率。

Answer 3

正如人们先前指出的那样，你想要回答的问题与之前所说的不一样，因为秩序是重要的。你给出的解是正确的，没有排列(333)。然而，我不认为尝试所有的选择都是解决这个问题的好方法。

如果您有兴趣在JavaScript中实现这一点，请参见下面的内容：

function pay (target, maxCoins, partial) {
    function sumArray (array) {
        var sum = 0;
        for (var i = 0; i < array.length; i++) {
           sum += array[i];
        }
        return sum;
    }

    if (typeof target === 'undefined')
        target = 49;
    if (typeof maxCoins === 'undefined')
        maxCoins = 15;
    if (!partial)
        partial = [];

    var sum = sumArray(partial);
    if (sum === target) {
        return 1;
    } else if (sum < target && partial.length < maxCoins) {
        var childSolutions = 0;
        for (var next = 1; next <= 5; next++) {
            var copy = partial.slice(0);
            copy.push(next);
            childSolutions += pay(target, copy);
        }
        return childSolutions % 1000; 
    }
    return 0;
}

不知道这到底需要多长时间才能运行(几个小时后我就放弃了！)有效解决问题的诀窍是做你所做的事情，但是对于你找到的每一个解决方案，都要找出硬币可以被重新排列的方法。幸运的是，有一个这是众所周知的公式。 (参见"Multiset位“)。下面是如何对代码进行调整以包括排列。

var factorials = [1 , 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000];

function permutations (a, b, c, d, e) {
    var n = a + b + c + d + e;
    var base = 1;

    for (var i = 0; i < 5; i++) {
        var arg = arguments[i];
        if (arg > 0)
            base *= factorials[arg - 1];
    }

    return n < 1 ? 1 : factorials[n - 1] / base ;
}

function pay() {
    var a, b, c, d, e,
        waysOfPaying = 0;

    for (e = 0; e < 10; e++) {
        for (d = 0; d < 13; d++) {
            for (c = 0; c < 16; c++) {
                for (b = 0; b < 16; b++) {
                    for (a = 0; a < 16; a++) {
                        if ((a + b + c + d + e <= 15) && (a + (2 * b) + (3 * c) + (4 * d) + (5 * e) == 49)) {
                            waysOfPaying += permutations(a, b, c, d, e);
                        }
                    }
                }
            }
        }
    }
    return waysOfPaying % 1000 ;
}

如果运行，就会得到714的值，这是您所期望的。