递归算法实现青蛙过河问题
一、 问题描述
一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L ，面积只容得下一只青蛙落脚，同样右岸也有一石柱R ，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用1，2，…，n 编号。规定初始时这队青蛙只能趴在左岸的石头L 上，当然是一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有S 个石柱，有y 片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求一个落一个，大的在下，小的在上。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱R ，与左岸的石柱L 一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下。当青蛙从左岸的L 上跳走后就不允许再跳回来；同样，从左岸L 上跳至右岸R ，或从溪中荷叶或溪中石柱跳至右岸R 上的青蛙也不允许再离开。问在已知溪中有S 根石柱和y 片荷叶的情况下，最多能跳过多少只青蛙？
二、 程序设计思想
定义函数
Jump ( S ,y ) ——最多可跳过河的青蛙数
其中：S ——河中柱子数
y ——荷叶数
1、当河中无柱子时：即S =0，Jump(0,y)当y = 1 时，
Jump(0,1)=2说明：河中有一片荷叶，可以过两只青蛙，起始时L 上有两只青蛙，1#在2#上面。第一步：1#跳到荷叶上；第二步：2#从L 直接跳至R 上；第三步：1#再从荷叶跳至R 上。
2、当y=2时，
Jump(0,2)=3；
说明：河中有两片荷叶时，可以过3只青蛙。起始时：
1#，2#，3# 3只青蛙落在L 上，
第一步：1# 从L 跳至叶 1上，
L 左岸R
第二步：2# 从L 跳至叶 2上，
第三步：3# 从L 直接跳至R 上，
第四步：2# 从叶2跳至R 上，
第五步：1# 从叶1跳至R 上，
采用归纳法：Jump(0,y)=y+1；
意思是：在河中没有石柱的情况下，过河的青蛙数仅取决于荷叶数，数目是荷叶数+1。
3、若Jump(S, y)，先看一个最简单情况： S=1，y=1。
从图上看出需要9步，跳过4只青蛙。
1# 青蛙从 L －> Y ； 2# 青蛙从 L －> S ； 1# 青蛙从 Y －> S ； 3# 青蛙从 L －> Y ； 4# 青蛙从 L －> R ； 3# 青蛙从 Y －> R ； 1# 青蛙从 S －> Y ；
2# 青蛙从 S －> R ； 1# 青蛙从 Y －> R ；
3、对于S = 1，y = 1的情形，从另外一个角度来分析若没有石柱S ，最多可过
y+1=2 只青蛙。有了石柱S 后，最多可过2*2 = 4 只青蛙。
步骤1：1#和2# 从L －> S ；
步骤2：3#和4# 从L －> R ；
步骤3：1#和2# 从S －> R ；
4、对于S = 1，y > 1的情形若没有石柱S ，最多可过y+1只青蛙。有了石柱S 后，最多可过2*(y+1) 只青蛙。
步骤1：前y+1只从L －> S ；
步骤2：后y+1只从L －> R ；
步骤3：前y+1只从S －> R ；
5、对于S = 2，y > 1的情形若只有石柱S1，最多可过2*(y+1)只青蛙。有了石
L
L R
柱S2后，最多可过4*(y+1)只青蛙。
步骤1：前2*(y+1)只从L －>S2；
步骤2：后2*(y+1)只从L －>R ；
步骤3：前2*(y+1)只从S2－>R ；
6、根据上述分析采用归纳法，可得出如下的递归形式：
Jump(S,y)=2*Jump(S-1,y)；
意思是：先让一半的青蛙利用y 片荷叶和S-1根石柱，落在河中剩下的那根石柱上；然后让另一半的青蛙利用y 片荷叶和S-1根石柱，落在右岸的R 上面；最后再让先前的一半青蛙，利用y 片荷叶和S-1根石柱，落在右岸的R 上面。
递归边界：Jump(0,y)=y+1
将上述分析出来的规律写成递归形式的与或结点图为：
举例：S=3，y=4，算 Jump(3,4)
y+1
三、程序代码
#include
int Jump(int s,int y) {
int a;
if(s==0){a=y+1;}
else
{
a=2*Jump(s-1,y);}
return a;
}
void main()
{
int s,y,a;
printf("请输入石柱数s=" );
scanf("%d",&s);
printf("请输入荷叶数y=" );
scanf("%d",&y);
a=Jump(s,y);
printf(“Jump(%d,%d)=%d\n",s,y,a); }
三、算法分析：
时间复杂度为T（n）=O(s),s为石柱的个数。
数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放
该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构B．存储实现 C．逻辑结构D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列B.链表C.有序表D.链栈 （6）以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i 递归算法的实现 【基本信息】 【课标要求】 （三）算法与问题解决例举 1. 内容标准 递归法与问题解决 （1）了解使用递归法设计算法的基本过程。 （2）能够根据具体问题的要求，使用递归法设计算法、编写递归函数、编写程序、求解问题。 【教材分析】 “算法的程序实现”是《算法与程序设计》选修模块第三单元的内容，本节课是“递归算法的程序实现”，前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序以及本节的前一小节知识点“什么是自定义函数”的学习，在学习自定义函数的基础上，学习递归算法的程序实现是自定义函数的具体应用，培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。 『递归算法在算法的学习过程中是一个难点，在PASCAL和C语言等程序语言的学习过程中，往往是将其放在“函数与过程”这一章节中来讲解的。递归算法的实现也是用函数或是过程的自我调用来实现的。从这一点上来讲，作者对教材的分析与把握是准确的，思路是清晰的，目标是明确的。』 【学情分析】 教学对象是高中二年级学生，前面学习了程序设计的各种结构，在学习程序设计各种结构的应用过程中培养了用计算机编程解决现实中问题的能力，特别是在学习循环语句的过程中，应用了大量的“递推”算法。前一节课学习了如何自定义函数，在此基础上学习深入学习和体会自定义函数的应用。以递推算法的逆向思维进行求解问题，在学习过程中体会递归算法的思想过程。多维度的思考问题和解决问题是提高学生的学习兴趣关键。 『递归算法的本质是递推，而递推的实现正是通过循环语句来完成的。作者准确把握了学生前面的学习情况，对递归算法的本质与特征也分析的很透彻，可以说作者对教学任务的分析是很成功的，接来就要看，在成功分析的基础上作者是如何通过设计教学来解决教学难点的了。』 【教学目标】 算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i 递 归 冯文科 一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引 用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及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 的前几项为 n = 3 Backtrack(1) t=1 for i = 1 to 3 i=1 Swap(x[1], x[1]) t=1时，x[1]取了x[1]=1 Backtrack(2) -----> t = 2 for i = 2 to 3 i=2 swap(x[2], x[2]) t=2时，x[2]取了x[2]=2 Backtrack(3) -----> t=3 for i = 3 to 3 swap(x[3],x[3]) t=3时，x[3]取了x[3]=3 Backtrack(4) ---> t = 4 > 3 输出(1,2,3) swap(x[3],x[3]) swap(x[2],x[2]) i=3 swap(x[2],x[3]) x[2]=3, x[3]=2 t=2时，x[2]取了3 Backtrack(3) -------> t=3 for i = 3 to 3 swap(x[3],x[3]) t=2时，x[3]取了x[3]=2 Backtrack(4) ---> t = 4 > 3 输出(1,3,2) swap(x[3],x[3]) swap(x[2],x[3]) x[2]=2, x[3]=3 Swap(x[1], x[1]) i=2 Swap(x[1], x[2]) x[1]=2, x[2]=1 t=1时，x[1]取了2 Backtrack(2) -----> t = 2 for i = 2 to 3 i=2 swap(x[2], x[2]) t=2时，x[2]取了x[2]=1 Backtrack(3) -----> t=3 for i = 3 to 3 swap(x[3],x[3]) t=3时，x[3]取了x[3]=3 Backtrack(4) ---> 网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题： 1.已知有3个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311. 算法分析(第二章)：递归与分治法 一、递归的概念 知识再现：等比数列求和公式： 1、定义：直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 2、与分治法的关系： 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。 3、递推方程： (1)定义：设序列01,....n a a a简记为{ n a}，把n a与某些个() i a i n <联系起来的等式叫做关于该序列的递推方程。 (2)求解：给定关于序列{n a}的递推方程和若干初值，计算n a。 4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序 5、优缺点： 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 二、递归算法改进： 1、迭代法： (1)不断用递推方程的右部替代左部 (2)每一次替换，随着n的降低在和式中多出一项 (3)直到出现初值以后停止迭代 (4)将初值代入并对和式求和 (5)可用数学归纳法验证解的正确性 2、举例： -----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1 (1)1 T n T n T =?+ = ()(1)1 W n W n n W =?+? （1）=0 《算法设计与分析》习题 第一章算法引论 1、算法的定义 答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。 通俗讲，算法：就是解决问题的方法或过程。 2、算法的特征 答：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性；４)有穷性 3、算法的描述方法有几种 答：自然语言、图形、伪代码、计算机程序设计语言 4、衡量算法的优劣从哪几个方面 答：(1) 算法实现所耗费的时间（时间复杂度）； (2) 算法实现所所耗费的存储空间（空间复杂度）； (3) 算法应易于理解，易于编码，易于调试等等。 5、时间复杂度、空间复杂度定义 答：指的是算法在运行过程中所需要的资源（时间、空间）多少。 6、时间复杂度计算： {i=1； while（i<=n） i=i*2； } 答：语句①执行次数1次， 语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n; 算法执行时间： T(n)= 2log2n +1 时间复杂度：记为O(log2n) ； 7.递归算法的特点 答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件） ②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式） 8、算法设计中常用的算法设计策略 答：①蛮力法；②倒推法；③循环与递归；④分治法； ⑤动态规划法；⑥贪心法；⑦回溯法；⑧分治限界法 9、设计算法： 递归法：汉诺塔问题兔子序列（上楼梯问题） 整数划分问题 蛮力法：百鸡百钱问题 倒推法：穿越沙漠问题 答：算法如下： （1） 递归法 汉诺塔问题 void hanoi(int n, int a, int b, int c) {if (n > 0) { hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } } 兔子序列（fibonaci 数列 ） 递归实现： Int F(int n) { if(n<=2) return 1; else return F(n-1)+ F(n-2); } 上楼梯问题 Int F(int n) { if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2); } 整数划分问题 问题描述：将正整数n 表示成一系列正整数之和，n=n1+n1+n3+… 将最大加数不大于m 的划分个数，记作q(n,m)。正整数n 的划分数 p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系： 递归算法： Int q( int n, int m){ if(n<1||m<1) return 0; If((n=1)||(m=1)) return 1; If (n 数据结构习题 一、填空题 1、算法应具有的五个特性，分别为输入，输出，， 及。 2、对于双向链表,在两个结点之间插入一个新结点需修改的指针共______个，单链表为_______个。 3、设有一个顺序栈S，元素s l，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s l，则顺序栈至少应能存放个元素。 4、串的两种最基本的存储方式是、。 5、具有10个顶点的有向图，边的总数最多为。 6、INDEX（‘DATASTRUCTURE’，‘STR’）=___ _____。（INDEX为子串定位） 7、一棵有n个结点的满二叉树有个度为1的结点、有 个分支（非终端）结点和个叶子。 8、堆排序的算法时间复杂度为。在数据表有序时，快速排序算法的时间复杂度是。 9、数据结构是研讨数据的____________和____________，以及它们之间的相互关系，并对与这种结构定义相应的______________。 10、数据结构中评价算法的两个重要指标是：和 。 11、栈中存取数据的原则，队列中存取数据的原则。 12、链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的。 13、如果一个函数，则称这个函数是一个递归函数。 14、具有10个顶点的无向图，边的总数最多为。 15、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次，当使用监视哨时，若查找失败，则比较关键字的次数为__ __。 16、已知二叉排序树的左右子树均不为空，则__________上所有结点的值均小于它的根结点值，__________上所有结点的值均大于它的根结点的值。 17、下列程序段的时间复杂度为________________。 product = 1; for (i = n;i>0; i--) for (j = i+1; j 递归算法详解 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.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 （1）源程序代码 #include if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } （2）运行界面 ①查找成功 ②查找失败 算法递归典型例题 实验一：递归策略运用练习 三、实验项目 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; 玩转算法与数据结构之递归算法 —HIT2000鲁天伟 递归算法在数据结构的树，图程序中都有应用。那么什么是递归算法呢。其实就是函数的自我调用。循环的在作一件事，把一个问题分成了可以重复的子问题去处理。递归这个词有两层含义，即递去和归来。递去，就是函数一层一层的在调用自己，我们在这里定义调用自己的函数为父函数，被调用的是子函数。父与子是个相对概念（参照二叉树中父结点与子结点来理解）。递去，何时结束呢，是要设定一个结束条件。那么这种结束条件的设置，第一种是设全局变量，全局变量随着每次自我调用在变化，当全局变量达到指定值或是全局变量参与的计算达到某个指定的值时结束。第二种是形参变量在被调用时达到指定值或形参参与的计算达到某个值时结束。第三种是当不满足自我调用条件时结束。这三种结束条件结合程序的需要可以组合使用。归来是指调用到某一次时，子程序执行结束了，子函数一层一层的把程序的执行权返还给自己的父函数，父函数执行所调用子函数的下一条命令。简单的递归，是一个函数体中调用自己一次，复杂的是在函数体中调用自己多次。 举一个字符串逆序输出的简单递归调用的例子如下图。 图表 1 递归函数调用 1、字符串逆序输出问题：将一个长为4的字符串逆序输出。代码如下： #include 一、教学目标 1、知识与技能 (1)．认识递归现象。 (2)．使用递归算法解决问题往往能使算法的描述乘法而易于表达 (3)．理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4)．认识递归算法往往不是高效的算法。 (5)．了解递归现象的规律。 (6)．能够设计递归程序解决适用于递归解决的问题。 (7)．能够根据算法写出递归程序。 (8)．了解生活中的递归现象，领悟递归现象的既有重复，又有变化的 特点，并 且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 （1）了解递归现象和递归算法的特点。 （2）能够根据问题设计出恰当的递归程序。 2、教学难点 (1)递归过程思路的建立。 (2)判断问题是否适于递归解法。 (3)正确写出递归程序。 三、教学环境 1、教材处理 教材选自《广东省普通高中信息技术选修一：算法与程序设计》第四章第五节，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远，但方法和答案却都是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 教学方法采用讲解、探究、任务驱动和学生自主学习相结合 2、预备知识 学生已掌握了用计算机解决问题的过程，掌握了程序设计基础，掌握了解析法、穷举法、查找法、排序法设计程序的技巧。 3、硬件要求 建议本节课在多媒体电脑教室中完成，最好有广播教学系统或投影仪，为拓展学习，学生机应允许上互联网。 4、所需软件 学生机要安装VB6.0或以上版本。 5、所需课时 2课时（90分钟） 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在 叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图是这条河以及河上的两个岛和七座桥的草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 图 七桥问题 南区 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。 编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。 #include java递归算法序列1 1 2 3 5 8 13 21 34编写一个递归方法计算序列[Java编程]悬赏点数10 1个回答588次浏览 江苏过客2009-4-5 20:55:30 58.208.132.* 18...@https://www.doczj.com/doc/551736090.html, 举报 java递归算法序列1 1 2 3 5 8 13 21 34编写一个递归方法计算序列 回答 登录并发表回答取 消 在谷歌搜索java递归算法序列1 1 2 3 5 8 13 21 34编写一个递归方法计算序列 回答按时间排序按投票数排序 ai000012009-9-21 20:37:04 119.61.11.* 举报 递归算法：是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。 递归算法的特点 递归过程一般通过函数或子过程来实现。 递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。 递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。 递归算法解决问题的特点： (1) 递归就是在过程或函数里调用自身。 (2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。 (3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。 (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。 递归算法所体现的“重复”一般有三个要求： 一是每次调用在规模上都有所缩小(通常是减半)； 通常,一个函数在调用另一个函数之前,要作如下的事情: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 数据结构与算法习题及答案
高中信息技术 算法与程序设计-递归算法的实现教案 教科版
算法分析与设计习题集整理
递归算法详解
算法设计与分析排列树递归推算
算法分析与设计复习题及参考答案
算法之2章递归与分治
算法设计与分析习题
数据结构习题
递归算法详解
算法设计与分析：递归与分治法-实验报告
算法设计及分析递归算法典型例题
递归算法实例C源码
递归算法与递归程序
算法设计与分析习题答案1-6章
递归算法
递归算法工作栈的变化详解
04.递归算法讲解
相关主题
文本预览