java 漢諾塔Hanoi遞歸、非遞歸(仿體系遞歸)和非遞歸紀律 完成代碼。本站提示廣大學習愛好者：（java 漢諾塔Hanoi遞歸、非遞歸(仿體系遞歸)和非遞歸紀律 完成代碼）文章只能為提供參考，不一定能成為您想要的結果。以下是java 漢諾塔Hanoi遞歸、非遞歸(仿體系遞歸)和非遞歸紀律 完成代碼正文
法式以下：
View Code
/*
* Hanoi塔游戲 成績描寫：
* 漢諾塔：漢諾塔（又稱河內塔）成績是源於印度一個陳舊傳說的益智玩具。
* 年夜梵天發明世界的時刻做了三根金剛石柱子，在一根柱子上從下往上依照
* 年夜小次序摞著64片黃金圓盤。年夜梵天敕令婆羅門把圓盤從上面開端按年夜小
* 次序從新擺放在另外一根柱子上。而且劃定，在小圓盤上不克不及縮小圓盤，在
* 三根柱子之間一次只能挪動一個圓盤。
*
* fuction:完成 hanoi塔
* 1.遞歸完成
* 2.非遞歸完成
* author:iGeneral
* date:2013.04.26
*
* expe:
* 1.留意：塔的狀況:當status=1時，表現可以直接將該Disk挪動到目的塔
* 而不是用Disk的id來斷定輸入
* 2.System.out.println();
System.out.println((int)3.3%3);
沒有(int)時，輸入：0.299999
加上(int)後，輸入：0
*/
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("請輸出Hanoi碟子的數目：");
int diskNum = scanner.nextInt();
Hanoi hanoi = new Hanoi();
System.out.println("遞歸完成：");
hanoi.play_recursive(diskNum, 'A', 'B', 'C');
System.out.println("非遞歸完成(模擬遞歸思惟)：");
hanoi.play_non_recursive(diskNum);
System.out.println("非遞歸完成(依據Hanoi紀律)：");
hanoi.play_regular(diskNum);
}
}
class Hanoi {
// 遞歸完成
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);
}
}
// 非遞歸完成：模擬遞歸思惟
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 {
// 反次序添加
// 將履行挪動 popDisk 的下一步的Disk添加到Stack
stack.push(new Disk(popDisk.status - 1, popDisk.B, popDisk.A,
popDisk.C));
// 將一個status為 "1" 且挪動次序與 popDisk 雷同的Disk 添加到Stack中
stack.push(new Disk(1, popDisk.A, popDisk.B, popDisk.C));
// 將履行挪動 popDisk 的前一步的Disk添加到Stack中
stack.push(new Disk(popDisk.status - 1, popDisk.A, popDisk.C,
popDisk.B));
}
}
}
// 非遞歸完成：依據Hanoi紀律
public void play_regular(int diskNum) {
// 依據紀律，須要依據 Disk 的個數，多塔的地位停止調劑
// 塔的個數為偶數時，將三個塔按“A->B->C”的次序分列成三角形
// 塔的個數為奇數時，將三個塔按"A->C->B"的次序分列成三角形
// 將diskNum個Disk按”上小下年夜“的次序放在A塔中（客棧完成），同時將B塔和C塔置空
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);
}
// 將三個塔模仿成三角形外形分列
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;
}
// 最小Dish地點的塔，經由過程該塔在towers中的
int towerOfMinimunDisk = 0;
// 依據證實：n個Disk挪動完成至多須要2^n-1次
// 赓續瓜代停止以下兩步
// 將最小的Disk按以上塔的次序下移到下一個塔
// 對除最小Disk地點的塔的別的兩個塔停止操作，能夠湧現兩種情形
// 情形一：一個塔中沒有Disk，此時將存在Disk的塔最下面的Disk挪動到沒Disk的塔上
// 情形二：兩個塔都有Disk，此時對他們最下面的塔停止比擬，將較小的Disk挪動到較年夜的Disk上
// 不會存在兩個塔都沒有Disk的情形，除非挪動曾經完成或未開端或只要一個盤子時的挪動
int ii = 0;
for (int i = 0; i < (Math.pow(2, diskNum) - 1);) {// --------------留意在此處不停止i++
// 掏出三個塔，使代碼更清楚
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)];
// 挪動最小的盤子
System.out.println(tower.name + " -> " + tower_1.name);
tower_1.push(tower.pop());
i++;// --------------留意在此處停止i++
towerOfMinimunDisk = (int) ((towerOfMinimunDisk + 1) % 3);
// ------------留意此時對三個tower停止從新賦值
tower = towers[towerOfMinimunDisk];
tower_1 = towers[(int) ((towerOfMinimunDisk + 1) % 3)];
tower_2 = towers[(int) ((towerOfMinimunDisk + 2) % 3)];
// 對別的兩個塔停止處置
if ((tower_2.getTop() != -1 && (tower_1.showTopDisk() > tower_2
.showTopDisk()))
// --------------留意要再加上 tower_2.getTop() != -1
// 停止斷定，不然能夠數組拜訪越界
|| (tower_1.getTop() == -1 && tower_2.getTop() != -1)) {
System.out.println(tower_2.name + " -> " + tower_1.name);
tower_1.push(tower_2.pop());
i++;// --------------留意在此處停止i++
} else if (((tower_1.getTop() != -1 && tower_1.showTopDisk() < tower_2
.showTopDisk()))
// --------------留意要再加上 tower_1.getTop() != -1
// 停止斷定，不然能夠數組拜訪越界
|| (tower_1.getTop() != -1 && tower_2.getTop() == -1)) {
System.out.println(tower_1.name + " -> " + tower_2.name);
tower_2.push(tower_1.pop());
i++;// --------------留意在此處停止i++
}
ii = i;
}
System.out.println(ii);
}
}
// 寄存信息的構造體
class Disk {
// 從A塔經由過程B塔挪動到C塔
char A;
char B;
char C;
// 塔的狀況:當status=1時，表現可以直接將該Disk挪動到目的塔
int status;
// 重寫結構函數
public Disk(int status, char A, char B, char C) {
this.status = status;
this.A = A;
this.B = B;
this.C = C;
}
}
// 寄存Disk的棧
class Stack {
// 用來存儲盤子的數組
Disk[] disks = new Disk[10000];
// 塔頂
private int top = 0;
// 檢查棧頂
public Disk stackTop() {
return disks[top];
}
// 出棧
public Disk pop() {
if (top != 0) {
top--;
return disks[top + 1];
} else {
return null;
}
}
// 入棧
public void push(Disk disk) {
top++;
disks[top] = disk;
}
}
// 為 play_regular(int diskNum) 創立的 Stack 類
// 以 diskId 來表現 Disk 對象
class Stack_play_regular {
// 塔名
char name;
// 塔頂
private int top = -1;
public int getTop() {
return top;
}
// 經由過程數組完成Stack,最多64個Disk
int[] stack = new int[64];
// 重寫結構函數，初始化塔的名字name
public Stack_play_regular(char name) {
this.name = name;
}
// 檢查棧頂
public int showTopDisk() {
if (top == -1) {
return -1;
}
return stack[top];
}
// 入棧
public void push(int diskId) {
stack[++top] = diskId;
}
// 出棧
public int pop() {
return stack[top--];
}
}
