Article directory
-
- introduce
- Two main concepts of this article:
- Use multi-way recursion to solve the nth term of the Fibonacci sequence
-
- Solution process display and algorithm analysis of multi-path recursive method
- Iterative method to solve the nth term of Fibonacci sequence
-
- Display of the solution process and algorithm analysis of the iterative method
- Frog climbing stairs problem
- Notes on BigInteger
Introduction
This article mainly introduces the concept of multi-path recursion by solving the nth term of Fibonacci, and optimizes the solution of the nth term of the sequence through the iteration method. Finally, it adds ideas for solving the frog climbing stairs problem, and I am writing about iteration The usage of BigInteger I learned during the method.
Two main concepts of this article:
Multi-path recursion: Single-path recursion refers to calling its own method only once in the method body, such as using recursion to implement bubble sorting, and multiple Road recursion refers to calling its own method multiple times in the method body.
The definition of the nth term of the Fibonacci sequence: f(n)=f(n-1) + f(n-2), this definition will be used in the two solution methods in this article , although simple but really important.
Use multi-path recursion method to solve the nth term of Fibonacci sequence
- The problem can be split into sub-problems that compute the n-1th and n-2th items. The following is the code that uses multi-way recursion to solve the nth term of the Fibonacci sequence:
public static int fibonacci(int n){<!-- -->
if(n<3){<!-- -->
return 1;
}
return rubbit(n-1) + rubbit(n-2);
}
-
In this method, when n is less than 3, 1 is returned directly as the base case. For other cases, the values of the n-1 and n-2 terms are calculated by recursively calling fibonacci(n – 1) and fibonacci(n – 2), and adding them together gives the value of the n-th term.
-
The multi-path recursion method can be solved directly according to the definition of Fibonacci sequence, but it is less efficient. Because it will perform a lot of repeated calculations, the time complexity will be very high. The execution time increases significantly when calculating larger n.
Solution process display and algorithm analysis of multi-path recursive method
The process of solving the fifth term of the Fibonacci sequence:
It can be seen from the above solution process that there is a phenomenon of repeated calculations using the multi-path recursive method. For example, when calculating fibonacci(5), you need to calculate fibonacci(3) and fibonacci(4), and when calculating fibonacci(4), you need to calculate fibonacci(3). These repeated calculations can cause significant performance penalties when the number of terms in the Fibonacci sequence is large.
Iterative method to solve the nth term of the Fibonacci sequence
This code uses an iterative method to calculate the nth term of the Fibonacci sequence, using a bottom-up strategy. It avoids the problem of integer overflow by using the BigInteger class to handle large values.
- The code first determines whether the value of n is less than 3. If so, it directly returns BigInteger.ONE as the base case.
- For the case where n is greater than or equal to 3, the code creates two BigInteger objects a and b, initialized to BigInteger.ONE, which is the value of the first two terms of the Fibonacci sequence.
- Then enter a loop, the loop condition is n > 2, and the value of the next item will be calculated at each iteration. Judging from the results, the next item will always be assigned to a, while b will always save the value of the previous item. In the loop, use the a.add(b) method to add a and b to get the value of the next item, and save it in the temporary variable temp.
- Then assign b to a and temp to b for the next iteration calculation.
- Finally, after the loop ends, the value of the nth item of the Fibonacci sequence is stored in variable b and is returned as the result.
This method gradually calculates each item of the Fibonacci sequence iteratively, avoiding repeated calculations in recursion, and is therefore more efficient. And thanks to the use of the BigInteger class, large integer values beyond the range of ordinary integers can be processed.
public static BigInteger fibonacci(int n){<!-- -->
if (n < 3) {<!-- -->
return BigInteger.ONE;
}
BigInteger a = BigInteger.ONE;
BigInteger b = BigInteger.ONE;
while (n > 2) {<!-- -->
BigInteger temp = a.add(b);
a = b;
b = temp;
n--;
}
return b;
}
Display of the solution process and algorithm analysis of the iterative method
[Time complexity analysis] Each loop will update the values of the left and right columns, save the currently found nth item in the left column (a), and save the previous item in the right column (b). In the program You only need to perform a few operations such as addition and judgment to continue solving the next item, avoiding repeated calculations.
[Space complexity analysis] Moreover, the left column and the right column actually only require the space of two variables. Counting the temp in the middle for exchange, only a total of three variables are opened up, and the space complexity is also very low.
Frog climbing stairs problem
Question: A frog can climb one or two steps at a time. How many different climbing methods are there for n levels?
Core concepts:
How to climb to the last level is actually decided during the first two levels.
Let’s first understand the core concepts:
| Stage to climb | Climbing method |
|---|---|
| 1 | (1,1) |
| 2 | (1,1), (2) |
| 3 | (1,1,1),(1,2) (2,1) |
| 4 | (1,1,1,1),(1,2,1), (1,1,2),(2,1,1),(2,2) |
(The above table has been line-wrapped according to the different levels of the frog before climbing to the last level. You can observe it for reference)
- When the frog wants to climb to the first step, there is only one way to climb, which is to jump directly to the first step.
- When the frog wants to climb to the second step, there are two ways to climb, that is, jump one step and then another step or jump directly two steps.
- When the frog wants to climb to the i-th step (i>2), it can only jump up from the (i-1)th or (i-2)th step. Therefore, the total number of climbing methods for the frog to climb to the i-th step is equal to the sum of the total number of climbing methods to climb to the (i-1)th and (i-2)th steps.
When the steps to be climbed are 1, 2, 3, 4, and 5 respectively, we can observe that the frog’s climbing methods are: 1, 2, 3, 5, 8. We can find that these numbers exactly correspond to each term in the Fibonacci sequence starting from the second term.
Through further observation, we found that the frog climbing the ladder problem can be transformed into the problem of solving the Fibonacci sequence. As long as the n + 1 operation is added to the original method of solving the Fibonacci sequence, the solution of the frog climbing the stairs can be obtained.
In short, the relationship between the number of ways a frog can climb a ladder and the Fibonacci sequence is: the number of ways a frog can climb a ladder is equal to the value of the n + 1 term in the Fibonacci sequence. This rule can help us quickly solve the frog climbing ladder problem.
public static BigInteger fibonacci(int n){<!-- -->
n=n+1;
//(Other codes are omitted)
//~~~
}
BigInteger’s notes
When writing the iterative method to solve the nth term of Fibonacci, in order to save the large numbers after more than 90 Fibonacci terms, I learned the simple usage of BigInteger.
- Implementation: Inside BigInteger, an array of type int is used to store the various bits of the integer. Each element of the array represents an integer bit. By default, the size of the array automatically expands or contracts as needed to accommodate integers of different lengths.
- Methods: The BigInteger class provides a variety of construction methods, which can accept different types of parameters, such as strings, integers, etc., to create corresponding BigInteger instances. It also provides a wealth of methods, including addition, subtraction, multiplication, division, modular operations, etc., as well as functions such as comparison, bit operations, power operations, etc.
- Advantages: Because BigInteger uses arrays internally to represent integers, it supports very large integer calculations without a fixed number of digits.
- Disadvantages: However, due to the need for high-precision calculations, BigInteger’s calculation speed will be slightly slower than native integer operations.
Overall, BigInteger provides a convenient, flexible, and safe way to process large integers, and is an effective tool for processing arbitrary-precision integer operations.