|
函数的递归调用与分治策略 发布于: 来源:互联网 作者:佚名 时间: 00:05 Hanoi:";cin>>n;cout<<"Answer:"<<endl;hanoi(n,'A','B','C');}函数递归调用的应用与分治策略许多算法都采用了分治策略求解，而可以说分治与递归是一对孪生兄弟，它们经常同时被应用于算法的设计中。下面讨论著名的Catalan数问题，人们在对它的研究中充分应用了分治策略。[例4]Catalan数问题。[问题描述]一个凸多边形，通过不相交于n边形内部的对角线，剖分为若干个三角形。求不同的剖分方案总数H(n)。H(n)即为Catalan数。例如，n=5时H(5)=5。[分析]Catalan数问题有着明显的递归子问题特征。在计算Catalan数时虽然可以推导出只关于n的一般公式，但在推导过程中却要用到递归公式。下面讨论三种不同的解法，其中第三种解法没有使用递归，它是由前两种解法推导而出的。[解法1]对于多边形V1V2…Vn，对角线V1Vi（i=3,4,…,n-1）将其分为两部分，一部分是i边形，另一部分是n-i 1边形。因此，以对角线V1Vi为一个剖分方案的剖分方案数为H(i)*H(n-i 1)。还有一种的特殊情形，是对角线V2Vn将其分为一个三角形V1V2Vn和一个n-2 1边形。为了让它同样符合粗体字给出的公式，规定H(2)=1。于是得到公式：H(n)=∑H(i)*H(n-i 1)（i=2,3,…,n-1）----公式(1)H(2)=1有了这个递归关系式，就可以用递推法或递归法解出H(n)。[解法2]从V1向除了V2和Vn外的n-3个顶点可作n-3条对角线。每一条对角线V1Vi把多边形剖分成两部分，剖分方案数为H(i)*H(n-i 1,t);}}[例6]“九宫阵”智力游戏。[问题描述]一个9×9方阵，由9个“九宫格”组成，每个九宫格又由3×3共9个小格子组成。请在每个空白小格子里面填上1～9的数字，使每个数字在每个九宫格内以及在整个九宫阵中的每行、每列上均出现一次。（1）编程将下面图中的九宫阵补充完整。（2）讨论是否可能给出“九宫阵”的全部解？ 注意斜体的“a[i,j]:=0”必不可少！当对某个结点(x,y)扩展的过程中，可能在扩展到(x m,y n)时它的子树被完全杀死（每个结点都被杀死，亦即按照(x,y)及之前的填数方案填数，无解）。这时需要保证(x,y)以后所填的数被重新置零，这个语句的作用即在每个结点被杀死时都将其置零。将伪代码翻译为C 递归方法在算法与数据结构中的应用无所不在，如动态规划（状态方程）、回溯法（深度优先搜索）等等，以上两例只是冰山一角。只有熟悉掌握函数递归调用的编程方法，深入理解分治策略的重要思想，才能编写出功能强大、高效简明的程序。="msonormal"style="margin:0cm0cm0pt"> |
1.一个函数调用其自身，就是递归
2.递归和普通函数调用一样是通过栈实现的
3.树与二叉树适合使用递归的形式来表述
4.算法分为基础步和归纳步
递归算法是将归纳法的思想应用于算法设计之中，递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对于相关且必要地信息的保存与回复
（1）问题的描述涉及规模
（2）问题的规模发生变化后，解决问题的方法完全相同，并且原问题的解由小规模问题的解构成
（3）小规模的问题是可以求解的（在有限步内可以停机）
输入：盘子的个数n、柱子的名称a,b,c
输出：斐波那契数列第n位的值
有n阶楼梯，每次只能下一个或者两个，计算一共有多少种下楼方法
什么是递归函数 一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递...
目录介绍 01.什么是递归 02.递归三个条件 03.斐波那契数列 04.找指定目录下所有文件 05.求1+2+…...
计算机科学的新学生通常难以理解递归程序设计的概念。递归思想之所以困难，原因在于它非常像是循环推理（circular...
递归的本质： 是指一种通过重复将问题分解为同类的子问题而解决问题的方法，其核心思想是分治策略。 递归分为两个过程，...
在计算机程序中，描述迭代的一种方法是使用循环，另一种完全不同的迭代实现方法就是递归。阶乘函数（通常表示为n!）是一...
版本：ios 1.2.1 亮点： 1.app角标可以实时更新天气温度或选择空气质量，建议处女座就不要选了，不然老想...
我是黑夜里大雨纷飞的人啊 1 “又到一年六月，有人笑有人哭，有人欢乐有人忧愁，有人惊喜有人失落，有的觉得收获满满有...
兔子虽然是枚小硕 但学校的硕士四人寝不够 就被分到了博士楼里 两人一间 在学校的最西边 靠山 兔子的室友身体不好 ...
