“This is the 9th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Topic describes

Write a function, input n, to find the NTH term of the Fibonacci sequence. The Fibonacci sequence is defined as follows:

F (0) = 0, F (1) = 1, F (N) = F (N – 1) + F (N – 2), where N > 1. The Fibonacci sequence starts with 0 and 1, and the Fibonacci numbers that follow are the sum of the previous two numbers.

1e9+7 (1000000007) is required for the answer. If the initial calculation result is 1000000008, return 1.

Example 1:

Input: n = 2 Output: 1Copy the code

Example 2:

Input: n = 5 Output: 5Copy the code

Tip:

0 <= n <= 100

The problem solving

1. The first three Fibonacci numbers are irregular, so the special case returns directly when the NTH term of the input is less than 3.

2. Start with Fibonacci’s fourth number, which is the sum of the first two numbers. So you can use recursion to process the data that you add each time

3. In each recursion, two numbers are passed, which are the first two numbers. When you add these two numbers together, you get a third number that is the value of the current position. When generated, the right pointer becomes the number, and the left pointer becomes the number of the original right pointer. Therefore, a temporary variable temp is needed to store the value of the original right pointer. At the beginning of each iteration, the value of the right pointer is first stored in the temporary variable temp, and then the sum of the two Pointers on the left and right of the value variable of the right pointer is added to the value of the temporary variable to the left pointer.

4. After each recursion, record the recursion times and compare them with the NTH item you want to output. If they are equal, output the result.

Class Solution {public static int fib(int n) {if (n == 0) {return 0; } if (n == 1 || n == 2) { return 1; } int left = 1; int right = 1; int temp = 0; return fbnq(left,right,temp,3,n); } public static int FBNQ (int left,int right,int temp,int n,int k) {public static int FBNQ (int left,int right,int temp,int n,int k) { right = (left + right) % 1000000007; left = temp; if (n == k) { return right; } n ++; return fbnq(left,right,temp,n,k); }}Copy the code