Source: blog.csdn.net/zandaoguang…
I. introduction :(easy to understand)
Hannotta’s seemingly simple lines of code contain a fantastic algorithm. I speak from my personal learning point of view. I understood the principle at first, but I couldn’t write the code. Do more research and debug in IDE (Eclipse-Java,VS-C/C++), read it a few times and I think we will make progress together! Come on, for their own goals.
When there is only one plate, just move one plate from tower A to tower C.
When there are two plates on tower A, first move the no.1 plate (numbered from top to bottom) from tower A to Tower B, then move the no.2 plate from tower A to Tower C, and finally move the small plate from tower B to Tower C.
When there are three plates on tower A, first move the plates numbered 1 to 2 from tower A to Tower B (with the help of Tower C), then move the largest plate no. 3 from tower A to Tower C, and finally move the two plates from tower B to tower C with the help of tower A.
If there are n plates on tower A, move the plates numbered from 1 to N-1 (n-1 in total) from tower A to Tower B (with the help of Tower C), then move the largest plate no. N from tower A to Tower C, and finally move the n-1 plates from tower B to tower C with the help of tower A.
To sum up, the situation is the same except when there is only one plate and no other tower is needed (only the complexity of the event is different). Hannota (also known as Hanoi Tower) is a puzzle toy derived from an ancient Indian legend. Mahama made three diamond pillars when he created the world, and on one pillar were stacked 64 gold disks in ascending order of size. Mahama ordered the Brahmin to rearrange the disks on another pillar, starting from below, in order of size. It is also stipulated that the disk cannot be enlarged on the small disk and that only one disk can be moved at a time between the three columns.
Second, the graphic
As shown in the figure below, from left to right there is A, B, C three pillars, in which A column above the fold since childhood to the big n disc, hereby request A pillar of the disc will be moved to the C column, there is only one principle: during A can only be moved to A big plate and not on the small plate plate, the number of steps for mobile and mobile \
Solution :(1) n == 1
Disk 1 ---->C sum = 1 (2) n == 2 Disk 1 A---->B Disk 2 A---->C Disk 3 B---->C sum = 3Copy the code(3) n == 3
Drive number 1 A — >C
No. 2 drive A — >B
No. 3 drive 1 C — >B
No. 4, No. 3 A — >C
Drive 5, Drive 1, B — >A
No. 6, No. 2 B — >C
A — >C sum = 7 times
It’s not hard to see the pattern: the degree of a disk is 2 to the first minus 1
The degree of 2 disks 2 to the 2nd minus 1
The degree of 3 disks 2 to the third minus 1. . . . . N disks 2 to the NTH power minus 1Copy the codeSo: number of moves: 2^n – 1
3. Stack mechanism for calling methods: (Features: First in, last out)
Starting from the main thread calls the method (functions) for constant pressure and the stack operation, function call is to press the function such as stack, the end of the function is the function of the stack, the process of flow, thus ensure the method call order when there was a multilayer nested function, need from the outer to the inner layers of the function in the stack, Finally, the function at the top of the stack finishes first (the innermost function finishes first) and exits the stack, the function at the penultimate level finishes and exits the stack, and finally, the first function on the stack pops back to the main thread after the call ends, and terminates.Copy the codeFour. Algorithm analysis (recursive algorithm) :
When we use the computer to solve the Hannotta problem, the essential step is to analyze the algorithm of the whole solution. So far, the simplest algorithm of Hanoi problem solving or with a recursion, as to what is recursive, recursive implementation mechanism, we say that simple point is oneself is a method or function, but in are there in this function calls itself the function of the statement, and the end of this call how can I call? And there has to be an end point, or more specifically, after a call the function returns a certain value, and then the penultimate function returns a certain value, until the first call of the function returns a certain value. The realization of this algorithm can be simply divided into three steps:Copy the code(1) Move n-1 plates from A to B;
(2) Move the NTH plate from A to C;
(3) Move n-1 plates from B to C;
Starting from this, plus the analysis of the above mathematical problem solution, it is not difficult to find that the number of steps to be moved must be an odd number of steps:
(1) The middle step is to move the largest dish from A to C;
(2) Above the middle step, it can be seen that n-1 plates on A are moved to B with the help of the auxiliary tower (tower C).
(3) In the middle step, n-1 plates on B are moved to C with the help of the auxiliary tower (tower A);
Five,javaThe source code:
package alizantest; import java.util.Scanner; public class Hanoi2 { static int m = 0; Public static void move(int disks, char N, char M) {system.out.println (" + (++ M) + "); "+" the disk "+ disks +", from "+ N +" - > to - > "+ M); } public static void Hanoi (int n, char A, char B, char C) {if (n == 1) Move (1, A, C); move(1, A, C); Hanoi (n-1, A, C, b); Move (n, A, C); move(n, A, C); move(n, A, C); Hanoi (n-1, B, A, C); }} public static void main(String[] args) {Scanner in = new Scanner(system.in); char A = 'A'; char B = 'B'; char C = 'C'; System.out.println("******************************************************************************************"); Println (" Hanover's Tower problem, moving small to large disks from Tower A to Tower C through Tower B "); System.out.println("******************************************************************************************"); System.out.print(" Please input number of disks: "); int n = in.nextInt(); Hanoi2.hanoi(n, A, B, C); System.out.println(">> move "+ m +", move all disks on A to C "); in.close(); }}Copy the codeSix. Illustrated program running process:
(1) Hanoi (int n,char A,char B,char C)
(2) Move (int n,char n,char M) moves (int n,char n,char M) from n to M
