8. Fibonacci sequence

subject

Title description
Everyone knows the Fibonacci sequence. Now you are required to enter an integer n. Please output the n-th term of the Fibonacci sequence (starting from 0, the 0-th term is 0).

Basic idea

This problem is actually treated as a counterexample of recursion in the sword-like offer.

The essence of recursion is that a problem is decomposed into two or more small problems. If multiple small problems overlap each other, there will be repeated calculations.

F(n) = f(n-1)+f(n-2) this kind of split using recursion is a typical case of overlap, so it will cause a lot of repeated calculations.

In addition, every function call needs to allocate space in memory, the stack capacity of each process is limited, too many recursion levels will cause stack overflow.

Recursion starts from the maximum number and is continuously broken down into small numbers. If recursion is not considered, we only need to start from the decimal number and accumulate from the bottom up. In fact, the idea is very simple.

Code

function Fibonacci(n)
{
if(n<=1){
return n;
}
let i = 1;
let pre = 0;
let current = 1;
let result = 0;
while(i++ < n){
result = pre + current;
pre = current;
current = result;
}
return result;
}

extend

1. Jump steps:

A frog can jump up one step or two at a time. Find out how many kinds of jumping methods the frog can use to jump up an n-level step (different orders will result in different results).

Looking for rules:

Jumping three steps is equal to jumping two steps+jumping one step.

Jumping four steps is equal to jumping three steps+jumping two steps.

Obviously, it also conforms to the law of Fibonacci sequence.

function jumpFloor(n)
{
if(n<=2){
return n;
}
let i = 2;
let pre = 1;
let current = 2;
let result = 0;
while(i++ < n){
result = pre + current;
pre = current;
current = result;
}
return result;
}

3. Rectangular coverage

We can use 21 to cover the larger rectangle horizontally or vertically. Please use N 2′ s.The small rectangle of 1 covers a large rectangle of 2*n without overlap. How many methods are there in total?

It is very similar to the question of jumping up the steps.

Suppose there are 8 blocks

The first piece is placed upright, and there are 7 pieces left behind, totaling f(7) methods.

The first piece was placed horizontally, and there were 6 pieces left behind, totaling f(6) methods.

That is, f(8)=f(6)+f(7)

f(n)=f(n-1)+f(n-2)

image

function rectCover(n)
 {
 if(n<=2){
 return n;
 }
 let i = 2;
 let pre = 1;
 let current = 2;
 let result = 0;
 while(i++ < n){
 result = pre + current;
 pre = current;
 current = result;
 }
 return result;
 }

3. Abnormal jumping steps

A frog can jump up one step at a time, or two steps at a time … it can also jump up n steps. Find out how many jumping methods the frog can use to jump up an n-step.

Each step can choose to jump or not jump, and the last step must jump.

Each step has two choices, and n steps have 2 n choices.

So there is a total of 2 n-1 hops.

Use bit operation

function jumpFloorII(number)
{
return 1<<(--number);
}