竞赛辅导22.ppt

《竞赛辅导22.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、8/17/20211程序设计竞赛讲座2递归专题3．1．2递归设计要点◆递归算法是一个模块（函数、过程）除了可调用其它模块（函数、过程）外，还可以直接或间接地调用自身的算法。◆递归是一种比迭代循环更强、更好用的循环结构。◆只需要找出递归关系和最小问题的解。◆递归方法只需少量的步骤就可描述出解题过程所需要的多次重复计算，大大地减少了算法的代码量。递归的关键在于找出递归方程式和递归终止条件。递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。递归边界条件：也就是所描述问题的最简单情况，它本身不再使用递归的定义。递

2、归算法解题通常有三个步骤：1）分析问题、寻找递归：找出大规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。2）设置边界、控制递归：找出停止条件，即算法可解的最小规模问题。3）设计函数、确定参数：和其它算法模块一样设计函数体中的操作及相关参数。两个经典的递归例题：【例1】汉诺塔问题【例2】整数的分划问题【例1】汉诺塔问题描述：古代有一个梵塔，塔内有3个基座A、B、C，开始时A基座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从A座移到B座，但每次只允许移动一个盘子，且在移动过程中在3

3、个基座上的盘子都始终保持大盘在下，小盘在上。在移动过程中可以利用C基座做辅助。请编程打印出移动过程。算法设计：用归纳法解此题，约定盘子自上而下的编号为1，2，3，……，n。首先看一下2阶汉诺塔问题的解，不难理解以下移动过程：初始状态为A（1,2）B（）C（）第一步后A（2）B（）C（1）第二步后A（）B（2）C（1）第三步后A（）B（1,2）C（）如何找出大规模问题与小规模问题的关系，从而实现递归呢？把n个盘子抽象地看作“两个盘子”，上面“一个”由1——n-1号组成，下面“一个”就是n号盘子。移动过程如下：第一步：先把上面“

4、一个”盘子以a基座为起点借助b基座移到c基座。第二步：把下面“一个”盘子从a基座移到b基座。第三步：再把c基座上的n-1盘子借助a基座移到b基座。把n阶的汉诺塔问题的模块记作hanoi(n,a,b,c)a代表每一次移动的起始基座，b代表每一次移动的终点基座，c代表每一次移动的辅助基座则汉诺塔问题hanoi(n,a,b,c)等价于以下三步：第一步，hanoi(n-1,a,c,b)；第二步，把下面“一个”盘子从a基座移到b基座；第三步，hanoi(n-1,c,b,a)。至此找出了大规模问题与小规模问题的关系。2hanoi(int

5、n,chara,charb,charc){if(n>0)/*0阶的汉诺塔问题当作停止条件*/{hanoi(n-1,a,c,b);printf("Movedise%dfrom%cto%c",n,a,b);hanoi(n-1,c,b,a);}}main(){inta=3,b=4;printf("%d",hanoi(2,'A','B','C'));}main(){intn;scanf(“%d”,&n);f(n);}f(intn){if(n<10)printf(“%d”,n);else{printf(“%d”,n%10);f

6、(n/10);}}【例2】任给十进制的正整数，输出对应的二进制数。main(){intn;scanf(“%d”,&n);f(n);}f(intn){if(n<10)printf(“%d”,n);else{f(n/10);printf(“%d”,n%10);}}【例3】用递归函数实现“辗转相除法，求最大公约数”【例4】用递归函数实现“折半查找法”【例5】整数的分划问题对于一个正整数n的分划就是把n写成一系列正整数之和的表达式。例如，对于正整数n=6，它可以分划为：65+14+2,4+1+13+3,3+2+1,3+1+1+12+

7、2+2,2+2+1+1,2+1+1+1+11+1+1+1+1+1根据例子发现“包括第一行以后的数据不超过6，包括第二行的数据不超过5，……，第六行的数据不超过1”。因此，定义一个函数Q(n,m)，表示整数n的“任何被加数都不超过m”的分划的数目，n的所有分划的数目P(n)=Q(n,n)。模型建立：一般地Q(n.m)有以下递归关系：1)Q(n,n)=1+Q(n,n-1)（m=n）Q(n,n-1)表示n的所有其他分划，即最大被加数m<=n-1的划分。2)Q(n,m)=Q(n,m-1)+Q(n-m,m)(m

8、示被加数中不包含m的分划的数目；Q(n-m,m)表示被加数中包含(注意不是小于)m的分划的数目，递归的停止条件：1)Q(n,1)=1，表示当最大的被加数是1时，该整数n只有一种分划，即n个1相加；2)Q(1,m)=1，表示整数n=1只有一个分划，不管最大被加数的上限m是多大。算法如下：Di