汉诺塔问题
汉诺塔问题
最近面试题遇到过汉诺塔的问题，当时竟然懵逼了，不会了！！大学研究的问题竟然都忘光了，于是抓紧捡起来。然而在网上看了看博客，发现非递归算法还真挺多。下面总结了一下。
一、递归算法
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移动到b
13 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;
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-03-22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读