汉诺塔的递归求解分析
学完函数，就马上出了道经典的汉诺塔来，书里说是把递归提前拿来研究学习了，这题目实在是把我弄晕了。几天都在时时想这个题目。
递归是数学归纳法的逆过程。
递归函数是直接或通过另一个函数间接调用自己的函数。C语言的特点就是允许函数的递归调用。
如果一个问题要用递归解决，得符合以下的条件：
1，该问题要能转换成一个新问题，而新问题的解决方法要和原来的问题相同，只是复杂度有所减少而已。既是要有一定的规律。如求n！。
2、这个问题当简单到一定程度就可以解决，而不用再继续简化。（即需要一个结束递归的条件。否则无限的递归下去，最终会导致系统资源枯竭系统崩溃）。
3、问题用其他方法解决非常困难或不如用递归解决来的简单，（所有递归能解决的问题都能用迭代{非递归}来解决）这个条件是非必要的，但人总需要简单。
?
要用递归解决问题，我们必须分析下列问题：
1、递归的参数，用递归解决的问题通常都比较复杂，规模比较大，要找出决定递归复杂度，规模的参数，比如n！，决定的递归复杂度、规模的就是n。
2、找出递归结束的标志，没有递归结束的条件，将无限循环。造成的后果是严重的。
3、找出递归的通式，才可以进一步简化问题。（通常这是比较困难的）（比如：n！的通式就是n*（n-1）！，而且是可以不断简化直到到达结束递归的边界值）
?
?
?
一般的格式是：
?
if 结束条件1
表达式1（赋予边界值1）
else if 结束条件2
表达式2（赋予边界值2）
.
.
.
else
递归的解决问题的通式。
?
?
汉诺塔的问题；
这个问题对于我这个初学者来说，确实棘手，对于执行的步骤很不理解，虽然递归不用去了解执行的步骤的。但是，不用去了解不等同于不了解。
一个庙里有三个柱子，第一个有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个和尚的任务才能完成。这是一个典型的递归问题。
?
现在我们以有3个盘子来分析：
?
第1个和尚命令：
㈠第2个和尚你先把第一柱子前2个盘子移动到第二柱子。（借助第三个柱子）㈡第1个和尚我自己把第一柱子最后的盘子移动到第三柱子。
㈢第2个和尚你把前2个盘子从第二柱子移动到第三柱子。
很显然，第㈡步很容易实现（哎，人总是自私地，把简单留给自己，困难的给别人）其中第㈠步。第2个和尚他有2个盘子，他就命令：
①第3个和尚你把第一柱子第1个盘子移动到第三柱子。（借助第二柱子）
②第2个和尚我自己把第一柱子第2个盘子移动到第二柱子上。
③第3个和尚你把第1个盘子从第三柱子移动到第二柱子。
同样，第步很容易实现，但第3个和尚他只需要移动1个盘子，所以他也不用在下派任务了。（注意：这就是停止递归的条件，也叫边界值）
第㈢步可以分解为，第2个和尚还是有2个盘子，命令：
①第3个和尚你把第二柱子上的第1个盘子移动到第一柱子。
②第2个和尚我把第2个盘子从第二柱子移动到第三柱子。
③第3个和尚你把第一柱子上的盘子移动到第三柱子。
分析组合起来就是：1-->3 1-->2 3-->2 1-->3 2-->1 2-->3 1-->3共需要七步。如果是4个盘子，则第一个和尚的命令中第1步和第3步各有3个盘子，所以各需要7步，共14步，再加上第1个和尚的1步，所以4个盘子总共需要移动7+1+7=15步，同样，5个盘子需要15+1+15=31步，6个盘子需要31+1+31=64步……由此可以知道，移动n 个盘子需要（2的n次方）--1步。
?
从上面整体综合分析可知把n个盘子从1座（相当第一柱子）移到3座（相当第三柱子）：（1）把1座上（n-1）个盘子借助3座移到2座。
（2）把1座上第n个盘子移动3座。
（3）把2座上（n-1）个盘子借助1座移动3座。
?
下面用hanoi（n,a,b,c）表示把1座n个盘子借助2座移动到3座。
很明显，(1)步上是 hanoi(n-1,1,3,2)
(2)步上是hanoi(n-1,2,1,3)
?
?
?
?
下面便是代码：
?
#include
static long int m=1;/*用来计算移动步骤步数,静态变量才能不断叠加*/
void hanoi(int n,int a,int b,int c)
{
if(n==1){
printf("(%d) %d-->%d/n",m,a,c);
m++;
}
else{
hanoi(n-1,a,c,b);
printf("(%d) %d-->%d/n",m,a,c);/*只有当上一句得到结果，它才会执行*/
m++;
hanoi(n-1,b,a,c);
}
}
main()
{
int d;
printf("Enter the hanoi shu:");
scanf("%d",&d);
hanoi(d,1,2,3);
return 0;
}
?
执行：
Enter the hanoi shu: 3
（1）1-->3
（2）1-->2
（3）3-->2
（4）1-->3
（5）2-->1
（6）2-->3
（7）1-->3
这里可能有个疑问：移动n-1个盘子确实是上面的步骤，但移动n-2的时候就不一样了啊？
hanoi(n-1,a,c,b);
printf("(%d) %d-->%d/n",m,a,c);/*只有当上一句得到结果，它才会执行*/
m++;
hanoi(n-1,b,a,c);
?
其实每一次调用hanoi（n,a,b,c）时a，b，c的值都不同。
如hanoi(n,1,2,3)时a=1,b=2,c=3.
hanoi(n-1,a,c,b);{a=1,b=2,c=3}
就是hanoi(n-1,1,3,2);
所以调用的就是1-->2
再次调用成了hanoi(n-2,a,c,b){a=1,b=3,c=2}
就是hanoi(n-2,1,2,3);
所以调用的就是，1-->3;
每一次都能不断自动改变。
?
Hanoi塔问题中函数调用时系统所做工作
?
一个函数在运行期调用另一个函数时，在运行被调用函数之前，系统先完成3件事：
①将所有的实参、返回地址等信息传递给被调用函数保存。
②为被调用函数的局部变量分配存储区；
③将控制转移到被调用函数的入口。
?
从被调用函数返回调用函数前，系统也应完成3件事：
①保存被调用函数的结果；
②释放被调用函数的数据区；
③依照被调用函数保存的返回地址将控制转移到调用函数。
当有多个函数构成嵌套调用时，按照“后调用先返回”的原则（LIFO），上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为其在栈顶分配一个存储区，每当从一个函数退出时，就释放其存储区，因此当前运行函数的数据区必在栈顶。堆栈特点：LIFO，除非转移或中断，堆栈内容的存或取表现出线性表列的性质。正是如此，程序不要求跟踪当前进入堆栈的真实
单元，而只要用一个具有自动递增或自动递减功能的堆栈计数器，便可正确指出最后一次信息在堆栈中存放的地址。
一个递归函数的运行过程类型于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。因此，和每次调用相关的一个重要的概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入下一层，即i＋1层。反之，退出第i层递归应返回至上一层，即i－1层。为了保证递归函数正确执行，系统需设立一个“递归工作栈”，作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有实参、所有局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。
?
?
?
?
下面为图例，以三个盘子为例：
?
?
Hanoi塔问题中函数调用时系统所做工作处参考文章：《递归处理汉诺塔问题》
递归与循环的优缺点（转载） 2011-08-24 17:49:40| 分类：算法数据结构| 标签：|字号大中小订阅 递归的话函数调用是有开销的，而且递归的次数受堆栈大小的限制。 以二叉树搜索为例： bool search(btree* p, int v) { if (null == p) return false; if (v == p->v) return true else { if (v < p->v) return search(p->left, v); else return search(p->right, v); } } 如果这个二叉树很庞大，反复递归函数调用开销就很大，万一堆栈溢出怎么办？现在我们用循环改写： bool search(btree* p, int v) { while (p) { if (v == p->v) return true; else { if (v < p->v) p = p->left; else p = p->right; } }
return false; } --------------------------------------------------------------------------------------------------------- 递归好处：代码更简洁清晰，可读性更好 递归可读性好这一点，对于初学者可能会反对。实际上递归的代码更清晰，但是从学习的角度要理解递归真正发生的什么，是如何调用的，调用层次和路线，调用堆栈中保存了什么，可能是不容易。但是不可否认递归的代码更简洁。一般来说，一个人可能很容易的写出前中后序的二叉树遍历的递归算法，要写出相应的非递归算法就比较考验水平了，恐怕至少一半的人搞不定。所以说递归代码更简洁明了。 递归坏处：由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。 楼上的有人说： 小的简单的用循环, 太复杂了就递归吧,,免得循环看不懂 话虽然简单，其实非常有道理：对于小东西，能用循环干嘛要折腾？如果比较复杂，在系统撑的住的情况下，写递归有利于代码的维护（可读性好） 另：一般尾递归（即最后一句话进行递归）和单向递归（函数中只有一个递归调用地方）都可以用循环来避免递归，更复杂的情况则要引入栈来进行压栈出栈来改造成非递归，这个栈不一定要严格引入栈数据结构，只需要有这样的思路，用数组什么的就可以。 至于教科书上喜欢n!的示例，我想只是便于递归思路的引进和建立。真正做代码不可能的。 -------------------------------------------------------------------------------------------------------------------- 循环方法比递归方法快, 因为循环避免了一系列函数调用和返回中所涉及到的参数传递和返回值的额外开销。 递归和循环之间的选择。一般情况下, 当循环方法比较容易找到时, 你应该避免使用递归。这在问题可以按照一个递推关系式来描述时, 是时常遇到的, 比如阶乘问题就是这种情况。反过来, 当很难建立一个循环方法时, 递归就是很好的方法。实际上, 在某些情形下, 递归方法总是显而易见的, 而循环方法却相当难找到。当某些问题的底层数据结构本身就是递归时, 则递归也就是最好的方法了。
递归算法与递归程序 岳西中学：崔世义一、教学目标 1知识与技能 (1) ?认识递归现象。 (2) ?使用递归算法解决冋题往往能使算法的描述乘法而易于表达 (3) ?理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4) ?认识递归算法往往不是咼效的算法。 (5) ? 了解递归现象的规律。 (6) ?能够设计递归程序解决适用于递归解决的问题。 (7) ?能够根据算法写出递归程序。 (8) ? 了解生活中的递归现象，领悟递归现象的既有重复，又有变化的特点，并且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2) 和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 (1) 了解递归现象和递归算法的特点。 (2) 能够根据问题设计出恰当的递归程序。 2、教学难点 (1) 递归过程思路的建立。 (2) 判断冋题是否适于递归解法。 (3) 正确写出递归程序。 三、教学环境 1、教材处理 教材选自《浙江省普通高中信息技术选修：算法与程序设计》第五章，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自 定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习⑵ 和练习
// test_project.cpp : 定义控制台应用程序的入口点。//汉诺塔问题的 // //递归实现 /*#include "stdafx.h" #include
{ count++; cout<<"第"< /*后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放A B C； 若n为奇数，按顺时针方向依次摆放A C B。 （）按顺时针方向把圆盘从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘在柱子A，则把它移动到B；若圆盘在柱子B，则把它移动到C；若圆盘在柱子C，则把它移动到A。 （）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。 （）反复进行（）（）操作，最后就能按规定完成汉诺塔的移动。 所以结果非常简单，就是按照移动规则向一个方向移动金片： 如阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C 汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。*/ /*#include "stdafx.h" #include 汉诺塔非递归算法C语言实现 #include 目录 摘要 (1) 研究背景 (2) 基本概念及特性.......................................................... (2) 栈的运算 (3) 栈的运用举例 (5) 递归原理 (6) 迷宫求解 (8) 栈实现迷宫问题 (8) 递归实现迷宫算法 (8) 参考文献 (9) 附录 (9) 栈与递归的关系 摘要：栈（stack）又称堆栈，他是线性表中的一种特殊情况，并且也是最简单的情况之一，它是一种运算受限的线性表，其限制是仅仅允许在表的一端进行插入和删除运算。由于栈的插入和删除运算仅在栈的一端实现，后进栈的元素必定先出栈，所以又把栈称为后进先出表。 递归是一种非常重要的概念和解决问题的方法，在计算机科学和数学领域有着广泛的应用，递归调用是计算机解决部分疑难问题特别有效,易于实现的一种算法。比如著名的汉诺塔问题、八皇后问题、树的遍历等如果不用递归算法解决,几乎难以实现,大部分计算机语言教材都涉及到这一重要算法。在计算机系统内，执行递归函数是通过栈来实现的，栈中的每一个元素包含有递归函数的每一参数域、每一个局部变量和调用后的返回地址域，其中引用参数域只保存传送来的实参的地址，以便按此地址访问实参的储存空间存取其值，其他的每个域是用于存储其值的实际存储空间，每次进行函数调用的时候，都要把相应的填压入栈，每次结束调用时，都按照本次返回地址返回到指定的位置进行，并且自动做一次退栈操作，使得下一层所使用的参数称为新的栈顶，继续被使用。栈与递归都能够解决一些实际问题，主要是通过C/C++语言来实现编程运算，得到相应的结果。 递归和栈是可以相互转换的，当编写递归算法时，虽然表面上没有使用栈，但是系统执行时会自动建立和使用栈，本文中在求解迷宫问题时就充分的体现出了这一点。 关键词：栈递归C/C++语言迷宫问题 归并排序算法实现（迭代和递归）\递归实现归并排序的原理如下： 递归分割: 递归到达底部后排序返回: 最终实现排序： #include } while(i 一、教学思想（包括教学背景、教学目标） 1、教学背景 本课程“递归算法”，属于《数据结构与算法》课程中“栈和队列”章节的重点和难点。数据结构与算法已经广泛应用于各行各业的数据存储和信息处理中，与人们的社会生活密不可分。该课程是计算机类相关专业核心骨干课程，处于计算机学科的核心地位，具有承上启下的作用。不仅成为全国高校计算机类硕士研究生入学的统考科目，还是各企业招聘信息类员工入职笔试的必考科目。数据结构与算法课程面向计算机科学与技术、软件工程等计算机类学生，属于专业基础课。 2、教学大纲 通过本课程的学习，主要培养学生以下几个方面的能力： 1）理解递归的算法； 2）掌握递归算法的实现要素； 3）掌握数值与非数值型递归的实现方法。 根据学生在学习基础和能力方面的差异性，将整个课程教学目标分成三个水平：合格水平（符合课标的最低要求），中等以上水平（符合课标的基本要求），优秀水平（符合或超出课标提出的最高要求）。具体如下表： 二、课程设计思路（包括教学方法、手段） “递归算法”课程以故事引入、案例驱动法、示范模仿、启发式等多元化教学方法，设计课程内容。具体的课堂内容如下所示： 1 1 2 3 3 7 4 15 5 31 count = 2n-1 思考：若移动速度为1个/秒，则需要 (264-1)/365/24/3600 >= 5849亿年。 四、总结和思考 总结： 对于阶乘这类数值型问题，可以表达成数学公式，然后从相应的公式入手推导，解决这类问题的递归定义，同时确定这个问题的边界条件，找到结束递归的条件。 对于汉诺塔这类非数值型问题，虽然很难找到数学公式表达，但可将问题进行分解，问题规模逐渐缩小，直至最小规模有直接解。 思考： 数值型问题：斐波那契数列的递归设计。 非数值型问题：八皇后问题的递归设计。阐述总结知识拓展 三、教学特色（总结教学特色和效果） 递归算法课程主要讨论递归设计的思想和实现。从阶乘实例入手，由浅入深，层层深入介绍了递归的设计要点和算法的实现。从汉诺塔问题，通过“边提问，边思考”的方式逐层深入地给出算法的分析和设计过程。通过故事引入、案例导入、实例演示、PPT展示、实现效果等“多元化教学方式”，努力扩展课堂教学主战场。加上逐步引导、问题驱动，启发学生对算法的理解，并用实例演示展示算法的分析过程，在编译环境下实现该算法，加深对算法实现过程的认识。 1、知识点的引入使用故事诱导法讲授 通过“老和尚讲故事”引入函数的递归调用，并通过“世界末日问题” 故事引入非数值型问题的递归分析，激发学习积极性，挖掘学生潜能。 实验二知识表示方法 梵塔问题实验 1．实验目的 （1）了解知识表示相关技术； （2）掌握问题规约法或者状态空间法的分析方法。 2．实验内容（2个实验内容可以选择1个实现） （1）梵塔问题实验。熟悉和掌握问题规约法的原理、实质和规约过程；理解规约图的表示方法； （2）状态空间法实验。从前有一条河，河的左岸有m个传教士、m个野人和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。 3．实验报告要求 （1）简述实验原理及方法，并请给出程序设计流程图。 我们可以这样分析： （1）第一个和尚命令第二个和尚将63个盘子从A座移动到B座； （2）自己将底下最大的盘子从A移动到C； （3）再命令第二个和尚将63个盘子从B座移动到C；（4）第二个和尚命令第三个和尚重复（1）（2）（3）；以此类推便可以实现。这明显是个递归的算法科技解决的问 题。 （2）源程序清单： #include int n; printf("input the number of diskes\n"); scanf("%d",&n); hanoi(n,'A','B','C'); } void hanoi(int n,char p1,char p2,char p3) { if(1==n) cout<<"盘子从"< 汉诺塔递归与非递归算法研究 作者1，作者2，作者33 (陕西师范大学计算机科学学院，陕西西安 710062) 摘要: 摘要内容(包括目的、方法、结果和结论四要素) 摘要又称概要,内容提要.摘要是以提供文献内容梗概为目的,不加评论和补充解释,简明,确切地记述文献重要内容的短文.其基本要素包括研究目的,方法,结果和结论.具体地讲就是研究工作的主要对象和范围,采用的手段和方法,得出的结果和重要的结论,有时也包括具有情报价值的其它重要的信息.摘要应具有独立性和自明性,并且拥有与文献同等量的主要信息,即不阅读全文,就能获得必要的信息. 关键词:关键词1; 关键词2；关键词3；……（一般可选3~8个关键词，用中文表示，不用英文 Title 如：XIN Ming-ming , XIN Ming (1.Dept. of ****, University, City Province Zip C ode, China；2.Dept. of ****, University, City Province Zip C ode, China；3.Dept. of ****, University, City Province Zip C ode, China) Abstract: abstract（第三人称叙述，尽量使用简单句；介绍作者工作（目的、方法、结果）用过去时，简述作者结论用一般现在时） Key words: keyword1;keyword2; keyword3;……（与中文关键词对应，字母小写(缩略词除外)）； 正文部分用小5号宋体字，分两栏排，其中图表宽度不超过8cm.。设置为A4页面 1 引言（一级标题四号黑体加粗） 这个问题当时老和尚和众僧们，经过计算后，预言当所有的盘子都从基柱A移到基座B上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。其实，不管这个传说的可信度有多大，如果考虑把64个盘子，由一个塔柱上移到另一根塔柱上，并且始终保持上小下大的顺序。假设有n个盘子，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2n-1。n=64时， f(64)= 2^64-1=18446744073709551615 假如每秒钟一次，共需多长时间呢？一年大约有 31536926 秒，计算表明移完这些金片需要5800多亿年，比地球寿命还要长，事实上，世界、梵塔、庙宇和众生都早已经灰飞烟灭。 对传统的汉诺塔问题，目前还有不少的学者继续研究它的非递归解法，本文通过对递归算法的研究……. 提示：（1）可以定义问题的规模n,如盘子的数量；（2）塔柱的数量（目前有部分理论可以支撑，不妨用计算机实现）分析规模的变化与算法的复杂度比较。（3）可以对经典的汉诺塔问题条件放松、加宽，如在经典的汉诺塔问题中大盘只能在小盘下面，放松其他条件可以定义相邻两个盘子必须满足大盘只能在小盘下面。其它盘子不作要求。 2 算法设计 2.1 汉诺塔递归算法描述（二级标题小五黑体加粗） 用人类的大脑直接去解3，4或5个盘子的汉诺塔问题还可以，但是随着盘子个数的增多，问题的规模变的越来越大。这样的问题就难以完成，更不用说吧问题抽象成循环的机器操作。所以类似的问题可用递归算法来求解。下面n个盘的汉 栈与递归的关系 姓名：郭小兵 学号：1007010210 专业：信息与计算科学院系：理学院 指导老师：彭长根 2012年10月17日 栈与递归的关系 郭小兵 摘要递归是计算机科学中一个极为重要的概念,许多计算机高级语言都具有递归的功能,对于初学计算机者来讲,递归是一个简单易懂的概念,但真正深刻理解递归,正确自如的运用递归编写程序却非易事,本文通过一些实例来阐述递归在计算机内的实现及递归到非递归的转换,也许使读者能加深对递归的理解。 关键词栈递归非递归 引言递归是一种程序设计的方式和思想。计算机在执行递归程序时，是通过栈的调用来实现的。栈，从抽象层面上看，是一种线性的数据结构，这中结构的特点是“先进后出”，即假设有a，b，c三个元素，依次放某个栈式存储空间中，要从该空间中拿到这些元素，那么只能以c、b、a的顺序得到。递归程序是将复杂问题分解为一系列简单的问题，从要解的问题起，逐步分解，并将每步分解得到的问题放入“栈”中，这样栈顶是最后分解得到的最简单的问题，解决了这个问题后，次简单的问题可以得到答案，以此类推。分解问题是进栈（或者说压栈）的过程，解决问题是一个出栈的过程。 科学家对栈与递归都做了很多深入的研究，研究表明“递归算法 和栈都有后进先出这个性质，基本上能用递归完成的算法都可以用栈完成，都是运用后进先出这个性质的”这个性质可用于进制的转换。与汇编程序设计中主程序和子程序之间的链接及信息交换相类似，在高级语言编制的程序中，调用函数和被调用函数之间的链接及信息交换需过栈来进行。递归是计算科学中一个极为重要的概念。许多计算机高级语言都具有递归的功能，本文将通过一些是例来阐述递归在计算机内的实现及递归到非递归的转换，也许能加深对递归的理解。递归是某一事物直接或间接地由自己完成。一个函数直接或间接地调用本身，便构成了函数的递归调用，前者称之为直接递归调用，后者为间接递归调用。递归会使某些看起来不容易解决的问题变得容易解决。特别当一个问题蕴含递归特性且结构比较复杂时，采用递归算法往往要自然、简洁、清晰，写出的程序较为简短。在很多时候，程序结构简单，可读性好甚至比运行时间更重要，所以掌握递归算法也就存在一定的必要性。但许多人，特别是计算机专业低年级和一些初学者，往往觉得递归很难理解。为了更好地掌握他，了解递归过程的操作原理就更有意义了。 Make By Mr.Cai 思路介绍： 首先，可证明，当盘子的个数为n 时，移动的次数应等于2^n - 1。 然后，把三根桩子按一定顺序排成品字型（如：C ..B .A ），再把所有的圆盘按至上而下是从小到大的顺序放在桩子A 上。 接着，根据圆盘的数量确定桩子的排放顺序： 若n 为偶数，按顺时针方向依次摆放C ..B .A ； 若n 为奇数，按顺时针方向依次摆放B ..C .A 。 最后，进行以下步骤即可： （1）首先，按顺时针方向把圆盘1从现在的桩子移动到下一根桩子，即当n 为偶数时，若圆盘1在桩子A ，则把它移动到B ；若圆盘1在桩子B ，则把它移动到C ；若圆盘1在桩子C ，则把它移动到A 。 （2）接着，把另外两根桩子上可以移动的圆盘移动到新的桩子上。 即把非空桩子上的圆盘移动到空桩子上，当两根桩子都非空时，移动较小的圆盘。 （3）重复（1）、（2）操作直至移动次数为2^n - 1。 #include } void Push(int top)//进栈 { s[++this->top]=top; } void setNext(Stake *p) { next=p; } Stake *getNext()//获取下一个对象的地址 { return next; } int getName()//获取当前桩子的编号 { return name; } private: int s[Cap+1];//表示每根桩子放盘子的最大容量 int top,name; Stake *next; }; void main() { int n; void hanoi(int,int,int,int); cout<<"请输入盘子的数量："; cin>>n; if(n<1) cout<<"输入的盘子数量错误!!!"< 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.实验步骤： 1.用c++ 或c语言设计实现汉诺塔游戏； 2.让盘子数从2 开始到7进行实验，记录程序运行时间和递 归调用次数； 3.画出盘子数n和运行时间t 、递归调用次数m的关系图， 并进行分析。 5.代码设计： Hanio.cpp #include"stdafx.h" #include 迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。 利用迭代算法解决问题，需要做好以下三个方面的工作： 一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。 三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。 例 1 ：一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到第 12 个月时，该饲养场共有兔子多少只？ 分析：这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ，第 2 个月时兔子的只数为 u 2 ，第 3 个月时兔子的只数为 u 3 ，……根据题意，“这种兔子从出生的下一个月开始，每月新生一只兔子”，则有 u 1 ＝ 1 ， u 2 ＝ u 1 ＋u 1 × 1 ＝ 2 ， u 3 ＝ u 2 ＋u 2 × 1 ＝ 4 ，…… 根据这个规律，可以归纳出下面的递推公式： u n ＝ u n － 1 × 2 (n ≥ 2) 对应 u n 和 u n － 1 ，定义两个迭代变量 y 和 x ，可将上面的递推公式转换成如下迭代关系： y=x*2 x=y 让计算机对这个迭代关系重复执行 11 次，就可以算出第 12 个月时的兔子数。参考程序如下： cls 利用栈实现递归参考程序1（Turbo2.0环境）： #define MAXSIZE 100 #include printf("%d",k); else printf("%c",k+55); } printf("\n"); } main(){ int num; clrscr(); printf("Input a num,-1 to quit:\n"); scanf("%d",&num); while(num!=-1){ trans(num); scanf("%d",&num); } } 参考程序2：（C＋＋/VC环境） #define STACK_INIT_SIZE 100//存储空间初始分配量 #define OVERFLOW -1 #define OK 1 #define STACKINCREMENT 10//存储空间分配增量 #define ERROR 0 #define TRUE 1 #define FALSE 0 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #include "iostream.h" typedef int status; typedef char SElemType; typedef struct{//顺序栈的定义 SElemType *base; SElemType *top; int stacksize; }SqStack; status InitStack(SqStack &S){//构造一个空栈S S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW);//存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } 一、用迭代法求斐波那契数列。 #include printf("输入sin（x）中的x:\n"); scanf("%lf",&x); do { sum=sum+sign*pow(x,n)/factorial(n); n=n+2; sign=-sign; }while(pow(x,n)/factorial(n)>=1e-6); printf("sin(%.2lf)=%.2lf\n",x,sum); return 0; } 课程实践报告 题目：汉诺塔 姓名： 学号： 班级： 日期： 一实践目的 1、初步具备根据应用需求选择合理数据结构并进行算法设计的能力； 2、进一步提升C语言的应用能力； 3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 5、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风； 6、提升文档写作能力。 二问题定义及题目分析 汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18，446，744，073，709，551，615 这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。后来，这个传说就演变为汉诺塔游戏: 1.有三根杆子A，B，C。A杆上有若干圆盘。2.每次移动一块圆盘，小的只能叠在大的上面。3.把所有圆盘从A杆全部移到C杆上。经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动圆盘：如3阶汉诺塔的移动：A→C，A→B，C→B，A→C，B→A，B→C，A→C。 程序所能达到的功能： 用户只需要输入所需的层数即可，程序会自动计算出最终需要的步骤，并同时给出中间移动的过程。 三概要设计 1、设计思想 如果盘子为1，则将这个盘子从塔座A移动到塔座C；如果不为1，则采用递归思想。将塔座A的前n-1个盘子借助C盘（即目的盘）移到塔座B，移后，此时C为空座，那我们就可以将塔座A的第n个盘子移到塔座C了。接下来就将塔座B的n-1个盘子借助A移到塔座C，从而完成盘子的移动。 2、数据类型 结构体：用来存放盘子的栈。同时，在函数的参数中还用到了结构体类型的引用。 其他类型：基本的数据类型，包括整形，字符型。用来存放临时变量。 3、主要模块 递归算法详解标准化管理处编码[BBX968T-XBB8968-NNJ668-MM9N] 递归 冯文科一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简 a与前面临近几项之间的关单，于是人们想出另一种办法来描述这种数列：通过初值及 n 系。 要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它，应该是： a的值，那么可以很容易地写成这样： 如果需要写一个函数来求 n 这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。 以上面求阶乘数列的函数) f为例。如在求)3(f时，由于3不是特殊值，因此需 (n 要计算)2( 3f，但)2(f是对它自己的调用，于是再计算)2(f，2也不是特殊值，需要计 * 算)1( f，返回 )1(= 2f，需要知道)1(f的值，再计算)1(f，1是特殊值，于是直接得出1 * 上一步，得2 3 * )2( )3(= = f，从而得最终 =f )1( 3 2 * * )2(= =f 2 f，再返回上一步，得6 解。 用图解来说明，就是 通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口. 从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的. ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现同步. 下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式). 下面以先序遍历来说明: void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法*/ { if (T) { visit(T); /* 访问当前结点*/ preorder_recursive(T->lchild); /* 访问左子树*/ preorder_recursive(T->rchild); /* 访问右子树*/ } } visit(T)这个操作就是对当前数据进行的处理, preorder_recursive(T->lchild)就是把当前数据变换为它的左子树,访问右子树的操作可以同样理解了. 现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的"叶子结点".汉诺塔非递归算法C语言实现
栈与递归
归并排序算法实现 (迭代和递归)
汉诺塔问题与递归思想教学设计
汉诺塔问题
汉诺塔问题的非递归算法分析
栈与递归的关系
汉诺塔问题非递归算法详解
汉诺塔问题实验报告
迭代与递归的区别
数据结构利用栈实现递归
C语言(迭代法与递归法)
课程实践报告_汉诺塔
递归算法详解完整版
递归算法工作栈的变化详解
相关主题
文本预览