本文共 2499 字，大约阅读时间需要 8 分钟。
汉诺塔问题
最近面试题遇到过汉诺塔的问题，当时竟然懵逼了，不会了！！大学研究的问题竟然都忘光了，于是抓紧捡起来。然而在网上看了看博客，发现非递归算法还真挺多。下面总结了一下。
一、递归算法
1、递归算法优缺点：递归算法算是最易于理解也是最容易实现的，但是对内存的消耗也是巨大的，因为递归需要系统堆栈来保存调用函数地址、形参、局部变量、返回值等数据，也就是回调N次，就要保存N个之前提到的数据。但是递归算法结构简洁，清晰。基于这个原因，我先介绍一下递归算法。
2、递归算法思路：
1）将N-1个盘子从A柱移动到B柱或者将N-1个盘子从B柱移动到A柱。
2）将第N个盘子移动到C柱。
代码：
1 /** 2 * 3 * @param n 需要移动的盘子数 4 * @param a a柱 这里的abc柱，并不是实际问题中的ABC三个柱子，是动态分析过程中的柱子 5 * @param b b柱 6 * @param c c柱 7 */ 8 static void move(int n, char a, char b, char c) { 9 if (n == 1)10 System.out.println(a + "-->" + c); // 当只有1个盘子的时候直接将盘子从a柱移动到c柱11 else {12 move(n - 1, a, c, b); // 将当前a柱的n-1个盘子，通过c移动到b13 System.out.println(a + "-->" + c);//将a柱子上的最大的盘子移动到c柱14 move(n - 1, b, a, c); // n-1个移动过来之后b柱成为a柱，这里就变成了n-1个盘子从b移动到c柱。15 }16 } 二、非递归算法
这里使用了便利二叉树的思路
1)算法推论描述：
这里用4个盘子举例
进行整合：
2)算法规律：
根据上面的二叉树的图，可以看到如下规率：
A.盘子数（N）=二叉树的高度（H）
B.第n层序号能被2的(n-1)次方整除，但不能被2的n次方整除（n从下至上增加）
C.每一层的节点数=2的(N-n)次方
D.无论有多少个盘子，每一层的步骤都是相同的，例如：所有的最上面一层都是A->C，第二层也是一样的。
E.每一层都是以A未开始，以C为结束
F.奇数层规律是A->C,C->B,B->A，依次循环
G.偶数层规律是A->B,B->C,C->A，依次循环
根据上面的特点进行进一步总结得到：
A.第M部层数确定（可以判断循环规律）：如果M能被2的(n-1)次方整除，但不能被2的n次方整除，那么，M步处于n层
B.第M步在J层的序号确定：K=M除以2的（n-1）次方
3)算法代码：
static void hanoi(int m) { int c = 1;// 总步骤数 int n = 1;// 步骤数 c <<= m; for (; n < c; n++) { shuchu(m, n); } } private static void shuchu(int m, int n) { for (int i = n, y = i % 2, c = m;; i = i / 2, y = i % 2, c--) { if (y != 0) { switch ((c % 2) * 3 + (i / 2) % 3) { case 0: System.out.println("第"+n+"步"+ ":A-B"+" 当前移动的盘子是："+(m-c+1)); break; case 1: System.out.println("第"+n+"步"+ ":B-C"+" 当前移动的盘子是："+(m-c+1)); break; case 2: System.out.println("第"+n+"步"+ ":C-A"+" 当前移动的盘子是："+(m-c+1)); break; case 3: System.out.println("第"+n+"步"+ ":A-C"+" 当前移动的盘子是："+(m-c+1)); break; case 4: System.out.println("第"+n+"步"+ ":C-B"+" 当前移动的盘子是："+(m-c+1)); break; case 5: System.out.println("第"+n+"步"+ ":B-A"+" 当前移动的盘子是："+(m-c+1)); } break; } } }
转载地址：http://tpttx.baihongyu.com/