汉诺塔问题 Hanio ——递归思想-白红宇

汉诺塔问题 Hanio ——递归思想

阅读量：4966 次

发布时间：2019-06-12

本文共 2622 字，大约阅读时间需要 8 分钟。

问题描述：一根柱子称原柱上，套有n个盘子，依次从小到大地从上往下地排序着，需要将这n个盘子移动一个目标柱上，要求在移的过程中，大的盘子不可以在小的盘子上面。可以使用一根辅助柱子;

分析：

//函数参数：第一个参数表示欲移动的原柱最顶上的n个盘子，第二个参数表示原柱子，第三个参数表示辅助柱子，第三个参数表示目标柱子；

n=1:只有一个盘子： Hanio(1,X,Y,Z) : X-Z;

n=2:有两个盘子： Hanio(2,X,Y,Z): 1:X->Y, 2:X->Z, 1:Y->Z;

n=3:有三个盘子时：Hanio(3,X,Y,Z): 1,2:hanio(2,X,Z,Y), 3:X->Z; 1,2:Hanio(2,Y,X,Z);

可见 n=3与n=2是递归关系。

其实n=2与n=1也是递归关系。 Hanio(2,X,Y,Z): 1: Hanio(1,X,Z,Y), 2:X->Z; 1：Hanio(1,Y,X,Z);

具体实现：每个柱子使用一个栈作为数据结构。

为了检测算法移动过程是否违反了”大盘子不可在小盘子之上“规则，

当n=1:即移动一个盘子时： Hanio(1,X,Y,Z) : X-Z; 操作中：先判断Z是否为空，若非空，比较当前欲放入元素与Z栈顶元素大小，若前者大，则违反了规则。

解决办法：

递归：将这个问题分解为三个子问题：(1...n):X->Z:

Hanio(X,Y,Z):划分为：

a.(1..n-1):X->Y; Hanio(n-1,X,Z,Y);

b. (n):X->Z;

c. (1..n-1):Y->Z; Hanio(n-1,Y,X,Z);

package com.algothrim;

import java.util.Deque;

import java.util.LinkedList;

* 在移动过程中进行检测：如果a要放在b上，对比大小，若b比a小，则打印错误消息，
* 若有错误消息，说明算法实现错误。
*/
public class HanioTemp {

　　public void Hanio(int n,Deque<Integer> X,Deque<Integer> Y,Deque<Integer> Z){

　　if(n==0) return;

　　if(n==1){

Integer bowl=X.pop();

　　 if(!Z.isEmpty()){

　　 Integer ztop=Z.peek();

　　 if(bowl>ztop) System.out.println("错误：出现大盘子"+bowl+"在小盘子"+ztop+"的情况之上");

　 }

Z.push(bowl);

return;

}else{

　　Hanio(n-1,X,Z,Y);

　　Integer bowl=X.pop();

　　 Z.push(bowl);

　　 Hanio(n-1,Y,X,Z);

　}

}
public static void main(String[] args) {

　　Deque<Integer> stackX=new LinkedList<Integer>();
　　Deque<Integer> stackY=new LinkedList<Integer>();
　　Deque<Integer> stackZ=new LinkedList<Integer>();
/*
* satckX初始化：（盘子号越大，表示盘子越大）：
* 67,55,23,12,6,3,1
*/
　　Integer initArray[]={67,55,23,12,6,3,1};
　　int n=initArray.length;
　　for(int i=0;i<n;i++){

　　　　stackX.push(initArray[i]);
　　}

　　System.out.println("移动前：-----------");

　　System.out.print("源柱上的盘子共（"+stackX.size()+")个:");

　　for(int j=n-1;j>=0;j--)

　　System.out.print(" "+initArray[j]);

　　System.out.println();

　　HanioTemp temp=new HanioTemp();

　　temp.Hanio(n,stackX,stackY,stackZ);

　　System.out.println("移动后：------------");

　　System.out.print("源柱上的盘子共（"+stackX.size()+")个:");

　　while(!stackX.isEmpty())

　　　　System.out.print(" "+stackX.pop());

　　System.out.println();