- 2021-01-17 20:41
*views 24*- 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

Daily Recommendation

views 5

views 3

©2019-2020 Toolsou All rights reserved,

Solve in servlet The Chinese output in is a question mark C String function and character function in language MySQL management 35 A small coup optimization Java performance —— Concise article Seven sorting algorithms （java code ） use Ansible Batch deployment SSH Password free login to remote host according to excel generate create Build table SQL sentence Spring Source code series ( sixteen )Spring merge BeanDefinition Principle of Virtual machine installation Linux course What are the common exception classes ?