Java hannotarhanoi recursion non recursion of of system recursion and non recursion law implementation code
- 2020-04-01 01:52:37
- OfStack
The procedure is as follows:
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--];
}
}