- 2021-01-17 20:41
*views 9*- C++
- algorithm
- C language

The application of function recursive algorithm has a classic example , That's the tower of Hanoi problem , Next, let's take a look at how to solve the tower of Hanoi problem with recursive function !

The origin of the tower of Hanoi problem ：

Hanoi （ Also known as Hanoi tower ） The problem is an old Indian legend . Brahma left three diamond sticks in a temple , The first one is covered with 64 A round piece of gold , The biggest one is at the bottom , The others are smaller than one , Fold them in turn , The monks in the temple tirelessly moved them one by one from one stick to another , It is stipulated that a bar in the middle can be used as a help , But only one at a time , And the big one can't be put on the small one . Facing huge numbers ( The number of times the wafer is moved )18446744073709551615, it seems , The monks exhausted their life energy and could not complete the movement of the gold . later , The legend evolved into the tower of Hanoi game .

Tower of Hanoi rule ：

In a nutshell , That's to say a On the post n A disc , adopt b The column is transported to the ground as an auxiliary c Go to the post . In the process of handling, only one disc can be carried at a time , And the big disk can't be put on the small disk .

What is recursion ?

We should solve this problem recursively , We need to know what recursion is first .

Recursion is when a function calls itself in its body . Executing a recursive function calls itself repeatedly , Each call goes to a new layer . A recursive function must have an end condition .

When the function is recursive all the time , Until you come back against the wall , This wall is the end condition .

So recursion has two elements , End condition and recurrence relation .

problem analysis ：

It's easy for us to know ：

When n=1 Time , We take the plate directly from the table a Column moved to c The column solved the problem .

When n=2 Time , We can put it first a The first plate on the column moves to b column （a The plate on the top of the column is numbered 1, Increase in descending order ）, And then a The second plate on the column moves to c column , And then b The plates on the column move to c Column is enough .

But when n The value of is 3 And then the problem becomes troublesome . So can we simplify the later complex problems into the first two simple cases ?

The answer is yes , This is also the purpose of function recursion ： Simplify complex problems .

code implementation ：

We just need to count the plates n There are two types of solutions ：

When n=1 Time , Remove the plate from the container a->c that will do .

When n>1 Time , take a On the post n-1 A plate moved to b On the pillar , And then a The one left on the post （ That's the second one n individual ） Move to c On the pillar , And then b On the post n-1 Move to ,c Just on the post .（ Remember that we are going to n-1 One plate as a whole ）

among void move(int n, char a, char b, char

c) It means that you want to n A plate from a Through the column b Column moved to c On the pillar .（ Through the number you pass in, that is, characters to achieve the corresponding operation ）

After programming, we can input a relatively easy to detect number to see if the program is correct .

Personal view ：

In my opinion, the tower of Hanoi problem, including most problems that can be solved by function recursion, requires us to have a kind of ability , That's to look at something as a whole . For example, in the case of the tower of Hanoi, we will n-1 As a whole , If you can't do it, have this understanding ability , Then it will be difficult to understand how to use function recursion to solve the tower of Hanoi problem .

Technology

- Java378 articles
- Python197 articles
- Linux110 articles
- MySQL83 articles
- Vue78 articles
- SpringBoot68 articles
- Spring61 articles
- javascript56 articles
- more...

Daily Recommendation

views 2

©2019-2020 Toolsou All rights reserved,

Bitcoin in ten years ,VDS Opportunity or fraud Don't annoy the panda with any cat !「 Kung Fu Panda 」20 It's the year of man 4 blood sort （ one ） bubble sort Random forest R Language implementation java Realize the function of grabbing red packets Python Basic knowledge and notes python To solve the problem of dictionary writing list in CSS architecture design Vue Common features （ one ）2021 year 2 Monthly programmer salary statistics , average 15144 element