时间戳

首页 > 解决方案 > 递归 Python 函数转换为 Javascript 不起作用，数组有问题

javascript - 递归 Python 函数转换为 Javascript 不起作用，数组有问题

问题描述

我想将一个 Python 程序（它解决了某个基本的组合问题）翻译成 Javascript。目标是评估my_function(200, [1,2,5,10,20,50,100,200])，结果是 Python 程序返回正确答案（~70k），但我尝试的 Javascript 翻译返回错误答案（〜60k）。

函数my_function是递归定义的，特别是第二个输入，一个列表，在递归步骤中被截断（参见倒数第二行代码）。我可能在 JS 版本中处理得不好。

Python函数：

import math

coin_sizes = [1,2,5,10,20,50,100,200]

def my_function(amount, coins_list):
    if amount == 0:
        return 1
    elif len(coins_list) == 0:
        return 0
    elif len(coins_list) == 1:
        return 1
    else:
        top_coin = coins_list[-1]
        d = math.floor(amount/top_coin)
        total = 0
        for i in range(0,d+1):
            total += my_function(amount - i*top_coin, coins_list[:-1])
        return total

Javascript函数：

var coin_sizes = [1,2,5,10,20,50,100,200];

var sublist = function(mylist) {
    var new_list = Array(mylist.length-1);
    for (var i = 0; i < mylist.length-1; i++){
        new_list[i] = mylist[i];
    }
    return new_list
};

var my_function = function(amount, coins_list) {
    if (amount == 0) return 1;
    else if (coins_list.length == 0) return 0;
    else if (coins_list.length == 1) return 1;
    else {
        var top_coin = coins_list[(coins_list.length-1)];
        d = Math.floor(amount/top_coin);
        var total = 0;
        for (var i = 0; i < d+1; i++) {
        total += my_function(amount - i*top_coin, sublist(coins_list));
        };
        return total;
    };
};

我尝试用 Java 编写类似的程序，但出现太多堆栈溢出错误。

问题：发生了什么事？为什么我会得到错误的答案，有没有更好的方法将这个 Python 程序翻译成 Javascript？

注意：原始的组合问题可以动态/无需递归解决，然后将其转换为 Javascript 就没有问题。我想学习如何编写类似于上面 Python 函数的东西。

标签： javascriptpythonarraysmathrecursion

解决方案

你错过了申报d。

顺便说一句，您可以使用 exit early 范式if ... return ...并在没有else和最后一个块的情况下继续，您需要声明所有变量，因为如果没有，变量是全局的，并且值会随着递归调用而变化。

另一个提示，在 block statements 之后{ ... }，比如 with foror else，你不需要分号。

最后，您可以使用as to参数（第二个）Array#slice从开始到结束 - 1 获取副本。-1

var coin_sizes = [1, 2, 5, 10, 20, 50, 100, 200],
    sublist = function(mylist) {
        return mylist.slice(0, -1);
    },
    my_function = function(amount, coins_list) {
        if (amount == 0) return 1;
        if (coins_list.length == 0) return 0;
        if (coins_list.length == 1) return 1;
        var top_coin = coins_list[(coins_list.length - 1)],
            d = Math.floor(amount / top_coin),
            total = 0;
        for (var i = 0; i < d + 1; i++) {
            total += my_function(amount - i * top_coin, sublist(coins_list));
        }
        return total;
    };

console.log(my_function(200, [1, 2, 5, 10, 20, 50, 100, 200]));

推荐阅读