java汉诺塔可视化代码（java使用非递归方式实现汉诺塔游戏）

汉诺塔的c语言里面的一个经典算法，我当时学c时就感觉这个程序挺好玩的，但是玩给玩，仔细想，计算机还真是强大的，可以计算这么复杂的事情，当时想了很久使用while循环来实现，但是就是想不出，感觉实在太难了。

递归很好理解，反正只要思路正确，计算机都能帮我们运行出结果，可是非递归就难了，没有一定的算法基础还真难理解哦。

我这里创建了一个step对象来保存每一个阶段的柱子和盘子数，使用堆栈来完成我们的非递归，我们要完成n个盘子移动，就要先移动n-1盘子到另外一个柱子（过渡柱子），移动n-1就要完成n-2移动，如此循环，在众多的循环中，目标柱子和中间柱子的角色不断地变换，而变换又是依据上一次的移动结果，所以我们只要从堆栈中取出step对象，就可以找到本次的目标柱子、中间柱子、盘子数，如此不断入栈出栈，直到栈为空，就完成了汉诺塔游戏

递归和非递归的方法如下：

import java.util.ArrayList; import java.util.List; import java.util.Stack; /** * 递归和非递归的方式实现汉诺塔移动盘问题 * @author ssj * */ public class HanotaTest { /** * 递归实现 * @param n * @param A * @param B * @param C * @param steps */ public static void hanotaDiGui(int n, char A, char B, char C,List<String> steps) { if (n == 1) { //只有一个圆盘需要移动的时候移动完结束 steps.add(getMove(A, C)); return; } // 先把A上的n-1个圆盘移动到B上 hanotaDiGui(n - 1, A, C, B,steps); // 把A上最后一个圆盘移动到C上 steps.add(getMove(A, C)); // 接下来递归，把B上的n-1个圆盘移动到C上 hanotaDiGui(n - 1, B, A, C,steps); } /** * 把A最上面的圆盘移动到C上去 * @param A * @param C */ private static String getMove(char A, char C) { return A "-->" C; } /** * 汉诺塔非递归的实现 * @param A * @param B * @param C * @param n * @param steps */ public static void hanota(char A, char B, char C,int n,List<String> steps) { Stack<HannoiStep> stk=new Stack<HannoiStep>(); //初始化入栈 HannoiStep stp = new HannoiStep(A, B, C, n); stk.add(stp); while(stk.size()>0) { HannoiStep st = stk.pop(); if(st.n>1) { //先将n-1个盘子从a移动到b HannoiStep stp1 = new HannoiStep(st.A, st.C, st.B, st.n-1); //n-1个盘子移动完成后，将最后一个盘子从a移动到c HannoiStep stp2 = new HannoiStep(st.A, st.B, st.C, 1); //先将n-1个盘子从b移动到c HannoiStep stp3 = new HannoiStep(st.B, st.A, st.C, st.n-1); //所有操作入栈，注意入栈顺序，先入栈的后操作，所以顺序倒着入栈 stk.add(stp3); stk.add(stp2); stk.add(stp1); }else { steps.add(getMove(st.A, st.C)); } } } public static void main(String[] args) { List<String> dsteps=new ArrayList<>(); System.out.println("用非递归的结果-"); hanotaDiGui(3, 'A', 'B', 'C',dsteps); System.out.println(" 总移动步数：" dsteps.size()); for(String s:dsteps) { System.out.println(" " s); } System.out.println("********************************"); List<String> steps=new ArrayList<>(); hanota('A', 'B', 'C', 3, steps); System.out.println("使用非递归的结果"); System.out.println(" 总移动步数：" steps.size()); for(String s:steps) { System.out.println(" " s); } } } /** * 构建移动对象 * @author ssj * */ class HannoiStep{ public char A;//柱子 a public char B;//柱子 b public char C;//柱子 c public int n;//盘子数量 public HannoiStep(char a, char b, char c, int n) { super(); A = a; B = b; C = c; this.n = n; } }

运行结果