君，已阅读到文档的结尾了呢~~
广告剩余8秒
文档加载中
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
汉诺塔 C++课程设计报告
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口欢迎加入我们，一同切磋技术。 &
用户名： &&&
密　码： &
共有 2721 人关注过本帖
标题：汉诺塔问题
等　级：论坛游侠
帖　子：139
专家分：144
结帖率：84.62%
&&已结贴√
&&问题点数：20&&回复次数：6&&&
汉诺塔问题
程序代码：#include&iostream.h&
void move(char one,char anoth)
&&& cout&&one&&&移动到&&&anoth&&
void hanoi(int n,char no1,char no2,char no3)
&&& if (n==<font color=#) move(no1,no3);
&&&&&&&&hanoi(n-<font color=#,no1,no3,no2);//
&&&&&&&&move(no1,no3);
&&&&&&&&hanoi(n-<font color=#,no2,no1,no3);//
void main()
&&& void hanoi(int n,char no1,char no2,char no3);
&&& cout&&&请输入A柱上的金盘子总数：&;
&&& cin&&m;
&&& cout&&&当有&&&m&&&个金盘子时，移动步骤依次为：&&&
&&& hanoi(m,'A','B','C');
程序如上能不能解释一下else那部分的递归是怎么回事，本人看了半天看不懂。
搜索更多相关主题的帖子:
等　级：论坛游民
专家分：21
hanoi(n-1,no1,no3,no2);//&&&&&&&&&把no1柱子上的n-1个盘子以no3柱子为中转转到no2柱子
&&&&&&&&move(no1,no3);&&&&&&&&&&&&&&&把no1柱子上的1个盘子移到no3柱子
&&&&&&&&hanoi(n-1,no2,no1,no3);//&&& 把no2柱子上的n-1个盘子以no1柱子为中转转到no3柱子
最后由嵌套循环实现了no1上的n个盘子移到了no3柱子
这是我的理解，仅供参考
等　级：论坛游侠
帖　子：139
专家分：144
回复 2楼 yiqiliu1209
n-1个盘一起移动吗？不是每次只能移动一个吗？如果不是一起移动，那计算机是怎么把那n-1个盘按要求移动的，上面的代码好像没有具体的做法。能不能解释详细点？
来　自：四川
等　级：蝙蝠侠
帖　子：179
专家分：760
不像重复回答,不过这样的问题:请看这里:
等　级：论坛游侠
帖　子：139
专家分：144
回复 4楼 非死亡！
那个帖子我看过，不过就是弄不懂计算机是怎么运行的，我从代码里面看不懂这个算法。能不能给个详细的解释。拜托了。
等　级：论坛游民
帖　子：18
专家分：42
&&得分:20&
这个是那天在网上看到的：x,y,z就是对应A.B.C三根柱子
汉诺塔问题的重点是分析移动的规则，找到规律和边界条件。
若需要将n个盘子从A移动到C就需要（1）将n-1个盘子从A移动到B；（2）将你第n个从A移动到C；（3）将n-1个盘子再从B移动到C，这样就可以完成了。如果n!=1，则需要递归调用函数，将A上的其他盘子按照以上的三步继续移动，直到达到边界条件n=1为止。
思路清楚了，程序就好理解了。程序中的关键是分析好每次调用移动函数时具体的参数和对应的A、B、C塔的对应的关系。下面来以实际的例子对照程序进行说明。
①move(int n,int x,int y,int z)
③&&&if (n==1)
④&&&&&&printf(&%c--&%c\n&,x,z);
⑦&&&&&&move(n-1,x,z,y);
⑧&&&&&&printf(&%c--&%c\n&,x,z);
⑨&&&&&&{getchar();}//此句有必要用吗？感觉可以去掉的吧
⑩&&&&&&move(n-1,y,x,z);
比如有4个盘子，现在全部放在A塔上。盘子根据编号为1、2、3、4依次半径曾大。现在要将4个盘子移动到C上，并且是按原顺序罗列。首先我们考虑如何才可以将4号移动到C呢？就要以B为中介，首先将上面的三个移动到B。此步的操作也就是程序中的①开始调入move函数（首次调用记为一），当然现在的n=4，然后判断即③n！=1所以不执行④而是到⑤再次调用move函数（记为二）考虑如何将3个盘移动到B的方法。此处是递归的调用所以又一次回到①开始调入move函数，不过对应的参数发生了变化，因为这次要考虑的不是从A移动4个盘到C，而是要考虑从A如何移动移动3个盘到B。因为n=3，故不可以直接移动要借助C做中介，先考虑将两个移动到C的方法，故再一次到⑤再一次递归调用move函数（记为三）。同理两个盘还是不可以直接从A移动到C所以要以B为中介考虑将1个移动到B的过程。这次是以B为中介，移动到C为目的的。接下来再一次递归调用move函数（记为四），就是移动到B一个，可以直接进行。程序执行③ ④句，程序跳出最内一次的调用（即跳出第四次的调用）返回上一次（第三次），并且从第三次的调用move函数处继续向下进行即⑧，即将2号移动到了C，然后继续向下进行到
⑩，再将已经移到B上的哪一个移回C，这样返回第二次递归（以C为中介将3个盘移动到B的那次）。执行⑧，将第三个盘从A移动到B，然后进入⑩，这次的调用时因为是将C上的两个盘移到B以A为中介，所以还要再一次的递归调用，对应的参数传递要分析清楚，谁是原塔谁是目标塔，谁是中介塔。过程类似于上面的分析，这里不再重复论述了。
等　级：论坛游侠
帖　子：139
专家分：144
回复 6楼 achj198781
谢谢，回答很详细！
版权所有，并保留所有权利。
Powered by , Processed in 0.056304 second(s), 8 queries.
Copyright&, BCCN.NET, All Rights Reserved汉诺塔问题C++递归算法浅析与思考
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
这个问题在高中数学课上也曾研究过，不过记得那时班上整体效果奇差，题的基数只是3，最后结果却只有我得出，貌似就是汉诺塔的数学计算公式
将64带入公式，可得出 sum(64)=2^64-1=
很蛋疼的数据。
然后的然后，下面的东西看不懂的可以直接绕道了。。。。。
----------------------------长的像我的都是分割线--------------------------------
前日学习C++指针与引用一章时例题处出现这个本该属于递归函数的题，当日考虑了很久，依然是一头雾水，加上近日感冒头痛，也确实木有心情，想着就头痛啊。当晚请教高手，一句“单步调试”就打发，估计问多了人也烦了，但是尼玛我确实还不会单调啊，今天终于好转，借助百度，却全是只分析递归整体过程，绝不分析内部的流程，借其理解了不少，无奈还是得拿起笔自己一步一步跟踪程序走向（只有不会单调的苦逼才这么干吧?)，废去稿纸几篇，终于理清了头绪。
从头到尾只有一个感叹：写出这算法的不是人，abc移来移去如此复杂的东西居然几行代码就给搞得天衣无缝。
据说学递归不要太注意每一步，只要能把主要过程想明白了，限定条件设定正确，一切就ok了，但是每一步都还没明白怎么出总体思想啊！
-------------------------------------------------------------------------------------
先贴代码：
（文尾附文字代码）
-------------------------------------------------------------------------------------
1.总体递归逻辑：设圆盘有n个
&cout&&a&&"--&"&&c&&//只有一块圆盘，直接移至c
& & &else{
&&&&&&&&&&move(n-1,a,c,b);//将a上的n-1块圆盘通过c移至b
cout&&a&&"--&"&&c&&//将a上第n块圆盘移至c
move(n-1,b,a,c);//将b上的n-1块圆盘移至c
很抽象，但是后面一个大弯要靠其绕过。
2.逐步考虑的方法：列表格跟踪递归的每一步（n=3时如图）
值来源指的是实参的来源，也是一个需要好好理解的大弯，后面详解。
m1,m2分别指程序中第一和第二个move(n-1,a,b,c)。
以上需自己动笔在草稿上考虑，一次过关终身受益。。。
分析a=3的情况。。其它只有计算机才考虑得过来
move(int n,char a,char b,char c)
cout&&a&&"--&"&&c&&
5&&&&&&&&move(n-1,a,c,b);
cout&&a&&"--&"&&c&&
move(n-1,b,a,c);
main函数首先传来实参'a','b','c'，第1行初始值既为move(3,a,b,c),3&1,进入第4行else语句，开始第5行m1的递归，分别为move(2,a,c,b)、move(1,a,b,c),此时n=1，执行语句2、3，完成第一步
m1的递归开始逐层返回，当然，这里只有move(2,a,c,b)（注意，这里是a,c,b，而不是n=1时最后的a,b,c,原因在于其实际各自调用一个函数，且后者在前者的函数内，n=1的值的改变不影响外层n=2的值，只在其自身函数作用域内有效。），程序继续执行第６行（一个递归引用相当于一个函数体，递归返回时便执行函数体内的语句），完成第二步　a--&b;
进入语句7，变为由move(2,a,c,b)变为move(1,c,a,b)，n=1，执行语句2、3，完成第三步
第四步最难理解，先说明：从进入函数，move(3)中实际包含三个部分：一是move(n=2,a,c,b)，二是cout&&a&&"--&"&&c&&endl，三是move(2,b,a,c),即实参下的5、6、7行语句，三个属于并列关系，上面已经完成三个输出的三个步骤都属于三个部分的第一部分move(n=2,a,c,b)，即第一部分已完成，于是将继续执行并列的语句6：cout&&a&&"--&"&&c&&endl，(需要注意的是，同上面一样，此时已近完成m1的递归，程序回到n=3的最外层，所以此时a,c的值分别从move(3,a,b,c)中获取）完成第四步
以上理解透了，接下来就非常简单，程序进入语句7，开始递归m2，其过程与m1完全相同，也是最开始的三步，简单写出：
第5行，由move(2,b,a,c)下推出move（1,b,c,a),进入2、3行，完成第五步
第6行，a,c从move(2,b,a,c)取值，完成第六步 b--&c;
第七行，move(1,a,b,c)，完成第七步 a--&c;
程序执行完毕。
-------------------------------------------------------------------------------------
本人新手一枚，出现任何低级或高级错误都很正常，还望发现的给以指教，先行谢过!
另，以上内容为百度大量资料学习后完成，字字均为幸苦打出，旨在加深理解，所取资料有知道新浪各种编程论坛csdn就不再列出。
-------------------------------------------------------------------------------------
附：完整代码
#include&stdafx.h&
#include&iostream&
#include&stdio.h&
using namespace
void move(int n,int x,int y,int z)
　char c1=x,c2=z;
　if(n==1)
　　cout&&
c1&&"--&"&&
　　move(n-1,x,z,y);
　　cout&&
　　move(n-1,y,x,z);
void main()
　cout&&"input
number:"&&
　cout&&"the step to moving
diskes:"&&
　move(h,'a','b','c');
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。第1页/共6页
1. 实验目的：
通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。
2. 问题描述：
汉诺塔问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A), 其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B 和塔C ）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A 上的碟子移动到塔C 上去，其间借助于塔B 的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。
3. 算法设计思想：
对于汉诺塔问题的求解，可以通过以下三个步骤实现：
(1)将塔A 上的n-1个碟子借助塔C 先移到塔B 上。
(2)把塔A 上剩下的一个碟子移到塔C 上。
(3)将n-1个碟子从塔B 借助于塔A 移到塔C 上。
4. 实验步骤：
用c++ 或c 语言设计实现汉诺塔游戏；
让盘子数从2 开始到7进行实验，记录程序运行时间和递归调用次数；
画出盘子数n 和运行时间t 、递归调用次数m 的关系图，并进行分析。
5. 代码设计：
#include "stdafx.h"
#include &stdlib.h&
#include &stdio.h&
#include &iostream&
printf(" 从%c-&搬到%c\n",x,z);
hanoi(n-1,x,z,y);
printf(" 从%c-&%c搬到\n",x,z);
hanoi(n-1,y,x,z);
第1页/共6页
寻找更多 ""