This is the 17th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021.

describe

Everybody knows the Fibonacci sequence, and now I want a positive integer n, so I want you to print the NTH term of the Fibonacci sequence.

The Fibonacci sequence is the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34….

The first and second numbers are both 1, and the last number is the sum of the first two.

Data range: 1 ≤ N ≤ 39

Requirements: Space complexity O(1), time complexity O(n), in this case also have time complexity O(logn) solution

Input description:

A positive integer n

Return value description:

Output a positive integer.

Problem.

Do this kind of problem, certainly do not need recursion, recursion 🐕 do not need.

Certainly need two variables: their weight.this, the latter, the former is used to store the old data, which is used to store the current position of the data, when the next Fibonacci number, only need to add the two variables, so the two variables is bound to create, create the array is unnecessary, we just be a number.

The result of adding the two variables is stored as latter. To save the value of latter, you have to create a variable to store it.

There is also a loop, which starts at 2 and returns as latter(1) when n is less than or equal to 2.

public int Fibonacci(int n) { int former=1; int latter=1; int temp=0; for(int i=2; i<n; i++){ temp=latter; latter+=former; former=temp; } return latter; }Copy the code

Run!

Running speed is pretty good, take up memory is more pull cross.

Try again

The best solution to the Fibonacci array on the Internet is log n, so we definitely want to match the best solution.

I also found a lot of blogs on the Internet, many of which were about linear algebra, but most of which were about time n. I had to read it for a long time, but didn’t I already write it? !

To be continued…

Here is a programmer Xu Xiaobai, daily algorithm [is] my new open a column, primary record my daily learning algorithm, here also hope that I can stick to the daily learning algorithm, don’t know whether this article style you like, don’t mean you free praise, your thumb up, collection, and comments are after work I insist on more power.