I am participating in the Mid-Autumn Festival Creative Submission contest, please see: Mid-Autumn Festival Creative Submission Contest for details

The Mid-Autumn Festival is about to arrive immediately, also do not know my home chang ‘e on the moon how, jade rabbit still accompany in her side?

primers

Today we are going to discuss an interesting question. If the Rabbit meets Leonardo Fibonacci, how many rabbits will chang ‘e have on the moon next Mid-Autumn Festival?

We know that The Italian mathematician Leonardo Fibonacci proposed the Fibonacci Rabbit Problem, a famous sequence problem, in his Book The Complete Book of Algorithms

Note, our jade rabbit is a god, can directly reproduce independently, and our jade rabbit will never die ~

  • Month 1: A little Jade Rabbit 1
  • Month 2: Little Yutu 1 grows into big Yutu 1
  • Month 3: Big Yutu 1 gave birth to a little Yutu 2
  • The fourth month: Big Yutu 1 gave birth to little Yutu 3, and little Yutu 2 grew into big Yutu 2
  • .

Let’s draw a picture to see how the Yutu reproduction, the same number of yutu means the same yutu ~

So our question is how many rabbits does Chang ‘e have in the twelfth month?

Fibonacci rabbit sequence problem modeling

The Fibonacci “Jade Rabbit” problem can be modeled to obtain the Fibonacci sequence:


1 . 1 . 2 . 3 . 5 . 8 . . . . One, one, two, three, five, eight…

Sequence from the third, each is equal to the sum of the first two, we ask next year’s Mid-Autumn Festival chang ‘e in the moon how many jade rabbit, is the sequence of the 121212 ~

We turn a math problem into a computer programming problem:

Write a function, input NNN, find the NNN term of the Fibonacci sequence (that is, F(N)F(N)F(N)).

The Fibonacci sequence is defined as follows: F (0) = 0, F (1) = F (0) = 0, 1 F (1) = F (0) = 0, 1 F (1) = 1, F (N) = F (N – 1) + F (N – 2) F (N) = F (N – 1) + F (N – 2) F (N) = F (N – 1) + F (N – 2), N>1N >1N >1.

The Fibonacci sequence starts with 000 and 111, and the subsequent Fibonacci numbers are the sum of the previous two numbers.

parsing

Violence recursive

Direct violence recursion will give us the answer we need

function fib(n) {
  if( n === 0) return 0
  if(n === 1) return 1
  return fib(n-1) + fib(n-2)};let result = fib(12)
console.log(result) / / 144
Copy the code

So, if yutu meets Leonardo Fibonacci, there will be 144 Yutu on the moon next Mid-Autumn festival!!

This brainless solution can solve the problem initially, but what if we ask the situation ten years from now?

Such violence up efficiency is too low, we carefully think about it, it can be optimized space is still very large!

The first problem is that there are so many repetitions going on here, so let’s say I want fib of 5, as you can see, and we’re solving fib of 2 and fib of 3 multiple times, which we don’t have to do, so we can use a cache cache to store the fib of n that we’ve solved, The next time you use it, you can just read it instead of reevaluating it recursively,

Recursion + cache

Int Fib(k = 2, Fib(k), Fib(k), Fib(k), Fib(k), Fib(k), Fib(k), Fib(k), Fib(k), Fib(k), Fib(k) , n
let cache = [];

function fib(n) {
  // If the value is already in the cache, return it without recursively evaluating it
  if(cache[n] ! = =undefined) {
    return cache[n];
  }

  // Two initial values
  if (n === 0) return 0;
  if (n === 1) return 1;

  // Find fib of n recursively
  let v = fib(n - 1) + fib(n - 2);

  // Store fib(n) in cache[n]
  cache[n] = v;

  / / return fib (n)
  return v;
}
Copy the code

So we can even calculate ten years from now

Dynamic programming

We can create a DP array, which is our Fibonacci sequence.

function fib(n) {
  let dp = [];
  // base case
  dp[1] = dp[2] = 1;
  for (let i = 3; i <= n; i++) {
    // State transition equation
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
Copy the code

Caching recursion and the above dynamic programming of the array reduce a lot of double computation and improve efficiency, but we can continue to optimize the space, we directly use two variables to receive the result of a later calculation, so that there is no need for an array

function fib(n) {
  if (n < 2) return n;

  let i = 0;
  let j = 1;
  let sum = 1;

  // Once in the loop, add the values of I and j to get sum after j, and move both I and j one bit later
  for (let k = 2; k < n; k++) {
    i = j;
    j = sum;
    sum = i + j;
  }

  return sum;
}
Copy the code

The last

So if yutu meets Leonardo Fibonacci, there will be 144 Yutu on the moon next Mid-Autumn festival!!

If it were 10 years later, there would be about 5.358359254990968 +24 yutu

Finally, I wish everyone a happy Mid-Autumn Festival in advance ~~