This is a classic recursion.
Analysis: This is a very good example of recursive programming. Unlike the previous recursive program, he first had a non-recursive program and then rewritten it into recursive form. If this problem does not use recursive procedures, it may not start. Let's take three pieces of gold as an example:
To move from bar a to bar b, you must make the conversion with the help of bar C. The mobile scheme is:
A-B
Step 2 A-C
Step 3 B-C
A-B
Step 5 C-A
Step 6 C-B
A-B
* * * Move seven times to complete the three gold nuggets on the A pole, and move to the B pole according to the rules required by the topic.
The title requires that n gold coins be moved from pole A to pole B in the same way:
1. First (recursively) move the n- 1 block above the A bar to the C bar (using the B bar);
2. Then move the only piece on the A bar to the B bar;
3. Then move the n- 1 block on article C (recursively) to article B (using article A).
This is a recursive calling process. The process is as follows:
Program P6-14;
defined variable
N: integer;
Process movement (n: integer; a,b,c:char); {Define recursive procedures}
begin
If n= 1
writeln('move ',n,' from ',a,' to ',b)
Else {multiple slices, recursive}
begin
move(n- 1,a,c,b); {recursively move the n- 1 block from A to C, and use lever B for conversion}
writeln('move ',n,' from ',a,' to ',b); {The last movie moved from A to b}
Move (n- 1, c, a, b); {recursively move n- 1 on rod C to rod B, and use rod A for transition}
End;
End;
Start {main program}
Write ('enter n:');
Read as (n);
move(n,' A ',' B ',' C ');
End.
Run:
Enter n: 3 (Enter)
Move 1 from A to B.
Move 2 from a to c
Move 1 from B to C.
Move 3 from A to B.
Move 1 from c to a.
Move 2 from c to b
Move 1 from A to B.
When the program is running, enter the value of n. You can choose 4, 5 and 6 except 3, but never enter 64. Because through deduction, if you move 64 gold coins according to the rules, you have to move 264-1=1.8 *1019 times. If it moves once every second, it will take one trillion years. According to scientific calculations, the "life span" of the earth is about billions to tens of billions of years. You can see the destruction of the earth, and you can't finish the game. Even if the computer "moves" 100 million times per second, it will take 5800 years, so it is impossible to complete the game.
Is this detailed enough? Excerpted from "Pascal Language Middle School Edition 2nd Edition, Training Textbook of Youth Informatics Olympic Competition" in beijing institute of technology press, this is not bad.