java implementation tower of Hannott details and implementation code

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!