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--];
}
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！
点击进行留言回复
我要评论
网友评论