java 漢諾塔Hanoi遞歸、非遞歸(仿系統(tǒng)遞歸)和非遞歸規(guī)律 實(shí)現(xiàn)代碼
更新時(shí)間：2013年05月10日 10:19:20 作者：
漢諾塔（Hanoi） 算法Java實(shí)現(xiàn)。通過三個(gè)函數(shù)，分別對(duì)Hanoi進(jìn)行遞歸、非遞歸和非遞歸規(guī)律實(shí)現(xiàn)。
程序如下：
View Code
/*
* Hanoi塔游戲 問題描述：
* 漢諾塔：漢諾塔（又稱河內(nèi)塔）問題是源于印度一個(gè)古老傳說的益智玩具。
* 大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照
* 大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小
* 順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在
* 三根柱子之間一次只能移動(dòng)一個(gè)圓盤。
*
* fuction:實(shí)現(xiàn) hanoi塔
* 1.遞歸實(shí)現(xiàn)
* 2.非遞歸實(shí)現(xiàn)
* author:iGeneral
* date:2013.04.26
*
* expe:
* 1.注意：塔的狀態(tài):當(dāng)status=1時(shí)，表示可以直接將該Disk移動(dòng)到目標(biāo)塔
* 而不是用Disk的id來判斷輸出
* 2.System.out.println();
System.out.println((int)3.3%3);
沒有(int)時(shí)，輸出：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("請(qǐng)輸入Hanoi碟子的數(shù)量：");
int diskNum = scanner.nextInt();
Hanoi hanoi = new Hanoi();
System.out.println("遞歸實(shí)現(xiàn)：");
hanoi.play_recursive(diskNum, 'A', 'B', 'C');
System.out.println("非遞歸實(shí)現(xiàn)(模仿遞歸思想)：");
hanoi.play_non_recursive(diskNum);
System.out.println("非遞歸實(shí)現(xiàn)(根據(jù)Hanoi規(guī)律)：");
hanoi.play_regular(diskNum);
}
}
class Hanoi {
// 遞歸實(shí)現(xiàn)
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);
}
}
// 非遞歸實(shí)現(xiàn)：模仿遞歸思想
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 {
// 反順序添加
// 將執(zhí)行移動(dòng) popDisk 的下一步的Disk添加到Stack
stack.push(new Disk(popDisk.status - 1, popDisk.B, popDisk.A,
popDisk.C));
// 將一個(gè)status為 "1" 且移動(dòng)順序與 popDisk 相同的Disk 添加到Stack中
stack.push(new Disk(1, popDisk.A, popDisk.B, popDisk.C));
// 將執(zhí)行移動(dòng) popDisk 的前一步的Disk添加到Stack中
stack.push(new Disk(popDisk.status - 1, popDisk.A, popDisk.C,
popDisk.B));
}
}
}
// 非遞歸實(shí)現(xiàn)：根據(jù)Hanoi規(guī)律
public void play_regular(int diskNum) {
// 根據(jù)規(guī)律，需要根據(jù) Disk 的個(gè)數(shù)，多塔的位置進(jìn)行調(diào)整
// 塔的個(gè)數(shù)為偶數(shù)時(shí)，將三個(gè)塔按“A->B->C”的順序排列成三角形
// 塔的個(gè)數(shù)為奇數(shù)時(shí)，將三個(gè)塔按"A->C->B"的順序排列成三角形
// 將diskNum個(gè)Disk按”上小下大“的順序放在A塔中（堆棧實(shí)現(xiàn)），同時(shí)將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);
}
// 將三個(gè)塔模擬成三角形形狀排列
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;
// 根據(jù)證明：n個(gè)Disk移動(dòng)完成至少需要2^n-1次
// 不斷交替進(jìn)行以下兩步
// 將最小的Disk按以上塔的順序下移到下一個(gè)塔
// 對(duì)除了最小Disk所在的塔的另外兩個(gè)塔進(jìn)行操作，可能出現(xiàn)兩種情況
// 情況一：一個(gè)塔中沒有Disk，此時(shí)將存在Disk的塔最上面的Disk移動(dòng)到?jīng)]Disk的塔上
// 情況二：兩個(gè)塔都有Disk，此時(shí)對(duì)他們最上面的塔進(jìn)行比較，將較小的Disk移動(dòng)到較大的Disk上
// 不會(huì)存在兩個(gè)塔都沒有Disk的情況，除非移動(dòng)已經(jīng)完成或未開始或只有一個(gè)盤子時(shí)的移動(dòng)
int ii = 0;
for (int i = 0; i < (Math.pow(2, diskNum) - 1);) {// --------------注意在此處不進(jìn)行i++
// 取出三個(gè)塔，使代碼更清晰
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)];
// 移動(dòng)最小的盤子
System.out.println(tower.name + " -> " + tower_1.name);
tower_1.push(tower.pop());
i++;// --------------注意在此處進(jìn)行i++
towerOfMinimunDisk = (int) ((towerOfMinimunDisk + 1) % 3);
// ------------注意此時(shí)對(duì)三個(gè)tower進(jìn)行重新賦值
tower = towers[towerOfMinimunDisk];
tower_1 = towers[(int) ((towerOfMinimunDisk + 1) % 3)];
tower_2 = towers[(int) ((towerOfMinimunDisk + 2) % 3)];
// 對(duì)另外兩個(gè)塔進(jìn)行處理
if ((tower_2.getTop() != -1 && (tower_1.showTopDisk() > tower_2
.showTopDisk()))
// --------------注意要再加上 tower_2.getTop() != -1
// 進(jìn)行判斷，否則可能數(shù)組訪問越界
|| (tower_1.getTop() == -1 && tower_2.getTop() != -1)) {
System.out.println(tower_2.name + " -> " + tower_1.name);
tower_1.push(tower_2.pop());
i++;// --------------注意在此處進(jìn)行i++
} else if (((tower_1.getTop() != -1 && tower_1.showTopDisk() < tower_2
.showTopDisk()))
// --------------注意要再加上 tower_1.getTop() != -1
// 進(jìn)行判斷，否則可能數(shù)組訪問越界
|| (tower_1.getTop() != -1 && tower_2.getTop() == -1)) {
System.out.println(tower_1.name + " -> " + tower_2.name);
tower_2.push(tower_1.pop());
i++;// --------------注意在此處進(jìn)行i++
}
ii = i;
}
System.out.println(ii);
}
}
// 存放信息的結(jié)構(gòu)體
class Disk {
// 從A塔通過B塔移動(dòng)到C塔
char A;
char B;
char C;
// 塔的狀態(tài):當(dāng)status=1時(shí)，表示可以直接將該Disk移動(dòng)到目標(biāo)塔
int status;
// 重寫構(gòu)造函數(shù)
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 {
// 用來存儲(chǔ)盤子的數(shù)組
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) 創(chuàng)建的 Stack 類
// 以 diskId 來表示 Disk 對(duì)象
class Stack_play_regular {
// 塔名
char name;
// 塔頂
private int top = -1;
public int getTop() {
return top;
}
// 通過數(shù)組實(shí)現(xiàn)Stack,最多64個(gè)Disk
int[] stack = new int[64];
// 重寫構(gòu)造函數(shù)，初始化塔的名字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--];
}
}
復(fù)制代碼 代碼如下:
View Code
/*
* Hanoi塔游戲 問題描述：
* 漢諾塔：漢諾塔（又稱河內(nèi)塔）問題是源于印度一個(gè)古老傳說的益智玩具。
* 大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照
* 大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小
* 順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在
* 三根柱子之間一次只能移動(dòng)一個(gè)圓盤。
*
* fuction:實(shí)現(xiàn) hanoi塔
* 1.遞歸實(shí)現(xiàn)
* 2.非遞歸實(shí)現(xiàn)
* author:iGeneral
* date:2013.04.26
*
* expe:
* 1.注意：塔的狀態(tài):當(dāng)status=1時(shí)，表示可以直接將該Disk移動(dòng)到目標(biāo)塔
* 而不是用Disk的id來判斷輸出
* 2.System.out.println();
System.out.println((int)3.3%3);
沒有(int)時(shí)，輸出：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("請(qǐng)輸入Hanoi碟子的數(shù)量：");
int diskNum = scanner.nextInt();
Hanoi hanoi = new Hanoi();
System.out.println("遞歸實(shí)現(xiàn)：");
hanoi.play_recursive(diskNum, 'A', 'B', 'C');
System.out.println("非遞歸實(shí)現(xiàn)(模仿遞歸思想)：");
hanoi.play_non_recursive(diskNum);
System.out.println("非遞歸實(shí)現(xiàn)(根據(jù)Hanoi規(guī)律)：");
hanoi.play_regular(diskNum);
}
}
class Hanoi {
// 遞歸實(shí)現(xiàn)
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);
}
}
// 非遞歸實(shí)現(xiàn)：模仿遞歸思想
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 {
// 反順序添加
// 將執(zhí)行移動(dòng) popDisk 的下一步的Disk添加到Stack
stack.push(new Disk(popDisk.status - 1, popDisk.B, popDisk.A,
popDisk.C));
// 將一個(gè)status為 "1" 且移動(dòng)順序與 popDisk 相同的Disk 添加到Stack中
stack.push(new Disk(1, popDisk.A, popDisk.B, popDisk.C));
// 將執(zhí)行移動(dòng) popDisk 的前一步的Disk添加到Stack中
stack.push(new Disk(popDisk.status - 1, popDisk.A, popDisk.C,
popDisk.B));
}
}
}
// 非遞歸實(shí)現(xiàn)：根據(jù)Hanoi規(guī)律
public void play_regular(int diskNum) {
// 根據(jù)規(guī)律，需要根據(jù) Disk 的個(gè)數(shù)，多塔的位置進(jìn)行調(diào)整
// 塔的個(gè)數(shù)為偶數(shù)時(shí)，將三個(gè)塔按“A->B->C”的順序排列成三角形
// 塔的個(gè)數(shù)為奇數(shù)時(shí)，將三個(gè)塔按"A->C->B"的順序排列成三角形
// 將diskNum個(gè)Disk按”上小下大“的順序放在A塔中（堆棧實(shí)現(xiàn)），同時(shí)將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);
}
// 將三個(gè)塔模擬成三角形形狀排列
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;
// 根據(jù)證明：n個(gè)Disk移動(dòng)完成至少需要2^n-1次
// 不斷交替進(jìn)行以下兩步
// 將最小的Disk按以上塔的順序下移到下一個(gè)塔
// 對(duì)除了最小Disk所在的塔的另外兩個(gè)塔進(jìn)行操作，可能出現(xiàn)兩種情況
// 情況一：一個(gè)塔中沒有Disk，此時(shí)將存在Disk的塔最上面的Disk移動(dòng)到?jīng)]Disk的塔上
// 情況二：兩個(gè)塔都有Disk，此時(shí)對(duì)他們最上面的塔進(jìn)行比較，將較小的Disk移動(dòng)到較大的Disk上
// 不會(huì)存在兩個(gè)塔都沒有Disk的情況，除非移動(dòng)已經(jīng)完成或未開始或只有一個(gè)盤子時(shí)的移動(dòng)
int ii = 0;
for (int i = 0; i < (Math.pow(2, diskNum) - 1);) {// --------------注意在此處不進(jìn)行i++
// 取出三個(gè)塔，使代碼更清晰
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)];
// 移動(dòng)最小的盤子
System.out.println(tower.name + " -> " + tower_1.name);
tower_1.push(tower.pop());
i++;// --------------注意在此處進(jìn)行i++
towerOfMinimunDisk = (int) ((towerOfMinimunDisk + 1) % 3);
// ------------注意此時(shí)對(duì)三個(gè)tower進(jìn)行重新賦值
tower = towers[towerOfMinimunDisk];
tower_1 = towers[(int) ((towerOfMinimunDisk + 1) % 3)];
tower_2 = towers[(int) ((towerOfMinimunDisk + 2) % 3)];
// 對(duì)另外兩個(gè)塔進(jìn)行處理
if ((tower_2.getTop() != -1 && (tower_1.showTopDisk() > tower_2
.showTopDisk()))
// --------------注意要再加上 tower_2.getTop() != -1
// 進(jìn)行判斷，否則可能數(shù)組訪問越界
|| (tower_1.getTop() == -1 && tower_2.getTop() != -1)) {
System.out.println(tower_2.name + " -> " + tower_1.name);
tower_1.push(tower_2.pop());
i++;// --------------注意在此處進(jìn)行i++
} else if (((tower_1.getTop() != -1 && tower_1.showTopDisk() < tower_2
.showTopDisk()))
// --------------注意要再加上 tower_1.getTop() != -1
// 進(jìn)行判斷，否則可能數(shù)組訪問越界
|| (tower_1.getTop() != -1 && tower_2.getTop() == -1)) {
System.out.println(tower_1.name + " -> " + tower_2.name);
tower_2.push(tower_1.pop());
i++;// --------------注意在此處進(jìn)行i++
}
ii = i;
}
System.out.println(ii);
}
}
// 存放信息的結(jié)構(gòu)體
class Disk {
// 從A塔通過B塔移動(dòng)到C塔
char A;
char B;
char C;
// 塔的狀態(tài):當(dāng)status=1時(shí)，表示可以直接將該Disk移動(dòng)到目標(biāo)塔
int status;
// 重寫構(gòu)造函數(shù)
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 {
// 用來存儲(chǔ)盤子的數(shù)組
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) 創(chuàng)建的 Stack 類
// 以 diskId 來表示 Disk 對(duì)象
class Stack_play_regular {
// 塔名
char name;
// 塔頂
private int top = -1;
public int getTop() {
return top;
}
// 通過數(shù)組實(shí)現(xiàn)Stack,最多64個(gè)Disk
int[] stack = new int[64];
// 重寫構(gòu)造函數(shù)，初始化塔的名字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--];
}
}
相關(guān)文章
詳解用Spring Boot零配置快速創(chuàng)建web項(xiàng)目
本篇文章主要介紹了詳解用Spring Boot零配置快速創(chuàng)建web項(xiàng)目，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下。2017-03-03
這篇文章主要介紹了Java跳出多重嵌套循環(huán)過程解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-12-12
詳解使用Spring Cloud Consul實(shí)現(xiàn)服務(wù)的注冊(cè)和發(fā)現(xiàn)
這篇文章主要介紹了詳解使用Spring Cloud Consul實(shí)現(xiàn)服務(wù)的注冊(cè)和發(fā)現(xiàn)，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-06-06
SpringBoot源碼分析之bootstrap.properties文件加載的原理
本文通過訪問看到bootstrap.properties中的信息獲取到了，同時(shí)age也被application.properties中的屬性覆蓋掉了。加載順序到底是什么？為什么會(huì)覆蓋呢？我們接下來分析下吧2021-12-12
RestFul風(fēng)格 — 使用@PathVariable傳遞參數(shù)報(bào)錯(cuò)404的解決
這篇文章主要介紹了RestFul風(fēng)格 — 使用@PathVariable傳遞參數(shù)報(bào)錯(cuò)404的解決，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-10-10
SpringBoot 項(xiàng)目添加 MDC 日志鏈路追蹤的執(zhí)行流程
日志鏈路追蹤就是將一個(gè)標(biāo)志跨線程進(jìn)行傳遞，在一般的小項(xiàng)目中也就是在你新起一個(gè)線程的時(shí)候，或者使用線程池執(zhí)行任務(wù)的時(shí)候會(huì)用到，比如追蹤一個(gè)用戶請(qǐng)求的完整執(zhí)行流程，本文給大家介紹SpringBoot MDC 日志鏈路追蹤的代碼，感興趣的朋友一起看看吧2021-06-06
淺談Java finally語句到底是在return之前還是之后執(zhí)行(必看篇)
下面小編就為大家?guī)硪黄獪\談Java finally語句到底是在return之前還是之后執(zhí)行(必看篇)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-06-06
驗(yàn)證碼在很多地方都會(huì)遇到，實(shí)現(xiàn)的方法和形式也有很多，主要的目的就是為了安全，防止一些惡意的攻擊等。今天在之前搭建好的一個(gè)spring框架上寫了一個(gè)驗(yàn)證碼的生成demo,我會(huì)貼出細(xì)節(jié)代碼，但是spring的配置就不在介紹了,有需要的可以參考借鑒。2016-08-08
Java中你絕對(duì)沒用過的一個(gè)關(guān)鍵字Record的使用
這篇文章主要給大家介紹一個(gè)?Java?中的一個(gè)關(guān)鍵字?Record，那?Record?關(guān)鍵字跟不可變類有什么關(guān)系呢？看完今天的文章你就知道了，快跟隨小編一起學(xué)習(xí)一下吧2022-11-11
這篇文章主要介紹了Java的線程同步以及線程間通信,多線程編程是Java學(xué)習(xí)中的重點(diǎn)和難點(diǎn),需要的朋友可以參考下2015-09-09