Java hannotarhanoi recursion non recursion of of system recursion and non recursion law implementation code

View Code 
 
 package part03.chapter10;

 import java.util.Scanner;

 public class _2exercise {

     public static void main(String[] args) {

         Scanner scanner = new Scanner(System.in);
         System.out.println(" Please enter the Hanoi Number of dishes: ");
         int diskNum = scanner.nextInt();
         Hanoi hanoi = new Hanoi();
         System.out.println(" Recursive implementation: ");
         hanoi.play_recursive(diskNum, 'A', 'B', 'C');
         System.out.println(" Non-recursive implementation ( Imitate the idea of recursion ) : ");
         hanoi.play_non_recursive(diskNum);
         System.out.println(" Non-recursive implementation ( According to the Hanoi regular ) : ");
         hanoi.play_regular(diskNum);

     }

 }

 class Hanoi {

     //The recursive implementation
     public void play_recursive(int num, char A, char B, char C) {
         if (num == 1) {
             System.out.println(A + " -> " + C);
             return;
         } else {
             play_recursive(num - 1, A, C, B);
             System.out.println(A + " -> " + C);
             play_recursive(num - 1, B, A, C);
         }

     }

     //Non-recursive implementation: mimics the idea of recursion
     public void play_non_recursive(int diskNum) {
         Stack stack = new Stack();
         stack.push(new Disk(diskNum, 'A', 'B', 'C'));
         Disk popDisk = null;
         while ((popDisk = stack.pop()) != null) {
             if (popDisk.status == 1) {
                 System.out.println(popDisk.A + " -> " + popDisk.C);
             } else {
                 //Antisequential addition
                 //Adds the next Disk that performs the move popDisk to the Stack
                 stack.push(new Disk(popDisk.status - 1, popDisk.B, popDisk.A,
                         popDisk.C));
                 //Add a Disk with a status of "1" and the same order of movement as popDisk to the Stack
                 stack.push(new Disk(1, popDisk.A, popDisk.B, popDisk.C));
                 //Adds to the Stack the Disk from the previous step to perform the move popDisk
                 stack.push(new Disk(popDisk.status - 1, popDisk.A, popDisk.C,
                         popDisk.B));
             }
         }
     }

     //Non-recursive implementation: according to Hanoi law
     public void play_regular(int diskNum) {

         //As a rule, the locations of the multiple towers need to be adjusted according to the number of disks
         //When the number of towers is even, press "A-> B -> The order of C "is arranged in a triangle
         //When the number of towers is odd, press "A-> C -> B" is arranged in a triangle
         //Place diskNum disks in tower A (stack implementation) in order of "up, down, and down", while leaving tower B and tower C empty
         Stack_play_regular A = new Stack_play_regular('A');
         Stack_play_regular B = new Stack_play_regular('B');
         Stack_play_regular C = new Stack_play_regular('C');
         for (int i = diskNum; i > 0; i--) {
             A.push(i);
         }
         //Arrange the three towers in a triangular shape
         Stack_play_regular[] towers = new Stack_play_regular[3];
         towers[0] = A;
         if (diskNum % 2 == 0) {
             towers[1] = B;
             towers[2] = C;
         } else {
             towers[1] = C;
             towers[2] = B;
         }
         //The smallest Dish in the tower, through the tower in the towers
         int towerOfMinimunDisk = 0;
         //According to the proof: n Disk moves to complete at least 2^n-1 times
         //Alternate between the following two steps
         //Move the smallest Disk down to the next tower in the order above
         //There are two possible scenarios for operating on two towers other than the one with the smallest Disk
         //Case 1: if there is no Disk in a tower, move the top Disk of the tower with Disk to the tower without Disk
         //Case two: both towers have disks, so compare their topmost tower and move the smaller Disk to the larger one
         //There can be no Disk in either tower, unless the movement has been completed or not started or there is only one plate
         int ii = 0;
         for (int i = 0; i < (Math.pow(2, diskNum) - 1);) {//-- notice that there is no i++ here
             //Take out the three towers to make the code clearer
             Stack_play_regular tower = towers[towerOfMinimunDisk];
             Stack_play_regular tower_1 = towers[(int) ((towerOfMinimunDisk + 1) % 3)];
             Stack_play_regular tower_2 = towers[(int) ((towerOfMinimunDisk + 2) % 3)];
             //Move the smallest plate
             System.out.println(tower.name + " -> " + tower_1.name);
             tower_1.push(tower.pop());
             i++;//-- notice i++ here
             towerOfMinimunDisk = (int) ((towerOfMinimunDisk + 1) % 3);
             //-- notice the reassignment of the three towers
             tower = towers[towerOfMinimunDisk];
             tower_1 = towers[(int) ((towerOfMinimunDisk + 1) % 3)];
             tower_2 = towers[(int) ((towerOfMinimunDisk + 2) % 3)];
             //The other two towers are treated
             if ((tower_2.getTop() != -1 && (tower_1.showTopDisk() > tower_2
                     .showTopDisk()))
             //-- tower_2.gettop ()! = 1
             //Make a judgment, otherwise the array access may overstep the bounds
                     || (tower_1.getTop() == -1 && tower_2.getTop() != -1)) {
                 System.out.println(tower_2.name + " -> " + tower_1.name);
                 tower_1.push(tower_2.pop());
                 i++;//-- notice i++ here
             } else if (((tower_1.getTop() != -1 && tower_1.showTopDisk() < tower_2
                     .showTopDisk()))
             //-- tower_1.gettop ()! = 1
             //Make a judgment, otherwise the array access may overstep the bounds
                     || (tower_1.getTop() != -1 && tower_2.getTop() == -1)) {
                 System.out.println(tower_1.name + " -> " + tower_2.name);
                 tower_2.push(tower_1.pop());
                 i++;//-- notice i++ here
             }
             ii = i;
         }
         System.out.println(ii);
     }

 }

 //A structure for holding information
 class Disk {
     //From tower A through tower B to tower C
     char A;
     char B;
     char C;
     //Tower status: when status=1, the Disk can be moved directly to the target tower
     int status;

     //Rewrite constructor
     public Disk(int status, char A, char B, char C) {
         this.status = status;
         this.A = A;
         this.B = B;
         this.C = C;
     }
 }

 //The stack that holds the Disk
 class Stack {
     //An array of dishes to store
     Disk[] disks = new Disk[10000];
     //The top of the tower
     private int top = 0;

     //Look at the top
     public Disk stackTop() {
         return disks[top];
     }

     //Out of the stack
     public Disk pop() {
         if (top != 0) {
             top--;
             return disks[top + 1];
         } else {
             return null;
         }
     }

     //Into the stack
     public void push(Disk disk) {
         top++;
         disks[top] = disk;
     }
 }

 //The Stack class created for play_regular(int diskNum)
 //DiskId represents a Disk object
 class Stack_play_regular {
     //Tower of
     char name;
     //The top of the tower
     private int top = -1;

     public int getTop() {
         return top;
     }

     //Implement the Stack through an array, up to 64 disks
     int[] stack = new int[64];

     //Rewrite constructor , the name of the initialization tower name
     public Stack_play_regular(char name) {
         this.name = name;
     }

     //Look at the top
     public int showTopDisk() {
         if (top == -1) {
             return -1;
         }
         return stack[top];
     }

     //Into the stack
     public void push(int diskId) {
         stack[++top] = diskId;
     }

     //Out of the stack
     public int pop() {
         return stack[top--];
     }
 }