【图文】汉诺塔非递归算法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
汉诺塔非递归算法
&&汉诺塔问题,非递归算法,总结。。。
大小：1.59MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢算法详解--汉诺塔
我的图书馆
算法详解--汉诺塔
汉诺塔算法详解&说明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家 Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小 至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当 盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。解法如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。&&&如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A-&B、A -&C、B-&C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。&&事实上，若有n个盘子，则移动完毕所需之次数为2^n - 1，所以当盘数为64时，则所需次数为：264- 1 = 为5.82e+16年，也就是约5000世纪，如果对这数字没什么概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。&演算法Procedure HANOI(n, A, B, C) [
IF(n == 1) [
PRINT("Move sheet " n " from " A " to " C);
HANOI(n-1, A, C, B);
PRINT("Move sheet " n " from " A " to " C);
HANOI(n-1, B, A, C);
] 实作C#include &stdio.h&void hanoi(int n, char A, char B, char C) {
if(n == 1) {
printf("Move sheet %d from %c to %c\n", n, A, C);
hanoi(n-1, A, C, B);
printf("Move sheet %d from %c to %c\n", n, A, C);
hanoi(n-1, B, A, C);
}}int main() {
printf("请输入盘数：");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;} Javaimport java.io.*;public class Hanoi {
public static void main(String args[]) throws IOException {
buf = new BufferedReader(new InputStreamReader(System.in));
System.out.print("请输入盘数：");
n = Integer.parseInt(buf.readLine());
Hanoi hanoi = new Hanoi();
hanoi.move(n, 'A', 'B', 'C');
public void move(int n, char a, char b, char c) {
if(n == 1)
System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
move(n - 1, a, c, b);
System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
move(n - 1, b, a, c);
}} 解释如下：【From：/question/】Hanoi塔问题, 算法分析如下，设A上有n个盘子。如果n=1，则将圆盘从A直接移动到C。如果n=2，则：（1）将A上的n-1（等于1）个圆盘移到B上；（2）再将A上的一个圆盘移到C上；（3）最后将B上的n-1（等于1）个圆盘移到C上。如果n=3，则：A）将A上的n-1（等于2，令其为n`）个圆盘移到B（借助于C），步骤如下：（1）将A上的n`-1（等于1）个圆盘移到C上。（2）将A上的一个圆盘移到B。（3）将C上的n`-1（等于1）个圆盘移到B。B）将A上的一个圆盘移到C。C）将B上的n-1（等于2，令其为n`）个圆盘移到C（借助A），步骤如下：（1）将B上的n`-1（等于1）个圆盘移到A。（2）将B上的一个盘子移到C。（3）将A上的n`-1（等于1）个圆盘移到C。到此，完成了三个圆盘的移动过程。从上面分析可以看出，当n大于等于2时， 移动的过程可分解为三个步骤：第一步 把A上的n-1个圆盘移到B上；第二步 把A上的一个圆盘移到C上；第三步 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。 当n=3时，第一步和第三步又分解为类同的三步，即把n`-1个圆盘从一个针移到另一个针上，这里的n`=n-1。
TA的最新馆藏[转]&[转]&[转]&[转]&[转]&
喜欢该文的人也喜欢欢迎加入我们，一同切磋技术。 &
用户名： &&&
密　码： &
共有 14940 人关注过本帖
标题：关于汉诺塔的递归算法，到底是怎么执行的？想的头痛
等　级：论坛游民
帖　子：76
专家分：51
&&已结贴√
&&问题点数：20&&回复次数：20&&&
关于汉诺塔的递归算法，到底是怎么执行的？想的头痛
关于汉诺塔的递归算法，到底是怎么执行的？想的头痛
当n等于2时可以理解，当n等于3是就理解不了了。现在就是想知道当n等于3时，程序到底是怎么执行的？为什么第一个输出的是a-&c;
程序代码：# include &stdio.h&
void move(int n, char a, char b, char c)
&&& if (n == <font color=#)
&&&&&&&&printf(&\t%c-&%c\n&, a, c);
&&&&&&&&move(n-<font color=#, a, c, b);
&&&&&&&&printf(&\t%c-&%c\n&, a, c);
&&&&&&&&move(n-<font color=#, b, a, c);
int main(void)
&&& printf(&请输入要移动的块数：&);
&&& scanf(&%d&, &n);
&&& move(n, 'a', 'b', 'c');
&&& return <font color=#;
/*执行结果：
[ 本帖最后由 whukeming 于
17:08 编辑 ]
搜索更多相关主题的帖子:
来　自：江西财经大学
等　级：贵宾
威　望：81
帖　子：3292
专家分：12819
要学会调试，一步步跟进
3, a, b, c
&&& 2, a, c, b
&&&&&&&&1, a, b, c
&&&&&&&&printf()&&& // a -& c
&&& printf()&&&&&&&&// a -& b
&&&&&&&&1, c, a, b
&&&&&&&&printf()&&& // c -& b
printf()&&&&&&&&&&&&// a -& c
&&& 2, b, a, c
&&&&&&&&1, b, c, a
&&&&&&&&printf()&&& // b -& a
&&& printf()&&&&&&&&// b -& c
&&&&&&&&1, a, b, c
&&&&&&&&printf()&&& // a -& c
[fly]存在即是合理[/fly]
来　自：斗气大陆
等　级：贵宾
威　望：43
帖　子：2218
专家分：13561
如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘 子，就将B当作辅助柱。
如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，
每次处理两个盘子，也就是：A-&B、A -&C、B-&C这三个步骤，
而被遮住的部份，其实就是进入程式的递回处理。
三十年河东，三十年河西，莫欺少年穷！
来　自：武汉
等　级：贵宾
威　望：30
帖　子：2780
专家分：6060
你不知道这个世界上有个东西叫做debug吗?
我总觉得授人以鱼不如授人以渔...
可是总有些SB叫嚣着:要么给代码给答案,要么滚蛋...
虽然我知道不要跟SB一般见识,但是我真的没修炼到宠辱不惊...
等　级：论坛游民
帖　子：76
专家分：51
回复 2楼 azzbcc
还没了解过栈，所以还不知道怎么调试呢。
为什么n=1的时候又是 a b c 了，这步不懂
[ 本帖最后由 whukeming 于
17:55 编辑 ]
来　自：江西财经大学
等　级：贵宾
威　望：81
帖　子：3292
专家分：12819
以下是引用whukeming在 17:53:11的发言：
还没了解过栈，所以还不知道怎么调试呢。
什么栈，我是说Debug，一步一步跟进语句执行，一般编译器应该有这功能的
[fly]存在即是合理[/fly]
等　级：论坛游民
帖　子：76
专家分：51
回复 6楼 azzbcc
我用的是mac的Xcode，不了解，具体怎么操作
来　自：江西财经大学
等　级：贵宾
威　望：81
帖　子：3292
专家分：12819
好高端的样子，我也不了解，建议 百度一下
[fly]存在即是合理[/fly]
等　级：贵宾
威　望：304
帖　子：25793
专家分：48814
没有或不会用debugger，可以自己写调试代码追踪数据和指令动向，这些也是很基本要学的东西。
授人以渔，不授人以鱼。
等　级：论坛游民
帖　子：194
专家分：99
首先你要理解递归~，就是你理解递归了吗？那么理解递归。
再复杂的问题也基于最简单的原理。耐心，耐心！丰富自己！等待时机！
版权所有，并保留所有权利。
Powered by , Processed in 0.088394 second(s), 7 queries.
Copyright&, BCCN.NET, All Rights Reserved博客分类：
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编程实现，使我们能够掌握解决此类问题的方法，也使
我们对递归算法能有个更加深刻的理解。
浏览 12692
白色彗星isme
浏览: 26700 次
来自: 深圳
谢谢你，我昨天想很一整晚，我就是突破不了如何用程序实现。你的解 ...
...你这存的是什么？ text？就这个？
代码还是格式一下撒
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'汉诺塔算法的递归算法C++实现
已有 13777 次阅读
|系统分类:|关键词:算法 C++ 程序
/****以下程序是汉诺塔算法的递归算法实现,算法虽然简单,但是能体现出递归算法的精髓,&& 正所谓"麻雀虽小,五脏俱全"!& 很值得编程人员回味 ^_^****/#include&iostream&void move(int n, char x, char y){&&& cout&&"No."&&n&&": "&&x&&" -& "&&y&&}void hanoi(int n, char a, char b, char c){&&& if(n==1)&&&&&&&&move(1,a,c);&&& else{&&&&&&& hanoi(n-1,a,c,b); //可以理解为通过借助c，在b处已经放好n-1个盘&&&&&&&&move(n,a,c);&&&&&& //第n号盘从a处移到c&&&&&&&&hanoi(n-1,b,a,c); //解决b处n-1个盘，最后放到c处&}& }int main(){&& &&& cout&&"Please enter the nunber for Hannoi: ";&&& int num=1;& //初始化为1
&&& cin&&&&& hanoi(num,'A','B','C');&&& cout&&"The process is finished!"&&&&& return 0;}&&&
转载本文请联系原作者获取授权，同时请注明本文来自陈俊清科学网博客。链接地址：
上一篇：下一篇：
当前推荐数：1
评论 ( 个评论)
扫一扫，分享此博文
作者的其他最新博文
热门博文导读
Powered by
Copyright &