我完全被一个递归问题阻塞了。这是一个其他人问过的问题,但似乎没有人在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; }