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 formula
F(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 with
N=3
To start, compute the result and keep moving the value until you compute toN
So far,
The values of first and second are updated with each iteration
second
Assigned tofirst
- Results of this cycle
result
Assigned 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