Fibonacci numbers

The title comes from

The Rikon-Fibonacci series

Description:

  • Write a function, input n, to find the NTH term of the Fibonacci sequence. The Fibonacci sequence is defined as follows:
F (0) = 0, F (1) = 1, F (N) = F (N - 1) + F (N - 2), where N > 1.Copy the code

The Fibonacci sequence starts with 0 and 1, and the Fibonacci numbers that follow are the sum of the previous two numbers. If the result is greater than 1000000007, you need to take the module. If the initial result is 1000000008, return 1.

Recursion + closure

/** * @description uses recursion + closure * @param {number} n * @return {number} */ const fib = function (n) {// cache, Const cache = new Map([[0, 0], [1, 1], [2, 1],]) If (cache.has(n)) {return cache.get(n)} // f(n) = f(n-2) + f(n-1) let result = inner(n-2) + inner(n-1) // Results over 1000000007, If (result > 1000000007) {result = result % 1000000007} result) return result } return inner(n) }Copy the code

Pure ergodic (dynamic programming)

  • According to the formulaF(N) = F(N - 1) + F(N - 2)And we know that n=0, the result is 0, n=1, the result is 1, n=2, the result is 1
  • We can start withN=3To start, compute the result and keep moving the value until you compute toNSo far,

The values of first and second are updated with each iteration

  • secondAssigned tofirst
  • Results of this cycleresultAssigned tosecond
/** * @param {number} n * @return {number} */ const fib = function(n) {// Const map = new map ([[0, 0], [1, 1], [2, 1), ]) if(n <= 2) { return map.get(n) } let i = 3 let first = map.get(1) let second = map.get(2) while(i <= n) { let result = second + first if(result > 1000000007) {result = result % 1000000007} First = second second = result i++} return second}Copy the code