public class HanoiTower {
/**
* 汉诺塔问题。很传统的算法问题，
* 把大问题转化为小问题的典型案例
* 。同时它也是递归思想的极具代表
* 性的体现。
* 假设目前A柱上面有n个盘子，现在我们要做的是把n-1个盘子借助B盘子移动到C柱子上面。
* 于是柱子就有了3个角色，
* 1、源柱子。
* 2、辅助柱子。
* 3、目标柱子。
* 当n=k时，从A先把k-1个盘子放在B上面，然后再把第k个盘子放到C上面去。
* 而要把A中的k-1个盘子放在B上去，就必须借助C，此时C却充当了辅助的角色。
* 这之后才会把第k个盘子放到C上面去。
* 当n=k-1时，从B先把k-2个盘子放在A上面，然后再把第k-1个盘子放到C上面去。
* 当n=k-2时，从A先把k-3个盘子放在B上面，然后再把第k-2个盘子放到C上面去。
* @param level
* @param sourcePillar
* @param temporaryPillar
* @param targetPillar
*/
static public void hanoi0(int level,String sourcePillar,String temporaryPillar,String targetPillar) {
if (level <= 0) {
System.out.println("错误!");
return;
}
//当只有1个待移动盘子的时候就不需要辅助柱子了
//直接从源柱子移动到目标柱子上面就可以了
if (level == 1) {
System.out.println(sourcePillar + "-->" + targetPillar);
} else {
//把上面的level-1个盘子挪走
hanoi0(level - 1,sourcePillar,targetPillar,temporaryPillar);
//移动第level个盘子到目标位置上。
hanoi0(1,sourcePillar,temporaryPillar,targetPillar);
//下一次递归
hanoi0(level - 1,temporaryPillar,sourcePillar,targetPillar);
}
}
/**
* 这是汉诺塔问题的非递归算法
* 思路为首先建立完全二叉树，
* 然后前序遍历即可。
* 仔细观察每一步移动的步骤会
* 发现，它的子步骤中的前一步
* 是由该步骤的左侧柱子组成的
* ，右步骤是由该步骤所缺失的
* 那个柱子组成的。后一步的右
* 侧边界是由该步骤的右侧边界
* 柱子组成的，左侧边界是由该
* 步骤缺失的那根柱子组成的。
* 又因为从递归方法的实现来看
* ，每一次回调必然产生2个结
* 果，所以可以由父步骤生成2
* 个子步骤。
* 生成完全二叉树以后再观察结
* 果发现这是二叉树的中序遍历
* 的结果，于是就可以得出汉诺
* 塔问题的非递归实现之一了。
* @param level
* @param sourcePillar
* @param temporaryPillar
* @param targetPillar
*/
static public void hanoi1(int level,String sourcePillar,String temporaryPillar,String targetPillar) {
if (level <= 0) {
System.out.println("错误!");
return;
}
//这样做可以把对符号的操作转换为对数字的操作——方便。
String[] pillarArray = new String[3];
pillarArray[0] = sourcePillar;
pillarArray[1] = temporaryPillar;
pillarArray[2] = targetPillar;
//队列最长也就是最下面那一排叶子结点的个数了
int queueDimension = (int) Math.pow(2,level - 1);
HanoiObject[] objectQueue = new HanoiObject[queueDimension];
int front = 0;
int rear = front;
//这里面的是自定义的一个每一步骤的状态对象。
HanoiObject rootObject = new HanoiObject(0,2);
objectQueue[rear] = rootObject;
//构建完全二叉树
while (front != (rear + 1) % queueDimension) {
HanoiObject frontObject = objectQueue[front++ % queueDimension];
int temporaryIndex = 3 - frontObject.getTargetPillar() - frontObject.getSourcePillar();
HanoiObject leftChild = new HanoiObject(frontObject.getSourcePillar(),temporaryIndex);
HanoiObject rightChild = new HanoiObject(temporaryIndex,frontObject.getTargetPillar());
frontObject.leftChild = leftChild;
frontObject.rightChild = rightChild;
objectQueue[++rear % queueDimension] = leftChild;
objectQueue[++rear % queueDimension] = rightChild;
}
//中序遍历
HanoiObject[] objectStack = new HanoiObject[level];
int objectStackPointer = -1;
HanoiObject objectPointer = rootObject;
while (objectStackPointer > -1 || objectPointer != null) {
while (objectPointer != null) {
objectStack[++objectStackPointer] = objectPointer;
objectPointer = objectPointer.leftChild;
}
if (objectStackPointer > -1) {
objectPointer = objectStack[objectStackPointer--];
System.out.println(pillarArray[objectPointer.getSourcePillar()] + "-->" + pillarArray[objectPointer.getTargetPillar()]);
objectPointer = objectPointer.rightChild;
}
}
}
/**
* 这是用递归方法转换成非递归方法的通用方法转换的
* 毫无以为这需要用到栈。
* 根据汉诺塔的递归可以看到这是一颗三叉树。
* @param level
* @param sourcePillar
* @param temporaryPillar
* @param targetPillar
*/
static public void hanoi2(int level,String sourcePillar,String temporaryPillar,String targetPillar) {
if (level <= 0) {
System.out.println("错误!");
return;
}
String[] pillarArray = new String[3];
pillarArray[0] = sourcePillar;
pillarArray[1] = temporaryPillar;
pillarArray[2] = targetPillar;
//由于是三叉树所以栈中结点数最多是3 * (level - 1) + 1
HanoiStep[] hanoiStack = new HanoiStep[3 * (level - 1) + 1];
int hanoiStepPointer = -1;
hanoiStack[++hanoiStepPointer] = new HanoiStep(level,0,1,2);
while (hanoiStepPointer > -1) {
HanoiStep popHanoiStep = hanoiStack[hanoiStepPointer--];
if (popHanoiStep.getLevel() == 1)
System.out.println(pillarArray[popHanoiStep.getSourcePillar()] + "-->" + pillarArray[popHanoiStep.getTargetPillar()]);
else {
//这是3个步骤
hanoiStack[++hanoiStepPointer] = new HanoiStep(popHanoiStep.getLevel() - 1,popHanoiStep.getTemporaryPillar(),popHanoiStep.getSourcePillar(),popHanoiStep.getTargetPillar());
hanoiStack[++hanoiStepPointer] = new HanoiStep(1,popHanoiStep.getSourcePillar(),popHanoiStep.getTemporaryPillar(),popHanoiStep.getTargetPillar());
hanoiStack[++hanoiStepPointer] = new HanoiStep(popHanoiStep.getLevel() - 1,popHanoiStep.getSourcePillar(),popHanoiStep.getTargetPillar(),popHanoiStep.getTemporaryPillar());
}
}
}
}
public class HanoiObject {
private int sourcePillar;
private int targetPillar;
public HanoiObject leftChild = null;
public HanoiObject rightChild = null;
public HanoiObject(int sourcePillar, int targetPillar) {
this.sourcePillar = sourcePillar;
this.targetPillar = targetPillar;
}
public int getSourcePillar() {
return sourcePillar;
}
public int getTargetPillar() {
return targetPillar;
}
}
public class HanoiStep {
private int level;
private int sourcePillar;
private int temporaryPillar;
private int targetPillar;
public HanoiStep(int level, int sourcePillar, int temporaryPillar, int targetPillar) {
this.level = level;
this.sourcePillar = sourcePillar;
this.temporaryPillar = temporaryPillar;
this.targetPillar = targetPillar;
}
public int getLevel() {
return level;
}
public int getSourcePillar() {
return sourcePillar;
}
public int getTemporaryPillar() {
return temporaryPillar;
}
public int getTargetPillar() {
return targetPillar;
}
}
网友评论