斐波那契数列

题目链接

• 牛客网

题目描述

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。 斐波那契数列是一个满足:

• x = 1,2时 fib(x) = 1
• x > 2 时 fib(x) = fib(x−1) + fib(x−2)

的数列 数据范围： 1≤n≤40 要求：空间复杂度O(1)，时间复杂度O(n) ，本题也有时间复杂度O(logn) 的解法

刷题思路

方案一：递归

方案二：动态规划、循环迭代

代码实现

/**
 * 斐波那契数列，递归调用
 * 难度：入门
 */
function fibonacciOne(n) {
  return n < 2 ? n : fibonacciOne(n - 1) + fibonacciOne(n - 2)
}

/**
 * 斐波那契数列，迭代
 * 难度：入门
 */
function fibonacciTwo(n) {
  // 数列初始化
  let firstValue = 0
  let secondValue = 1

  let result = 1

  for (let index = 3; index <= n; index++) {
    result = firstValue + secondValue
    // 前面两列重新赋值
    firstValue = secondValue
    secondValue = result
  }

  return result
}

console.log(fibonacciOne(4))
console.log(fibonacciTwo(4))

一些建议

• 熟记斐波那契数列特性