如何使用复杂度为 O(n) 的 Javascript 找到第 n 个斐波那契数

debugcn 发表于 Dev

爱伦普苏姆

真的很努力想弄清楚如何解决这个问题。问题是使用 javascript 找到具有 O(n) 复杂度的第 n 个斐波那契数。

我发现了很多很棒的文章如何使用 C++ 或 Python 解决这个问题，但是每次我尝试实现相同的逻辑时，我最终都会在Maximum call stack size exceeded.

Python 中的示例代码

MAX = 1000

# Create an array for memoization
f = [0] * MAX

# Returns n'th fuibonacci number using table f[]
def fib(n) :
        # Base cases
        if (n == 0) :
                return 0
        if (n == 1 or n == 2) :
                f[n] = 1
                return (f[n])

        # If fib(n) is already computed
        if (f[n]) :
                return f[n]

        if( n & 1) :
                k = (n + 1) // 2
        else : 
                k = n // 2

        # Applyting above formula [Note value n&1 is 1
        # if n is odd, else 0.
        if((n & 1) ) :
                f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1))
        else :
                f[n] = (2*fib(k-1) + fib(k))*fib(k)

        return f[n]


// # Driver code
// n = 9
// print(fib(n))

然后尝试将其移植到 Javascript

const MAX = 1000;
let f = Array(MAX).fill(0);
let k;

const fib = (n) => {

    if (n == 0) {
        return 0;
    }

    if (n == 1 || n == 2) {
        f[n] = 1;

        return f[n]
    }

    if (f[n]) {
        return f[n]
    }

    if (n & 1) {
        k = Math.floor(((n + 1) / 2))
    } else {
        k = Math.floor(n / 2)
    }

    if ((n & 1)) {
        f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1))
    } else {
        f[n] = (2*fib(k-1) + fib(k))*fib(k)
    }

    return f[n]
}

console.log(fib(9))

那显然行不通。在 Javascript 中，这最终会陷入无限循环。那么你将如何使用 Javascript 解决这个问题？

提前致谢

工程师

问题与k变量的作用域有关。它必须在函数内部：