October 30, 2021 schedule

Recursion and recursion -- by Toby

First, let's tell a story!

On a sunny morning, shashiri stayed in her room and you stood outside her room. (what do you think?!) (FOG)

Interestingly, shashili suddenly found a door in her room, so she pushed the door in with curiosity.
Even more as like as two peas, the new room she entered was exactly the same as the old one, and there was also such a magical door. So she pushed the door in again.
But the room is as like as two peas. Shashiri felt very confused, but she still planned to go on.
But she was very clever. She planted a flower in this room and hoped that the flower would be in full bloom when she came back. Then she went into the next room.
Then she saw many of the same rooms, and she planted a seed in every room she passed.

Until

What shashiri doesn't know at this moment is that she is in the program you write, and you will determine her fate.
Please select the following codes to determine the direction of the story:

• A.

  int main()
  {
      for (int i = 0; i < total_rooms; i++)
      {
          create_room();
      }
      return 0;
  }
  

• B.

  void recursion(int room_id)
  {
      if(room_id <= 0) return;
      create_room();
      recursion(room_id + 1);
  }
  
  int main()
  {
      recursion(1);
      return 0;
  }
  

• C.

  void recursion(int room_id)
  {
      if(room_id > total_room) return;
      create_room();
      recursion(room_id + 1);
  }
  
  int main()
  {
      recursion(1);
      return 0;
  }
  

General recursive form

The C option of the above story has presented A recursive way of writing. But obviously, this writing can also be replaced by the cycle in A. In fact, almost all recursions can be replaced by loops, but sometimes it's very troublesome to write.

Now let's fully implement the above story:

void SayoriRoom(int room_id)
{
    if(room_id == total_room)
    {
        leaveRoom(room_id);
    }
    enterRoom(room_id);
    raiseFlower();
    SayoriRoom(room_id+1);
    pluckFlower();
    exitRoom(room_id);
}

As you can see, this is a very basic recursive pattern:
That is, do something before calling yourself recursively, then call yourself recursively, do something with when you come back, and then end.

answering question

Hanoi

Many people ask this question. So let's focus on it.

First find the recursive boundary! Any recursion must first have a recursion boundary.

• Recursive boundary, first of all, must be a very simple problem. For example, only 1 1 One disc.
• Obviously, just move 1 1 One time is enough.

Then think about recursion! If recursion is particularly difficult to think about, think about it first 2 2 2 discs, only 3 3 Three discs.

• only 2 2 When there are two discs, the conclusion is also better, that is, put the small disc on the middle column first, move the large disc to the target column, and then move the small disc to the target column. So there is 3 3 3 operations.
• as for 3 3 3 discs, which can be imitated 2 2 2, first move the small disc and the medium disc to the middle column (3 steps are required according to 2), then move the large disc to the target column, and finally move the small disc and the medium disc to the target column. So need 3 + 1 + 3 = 7 3+1+3=7 3 + 1 + 3 = 7 steps.
• Finally, we found out. For yes n n In the case of n disks, you can put the front n − 1 n-1 Move n − 1 disc to the middle column, then move the largest disc to the target column, and finally move the front n − 1 n-1 n − 1 disc moves to the target column. The number of moves required f ( n ) = f ( n − 1 ) + 1 + f ( n − 1 ) = 2 f ( n − 1 ) + 1 f(n)=f(n-1)+1+f(n-1)=2f(n-1)+1 f(n)=f(n−1)+1+f(n−1)=2f(n−1)+1.

So the problem is solved:

Apply the recursive template in the story just now:

