递 归
冯文科
一、递归的基本概念。
一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引
用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。
二、递归的最简单应用：通过各项关系及初值求数列的某一项。
在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及n a 与前面临近几项之间的关系。
要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。
比如阶乘数列
1、2、6、24、120、720……
如果用上面的方式来描述它，应该是：
???>==-1
,1,11n na n a n n
如果需要写一个函数来求n a 的值，那么可以很容易地写成这样：
这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一
些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。
递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为
特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。
以上面求阶乘数列的函数)(n f 为例。如在求)3(f 时，由于3不是特殊值，因此需要计
算)2(*3f ，但)2(f 是对它自己的调用，于是再计算)2(f ，2也不是特殊值，需要计算
)1(*2f ，需要知道)1(f 的值，再计算)1(f ，1是特殊值，于是直接得出1)1(=f ，返回上
一步，得2)1(*2)2(==f f ，再返回上一步，得62*3)2(*3)3(===f f ，从而得最终解。
用图解来说明，就是
下面再看一个稍复杂点的例子。
【例1】数列}{n a 的前几项为
1、
1
11+、1
1111++、
1
111111++
+
、……
输入n ，编程求n a 的精确分数解。 分析：
这个题目较易，发现11=a ，其它情况下有1
11
-+=
n n a a 。如要求实数解的话，这基本
已经可以写出递归函数了。但由于题目要求精确的分数解，还需做一些调整。设p
q a n =
-1，则由递归关系，有q
p p p
q a a n n +=
+
=
+=
-1111
1
，再约分化简，即得n a 。但发现一个问题：求出1-n a 时，需要返回两个整数：分子q 与分母p ，而通常的函数只能返回一个整数。
这个问题一般有两类解决办法，一种是让求值函数返回一个结构体变量，这样就可以返
回两个变量了（其实还可以不只两个呢）；另一种是在求值函数的参数表中加入两个指针变量或引用变量，通过参数给带回数值。但由于后一种做法会使程序结构不清晰——返回值是由参数表得到的，因此我们使用前一种方法。
另外，在通过p q a n =
-1得出q
p p
a n +=后，n a 就已经是最简分数了，无须化简。证明如下：
若
p
q
是最简分数，即说明q p ,的最大公约数为1，即对任何q r ≤<1，都有r q mod 与r p mod 不全为0，不防记a r q =mod 、b r p =mod ，则有
r b a r q p mod )(mod )(+=+
只要a 与b 不全为0，且r b r a <<,，就有a 与r b a mod )(+不全为0。因此对任何的
q r ≤<1，有r p mod 与r q p mod )(+不全为0。
而对于p r q ≤<的情况而言，记a r p =mod ，则有
r q a r q p mod )(mod )(+=+
由于r q r a <<<≤0,0，因此同样有r p mod 与r q p mod )(+不全为0。
所以对任意p r ≤<1，都有r p mod 与r q p mod )(+不全为0，因此它们的最大公约
数为1，即
q p p +是最简分数。虽然这是个要求1-n a （即p
q
）是最简分数的结论，但由于数列第二项为
2
1
，是最简分数，因此可以证明第三项也是最简分数，同时也证明对所有的n a ，求出的
q
p p
+就是最简分数，无须化简。 具体代码如下：
)90(≤≤N N N -0i 1+i 2+i N N N i N i 12+i )1(2+i , MAX*sizeof(char));
t[n]='\0'; for(i=0;i t[q[i]]='Q'; cout< cout< bool test(int i, int k) { 1 3 5 7 9 0 2 4 6 8 int j; j=0; while(j if(j==k && mark[i]==false) return true; else return false; } void search(int k) { if(k==n) { write(); c++; return; } int i; for(i=0;i if(test(i, k)) { mark[i]=true; q[k]=i; search(k+1); mark[i]=false; } 六、练习 【练习】为给定的表达式建立表达式树，并求值。给定的表达式中，所有数字都是1位正整数，出现的符号可能为＋、－、*、/、（、）。 分析： 这是一个与一般数据结构书上讲的用栈计算的方法本质不同的方法。 在详细说明这个算法之前，需要首先明确这个算法用到的概念 1、单元：一个单元可能是用括号括起来的一个表达式，或是一个整数； 2、项：一个项是指由*与/连接起来的若干单元； 3、表达式：一个表达式是指由＋或－连接起来的若干项。 要建立表达式树，需要三个函数互相调用的函数：一个是getunit，用于建立一个单元；一个是getexpr，用于建立一个项，另一个就是build，用于建立一个表达式。 getunit函数较易，如果字符串首字母是（的话，那么从它后面的字符开始用build建立一个表达式，这个表达式就是一个单元；否则，就处理一个整数； getexpr函数是建立在getunit之上的，它先用getunit建立一个单元，然后不停地考察之后地连接符号是不是*或/，若是，则不停地重复读连接符、建立另一个单元、建立连接的操作，直到连接符号不是*或/为止。 build函数是用于最终建立表达式的，它先用getexpr建立一个项，再用符号将剩余的各项连接成二叉树。 代码如下： if(n>0){ hanoi(n-1 ,x,z,y); hanoi(n-1,y,x,z); }.w[10]中 int knap(int s,int n){ 算法32是求n个数的和的递归算法。算法33是相应的迭代版本。假设n个数已存储在 数组a的分量a[1]，…,a[n]中。 float sum(int n){.a[n]都置为0 a[0]=1; */ /* ---------------------------------------- */ void main() { int i; for ( i = 0; i < 5; i++ ) printf("%d! = %d\n",i,factorial(i));/*递归阶乘函数调用*/ } /* ======================================== */ /* 使用列印数组函数来说明递归调用*/ /* ======================================== */ int list[6] = { 1, 2, 3, 4, 5, 6 }; /* 数组内容 */ /* ---------------------------------------- */ /* 递归数组反向列印函数*/ /* ---------------------------------------- */ void invert_array(int j) { if ( j < 6 ) /* 终止条件 */ { /* 递归链表列印函数调用 */ invert_array(j + 1); printf("[%d]",list[j]); /* 列印元素资料 */ } } /* ---------------------------------------- */ /* 主程式: 反向列印数组内容. */ /* ---------------------------------------- */ void main() { int i; printf("数组的内容:\n"); for ( i = 0; i < 6; i++ ) printf("[%d]",list[i]); /* 列印元素资料 */ printf("\n"); /* 换 行 */ printf("递归列印数组的内容:\n"); invert_array(0); /* 调用列印函数 */ printf("\n"); /* 换 行 */ } /* ======================================== */ /* 递归阶乘函数来说明递归内部处理*/ /* ======================================== */ /* ---------------------------------------- */ /* 递归阶乘函数*/ /* ---------------------------------------- */ int factrial(int j) { int sum = 0; /* 阶乘总和变数 */ int temp = 0; /* 阶乘总和暂存变数 */ if ( j == 0 ) /* 终止条 件 */ { sum = 1; printf("到达终止条件(j = 0)\n"); } else { printf("从函数factrial(%d)调用前的状态: sum = %d\n", j, sum); temp = factrial(j - 1); /* 递归阶乘函数调用 */ printf("返回函数factrial(%d)后的状态: sum = %d\n", j, sum); sum = j * temp; /* 计算j!的值 */ printf(" ==> 在计算%d!阶乘后的状态: sum = %d\n", j, sum); } return sum; } /* ---------------------------------------- */ /* 主程式: 计算整数 4 的阶乘. */ /* ---------------------------------------- */ void main() { printf("4! = %d\n",factrial(4)); /* 递归阶乘函数调用 */ } /* ======================================== */ /* 递归的链表建立和列印*/ /* ======================================== */ #include <> struct list /* 链表结构宣 告 */ { int data; /* 节点资 料 */ struct list *next; /* 指向下一节点 */ }; typedef struct list node; /* 定义新型态 */ typedef node *link; /* 定义新型态指标 */ /* ---------------------------------------- */ /* 递归链表列印函数*/ /* ---------------------------------------- */ void print_list(link ptr) { if ( ptr != NULL ) /* 终止条件 */ { printf("[%d]",ptr->data); /* 列印节点资料 */ /* 递归链表列印函数调用 */ print_list(ptr->next); } } /* ---------------------------------------- */ /* 递归链表建立函数*/ /* ---------------------------------------- */ link create_list(int *array,int len,int pos) { link head; /* 链表节点的指标 */ if ( pos == len ) /* 终止条件 */ return NULL; else { /* 建立节点记忆体 */ head = ( link ) malloc(sizeof(node)); if ( !head ) return NULL; head->data = array[pos]; /* 建立节点内容 */ head->next = create_list(array,len,pos + 1); return head; } } /* ---------------------------------------- */ /* 主程式: 建立链表后将内容印出. */ /* ---------------------------------------- */ void main() { int list[6] = { 1, 2, 3, 4, 5, 6 }; /* 数组内容 */ link head; /* 指向链表开 始 */ head = create_list(list,6,0); /* 建立链表 */ if ( !head ) { printf("记忆体配置失败! \n"); exit(1); } printf("链表的内容:\n"); print_list(head); /* 列印链表 */ printf("\n"); /* 换 行 */ } /* ======================================== */ /* 递归的链表建立和反向列印*/ /* ======================================== */ #include <> struct list /* 链表结构宣 告 */ { int data; /* 节点资 料 */ struct list *next; /* 指向下一节点 */ }; typedef struct list node; /* 定义新型态 */ typedef node *link; /* 定义新型态指标 */ /* ---------------------------------------- */ /* 递归链表反向列印函数*/ /* ---------------------------------------- */ void print_list(link ptr) { if ( ptr != NULL ) /* 终止条件 */ { /* 递归链表列印函数调用 */ print_list(ptr->next); printf("[%d]",ptr->data); /* 列印节点资料 */ } } /* ---------------------------------------- */ /* 递归链表建立函数*/ /* ---------------------------------------- */ link create_list(int *array,int len,int pos) { link head; /* 链表节点的指标 */ if ( pos == len ) /* 终止条件 */ return NULL; else { /* 建立节点记忆体 */ head = ( link ) malloc(sizeof(node)); if ( !head ) return NULL; head->data = array[pos]; /* 建立节点内容 */ head->next = create_list(array,len,pos + 1); return head; } } /* ---------------------------------------- */ /* 主程式: 建立链表后将内容印出. */ /* ---------------------------------------- */ void main() { int list[6] = { 1, 2, 3, 4, 5, 6 }; /* 数组内容 */ link head; /* 指向链表开 始 */ head = create_list(list,6,0); /* 建立链表 */ if ( !head ) { printf("记忆体配置失败! \n"); exit(1); } printf("链表的内容:\n"); print_list(head); /* 列印链表 */ printf("\n"); /* 换 行 */ /* ======================================== */ /* 河诺塔问 题*/ /* ======================================== */ /* ---------------------------------------- */ /* 河内塔问题的递归函数*/ /* ---------------------------------------- */ int hanoi(int dishs,int peg1,int peg2,int peg3) { if ( dishs == 1) /* 终止条件 */ printf("盘子从 %d 移到 %d\n",peg1,peg3); else { hanoi(dishs - 1,peg1,peg3,peg2); /* 第一步骤 */ printf("盘子从 %d 移到 %d\n",peg1,peg3); hanoi(dishs - 1,peg2,peg1,peg3); /* 第三步骤 */ } } /* ---------------------------------------- */ /* 主程式: 找出河内塔问题的解. */ /* ---------------------------------------- */ void main() { hanoi(3,1,2,3); /* 调用递归函数 */ } /* ======================================== */ /* 应用递归来走迷宫*/ /* 数字 0: 表示是可走的路*/ /* 数字 1: 表示是墙壁,不可走的路 */ /* 数字 2: 标示是走过的路*/ /* ======================================== */ int maze[7][10] = { /* 迷宫的数 组 */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; /* ---------------------------------------- */ /* 走迷宫的递归函数*/ /* ---------------------------------------- */ int find_path(int x,int y) { if ( x == 1 && y == 1 ) /* 是否是迷宫出口 */ { maze[x][y] = 2; /* 记录最后走过的路 */ return 1; } else if ( maze[x][y] == 0 ) /* 是不是可以走 */ { maze[x][y] = 2; /* 记录己经走过的路 */ if ( ( find_path(x - 1,y) + /* 调用递归函数往上 */ find_path(x + 1,y) + /* 往 下 */ find_path(x,y - 1) + /* 往 左 */ find_path(x,y + 1) ) > 0 ) /* 往右 */ return 1; else { maze[x][y] = 0; /* 此路不通取消记号 */ return 0; } } else return 0; } /* ---------------------------------------- */ /* 主程式: 用递归的方法在数组迷宫找出口. */ /* ---------------------------------------- */ void main() { int i,j; find_path(5,8); /* 调用递归函 数 */ printf("迷宫的路径如下图所示:\n"); for ( i = 1; i < 6; i++) /* 印出迷宫的图形 */ { for ( j = 1; j < 9; j++) printf("%d",maze[i][j]); /* 印出各座标 */ printf("\n"); /* 换 行 */ } } /* ======================================== */ /* 应用递归来解 N 皇后问题 */ /* 数字 1: 表示是放置皇后*/ /* 数字 0: 表示没有放置*/ /* ======================================== */ #define MAXQUEEN 8 /* 最大放置的皇后数 */ int pad[MAXQUEEN][MAXQUEEN] = { /* N X N 的棋盘 */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; /* ---------------------------------------- */ /* 放 N 个皇后的递归函数 */ /* ---------------------------------------- */ int put_queen(int x,int y,int times) { 递归算法的实现 【基本信息】 【课标要求】 （三）算法与问题解决例举 1. 内容标准 递归法与问题解决 （1）了解使用递归法设计算法的基本过程。 （2）能够根据具体问题的要求，使用递归法设计算法、编写递归函数、编写程序、求解问题。 【教材分析】 “算法的程序实现”是《算法与程序设计》选修模块第三单元的内容，本节课是“递归算法的程序实现”，前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序以及本节的前一小节知识点“什么是自定义函数”的学习，在学习自定义函数的基础上，学习递归算法的程序实现是自定义函数的具体应用，培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。 『递归算法在算法的学习过程中是一个难点，在PASCAL和C语言等程序语言的学习过程中，往往是将其放在“函数与过程”这一章节中来讲解的。递归算法的实现也是用函数或是过程的自我调用来实现的。从这一点上来讲，作者对教材的分析与把握是准确的，思路是清晰的，目标是明确的。』 【学情分析】 教学对象是高中二年级学生，前面学习了程序设计的各种结构，在学习程序设计各种结构的应用过程中培养了用计算机编程解决现实中问题的能力，特别是在学习循环语句的过程中，应用了大量的“递推”算法。前一节课学习了如何自定义函数，在此基础上学习深入学习和体会自定义函数的应用。以递推算法的逆向思维进行求解问题，在学习过程中体会递归算法的思想过程。多维度的思考问题和解决问题是提高学生的学习兴趣关键。 『递归算法的本质是递推，而递推的实现正是通过循环语句来完成的。作者准确把握了学生前面的学习情况，对递归算法的本质与特征也分析的很透彻，可以说作者对教学任务的分析是很成功的，接来就要看，在成功分析的基础上作者是如何通过设计教学来解决教学难点的了。』 【教学目标】 算法设计的特征：有穷性，确定性，输入和输出，可行性 运行算法的时间：硬件的速度。书写程序的语言。问题的规模，编译生成程序的代码质量算法复杂度: 时间复杂度和空间复杂度 1．迭代法 迭代法又称为辗转法，是用计算机解决问题的一种基本方法，为一种不断用变量的旧值递推新值的过程，与直接法相对应，一次性解决问题。迭代法分为精确迭代和近似迭代，“二分法”和“牛顿迭代法”属于近似迭代法。迭代法利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。 利用迭代算法解决问题，需要做好以下三个方面的工作： 1.确定迭代变量（在可以用迭代算法解决的问题中，至少存在一个直接或间接地 不断由旧值递推出新值的变量，这个变量就是迭代变量。） 2. 建立迭代关系式（所谓迭代关系式，指如何从变量的前一个值推出其下一个值 的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以顺推 或倒推的方法来完成。） 3.对迭代过程进行控制（在什么时候结束迭代过程？这是编写迭代程序必须考虑 的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为 两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所 需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实 现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程 的条件。） 2．穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。 即本方法使用可以理解为暴力循环方法，穷举所有可能性，一般这种方法的时间效率太低，不易使用。但是方法简单，易理解。 3．递推法 递推是计算机数值计算中的一个重要算法，思路是通过数学推导，将复杂的运算化解为若干重复的简单运算，以充分发挥计算机长于重复处理的特点。递推法: 递推法实际上是一种递推关系，就是为了得到问题的解，把它推到比原问题简单的 问题求解，可分为顺推法和倒推法。 i.顺推法，就是先找到递推关系式，然后从初始条件出发，一步步地按 递推关系式递推，直至求出最终结果。 ii.倒推法，就是在不知道初始条件的情况下，经某种递推关系而获知问题的解，再倒过来，推知它的初始条件。 4．递归法（递推加回归） 一个过程或函数在其定义或说明中又间接或间接调用本身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题类似的规模较小的问题来求解，递 归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了 程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想 写出的程序往往十分简洁易懂。 一般来说，递归需要有边界条件、递归前进段和递归前往段。当边界条件不满脚时，递归前进;当边界条件满脚时，递归前往。 递 归 冯文科 一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引 用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及n a 与前面临近几项之间的关系。 要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它，应该是： ???>==-1 ,1,11n na n a n n 如果需要写一个函数来求n a 的值，那么可以很容易地写成这样： 这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一 些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为 特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。 以上面求阶乘数列的函数)(n f 为例。如在求)3(f 时，由于3不是特殊值，因此需要计 算)2(*3f ，但)2(f 是对它自己的调用，于是再计算)2(f ，2也不是特殊值，需要计算 )1(*2f ，需要知道)1(f 的值，再计算)1(f ，1是特殊值，于是直接得出1)1(=f ，返回上 一步，得2)1(*2)2(==f f ，再返回上一步，得62*3)2(*3)3(===f f ，从而得最终解。 用图解来说明，就是 下面再看一个稍复杂点的例子。 【例1】数列}{n a 的前几项为 算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i; 递归算法详解标准化管理处编码[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 解。 用图解来说明，就是 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<<"输入的盘子数量错误!!!"< 递归算法详解 C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。 许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任何优越之处。在菲波那契数列中，它的效率更是低的非常恐怖。 这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。 我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267除10的余数是7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在ASCII码中，字符‘7’的值是55，所以我们需要在余数上加上48来获得正确的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性。‘0’的ASCII码是48，所以我们用余数加上‘0’，所以有下面的关系： ‘0’+ 0 =‘0’ ‘0’+ 1 =‘1’ ‘0’+ 2 =‘2’ ... 从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10等于426。然后用这个值重复上述步骤。 这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。 我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。 这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身。 在程序中，递归函数的限制条件就是变量quotient为零。在每次递归调用之前，我们都把quotient除以10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。 /*接受一个整型值（无符号0，把它转换为字符并打印它，前导零被删除*/ ○1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 ○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 边界条件与递归方程是递归函数的二个要素 应用分治法的两个前提是问题的可分性和解的可归并性 以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。 回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。 舍伍德算法设计的基本思想: 设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为 这显然不能排除存在x∈Xn使得的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有 拉斯维加斯( Las Vegas )算法的基本思想: 设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)>0。 设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有： 解此方程可得： 蒙特卡罗(Monte Carlo)算法的基本思想: 设p是一个实数，且1/2 通常,一个函数在调用另一个函数之前,要作如下的事情: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)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的"叶子结点". 1.用递归法计算n! 【讲解】 递归是算法设计中的一种基本而重要的算法。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。 递归方法具有易于描述、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。 递归概述 一个函数在它的函数体内调用它自身称为递归（recursion）调用。是一个过程或函数在其定义或说明中直接或间接调用自身的一种方法，通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 使用递归要注意以下几点： （1）递归就是在过程或函数里调用自身； （2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。 例如有函数r如下： int r(int a) { b=r(a?1); return b; } 这个函数是一个递归函数，但是运行该函数将无休止地调用其自身，这显然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。 构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的，也可以是递推描述的。 例4-1 用递归法计算n!。 n!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。 （1）描述递归关系 递归关系是这样的一种关系。设{U 1,U 2 ,U 3 ,…,U n ,…}是一个序列，如果从某一项k开始， U n 和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。 注意到，当n≥1时，n!=n*(n?1)!（n=0时，0!=1），这就是一种递归关系。对于特定的k!，它只与k与(k?1)!有关。 （2）确定递归边界 在步骤1的递归关系中，对大于k的U n 的求解将最终归结为对U k 的求解。这里的U k 称 为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。 确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序： #include 实验一：循环与递归算法的应用 【实验目的】 1．掌握循环、递归算法的基本思想、技巧和效率分析方法。 2．熟练掌握循环和递归的设计要点，清楚循环和递归的异同。 3．学会利用循环、递归算法解决实际问题。 【实验内容】 1. 问题描述： （1）题目一：打印图形 编程打印如下图所示的N阶方阵。 1 3 6 10 15 2 5 9 14 4 8 13 7 12 11 （2）题目二：计算前n项和 根据参数n，计算1+2+……+n。 要求：用循环和递归分别实现 （3）题目三：回文判断 判断s字符串是否为“回文”的递归程序。 2. 数据输入：个人设定，由键盘输入。 3. 要求： （1）上述题目一、二必做，题目三选做； （2）独立完成实验及实验报告。 【具体实现过程】 题目一： 【算法分析】 通过两个for循环控制数字的输出。 【实现代码】 #include 题目二： 【算法分析】 定义一个sum函数求和,把求出的新值赋给sum,最后求得的值即为前n项和。【实现代码】 递归 #include "stdio.h" int fun(int num) { int sum; if( num==1) sum=1; else sum=num+fun(num-1); return sum; } void main() { int n,s; printf("n="); scanf("%d",&n); s=fun(n); printf("s=%d\n",s); } 递归算法的优缺点： ○ 1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 ○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 边界条件与递归方程是递归函数的二个要素 应用分治法的两个前提是问题的可分性和解的可归并性 以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。 回溯法以深度优先的方式搜索解空间树T ，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T 。 舍伍德算法设计的基本思想: 设A 是一个确定性算法，当它的输入实例为x 时所需的计算时间记为tA(x)。设Xn 是算法A 的输入规模为n 的实例的全体，则当问题的输入规模为n 时，算法A 所需的平均时间为 这显然不能排除存在x ∈Xn B ，使得对问题的输入规模为n 拉斯维加斯( Las Vegas )算法的基本思想: 设p(x) 是对输入x 调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x 均有p(x)>0。 设t(x)是算法obstinate 找到具体实例x 的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x 蒙特卡罗(Monte Carlo)算法的基本思想: 设p 是一个实数，且1/2 实验九 一、实验内容 教材3.9 定义递归函数实现下面的Ackman函数 n+1 m=0 Acm(m,n)= Acm(m-1,1) n=0 Acm(m-1,Acm(m,n-1)) n>0,m>0 教材3.10 用递归法实现勒让德多项式： 1 n=0 Pn= x n=1 ((2n-1)xPn-1(x)-(n-1)Pn-2(x))/n 教程p24 使用欧几里得算法计算两个数的最大公约数，分别用递推和递归两种算法实现 教程p26 编程：将上题以多文件方式组织，在area.h中声明各个area（）函数原型，在area.cpp文件中定义函数，然后在Exp9_2中包含area.h,定义main（） 函数并执行。 二、实验目的 1、掌握函数的嵌套调用好递归调用 2、掌握递归算法 3、了解内联函数、重载函数、带默认参函数的定义及使用方法 4、掌握程序的多文件组织 5、掌握编译预处理的内容，理解带参数宏定义与函数的区别 三、实验步骤 教材3.9 定义递归函数实现下面的Ackman函数 n+1 m=0 Acm(m,n)= Acm(m-1,1) n=0 Acm(m-1,Acm(m,n-1)) n>0,m>0 教材3.10用递归法实现勒让德多项式： 1 n=0 Pn= x n=1 ((2n-1)xPn-1(x)-(n-1)Pn-2(x))/n 教程p24 使用欧几里得算法计算两个数的最大公约数，分别用递推和递归两种算法实现 教程p26 编程：将上题以多文件方式组织，在area.h中声明各个area（）函数原型，在area.cpp文件中定义函数，然后在Exp9_2中包含area.h,定义main（） 函数并执行。 四、实验数据及处理结果 玩转算法与数据结构之递归算法 —HIT2000鲁天伟 递归算法在数据结构的树，图程序中都有应用。那么什么是递归算法呢。其实就是函数的自我调用。循环的在作一件事，把一个问题分成了可以重复的子问题去处理。递归这个词有两层含义，即递去和归来。递去，就是函数一层一层的在调用自己，我们在这里定义调用自己的函数为父函数，被调用的是子函数。父与子是个相对概念（参照二叉树中父结点与子结点来理解）。递去，何时结束呢，是要设定一个结束条件。那么这种结束条件的设置，第一种是设全局变量，全局变量随着每次自我调用在变化，当全局变量达到指定值或是全局变量参与的计算达到某个指定的值时结束。第二种是形参变量在被调用时达到指定值或形参参与的计算达到某个值时结束。第三种是当不满足自我调用条件时结束。这三种结束条件结合程序的需要可以组合使用。归来是指调用到某一次时，子程序执行结束了，子函数一层一层的把程序的执行权返还给自己的父函数，父函数执行所调用子函数的下一条命令。简单的递归，是一个函数体中调用自己一次，复杂的是在函数体中调用自己多次。 举一个字符串逆序输出的简单递归调用的例子如下图。 图表 1 递归函数调用 1、字符串逆序输出问题：将一个长为4的字符串逆序输出。代码如下： #include 案例一： publicclass Fibonacci { //一列数的规则如下: 1、1、2、3、5、8、13、21、34 ，求第30位数是多少？使用递归实现 publicstaticvoid main(String[] args){ System.out.println(Fribonacci(9)); } publicstaticint Fribonacci(int n){ if(n<=2) return 1; else return Fribonacci(n-1)+Fribonacci(n-2); } } 案例二： publicclass Hanio1 { /* * 汉诺塔（又称河内塔）问题其实是印度的一个古老的传说。开天辟地的神勃拉玛（和中国的盘古差不多的神吧）在一个庙里留下了三根金刚石的棒， * 第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上， * 规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖(移动圆片的次数)18446744073709551615， * 众僧们即便是耗尽毕生精力也不可能完成金片的移动了。 *要求：输入一个正整数n，表示有n个盘片在第一根柱子上。输出操作序列，格式为“移动 t从 x 到y”。每个操作一行， *表示把x柱子上的编号为t的盘片挪到柱子y上。柱子编号为A，B，C，你要用最少的操作把所有的盘子从A柱子上转移到C柱子上。 */ publicstaticvoid main(String[] args){ int i=3; char a ='A',b='B',c='C'; hanio(i,a,b,c); } publicstaticvoid hanio(int n,char a,char b,char c){ if(n==1) System.out.println("移动"+n+"号盘子从"+a+"到"+c); else{ hanio(n-1,a,c,b);//把上面n-1个盘子从a借助b搬到c System.out.println("移动"+n+"号盘子从"+a+"到"+c);//紧接着直接把n搬动c hanio(n-1,b,a,c);//再把b上的n-1个盘子借助a搬到c } } } 案例三： publicclass Rabbit { /* 古典问题：3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ 分析：首先我们要明白题目的意思指的是每个月的兔子总对数；假设将兔子分为小中大三种，兔子从出生后三个月后每个月就会生出一对兔子， 那么我们假定第一个月的兔子为小兔子，第二个月为中兔子，第三个月之后就为大兔子，那么第一个月分别有1、0、0，第二个月分别为0、1、0， 第三个月分别为1、0、1，第四个月分别为,1、1、1，第五个月分别为2、1、2，第六个月分别为3、2、3，第七个月分别为5、3、5…… 兔子总数分别为：1、1、2、3、5、8、13…… 于是得出了一个规律，从第三个月起，后面的兔子总数都等于前面两个月的兔子总 数据结构课程设计 设计说明书 n！非递归算法的设计与实现 学生姓名赵娜 学号1021024042 班级信管102班成绩 指导教师曹记东 数学与计算机科学学院 2012 年 3 月 3 日 数据结构课程设计评阅书 注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。 课程设计任务书 2011—2012学年第2学期 专业：计算机科学与技术学号：1021024042 姓名：赵娜 课程设计名称：数据结构课程设计 设计题目：n！非递归算法的设计与实现 完成期限：自2012 年 2 月20 日至2012 年 3 月 3 日共 2 周 设计内容： 利用非递归算法实现n！的计算，在设计过程中应注意n值大小与数据类型表数范围之间的关系，并尽可能求出较大n值的阶乘。 要求: 1）阐述设计思想，画出流程图； 2）说明测试方法，写出完整的运行结果； 3）从时间、空间对算法分析； 4）较好的界面设计； 5）编写课程设计报告。 以上要求中第一个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。 指导教师（签字）：教研室主任（签字）： 批准日期：2012年 2 月20 日 摘要 设计了一个用非递归算法实现n!的软件，该软件具有计算从1到999之间整数的阶乘的运算的功能。本计算器采用VC++作为软件开发环境，采用数组存储运算的结果，用栈输出运算结果，用递推法实现了整数的阶乘运算，界面清晰，易于为用户所接受。 关键词：n!; 非递归;数组;栈 目录 1 课题描述 (1) 2 需求分析 (2) 3 概要设计 (3) 4 详细设计 (4) 5 程序编码 (8) 6 程序调试与测试 (10) 7 结果分析 (12) 8 总结 (13) 参考文献 (14) 一分而治之算法 分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。下列通过实例加以说明。 例：利用分而治之算法求一个整数数组中的最大值。 练习：[找出伪币] 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。 二贪心算法 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪心算法(Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪心算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪 《递归算法与递归程序》(一)教学设计 一、教材分析 “递归算法与递归程序”是广东教育出版社《算法与程序设计》选修1第四单元第五节的内容，前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序，且在第二章中学习了自定义过程与函数。在前面学习的基础上，学习递归算法的程序实现是自定义函数的具体应用，在培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。 二、学情分析 教学对象是高中二年级学生，前面学习了程序设计的各种结构与自定义函数（过程）及常用基础算法，在学习程序设计各种结构的应用过程中，培养了学生用计算机编程解决现实中的问题的能力。在学习循环语句的过程中，应用了大量的“递推”算法，在第二章中，学习了如何使用自定义函数，在此基础上深入学习和体会自定义函数的应用，以递推算法的逆向思维进行求解问题，在学习过程中体会递归算法的思想过程。多维度的思考问题和解决问题是提高学生的学习兴趣关键。 三、教学目标 知识与技能： 1、理解什么是递归算法，学会递归算法的思想分析问题 2、能够应用递归算法编程处理实际问题 过程与方法：学生参与讨论，通过思考、动手操作，体验递归算法的方法 情感态度与价值：结合数学中的实例，激发学生使用数学知识建模的意识，培养学生多维度的思考问题和解决问题。 四、教学重点与难点 重点：理解什么是递归算法 难点：学生用递归算法的思想分析问题 五、教学过程 进程教师活动学生活动设计意图 创设情境课堂导入： 师：今天我们先做一个小的智力题目 有4个人排成一队，问最后一个人的身高时，他 说比第3个人高2厘米；问第3个人的身高时， 他说比第2个人高2厘米；问第2个人的身高时， 他说比第1个人高2厘米；最后问第1个人的身 师生共同活动找 出递变规律 使用情境教学法 在此活动过程中能 让学生初步从活动 中体验“问题的发与 收”从而走进了递归 的思维模式，为进一高中信息技术 算法与程序设计-递归算法的实现教案 教科版
算法设计题详解
递归算法详解
算法设计及分析递归算法典型例题
递归算法详解完整版
汉诺塔问题非递归算法详解
递归算法详解
递归算法的优缺点
递归算法工作栈的变化详解
04.递归算法讲解
实验1：循环与递归算法实验
递归算法的优缺点
c++,使用欧几里得算法计算两个数的最大公约数,分别用递推和递归两种算法实现5
递归算法实例C源码
递归算法经典案例
n!非递归算法的设计与实现
C语言经典算法详解
高中信息技术递归算法的实现教案 粤教版
相关主题
文本预览