This is the 26th day of my participation in Gwen Challenge

Ask canal that had to be so clear, for a source of living water.

The most effective way to keep your technology alive is to provide enough nutrients through constant input. We also do not have to deliberately pursue advanced or fresh knowledge points, through the comprehensive multidimensional analysis of a basic problem, will also reap no small harvest.

The title

Here’s a question we need to answer:

  • Try printing the first 10 terms of the Fibonacci sequence, i.e. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Analysis of the

Some people may be confused when they see the Fibonacci sequence in the title, but there is no need!

For this problem, we can ignore this unfamiliar concept, and we just need to worry about the number pattern that it gives us.

We can see that the rule can be summed up in one sentence: starting with the third digit, the value of each successive term is equal to the sum of the first two terms, expressed as: A n = a n-1 + a n-2 (n ≥ 2).

There are two things we should do:

  1. Generates the value of each item.
  2. Print out all values.

Basic solution

Answer:

  • Creates an array to hold the values of the items in the array.
  • The for loop generates the items in the list and stores them in an array (to compute the values of subsequent items), printing the resulting items.

The code implementation is as follows:

/ * * *@description Creates a method that generates an array of numbers@param {number} N indicates how many items to generate (that is, the array length, not the array subscript) */
function createFibArr(n) {
    // Declare an array of data
    let fibArr = [];
    // Starting with the third term (subscript 2), each term equals the sum of the first two terms
    for (let index = 0; index < n; index++) {
        index < 2 ? fibArr.push(1) : fibArr.push(fibArr[index - 1] + fibArr[index - 2]);
        console.log(fibArr[index]); }}// Call the method
createFibArr(10);
Copy the code

Analysis:

This is probably the most basic way to do it, and it’s pretty easy to do.

But if this is the interview question, such an answer can only be said to be normal, there is no place out of the ordinary, the most important thing is to reflect our distinctive temperament ah, so, we should use some other means to improve their forced case!

Primary recursive

Answer:

  • Calculate the value of each position by recursion (the premise here is that the first and second terms are definite values, otherwise, recursion is not useful).
  • Print the results.

The code implementation is as follows:

/ * * *@description So let's figure out the NTH term *@param {number} N represents the subscript value * of each item@returns {number} The value of position with subscript n */
function calFibValue(n) {
    console.count("Number of executions:")
    return n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2));
}

/ * * *@description Print the calculated result *@param {number} N stands for how many items to print */
function printRes(n) {
    for (let index = 0; index < n; index++) {
        console.log(calFibValue(index)); }}// Call the print method
printRes(10);

// Number of executions: : 276
Copy the code

Analysis:

The use of recursion does improve the code, but it introduces another problem: performance.

The value of each term is calculated from the first term, such as the value of the fourth term, the process is as follows:

  1. Returns the value of the first item: 1.
  2. Returns the value of the second item: 1.
  3. Calculate the third term as 1 + 1 = 2.
  4. Calculate the fourth term as 2 + 1 = 3.

When calculating the value of the fifth term, we have to go through the above process to get the value of the fourth term, which involves a lot of repeated operations.

In order to impress the interviewer, we need to do some more optimization!

Recursive optimization

Answer:

  • It’s the recursion part of the logic that causes the double calculation, so the optimization point is in the recursion.

  • The existence of repeated operations means that subsequent operations can use the values previously calculated, so we need to introduce a cache to store the results of each calculation.

Code implementation:

/ * * *@description So let's figure out the NTH term *@param {number} N represents the subscript value * of each item@returns {number} The value of position with subscript n */

// Store the Map structure of each calculation result
// Arrays can also be used here, but there is no semantically Map or object direct
let fibValueMap = new Map(a);function calFibValue(n) {
    console.count("Number of executions:");
    // If the corresponding value already exists in the cache, it is returned directly
    if (fibValueMap.has(n)) {
        return fibValueMap.get(n);
    }
    const value = n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2));
    // After each item has been calculated, the Map needs to be saved in time
    fibValueMap.set(n, value);
    return value;
}

/ * * *@description Print the calculated result *@param {number} N stands for how many items to print */
function printRes(n) {
    for (let index = 0; index < n; index++) {
        console.log(calFibValue(index)); }}// Call the print method
printRes(10);

// Number of executions: : 26
Copy the code

Analysis:

According to the printed count, the number of recursions after optimization is about 1/10 of the number before optimization, which is quite a surprise.

This time the interviewer should be satisfied.

conclusion

As long as the solution is clear, the code implementation is just a result. In the ordinary work and study, we should consciously cultivate their divergent thinking, look at the problem from multiple angles, you may find different scenery oh! I hope I can inspire you!

There is nothing wrong with using ideas that look superior in an interview in order to highlight your unique temperament or the specific requirements of the interview question.

However, in ordinary work, I still recommend you: in the case of similar performance, can use the basic method to solve the general do not use the “high-grade” method, because the probability of error of the basic method is much smaller. So for example in this problem, the basic solution actually has the best performance.

By writing fewer bugs, we’ll have more time to fish, won’t we?

~

Thanks for reading!

~

Learn interesting knowledge, meet interesting friends, shape interesting soul!

I am the author of programming Samadhi, yi Wang, my public account is “programming Samadhi”, welcome to pay attention to, I hope you can give me more advice!

You come, with expectations, I have ink to welcome! You return, no matter gain or loss, only to yu Yun give each other!

Knowledge and skills should be paid equal attention to, internal force and external power should be repaired simultaneously, theory and practice should grasp both hands, both hands should be hard!