java implementation tower of Hannott details and implementation code
- 2020-07-21 08:11:06
- OfStack
java implementation tower of Hannott details and implementation code
Hanoi problem: there are three pillars A B, C, including A with n a disc, the disc from top to bottom gradually increase, can only move one disk at a time, and prescribed large disk cannot be stacked above the disc of the small, now want to move in all the A n above a disc to C, total output mobile number and the process of moving
Analysis:
// So let's figure out the total number of moves
1 , it is assumed that g ( n ) said n The total number of moves at the number of disks, when n=1 When, g(1)=1;
2. Now we can put g(n) Subdivide into 3 Step:
1> First the n-1 A disc from A through C Move to the B Up here, it's going to be equal to n-1 A disc from A Move to the C Therefore, it is necessary to g(n-1) Step;
2> And then you take the largest remaining disk from A Move to the C , you need to 1 Step;
3> Finally, the n-1 A disc from B through A Move to the C Up here, it's going to be equal to n-1 A disc from A Move to the C , so it also needs to g(n-1) Step;
Therefore, the recursive relation can be obtained as follows: g(n) = 2*g(n-1)+1;
// Now we're going to figure out how to move
1. Assuming that hm(m,a,b,c) Said it would m A disc from a through b Move to the c Process, hypothesis mv(a,c) The output 1 time a to c The process of, i.e print a-->c
2. Initialize the hm when m=1 When, hm(1,a,b,c)=mv(a,c);
2. Can put the hm(m,a,b,c) Subdivide into 3 Step:
1> First the n-1 A disc from A through C Move to the B At this time, b and c I'm going to swap it out hm(m-1,a,c,b);
2> And then you take the largest remaining disk from A Move to the C , that is, hm(1,a,b,c);
3> The final will be n-1 A disc from B through A Move to the C At this time, b and a I'm going to make the exchange, which is theta hm(m-1,b,a,c);
Finally, the recursive relation of the process is obtained: hm(m,a,b,c) = hm(m-1,a,c,b)+1+hm(m-1,b,a,c);
Implementation code:
public class test{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
test t = new test();
// Gets the total number of steps
System.out.println(" The total number of steps to move is :" +t.getSum(n));
// The process of getting a move
t.hm(n,'a','b','c');
}
// Gets the total number of steps
public int getSum(int n){
if(n == 1)
return 1;
return 2 * getSum(n-1) +1 ;
}
// The process of getting a move
public void hm(int m,char a,char b,char c){
if(m == 1)
move(a,c);
hm(m-1,a,c,b);
move(a,c);
hm(m-1,b,a,c);
}
// The output 1 The process of secondary movement
public void move(char a,char c){
System.out.print(a + "-->" + c + " ");
}
}
Thank you for reading, I hope to help you, thank you for your support to this site!