斐波那契数列的几种解法

发表于 分类于

费波那契数列由0和1开始，之后的费波那契系数就是由之前的两数相加而得出。
首几个费波那契系数是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
特别指出：0不是第一项，而是第零项。
显然可以用程序来求斐波那契数列，那么请问斐波那契第5000项是多少？
赶快试一试吧~

解法一：应该很快能写出来：

1
2
3
4
5
6
7
8
9
10
11
12
function fibonacci(n) {
    if (n < 3) {
        return 1
    }
    return fibonacci(n - 1) + fibonacci(n - 2)
}
fibonacci(30)
    // => 832040
fibonacci(40)
    // 卡一会儿.. => 102334155
fibonacci(50)
    // 卡住了..

看来以上方法性能太差了，因为递归太深了，下面来进行优化 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 解法二：循环，迭代
function fibonacci(n) {
    let fib1 = 1
    let fib2 = 1
    let fib3
    if (n < 3) {
        return 1
    }
    for (let i = 0; i < n - 2; i++) {
        fib3 = fib1 + fib2
        fib1 = fib2
        fib2 = fib3
    }
    return fib3
}

fibonacci(1476)
    // => 1.3069892237633987e+308
fibonacci(1477)
    // => Infinity


// 解法三：把依赖上一层环境的递归转变为一个不依赖上一层环境的递归，即尾递归，通过参数传递给下一层，不需要回溯。
function fibonacci(n, fib1 = 1, fib2 = 1) {
    if (n === 1) {
        return fib1
    } else {
        return fibonacci(n - 1, fib2, fib1 + fib2)
    }
}

fibonacci(1476)
    // => 1.3069892237633987e+308
fibonacci(1477)
    // => Infinity

// 解法四：用数组把每次计算结果缓存起来
function fibonacci(n, cache = [0, 1, 1]) {
    let value = cache[n]
    if (value) {
        return value
    } else {
        let newVal = fibonacci(n - 1, cache) + fibonacci(n - 2, cache)
        cache.push(newVal)
        return newVal
    }
}

fibonacci(1475)
    // => 8.077637632156222e+307
fibonacci(1476)
    // => 1.3069892237633987e+308
fibonacci(1477)
    // => Infinity
Number.MAX_VALUE
    // => 1.7976931348623157e+308

目前经过测试最多只能算到1476项，因为JS能表示最大的数Number.MAX_VALUE为1.7976931348623157e+308,能不能想办法求更多项呢？
首先自定义大整数加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 大数字加法
function bigPlus(a, b) {
    let x = a.split('').map(it => Number(it))
    let y = b.split('').map(it => Number(it))
    let m = x.length - 1
    let n = y.length - 1
    let l = (m >= n ? m : n) + 2
    let sum = new Array(l).fill(0)

    for (let i = l - 1; i > 0; i--) {
        sum[i] = (x[m] == undefined ? 0 : x[m]) + (y[n] == undefined ? 0 : y[n]) + sum[i]
        sum[i - 1] = parseInt(sum[i] / 10)
        sum[i] %= 10
        m--
        n--
    }
    if (sum[0] == 0) {
        sum.shift()
    }
    return sum.join('')
}
// 用字符串表示
function fibonacci(n, fib1 = '1', fib2 = '1') {
    if (n === 1) {
        return fib1
    } else {
        return fibonacci(n - 1, fib2, bigPlus(fib1, fib2))
    }
}

fibonacci(10)
// =>"55"
 
fibonacci(3000)
// => "41061588630797126033356837871926710522012510863736925240888543092690558427411340373133049
//     16608500445608300368357069422745885693621454765026743730454468521604866062924973605034697
//     73453733196887405847255290082049086907512622059054542195889758031109222670849274793859539
//     13331837124479554314761107327624006673793408519173181099320170677683893476676477873950217
//     44702686278209185538422258583064083016618629003582668572382102358025043519514729979196765
//     24004784236376453347268364152648346245840573214241419937917242918602639810097866942392015
//     40462015381867142573983507485139642113998271364067958117845819865869228596804324365670979
//     6000"
     
fibonacci(5000)
// => "38789684543883256337019163083259053120821277146462451061605972148955501390440370970108229
//     16462210669479293452858882973813483102008954982940361430156911478938364216563944106910214
//     50563413370655865623825465670071252592990385493381392883637834751890876297071203333705292
//     31076930085180938498018038478139967488817655546537882916442689129803846137789690215022930
//     82475666346224923071883324803280375039130352903304505842701147635242270210934637699104006
//     71417488329842289149127310405432875329804427367682297724498774987455569190770388063704683
//     27948113589737399931101062193081490185708153978543791953056175107610530756887837660336673
//     55445258844886241619210553457493675897849027988234351023599844663934853256411952221859563
//     06047536464547076033090242080638258492915645287629157575914234380914230291749108898415520
//     98544324865940797935713168416928680395453095453886981146650820668628974206393234384884652
//     40988742395873801976993820317174208932265468879364002630797780058759129671389634214252579
//     116872755600360311370547754724604639987588046985178408674382863125"

完