汉诺塔问题（详解） - 喜欢自由自在的生活，热衷于程序开发！ - ITeye博客
博客分类：
1问题描述
问题提出：有三个塔(分别为A号，B号和C号)。开始时．有
n个圆形盘以从下到上、从大到小的次序叠置在A塔上。现要将A
塔上的所有圆形盘，借助B搭，全部移动到C搭上。且仍按照原来
的次序叠置。
移动的规则如下：这些圆形盘只能在3个塔问进行移动．一
次只能移动一个盘子，且任何时候都不允许将较大的盘子压在比
它小的盘子的上面。
要求如下：从键盘输入初始圆形盘子个数n．用JAVA实现n
个盘子最佳移动的全过程。
2算法分析
此题的目的是设计一个盘子移动的方案．使得A号塔上的所
有盘子借助于B号塔按照原来的次序移动到C号塔上，并且．要
给出完整的最佳的盘子移动的方案。
我们从实际的、具体的盘子的移动过程来分析．找出问题内
在的规律。经分析无论盘子的个数有多少．是1、2、3..或n个．
也不管我们怎么去移动盘子(当然是按规则来移动)．但在移动的
过程中，将始终会出现这样的状态情况：(n一1)个盘子将会以从下
到上、从大到下的次序叠置在B塔上，这时，A塔上第n个盘子就
能被轻而易举叠放到c塔上；接着，我们再把B塔上的其fn一1)十
盘子移动到C塔上，问靼好像已经解决
但，B塔上fn—1)个盘子怎么移动到C塔上呢?这是我们要解
决的第二个问题。同样，不管我们怎么移动，也将会出现这样的状
态情况：(n一2)个盘子将会以从上到下、从大到小的次序叠置在A
塔上，这时。B塔上第(n一1)个盘子就能被轻而易举放到C塔上；接
着，我们把A塔上的共(n一2)个盘子移动到C塔上。
这样，不断深入，不断细小化，最终，将到达仅有一个盘的情
形。这时，递归也就终止了，问题也得到了解决。通过以上分析．这
里有很明显递归关系
由此，想到了采用递归算法来解决该问题。因为递归算法有这
样特征描述：为了求解出规模力N的问题的解．我们先设法将它分
解成一些规模较小的问题，然后从这些较小问题的解能方便地构
造出大问题的解，并且这些规模较小的问题也能采用同样的方法
分解，分解成规模更小的问题，并能从这些更小的问题的解构造出
规模稍大问题的解。特别地是，当规模N-I时，能直接得到解。
现在，严格按照递归算法来解决问题。先定义递归方法Hanio
(int N，char A，char B，char C)，按如下步骤进行解题(设初始盘子个
数为N)：若A塔上仅仅只有一个盘子(N=1)，则直接从A移动到
C，问题完全解决。若A塔上有一个以上的盘子(N&1)，则需要考虑以下三个步骤。
第一步：把 一1)个盘子从A塔经过移动，叠放到B塔上。在
不违反规则情况下，所有fN一1)个盘子不能作为一个整体一起移
动，而是要符合要求地从一个塔移到另一个塔上。用Hanio(N—1．A，
C，B)调用递归方法，注意：这里是借助于C塔，将(N一1)个盘子从A
塔移动到B塔，A是源塔，B是目标塔。
第二步：将剩下的第N个盘子(也就是最底下的一个)直接从A塔
叠放到空着的C塔上。
第三步 用第一步的方法，再次将B塔上的所有盘子叠放到
C塔上。同样，这一步实际上也是由一系列更小的符合规则的移动
盘子的操作组成的。用Hanio(N一1，B，A，C)调用递归方法，注意：这
里是借助于A塔，将(N—1)个盘子从B塔移动到C塔，B是源塔，℃
是目标塔。
这个算法达到了预期的目标．即在C塔上按正确的次序叠放
了所有的圆形盘子。有了前面问题算j去分析的基础，继而，我们可
以用JAVA来实现算法。
3 JAVA实现
3．1说明如下
(1)n为A塔初始盘子个数；
(2)A塔上盘子从上到下、从小到大编号依次为l，2，3. . ：
(3)Hanio0方法采用递归算法，实现盘子移动的最佳方案：
(5)InputnO方法实现盘子个数n的键盘输入(输入必须为阿
拉伯数字)。
3．2编程如下
import java．io． ；，／引用java包的io子包的所有公有类
public class Hanio／／Hanio类的声明
{static int n；
public static void main(Strin乱J args)throws IOException
I System．out．print(”请输入盘子的个数lI=”)；
n=Integer．parselnt(Inputn0)；
System．out．prindn(”盘子的整个移动过程如下．I ；
Hanio(n， A ， B ， C )；，／调用Hanio方法l
#HanioO方法采用递归算法
public static void Hanio(int N，char A，char B，char C)
{if(N==1)
System．out．prlntln(”Dish l from”+A+”to”+C)；
else ·
{Hanio(N—l，A，C，B)；／／把A上的N一1个盘子借助于C叠放刘
B上
System．out．println(”Dish”+N+”from”+A+”to“+C)：
Hanio(N一1，B，A，C)；／／再把B上的N—1个盘子借助于A叠放到
C上
ll ，，读从键盘输入的数据流的方法
public static String InputnO throws IOException
{String str；
BuferedReader Input=new BuferedReader fnew InputStream．
Reader(System．in11；
str=Input．readLine0；
retum str；}l
3．3编译、解释运行iava程序
上面的代码可以使用记事本录入，保存文件名为Hanio．java。
在运行iava程序前首先使用编译程序iavac进行编译，通过后再
使用java运行即可。具体的命令操作如下。
(1)编译程序
C：＼java&javac Hanio．java
编译成功后生成类文件Hanio．class
(2)运行程序
C：＼java&java Hanio
注：编写iava程序的运行环境必须安装JDK工具包，并进行
配置．可以从WWW．java．com下载。
4总结
其实。递归算法的执行过程分为递推和回归两个阶段。在递推阶段，把较为复杂的问题(如规模为N)的求解推到比原问题简
单一些的问题(规模小于N)的求解。’例如上面分析过程中，为求
解Hanio(N，A，B，C)，推到计算Hanio(N一1，A。C。B)。
在回归阶段，当获得最简单情况的解后，逐级返回。依次获得
稍复杂问题的解。在这里的“汉诺塔”问题中，有它的特别的地方，
回归的过程当中．还要涉及到递推。
另外．在编写递归方法时要注意是：每次调用递归方法，方法
中的参数只是局限于当前调用层的，当递推进入“简单问题”层
时，原来层次上的参数便被隐藏起来。在一系列“简单问题”层，它
们各有自己的参数。 ．
最后．通过经典“汉诺塔”问题移动过程的分析、解决以及最
后JAVA编程实现，使我们能够掌握解决此类问题的方法，也使
我们对递归算法能有个更加深刻的理解。
浏览 12583
白色彗星isme
浏览: 26166 次
来自: 深圳
谢谢你，我昨天想很一整晚，我就是突破不了如何用程序实现。你的解 ...
...你这存的是什么？ text？就这个？
代码还是格式一下撒汉诺塔问题的算法分析及C语言演示程序的实现_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
汉诺塔问题的算法分析及C语言演示程序的实现
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
你可能喜欢汉诺塔的图解递归算法
来源：博客园
一．起源：
　　汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
二．抽象为数学问题：
　　如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

解：（1）n == 1
sum = 1 次
n == 2
A----&B
A----&C
sum = 3 次
　　（3）n == 3
　　第1次
A----&C
　　第2次
A----&B
　　第3次
C----&B
　　第4次
A----&C
　　第5次
B----&A
　　第6次
B----&C
　　第7次
sum = 7 次
 
不难发现规律：1个圆盘的次数 2的1次方减1
　　　　　　　2个圆盘的次数 2的2次方减1
3个圆盘的次数 2的3次方减1
n个圆盘的次数 2的n次方减1
 故：移动次数为：2^n - 1
三．调用方法的栈机制:（特点：先进后出）
从主线程开始调用方法（函数）进行不停的压栈和出栈操作，函数的调用就是将函数压如栈中，函数的结束就是函数出栈的过程，这样就保证了方法调用的顺序流，即当函数出现多层嵌套时，需要从外到内一层层把函数压入栈中，最后栈顶的函数先执行结束（最内层的函数先执行结束）后出栈，再倒数第二层的函数执行结束出栈，到最后，第一个进栈的函数调用结束后从栈中弹出回到主线程，并且结束。
四．算法分析（递归算法）：
我们在利用计算机求汉诺塔问题时，必不可少的一步是对整个实现求解进行算法分析。到目前为止，求解汉诺塔问题最简单的算法还是同过递归来求，至于是什么是递归，递归实现的机制是什么，我们说的简单点就是自己是一个方法或者说是函数，但是在自己这个函数里有调用自己这个函数的语句，而这个调用怎么才能调用结束呢？，这里还必须有一个结束点，或者具体的说是在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，一直到第一次调用的这个函数能返回一个确定的值。
实现这个算法可以简单分为三个步骤：
　　　　（1）
把n-1个盘子由A 移到 B；
　　　　（2）
把第n个盘子由 A移到 C；
　　　　（3）
把n-1个盘子由B 移到 C；
从这里入手，在加上上面数学问题解法的分析，我们不难发现，移到的步数必定为奇数步：
　　　　（1）中间的一步是把最大的一个盘子由A移到C上去；
　　　　（2）中间一步之上可以看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上，
　　　　（3）中间一步之下可以看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上；
五，java源代码：

package
/**
 * 目的：实现汉诺塔问题求解
 * 作者：Dmego
时间：
 */
import java.util.S

public class TowersOfHanoi {
static int m =0;//标记移动次数
//实现移动的函数
public static void move(int disks,char N,char M)
System.out.println("第" + (++m) +" 次移动 : " +" 把 "+ disks+" 号圆盘从 " + N +" -&移到-&
" + M);
//递归实现汉诺塔的函数
public static void hanoi(int n,char A,char B,char C)
if(n == 1)//圆盘只有一个时，只需将其从A塔移到C塔
TowersOfHanoi.move(1, A, C);//将编b号为1的圆盘从A移到C
{//否则
hanoi(n - 1, A, C, B);//递归，把A塔上编号1~n-1的圆盘移到B上，以C为辅助塔
TowersOfHanoi.move(n, A, C);//把A塔上编号为n的圆盘移到C上
hanoi(n - 1, B, A, C);//递归，把B塔上编号1~n-1的圆盘移到C上，以A为辅助塔
public static void main(String[] args) {
Scanner imput = new Scanner(System.in);
char A = 'A';
char B = 'B';
char C = 'C';
System.out.println("******************************************************************************************");
System.out.println("这是汉诺塔问题（把A塔上编号从小号到大号的圆盘从A塔通过B辅助塔移动到C塔上去");
System.out.println("******************************************************************************************");
System.out.print("请输入圆盘的个数：");
int disks = imput.nextInt();
TowersOfHanoi.hanoi(disks, A, B, C);
System.out.println("&&移动了" + m + "次，把A上的圆盘都移动到了C上");
imput.close();
}

}

六．图解程序运行流程：
　　（1）函数hanoi(int n,char A,char B,char C)的功能是把编号为n的圆盘借助B从A移动到 C上。
　　（2）函数move(int n ,char N ,char M)的功能是把1编号为n的圆盘从N 移到M上

 
七．程序运行截图：

免责声明：本站部分内容、图片、文字、视频等来自于互联网，仅供大家学习与交流。相关内容如涉嫌侵犯您的知识产权或其他合法权益，请向本站发送有效通知，我们会及时处理。反馈邮箱&&&&。
学生服务号
在线咨询，奖学金返现，名师点评，等你来互动18204人阅读
程序员面试题（62）
汉诺塔问题描述： A、B、C 三个桌子，其中A桌子上放了几个大小不同的盘子，盘子的排列顺序为： 从上到下，依次从小到大递增；现要求把这些盘子从 A 桌子上移动到 C 桌子上，盘子移动时有一点要求：每次移动必须保证三张桌子上大盘子在下、小盘子在上；打印移动次序。
如 A 上一张 盘子时，移动顺序： A -& C
代码实现：
#include &iostream&
*汉诺塔问题: 将 A 上所有的盘子，移动到 C 上 ，A B C
void moveAC(char A,char C)
cout&&A&&&-&&&&C&&
void recursion_hano(int n,char A,char B,char C)
//递归的终止条件
moveAC(A,C);
//先将 A 上上边n-1个盘子移动到 B上
recursion_hano(n-1,A,C,B);
// 将 上 n-1 个圆盘移动到 B上
moveAC(A,C);
//将最大的圆盘移动到 C上
recursion_hano(n-1,B,A,C);
//将B上的圆盘移动到C上
int main()
cout && &Hello world!& &&
recursion_hano(4,'A','B','C');
算法理解：
宏观上我们可以这样理解：要将A上的n个盘子按照要求移动到C上，我们可以想到：先将上边的 n-1 个盘子移动到B上，再将A上剩余的最大的盘子移动到C上，然后将B上所有的盘子移动到C上，这是比较简单的理解，但是对于算法实现的过程，还是没有弄透彻。
我们知道当盘子数为n时，移动的次数应该为 2^n-1；这个有公式 &H(n) = 2H(n-1) +1 得来，理解为：上边的n-1个盘子先翻转到B上，将最大的盘子移动到C上，花费1步，然后将B上的盘子翻转到C上，花费2H(n-1)步。
后来美国的一位学者发现一种出人意料的简单的算法，只要轮流两步操作既可以实现：首先，把三张桌子按顺序首尾相接的排列，形成一个环，然后对A上的盘子开始移动，顺时针摆放成 A B C的顺序：
若n为奇数，圆盘的移动顺序是 A-&C-&B-&A-&C-&B-&A......... 即 间隔两个步长移动 &。此处的n代表盘子位的层数，比如说 3 层汉诺塔就是从下往上数第1、3 个盘子移动的顺序。
若n为偶数，圆盘移动的顺序为A-&B-&C-&A-&B-&C-&A..........即 间隔一个步长移动。对n的解释同上 第二个盘子移动 A-&B-&C。
现在开始算法：
首先先找到能够移动的 即 A的最上边的那个盘子 如代码：
recursion_hano(n-1,A,C,B);
该调用从下往上数层数，第一次调用时是第二层的移动 应该为： A-&B
第二次调用时为第三层的移动，经过两次调用B、C翻转，应该为 ：A-&C
........................
& & &如此到最高层来移动第一个盘子
A上的盘子移动过之后，我们要移动B、C上的盘子，移动策略同上
第二段代码的理解为：
moveAC(A,C);
对塔顶的两个盘子，最上层的盘子假如移动到了C上，下一层的盘子就移动到B上，因为第一段代码调用一次，B、C的顺序翻转一次。
最后一段代码的理解：
recursion_hano(n-1,B,A,C);
交换B、A的顺序是为了将 B上的盘子移动到C上，此处相当于为了实现步长为 1 的移动。
按照这样的理解，可非常清楚的了解递归每一步实现的是什么
如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1005239次
积分：9522
积分：9522
排名：第1856名
原创：105篇
转载：121篇
评论：101条
(1)(2)(2)(7)(5)(7)(17)(17)(41)(21)(3)(18)(17)(20)(15)(29)(3)(1)}