This is the 9th day of my participation in the August More Text Challenge. For details, see:August is more challenging
C++ basic review series — sun bujian 1208
C++ basic review series 01 (input/output class, calling mathematical function class)
C++ basics review series 2 (print graphics (loop), classic problems)
C++ basic review series 3 (recursive algorithm) {Fibonacci function, Hanoi issues}
C++ basics review series 4 (summary of scattered data)
C++ basics review series 5
Five, recursive algorithm
(1) recursion
Recursion: An algorithm that solves problems by calling itself to “recurse” and “return” during operation. Recursive algorithms are generally used to solve three types of problems: (1) the definition of data is defined recursively. Fibonacci function (2) the solution of the problem is realized by recursive algorithm. Although this kind of problem itself has no obvious recursive structure, but the recursive solution is simpler than the iterative solution, such as Hanoi problem. (3) The structure of data is defined recursively. Such as binary tree, generalized table, etc., because of the inherent recursive characteristics of the structure itself, their operations can be described recursively.
(2) The three elements of recursion
First element: What do you want with this function
The important thing about recursion is, what does this function do, what does it do, and that’s completely up to you to define. In other words, we don’t care what the code in the function is, but we need to know what the function is for. So let’s say I define a function
// Calculate n factorial (assuming n is not 0)
int f(int n)
{}Copy the codeAnd what this function does is it calculates n factorial. Okay, so now that we’ve defined a function, and we’ve defined what it does, let’s look at the second element.
The second element: find the end condition of recursion
Recursion means that the function itself is being called inside the code of the function, so we have to figure out the end condition of the recursion, otherwise we’re going to keep calling ourselves into an infinite loop. In other words, we need to find out what the argument is, we need to end the recursion, and we need to directly return the result, and notice that we need to be able to directly know what the result of the function is based on the value of the argument. For example, in the example above, when n = 1, then you should be able to directly know what f(n) is, right? In this case, f of 1 is equal to 1. Refine the code inside our function by adding the second element to the code, as follows
// Calculate n factorial (assuming n is not 0)
int f(int n)
{
if(n == 1)
{
return 1; }}Copy the codeOne might say, well, when n is equal to 2, then we know directly what f of n is, so can I use n is equal to 2 as the end of the recursion? Of course, as long as you know what the argument is, and you know what the result of the function is, then you can use that argument as the end condition, so the following code is ok.
// Calculate n factorial (assuming n>=2)
int f(int n){
if(n == 2) {return 2; }}Copy the codeNote the comment in my code, assuming n >= 2, because if n = 1, it will be missed, and if n <= 2, f(n) = n, so to be more rigorous, we can write it like this:
// Calculate n factorial (assuming n is not 0)
int f(int n){
if(n <= 2) {returnn; }}Copy the codeThe third element: find the equivalent relation of the function
The third element is that we need to keep narrowing down the parameters, and then we can use some auxiliary variables or operations to keep the result of the function the same. For example, f of n, which is a big range, we could set f of n equal to n times f of n minus 1. So the range from n to n minus 1, the range is smaller, and in order to keep the function f of n constant, we need to multiply f of n minus 1 times n. In other words, we want to find an equivalent relationship for this function, and the equivalent relationship for f of n is n times f of n minus 1, which is equal to n times f of n minus 1. So having found this equivalence relationship, and continuing to refine our code, we write this equivalence into our function. As follows:
// Calculate n factorial (assuming n is not 0)
int f(int n){
if(n <= 2) {return n;
}
// Write the equivalent operations for f(n)
return f(n- 1) * n;
}
Copy the codeSo far, all three elements of recursion have been written into the code, so we’ve written the internal code for this f(n) function. These are the three most important elements of recursion.
(3) Recursion simple case
Example 1: Fibonacci series
The Fibonacci sequence is the sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34…. The first term f(1) = 1, the second term F (2) = 1….. , the NTH item is f(n) = f(n-1) + f(n-2). Let’s figure out what the NTH term is.
1, the first recursive function function
Suppose the function of f(n) is to find the value of the NTH term, and the code is as follows:
int f(int n){}Copy the code2. Find the conditions for the end of the recursion
Obviously, when n is equal to 1 or n is equal to 2, we can easily see that f of 1 is equal to f of 2 is equal to 1. So the end of recursion condition can be n <= 2. The code is as follows:
int f(int n){
if(n <= 2) {return 1; }}Copy the code3. Find the equivalent relation of the function
They’ve given us the equivalent relationship, so we can easily see that f of n is equal to f of n minus 1 plus f of n minus 2.
So the final code looks like this:
int f(int n){
// 1. Write the end-of-recursion condition first
if(n <= 2) {return 1;
}
// 2. Then write the equivalent relation
return f(n- 1) + f(n - 2);
}
Copy the codeCase 2: HZX jump steps
HZX is a brave pig who can jump up 1 or 2 steps at a time. Find out how many ways HZX can jump up an n step.
1, the first recursive function function
Suppose the function of f(n) is to find out how many ways HZX can jump up an n step. The code is as follows:
int f(int n){}Copy the code2. Find the conditions for the end of the recursion
For the end of the recursion, let’s just make n very, very small, because the smaller n is, the easier it is to figure out intuitively what f(n) is, so when n is equal to 1, we know what f(1) is, right? F of 1 is equal to 1. The code is as follows:
int f(int n)
{
if(n == 1)
{
return 1; }}Copy the code3. Find the equivalent relation of the function
Each time you jump, HZX can jump one step or two steps, so each time you jump, there are two ways for HZX to jump. The first jump method: the first time HZX jumps a step, then there are n-1 steps left to jump, the remaining N -1 steps of the jump method has f(n-1). The second way: the first time HZX jumped two steps, so there are n-2 steps left, and there are f(n-2) ways to jump the remaining N -2 steps. So, all the jumps for HZX are the sum of these two jumps, f(n) = f(n-1) + f(n-2). So now we have the equivalent relation. So write the code as follows:
int f(int n)
{
if(n == 1)
{
return 1;
}
return f(n- 1) + f(n2 -);
}
Copy the codeDo you think the above code is correct? That’s not true. When n is equal to 2, obviously f of 2 is equal to f of 1 plus f of 0. We know that f of 0 is equal to 0, so we don’t have to keep calling it, but in our code above, we’re going to keep calling f of 0 is equal to f of -1 plus f of -2. This leads to an infinite number of calls and an infinite loop. This is also what we need to pay attention to. As for the problem of whether the closing condition of recursion is rigorous enough, many people use recursion, because the closing condition is not rigorous enough, resulting in infinite loop. That is to say, when we are at the end of the second step is to find a recursive conditions, can write the ending condition into the code, and then to the third step, but please note, when we step 3 to find equivalent function, still have to return to the second step, according to the third step function call relations, will appear a few missed the end of the conditions. Just like up here, the call to f of n minus 2, it’s possible that the call to f of 0 will lead to an infinite loop, so let’s just fill it in. The total code is as follows:
int f(int n)
{
if(n <= 2)
{
return n;
}
return f(n- 1) + f(n2 -);
}
Copy the codeCase 3: The Tower of Hannover problem
Problem description:
Legend has it that in the ancient Indian temple, there is a game called Hanoi (Hanoi). The game is played on A copper plate device with three rods (numbered A, B and C), on which 64 gold plates are placed in order from large to small from bottom to top (as shown below). The goal of the game: move all the gold plates on rod A to rod C, and keep the original order stacked. Operation rules: only one plate can be moved at A time, and in the process of moving, the three rods always keep the plate down, the small plate in the process of operation, the plate can be placed on A, B, C any rod.
Problem analysis:
Let the three pillars be named X, Y, and Z. The plate is on pillar X and should be moved to pillar Z.
1. When n=1, the plate moves directly from x column to Z column;
2. When n>1, then
(1) Try to move the first N — 1 plate from X to y column with the help of Z, and move the plate n from X to Z column;
② Move n — 1 plate from Y to Z pillar.
The Tower of Hanover problem can be divided into three sub-problems:
1.Hanoi(n-1, x, z, y)
// Move n-1 disk on column X to column Y by means of column Z, and then only the n disk on column X is left;
2.Move(n, x, z)
// Move n from X column to Z column
3.Hanoi(n-1, y, x, z)
// Move n-1 disks on column Y to column Z by means of column X;
If n is equal to 1, you can solve for it directly
Visual diagram
#include <iostream>
using namespace std;
long count = 0;// Record the number of moves
void hanoi(int n,char a,char b,char c) // For n plates, move a to C and use B as a temporary tower
{
if (1 == n)
{
cout<<"The first"<<++count<<"Time."<<a<<"The tower -- - >"<<c<<"The tower"<<endl;
}
else
{
hanoi(n- 1,a,c,b);// Make a recursive call where a moves to B and C makes a temporary tower
cout<<"The first"<<++count<<"Time."<<a<<"The tower -- - >"<<c<<"The tower"<<endl;
hanoi(n- 1,b,a,c); }}int main(a)
{
int n;
cout<<"Enter the number of Tower of Hannot disks:";
cin>>n;
hanoi(n,'A'.'B'.'C');
return 0;
}
Copy the codeCase 4: The problem of dividing fish
Problem description:
The five men, A, B, C, D, and E, had been fishing together for the night. They were tired by the early morning, so they each found A place among the trees by the river and fell asleep. The next morning, A was the first to wake up. He divided the fish into five parts and threw the spare part back into the river. Then he took his share home. The second person wakes up, but does not know that A has already taken A portion of the fish, so he divides the remaining fish into five pieces, throws away the extra one, and then takes only his share. Then C, D, and E woke up in turn, and they all divided the fish in the same way. How many fish did they catch together? How many fish does everyone see when they wake up?
Problem analysis
Suppose that five people have caught x fish together, and “A wakes up first, divides the fish into five, throws the extra one back into the river, and goes home with his own”, there are still 4(x-1)/5 fish left. If Xn is the total number of fish before the NTH (n=1, 2, 3, 4, 5) individual divides, then (xn-1)/5 must be a positive integer. (xn-1)/5 is a positive integer that is (X ~ L)mod5=0 must be true. According to the question, there should be the following equation: 4 X4 = (x 5-1) / 5 X3 = 4 X4-1) / 5 X2-4 5 X1 = 4 (X3-1)/(X2-1) / 5
#include<iostream>
using namespace std;
int fish(int n, int x)
{
if((x- 1) %5= =0)
{
if(n == 1)
return 1;
else
return fish(n- 1, (x- 1) /5*4);
}
return 0; Return 0 if x is not a valid solution
}
int main(a)
{
int i=0, flag=0, x;
do
{ i=i+1;
x=i*5+1; // The minimum value of x is 6, and then each increment is 5
if(fish(5, x)) // Pass x into the partition recursive function to verify
{
flag=1; // Set the flag bit to 1 when the first x is found
cout<<"The total number of fish caught by a team of five is<<x; }}while(! flag);// If x is not found, continue the loop, otherwise exit the loop
return 0;
}
Copy the code