扭曲的斐波那契 - JavaScript

Question

JavaScript 面试时有人问我这个问题。

实现斐波那契数列以列出 n 个数字（n 不包括在内）的序列，其中递归仅对偶数发生。例如

fib(10) -> fib(8) + fib (6)
fib(8) -> fib(6) + fib(4)
fib(6)  -> fib(4) +fib(2)
fib(4) -> fib(2)

我不知道该怎么做。

Answer 1

这绝对需要更多的说明。（面试官应该更清楚）

但据我了解...

所以这个系列必须从某个地方开始，我假设它从 fib(2) = 1 开始。然后是面试官给出的 "code" 部分。

这可以很简单：

fib(2) = 1
fib(4) = 1
fib(6) = 2
...

即fib(n) = fib_orig(n/2)

Answer 2

考虑

fib( 4) = fib( 2)           =  1 * fib(2)
fib( 6) = fib( 4) + fib( 2) =  2 * fib(2)
fib( 8) = fib( 6) + fib( 4) =  3 * fib(2)
fib(10) = fib( 8) + fib( 6) =  5 * fib(2)
fib(12) = fib(10) + fib( 8) =  8 * fib(2)
fib(14) = fib(12) + fib(10) = 13 * fib(2)
                               ^
                               this is fibonacci

在代码中我们得到这个 - 一个很好的小递归（对所有偶数 n >= 0 有效）：

var i;

function fib(n) {
    switch (true) {
        case n === 0:
            return 0;
        case n === 2:
            return 1;
        default:
            return fib(n - 2) + fib(n - 4);
    }
}

function writeFib(n) {
    document.write('fib(' + n + ') = ' + fib(n) + ' * fib(2)<br>');
}

for (i = 0; i <= 20; i += 2) {
    writeFib(i);
}

如果您想要 fib(10) -> fib(8) + fib(6) 这样的结果，那么这样做（无递归）：

var i;

function fib(n) {
    switch (true) {
        case n === 0:
            return '0';
        case n === 2:
            return 'fib(2)';
        default:
            return 'fib(' + (n - 2) + ') + fib(' + (n - 4) + ')';
    }
}

function writeFib(n) {
    document.write('fib(' + n + ') -&gt; ' + fib(n) + '<br>');
}

for (i = 0; i <= 20; i += 2) {
    writeFib(i);
}

扭曲的斐波那契 - JavaScript

Fibonacci with a Twist - JavaScript

javascript

fibonacci