int Hanoi(int n) //If necessary, use long long as the return value
{
    if(n <= 0) return 0; //If we don't have a disc
    if(n == 1) return 1; //Recursive boundary must have, remember! (or you'll like to mention "Sunny Doll")
    int ans;//Instead of planting flowers before entering the next room this time, we need a container to hold flowers (declare a variable to store the answer).
    ans = 2 * Hanoi(n-1) + 1;//Enter the next room (call yourself recursively). This time we use the recursive formula.
    return ans;//Remember to take the flowers back! (pass back the calculation results)
    /*Of course, attentive students can see that the above three lines can actually be a straight line:
    return 2 * Hanoi(n-1) + 1;
    In fact, this line of code implements several functions*/
}

E5-F world line

The author of this question is really bad. The meaning of the question is very unclear. Fortunately, there are examples to explain it

Simply put, the problem is to determine which world line to cross next time according to the value of op.

Go directly to the code:

int WorldLine(int depth, char world) //depth represents the current number of layers and world represents the current location
{
    if(depth == N) //According to the meaning of the topic, N is the recursive boundary
    {
        if(world == 'a') return a;
        if(world == 'b') return b;
        if(world == 'c') return c;
    }
    int ans = 0; //Declare and initialize the storage container
    //Let's consider whether I want to enter a world line in turn
    if(op[depth] & 4) ans += WorldLine(depth+1, 'a');
    if(op[depth] & 2) ans += WorldLine(depth+1, 'b');
    if(op[depth] & 1) ans += WorldLine(depth+1, 'c');
    return ans; //Settlement answer
}
// This code actually has a small problem. I don't know if you have found it (a problem that has nothing to do with recursion)

Combinatorial number problem

Next, let's calculate the combination number. First, you should be familiar with the following two formulas:
C m n = C m − 1 n + C m − 1 n − 1 C m n = C m m − n C^n_m = C^n_{m-1} + C^{n-1}_{m-1} \\ C^n_m = C^{m-n}_m Cmn​=Cm−1n​+Cm−1n−1​Cmn​=Cmm−n​
This is the content of high school mathematics

Now that we have recursion, we can write code!

int Combination(int m, int n) //Choose n from m
{
    if(n == 0 || n == m) return 1; //If you choose 0 in m and n in m, you get 1
    if(n > m / 2) return Combination(m, m - n); //This step is to speed up
    return Combination(m-1, n) + Combination(m-1, n-1);
}

Let's work together

In fact, it's better to say more than to do more. Let's do a problem together!

P1010 power
P1464 memorization
P1928 decompression
P1028 simple DP

These are some courses I chose. The difficulty is normal. In theory, you are likely to take such questions.
(but I guess the test questions will be simpler than this, so you can solve similar recursion problems as long as you write these questions.)

If you are not satisfied, I will send you a whole list of questions:
Reference list

Last last

Finally, I wish you all a happy AK tomorrow!

This class is videotaped! It may leave station B! It is said that one button three company's little partner will be easier to AK tomorrow!

The answer to the story

1-A

Shashili walked and walked. Finally, she came to the last room. The door of this room led to the outside world. Shashili was very happy and rushed out into another world. Unfortunately, she will never come back. It is impossible to see the flowers she planted in full bloom. It is impossible to see you standing at the door waiting for her.

Back to the topic

1-B

The gauze world walked and walked, walked very far, but never saw the end, and couldn't find the way back. Finally, standing at the door, you couldn't help pushing the door in, walked along the road in Shashi, and saw that the flowers she planted were in full bloom. You were in a good mood. But after a long journey, what is waiting for you is not the gauze world, but the sunny doll.

Back to the topic

1-C

Sha Shili walked and walked. Finally, she came to the last room. This room is different from the one in front. The door leading to the next room is closed, and the notice on it says how to return the same way. According to the instructions, shashili returned to the last room. The fragrance of flowers came to her face. The flowers she planted were in full bloom. She took off one of them and went back to the previous room. All the flowers in the rooms she had passed were in full bloom. She selected the most beautiful and fragrant one from each room and held it in her hand. Finally, she returned to the original room. She packed the flowers collected along the way, walked out of the door with a happy mood and gave you all this big bouquet.

Back to the topic