在Javascript中实现一个递归的硬币更改函数

Implementing a recursive coin change function in Javascript

本文关键字：递归 硬币 函数 一个 Javascript 实现      更新时间：2023-09-26

我完全被一个递归问题阻塞了。这是一个其他人问过的问题，但似乎没有人在JS中问过它，我可以看到(对不起，如果我错过了什么!)，阅读其他答案没有帮助。

在任何情况下，我都有一个递归程序，它返回所需的最小硬币数:

function change(amount, coins){
    if (amount == 0){
        return 0;
    } else if (coins.length == 0 && amount > 0){
        return Infinity;
    } else if (coins[0] > amount){
        return change(amount, coins.slice(1));
    } else {
        var loseIt = 0 + change(amount, coins.slice(1));
        var useIt = 1 + change(amount - coins[0], coins);
        return Math.min(loseIt, useIt);
    }
}
change(48, [1, 5, 10, 25, 50])
>>> 6
change(48, [1, 7, 24, 42])
>>> 2

但是当我试图修改它返回不只是硬币的数量，但也硬币使用，我一直超过最大数量的堆栈调用或只是崩溃控制台在Chrome。

答案应该像:

change(48, [1, 5, 10, 25, 50])
>>> [6, [25, 10, 10, 1, 1, 1]]
change(48, [1, 7, 24, 42])
>>> [2, [24, 24]]

下面是我的代码:

function change(amount, coins){
    if (amount == 0){
        return [0,[]];
    } else if (coins.length == 0 && amount > 0){
        return [Infinity,[]];
    } else if (coins[0] > amount){
        return change(amount, coins.slice(1));
    } else {
        var loseIt = [change(amount, coins.slice(1))[0], [].concat(change(amount, coins.slice(1))[1])];
        var useIt = [1 + change(amount - coins[0], coins)[0], [coins[0]].concat(change(amount - coins[0], coins)[1])];
        if (useIt[0] > loseIt[0]){
            return loseIt;
        } else {
            return useIt;
        }
    }
}

的想法是，应该总是返回一个包含硬币计数和硬币数组的数组。我逐步通过该函数，它似乎返回正确的答案，但它并没有停止运行。

我感觉它在loseIt/useIt定义中，但是当我测试像

这样的东西时
[x[0] + y[0], x[1].concat(y[1])]

其中x和y是格式化的数组，就像我在函数中返回的那样，它似乎一直返回正确的格式。

我是自学这些东西，所以没有实验室或助教来帮助我-希望有人能解释我在这里做错了什么!

问题

var loseIt = [
    change(amount, coins.slice(1))[0], [].concat(
    change(amount, coins.slice(1))[1])];
var useIt = [1 + 
    change(amount - coins[0], coins)[0], [coins[0]].concat(
    change(amount - coins[0], coins)[1])];

和

工作
var loseIt = 0 + change(amount, coins.slice(1));
var useIt = 1 + change(amount - coins[0], coins);

如您所见，change()的调用为loseIt和useIt完成了一次。在带有硬币计数的数组版本中，使用相同的形参调用函数change()两次，但这里需要函数返回值的数组元素。

解决方案:

与仅计数版本基本相同。对loseIt和useIt分别调用一次change()。稍后您可以使用该数组进行进一步处理。

function change(amount, coins) {
    if (amount === 0) {
        return [0, []];
    }
    if (coins.length === 0 && amount > 0) {
        return [Infinity, []];
    }
    if (coins[0] > amount) {
        return change(amount, coins.slice(1));
    } else {
        var loseIt = change(amount, coins.slice(1));  // just one call of change
        var useIt = change(amount - coins[0], coins); // just one call of change
        if (loseIt[0] < 1 + useIt[0]) {
            return loseIt;
        } else {
            return [1 + useIt[0], useIt[1].concat(coins[0])];
        }
    }
}
console.log(change(12, [9, 6, 1]));                   // [2, [6, 6]]
console.log(change(48, [1, 5, 10, 25, 50]));          // [6, [25, 10, 10, 1, 1, 1]]
console.log(change(48, [1, 7, 24, 42]));              // [2, [24, 24]]
console.log(change(189, [1, 77, 17, 63, 92, 8, 14])); // [3, [63, 63, 63]]
.as-console-wrapper { max-height: 100% !important; top: 0; }

相关文章：