Shulou(Shulou.com)06/01 Report--

This article introduces the relevant knowledge of "how to output Fibonacci series by JS". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Try to output the first 10 items of the Fibonacci series, that is, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Analysis.

Some people may be blinded when they see the concept of "Fibonacci series" in the title, but they don't have to!

For this problem, we can ignore this strange concept, we only need to pay attention to the numerical rules given by it later.

We can see that the law can be summed up in one sentence: starting from the third position, the value of each term is equal to the sum of the first two terms, which is expressed in the formula: an = an-1 + an-2 (n ≥ 2).

According to the requirements of the title, we are actually asked to do two things:

Generate the value of each item.

Print out all values.

Basic solution

Ideas for solving the problem:

Create an array to hold the values of the items in the array.

The for loop generates the items in the array and stores them in the array (to calculate the values of the following items), and prints the generated items.

The code is implemented as follows:

/ * * @ description method for creating an array array * @ 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 is equal to the sum of the first two terms for (let index = 0; index < n; index++) {index < 2? FibArr.push (1): fibArr.push (calling Arr [index-1] + fibArr [index-2]); console.log (calling Arr [index]);}} / / calling method createFibArr (10)

Analysis:

This should be the most basic way to solve the problem, and it can be easily realized.

But if this is an interview question, such an answer can only be said to be in order, there is no outstanding place, the most important thing is that we do not reflect our distinctive temperament, so we should use some other means to improve our own pressure!

Primary recursion

Ideas for solving the problem:

The corresponding values of each setting are calculated by recursive means (there is a premise here: the first and second terms are definite values, otherwise, recursion will not work).

Print the results.

The code is implemented as follows:

/ * * @ description calculates the value of item n * @ param {number} n represents the subscript value of each item * @ returns {number} the value of the position where the subscript is n * / function calFibValue (n) {console.count ("number of execution:") return n < 2? 1: (calFibValue (n-1) + calFibValue (n-2)) } / * @ description print calculation result * @ param {number} n represents how many items to print * / function printRes (n) {for (let index = 0; index < n; index++) {console.log (calFibValue (index));}} / / call print method printRes (10); / / number of execution:: 276

Analysis:

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

The value of each item is calculated and accumulated from the first item, for example, the value of the fourth item is calculated as follows:

Returns the value of the first item: 1.

Returns the value of the second item: 1.

The value of the third item is calculated as 1 + 1 = 2.

The value of the fourth item is calculated as 2 + 1 = 3.

When calculating the value of the fifth item, we have to go through the above process to obtain the value of the fourth item, and a large number of repeated operations have been carried out.

In order to surprise the interviewer, we still need to do more optimization!

Recursive optimization

Ideas for solving the problem:

What causes the double calculation is the logic of the recursive part, so the optimization point is here in the recursion.

Since there are repeated operations, it means that the later operations can use the previously calculated values, so we need to introduce a cache to save the results of each calculation.

Code implementation:

/ * * @ description calculates the value of item n * @ param {number} n represents the subscript value of each item * @ returns {number} the value of the position where the subscript is n * / / the Map structure / / which stores the result of each calculation can also be used here, but there is no Map or object directly let fibValueMap = new Map (); function calFibValue (n) {console.count ("execution times:") / / if the corresponding value already exists in the cache, return if (fibValueMap.has (n)) {return fibValueMap.get (n);} const value = n < 2? 1: (calFibValue (n-1) + calFibValue (n-2)); / / after calculating each item, you need to deposit it in MapfibValueMap.set (n, value); return value } / * @ description print calculation result * @ param {number} n represents how many items to print * / function printRes (n) {for (let index = 0; index < n; index++) {console.log (calFibValue (index));}} / / call print method printRes (10); / / number of execution:: 26

Analysis:

According to the printed count, the number of recursions after optimization is about 10 of that before optimization, which is a pleasant surprise.

This is the end of the introduction of "how to output Fibonacci series by JS". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.