 上传我的文档
 下载
 收藏
计量、质量管理体系、质量手册、程序文件、医药、食品安全，法律法规、生活常识、销售管理、国学、论文等专业文档。知识改变世界，知识让你我成长。部分文档为本人收集整理，如有（疑似）侵权，请联系我或道客客服删除。
 下载此文档
正在努力加载中...
数据结构（c语言版） 高佳琴 第5章 递归
下载积分：1000
内容提示：数据结构（c语言版） 高佳琴 第5章 递归
文档格式：PPTX|
浏览次数：0|
上传日期： 15:46:31|
文档星级：
该用户还上传了这些文档
数据结构（c语言版） 高佳琴 第5章 递归
官方公共微信汉诺塔问题递归算法分析
我的图书馆
汉诺塔问题递归算法分析
汉诺塔问题递归算法分析：
　　一个庙里有三个柱子，第一个有64个盘子，从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。
　　1、此时老和尚（后面我们叫他第一个和尚）觉得很难，所以他想：要是有一个人能把前63个盘子先移动到第二个柱子上，我再把最后一个盘子直接移动到第三个柱子，再让那个人把刚才的前63个盘子从第二个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他找了比他年轻的和尚（后面我们叫他第二个和尚），命令：
① 你丫把前63个盘子移动到第二柱子上
&&&& ② 然后我自己把第64个盘子移动到第三个柱子上后
③ 你把前63个盘子移动到第三柱子上
&&&&& 2、第二个和尚接了任务，也觉得很难，所以他也和第一个和尚一样想：要是有一个人能把前62个盘子先移动到第三个柱子上，我再把最后一个盘子直接移动到第二个柱子，再让那个人把刚才的前62个盘子从第三个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他也找了比他年轻的和尚（后面我们叫他第三和尚），命令：
① 你把前62个盘子移动到第三柱子上
&&&& ② 然后我自己把第63个盘子移动到第二个柱子上后
&&&& ③ 你把前62个盘子移动到第二柱子上
　　3、第三个和尚接了任务，又把移动前61个盘子的任务依葫芦话瓢的交给了第四个和尚，等等递推下去，直到把任务交给了第64个和尚为止（估计第64个和尚很郁闷，没机会也命令下别人，因为到他这里盘子已经只有一个了）。
　　4、到此任务下交完成，到各司其职完成的时候了。完成回推了：
第64个和尚移动第1个盘子，把它移开，然后第63个和尚移动他给自己分配的第2个盘子。
第64个和尚再把第1个盘子移动到第2个盘子上。到这里第64个和尚的任务完成，第63个和尚完成了第62个和尚交给他的任务的第一步。
从上面可以看出，只有第64个和尚的任务完成了，第63个和尚的任务才能完成，只有第2个和尚----第64个和尚的任务完成后，第1个和尚的任务才能完成。这是一个典型的递归问题。/************************************************************************/
& 13 12 32
& |13 | 21 23 13 |
&&&&&& 4133
&&&&&& 71411
&&&&&& 515+1+15=31631+1+31=64
&&&&&& n2n-1
&&&&&& hanoin,a,b,c1n23
&&&&&& & :&&&
&&&&&& & (1)
hanoi(n-1,1,3,2)
&&&&&& & (3)
hanoi(n-1,2,1,3)
&&&&&& & C
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
/************************************************************************/
#include &stdio.h&
#include &iostream&
using namespace std;
int move(int n,char a, char b)
&&&&&& printf("==&==&:&&&
%c\n\n",n,a,b);
&&&&&&&&&&&&& return 0;
int hanoi(int n,char a,char b,char c)
&&&&&& cout&&"******************int
hanoi(int n,char a,char b,char c) begin!!!"&&endl;
&&&&&& if (n == 1)
&&&&&&&&&&&&& cout&&"
n="&&n&&""&&a&&""&&c&&""&&endl;
&&&&&& else
&&&&&&&&&&&&& cout&&"
n="&&n&&""&&a&&""&&b&&""&&c&&""&&endl;
&&&&&& if( n==1 )
&&&&&&&&&&&&& cout&&endl&&"11111=&:
&&&&&&&&&&&&& move (1,a,c);
&&&&&& else
&&&&&&&&&&&&& hanoi(n-1,a,c,b);//根据上面解说知道：移动n个盘子需要（2的n次方）-1步，这里需要移动n-1个盘子需要（2的n次方）-2步，也就是说这里的第一轮递归 要进行 n-1 层递归循环，才会结束调用，完成 将&
n-1&个盘子从a座上借助c座，最终放到了b座上，
&&&&&&&&&&&&& move(n,a,c);//完成 将 最后一个盘子即第&n&个盘子从a座上放到了c座上，至此完成第一轮的调用，其结果是将最后一个盘子完成了任务，其余的盘子都还在b座上放着呢，下面一步是对剩余的n-1个盘子进行新一轮的递归调用
&&&&&&&&&&&&& hanoi(n-1,b,a,c);//开启新一轮的递归调用
&&&&&& if (n == 1)
&&&&&&&&&&&&& cout&&"-----------
n="&&n&&""&&a&&""&&c&&""&&endl;
&&&&&& else
&&&&&&&&&&&&& cout&&"-----------
n="&&n&&""&&a&&""&&b&&""&&c&&""&&endl;
&&&&&& cout&&"int
hanoi(int n,char a,char b,char c) end end&
end end end end @@@!!!@@@"&&endl&&endl;
&&&&& return 0;
int main()
&&&&&& freopen("hanoi.in","r",stdin);
&&&&&& freopen("hanoiOutPut.txt","w",stdout);
&&&&&& int num;
&&&&&& scanf("%d",&num);
&&&&&& cout&&""&&endl&&endl;
&&&&&& hanoi(num,'A','B','C');
&&&&&& cout&&endl&&endl&&""&&endl&&endl;
&&&&&& return 0;
******************int hanoi(int n,char
a,char b,char c) begin!!!
******************int hanoi(int n,char
a,char b,char c) begin!!!
******************int hanoi(int n,char
a,char b,char c) begin!!!
11111=&: ==&==&:&
----------- n=1AC
int hanoi(int n,char a,char b,char c) end
end& end end end end @@@!!!@@@
******************int hanoi(int n,char
a,char b,char c) begin!!!
11111=&: ==&==&:&
----------- n=1CB
int hanoi(int n,char a,char b,char c) end
end& end end end end @@@!!!@@@
----------- n=2ACB
int hanoi(int n,char a,char b,char c) end
end& end end end end @@@!!!@@@
******************int hanoi(int n,char
a,char b,char c) begin!!!
******************int hanoi(int n,char
a,char b,char c) begin!!!
11111=&: ==&==&:&
----------- n=1BA
int hanoi(int n,char a,char b,char c) end
end& end end end end @@@!!!@@@
******************int hanoi(int n,char
a,char b,char c) begin!!!
11111=&: ==&==&:&
----------- n=1AC
int hanoi(int n,char a,char b,char c) end
end& end end end end @@@!!!@@@
----------- n=2BAC
int hanoi(int n,char a,char b,char c) end
end& end end end end @@@!!!@@@
----------- n=3ABC
int hanoi(int n,char a,char b,char c) end
end& end end end end @@@!!!@@@
TA的最新馆藏[转]&[转]&[转]&[转]&[转]&[转]&今天看啥 热点：
现在有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，现在把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动？
解决方案：
class HanRuoTa {static long s=0;public static void main(String args[]) {& &&& int n =3;&&& System.out.println("汉诺塔层数为" + n);&&& System.out.println("移动方案为：" );&&& hanoi(n, 'a', 'b', 'c');&&& System.out.println("需要移动次数："+s);& }
static void hanoi(int n, char a, char b, char c) {& && if (n & 0) {&& &&& hanoi(n - 1, a, c, b);&&& move(a, b);&&& hanoi(n - 1, c, b, a);&&& s++;&& && }}
static void move(char x, char y) {& && System.out.println(x + "-&" + y + "\t");& }}
运行结果：
汉诺塔层数为3移动方案为：a-&b a-&c b-&c a-&b c-&a c-&b a-&b 需要移动次数：7
期待更好的方法！！！
相关搜索：
相关阅读：
相关频道：
&&&&&&&&&&&&&&&&
工具软件最近更新c语言汉诺塔实验报告
您现在的位置：&&
c语言汉诺塔实验报告
相关热词搜索：
篇一：c语言课程设计--汉诺塔
课 程 设 计 报 告
课程设计名称：C语言课程设计 课程设计题目：汉诺塔问题求解演示
院（系）：计算机学院 专 业：计算机科学与技术 班 级： 学 号： 姓 名： 指导教师： 完成时间：日目录 第1章
需求分析 ................................................... 3 1.1
课程设计的题目及要求............................................................................... 3 1.2总体分析...................................................................................................... 3 第2章
系统设计 ................................................... 4 2.1
主要函数和函数功能描述........................................................................... 4 2.2
功能模块图................................................................................................... 4 第3章
详细设计 ................................................... 5 3.1主函数流程图.................................................................................................. 5 3.2各功能模块具体流程图.................................................................................. 6 第4章
调试分析 .................................................. 10 4.1.调试初期....................................................................................................... 10 4.2.调试中期....................................................................................................... 10 4.3.调试后期....................................................................................................... 10 参考文献........................................................... 11 附录............................................................ 12第1章
需求分析 1.1
课程设计的题目及要求 题目：汉诺塔问题求解演示 内容： 在屏幕上绘出三根针，其中一根针上放着N个从大到小的盘子。要求将这些盘子从这根针经过一个过渡的针移到另外一根针上，移动的过程中大盘子不能压在小盘子上面，且一次只能移动一个盘子。要求形象直观地演示盘子移动的方案和过程。 要求： 1）独立完成系统的设计，编码和调试。 2）系统利用C语言实现。 3）安照课程设计规范书写课程设计。 4）熟练掌握基本的调试方法，并将程序调试通过 1.2总体分析 本题目需要使用C语言绘制图形，所以需要turbo C，需要绘图函数，而汉诺塔的函数属于经典的函数，在书本上都学习过，所以这个题目的难点在于需要绘制汉诺塔图形。攻克这一点其他的问题都迎刃而解。但是我个人以前也没有学过一些关于turboC 方面的知识。所以我将重点放在了对#include&graphics.h&下的一系列绘图函数的研究与应用,对屏幕上的图像坐标分析是一个难点。其中用到了graphics.h头文件中的bar, outtextxy, setfillstyle，closegraph函数。进行了画图（利用bar函数进行画框的操作），填充颜色（利用setfillstyle函数填充白色和黑色，以分辨图形与图形背景），在特定位置输出特定字符等操作（利用outtextxy函数）。 第2章
系统设计 2.1
主要函数和函数功能描述 1）：递归函数：void hanoi(char x,char y,char z,int n,struct H num[3]); ，根据递归的方法，实现汉诺塔的运行； 2）：用来进行移动的函数：void move(char x,char y,struct H num[3]); 3）：初始化函数：void kaishi（） 4）：图形关闭：void close() 5）：系统主函数：main（） 2.2
功能模块图图2.1
功能模块图 本程序共分为两个模块，分为图形模块与递归模块，其中图形模块中有kaishi函数，主要功能为绘制出初始化的图形。填色函数，填色函数承担着将移走的盘子的原位置填充成为黑色，将移到的盘子的位置填充为白色。画图函数的主要功能是在相应的位置使用bar函数画出相应的图形，创造出汉诺塔的图形轮廓。第二部分为递归部分，包含两个主要函数，其中有Hanoi函数，本函数的主要功能是实现递归操作。Move函数的主要功能是实现盘子移动的操作，并指导图形函数在什么位置画出图形，为图形函数提供准确的坐标。第3章
详细设计 3.1主函数设计 图3.1主函数流程图篇二：汉诺塔问题C语言程序设计 三峡大学理学院2011级电信专业 《高级语言程序设计》课程设计 说明书 ? 设计题目: 汉诺塔的搬移过程设计 ? 班 级：高级语言程序设计1 班 ? 学 号： ? 姓 名：徐飞 ? 完成日期：2012 年6月20日
1设计任务 设计题目：用递归法计算解决汉诺塔问题，并能够演示解决汉诺塔问题过；要求：设计一个运用递归法计算解决汉诺塔问题C语言程序； 2 汉诺（Hanoi）塔问题的提出 古代有一个梵塔，塔内有A,B,C，3个座，座A上有64个大小不等的盘子，大的在下，小的在上（如下图）。有一个和尚想把这64个盘子从座A全部移到座C ，在移动过程中可以借用座A，座B或座C,但每次只允许移动一个盘子，并且不允许大盘放在小盘的上面。 3编程思路 首先，要找出递归的两个关键点，即： 递归终止条件：只有一个盘子时，可以移动。 递归表达式：要找出递归表达式，可以如下设想： 下面以3个盘子为例说明详细的移动过程： (1)将座A上的2个盘子移动到座B上； (2)将座A上的1个盘子移动到座C上； (3)将座B上的2个盘子移动到座C上；
上面第1步可用递归方法分解为： （1）将座A上的1个盘子从座A移动到座C上；
（2）将座A上的1个盘子从座A移动到座B上； (3)将座C上的1个盘子从座C移动到座B上； 第（3）步可用递归方法分解为： （1）将座B上的1个盘子从座B移动到座A上； （2）将座B上的1个盘子从座B移动到座C上； （3）将座B上的1个盘子从座A移动到座C上; 第（1）步操作可归纳为：将座A上的2个盘子借助座C移到座B; 第（3）步操作可归纳为：将座B上的2个盘子借助座A移到座C; 因此，将n个盘子从座A移到座C可以描述为： （1） 将n-1个盘子从座A借助座C移到座B; （2） 将剩下的一个盘子从座A移到座C; （3） 将n-1个盘子从座B借助座A移到座C;
3系统操作流程图;
4.程序说明；
函数HN(int n,char a,char b,char c)表示将n个盘子从座A移到座C,移动过程中借助B 关键语句：HN(n-1,a,c,b)； printf(&from %c to %c\n&,a,c)； HN(n-1,b,a,c); 假设盘子数为2、5，则其运行过程为：5源程序附录； #include&stdio.h&void main() { void HN(int n,char a,char b,char c); printf(&请输入盘子的个数:&); scanf(&%d&,&m); printf(&%d个盘子移动的步骤如下:\n&,m);HN(m,'A','B','C'); } void HN(int n,char a,char b,char c) { if(n==1) printf(&from %c to %c\n&,a,c);
else { HN(n-1,a,c,b); printf(&from %c to %c\n&,a,c);HN(n-1,b,a,c); } }篇三：汉诺塔c语言程序代码 汉诺塔c语言程序代码（通过vc++6.0验证）（附讲解） 让我们先看看代码吧 #include &stdio.h& int hj(int a,int b, int c,int i) {
if(i==1) printf(&%d-&%d\n&,a,c); else {t=c; c=b; b=t; hj(a,b,c,i-1); printf(&%d-&%d\n&,a,b); t=a; a=c; c=t; t=b; b=c; c=t; hj(a,b,c,i-1); return 0; } } main() { int a,b,c,i; a=1; b=2; c=3; printf(&请输入汉诺塔的盘数&); scanf(&%d&,&i); hj(a,b,c,i); return 0; }
以上是汉诺塔的代码，该程序主要是运用了递归的思想，比如数学中的f(x)=f(x-1)+f(x-2)，在本程序中为：int hj(int a,int b, int c,int i) {
if(i==1) printf(&%d-&%d\n&,a,c); else {t=c;c=b; b=t; hj(a,b,c,i-1); 也就是说，我们在这个函数中再次调用这个函数，相当于一个循环，而在再次调用的过程中，i的值变成i-1，就类似于f（x-1），这样层层调用，最终就变成当i=1的时候的值，然后通过运算，计算出想要得到的值。 汉诺塔的数值分析： 我们可以发现，当只有一个盘的时候，我们只需要做1-&3（就是把第一个柱子上的最顶端的盘移动到第三根柱子，以下不再解释） 当有两个盘的时候，是1-&21-&32-&3 三个盘子是：1-&31-&23-&21-&32-&12-&3 分析一下可以得出以下结论： 初始值a=1 b=2 c=3 一个盘子就是a-&c 两个盘子与一个盘子的关系是： 第一步：b与c交换值，然后打印a-&c 第二步：打印a-&b 第三步：a与c交换值，b与c交换值，打印a-&c 进一步分析，便可以得出以下结论 只要盘子数量为i（i大于1），那么它就有三部分 第一部分，b与c交换值，然后运行i-1 第二部分，打印a-&b 第三部分，a与c交换值，b与c交换值，然后运行i-1 程序表示便是： if(i==1) printf(转 载 于: 写论文网:c语言汉诺塔)(&%d-&%d\n&,a,c); else {t=c; c=b;（交换值） b=t; hj(a,b,c,i-1); printf(&%d-&%d\n&,a,b); t=a; a=c; c=t;（a c交换） t=b; b=c; c=t;（b c交换） hj(a,b,c,i-1); 不明加QQ（请写清备注）
1-&3本&&篇:《》来源于:
优秀范文，论文网站
本篇网址:/2016/shiyanbaogao_.html
好文大家读
Copyright &
All Rights Reserved.