用js计算斐波那契数列的第n个值

发表于 更新于 分类于
用js计算斐波那契数列的第n个值

题目如下

  • 用js计算斐波那契数列的第n个值，注意时间复杂度

动态规划

  • 把一个大问题，拆解为多个小问题，逐级向下拆解
  • 用递归的思路去分析问题，再改为循环来实现
  • 算法三大思维：贪心，二分，动态规划

思路如下

  • 递归（不可取，时间复杂度O(2^n)）
  • 循环，记录中间结果，时间复杂度为O(n)
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
/**
 * @description 斐波那契数列
 * @author sola-grj
 */

/**
 * 斐波那契数列（递归）
 * @param n n
 */
function fibonacci(n:number):number {
  if(n<=0) return 0
  if(n === 1) return 1
  
  return fibonacci(n - 1) + fibonacci(n - 2)
}

/**
 * 斐波那契数列（循环）
 * @param n n
 */
function fibonacci(n:number):number {
  if(n<=0) return 0
  if(n === 1) return 1
  
  let n1 = 1 // n-1
  let n2 = 0 // n-2
  let res = 0
  
  for(let i = 2;i <= n,i++){
    res = n1 + n2
    // 记录中间结果
    n2 = n1
    n1 = res
  }
  return res
}

单元测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @description 斐波那契数列 test
 * @author sola-grj
 */

import { fibonacci } from './fibonacci'

describe('斐波那契数列', () => {
    it('0 和 1', () => {
        expect(fibonacci(0)).toBe(0)
        expect(fibonacci(1)).toBe(1)
    })
    it('正常情况', () => {
        expect(fibonacci(2)).toBe(1)
        expect(fibonacci(3)).toBe(2)
        expect(fibonacci(6)).toBe(8)
    })
    it('n 小于 0', () => {
        expect(fibonacci(-1)).toBe(0)
    })
})

加问

  • 青蛙跳台阶，一只青蛙，一次可以跳1级，也可以跳2级，问：青蛙跳到n级台阶，一共有多少种方式

思路如下(动态规划)

  • 要跳一级台阶，就1种方式f(1) = 1
  • 要跳二级台阶，就2种方式f(2) = 2
  • 要跳n级台阶，f(n) = f(n-1) + f(n-2)