《计算机常用算法与程序设计教程 第3章 递归与分治.ppt》由会员分享，可在线阅读，更多相关《计算机常用算法与程序设计教程 第3章 递归与分治.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计3.1 递归及其应用递归及其应用 3.2 分治法概述分治法概述 3.3 分治法的基本应用分治法的基本应用 3.4 消除递归消除递归 2常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计3.1 递归及其应用递归及其应用3.1.1 递归与递归调用递归与递归调用 一个函数在它的函数体内调用它自身称为递归(recursion)调用。使用递归要注意以下几点：(1)递归就是在过程或函数里调用自身；(2)在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口递归和分治是相统一的，递归算法中含有分治思想，分
2、治算法中也常用递归算法。3常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计例如有函数r如下：int r(int a)b=r(a-1);return b;这个函数是一个递归函数。但是运行该函数将无休止地调用其自身，这显然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。4常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计3.1.2 递归应用递归应用【例3.1】用递归法计算n!。分析 n!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解
3、。步骤1 描述递归关系 递归关系是这样的一种关系。设U1,U2,U3,Un是一个序列，如果从某一项k开始，Un和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。注意到，当n=1时，n!=n*(n-1)!（n=0时，0!=1），这就是一种递归关系。对于特定的k!，它只与k与(k-1)!有关。步骤2 确定递归边界 在步骤1的递归关系中，对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。5常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计确定递归边界
4、十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序：#include int f(int x)return(f(x-1);main()printf(f(5);它没有规定递归边界，运行时将无限循环，会导致错误。步骤3 写出递归函数并译为代码 将步骤1和步骤2中的递归关系与边界统一起来用数学语言来表示，即 n*(n-1)!当n=1时n!=1 当n=0时再将这种关系翻译为代码，即一个函数：long ff(int n)long f;if(n0)printf(n0,input error);else if(n=0|n=1)f=1;else f=ff(n-1)*n;return(
5、f);6常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计步骤4 完善程序 主要的递归函数已经完成，将程序依题意补充完整即可。#include long ff(int n)long f;if(n0)printf(n0,input error);else if(n=0|n=1)f=1;else f=ff(n-1)*n;return(f);void main()int n;long y;printf(n input a integer number:n);scanf(%d,&n);y=ff(n);printf(%d!=%ld,n,y);7常用算法与程序设计常用算法与程序设计常
6、用算法与程序设计常用算法与程序设计3.2 分治法概述分治法概述3.2.1 分治法基本思想分治法基本思想 在算法设计中，首先对求解问题进行系统的分析，之后将其分解成若干性质相同的子问题，所得结果称为求解子集，再对这些求解子集分别处理。如果某些子集还需分而治之，再递归的使用上述方法，直到求解子集不需要再细分为止。最后归并子集的解即得原问题的解。8常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计9常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计因而对分治法算法设计过程可以如下描述：设原问题输入为an，简记为(1，n)；子问题为apaq，1pqn，简记为
7、(p，q)。已知：SOLUTION;int divide(int,int);int small(int,int);SOLUTION conquer(int,int);SOLUTION combine(SOLUTION,SOLUTION);10常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计分治法的抽象控制算法为：SOLUTION DandC(p,q)/*divide and conquer*/if(small(p,q)return conquer(p,q);else m=divide(p,q);return combine(DandC(p,m),DandC(m+1,q)
8、;11常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计3.2.2 分治算法设计方法和特点分治算法设计方法和特点分治算法设计的两个基本特征：(1)分治法求解子集是规模相同、求解过程相同的实际问题的分解。(2)求解过程反复使用相同的求解子集来实现的，这种过程可以使用递归函数来实现算法，也可以使用循环。用分治法设计出来的程序一般是一个递归算法，因而例3.4中是用递归来来实现的。12常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计【例3.4】在含有n个不同元素的集合an中同时找出它的最大和最小元素。不妨设。对求n个数的最大和最小，可以设计出许多种算法，这
9、里使用分治法设计求解。1.直接搜索 StraitSearch(n,&max,&min)*max=*min=a0;for(i=1;i*max)*max=ai;if(ai*max)*max=ai;else if(ai*min)*min=ai;则有：最好情况比较次数：n-1最坏情况比较次数：2(n-1)平均情况比较次数：3/2(n-1)13常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计2.分治法集合只有一个元素时：*max=*min=ai；集合只有两个元素时：if(aiaj)*max=aj;*min=ai;else *max=ai;*min=aj;集合中有更多元素时：将原集
10、合分解成两个子集,分别求两个子集的最大和最小元素,再合并结果。算法如下：typedef struct ElemType max;ElemType min;SOLUTION;SOLUTION MaxMin(i,j)SOLUTION s,s1,s2;if(i=j)s.max=s.min=ai;return s;if(i=j-1)if(ai=s2.max)?(s.max=s1.max):(s.max=s2.max);(s1.min=s2.min)?(s.min=s1.min):(s.min=s2.min);return s;输入一组数a=22,10,60,78,45,51,8,36，调用MaxMin
11、函数，划分区间，区间划分将一直进行到只含有1个或2个元素时为止，然后求子解，并返回。15常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计3.3 分治法的基本应用分治法的基本应用3.3.1 数据查找与排序数据查找与排序【例3.5】二分检索：已知n个按非降次序排列的元素an，查找元素x是否在表中出现，若找到，返回其下标值，否则返回一负数。二分检索是数据查找中典型使用分治法的实例 16常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计原问题:(n,a0,an-1,x)数据分组:a0ak-2 ak-1 akan-1三个子问题:(k-1,a0,ak-2,x)
12、(1,ak-1,x)(n-k,ak,an-1,x)17常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计递归算法 int BinSearch1(p,q,x)int k=(p+q)/2;if(qp)return 1;/*参数错误*/if(x=ak)return k;if(xak)return BinSearch1(k+1,q,x);18常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计二元比较树l 左子树上所有元素不比父节点元素值大l 以有序表的中间元素为根节点的二分树l 右子树上所有元素不比父节点元素值小19常用算法与程序设计常用算法与程序设计常用算
13、法与程序设计常用算法与程序设计内节点内节点:成功检索外节点外节点:不成功检索 二分检索树的深度二分检索树的深度二元比较树的深度二元比较树的深度 20常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计3.3.2 计数逆序排名问题计数逆序排名问题一个核心问题是对两个排名进行比较的问题。你对一组n个电影排名，然后一个协同过滤系统向他的数据库咨询来找有着“类似”排名的其他人。但是从数量上说什么嗜好的方式来度量两个人的排名由多相似呢？显然一个相等的排名是非常相似的，一个完全相反的排名是非常不同的；我们想要的是介于整个中间区域的东西。21常用算法与程序设计常用算法与程序设计常用算法与
14、程序设计常用算法与程序设计先放下这个定义，考虑一个例子，其中的序列是1，4，1，3，5.在这个序列中有三个逆序：（2，1），（4，1），（4，3）。也存在一个几何方法把它形象化，如图3.6所示。我们把输入数的序列按照它们被提供的次序画出来，而下面的序列处于上升次序。然后我们在顶部表格中的每个数与下面表各种相同的数之间划一条线段。每对交叉线段于在两个表格中相反次序的一对数即一个逆序对应。22常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计注意逆序个数怎样作为一个度量使得他平滑的介于完全一致（当序列是上升的次序，那么没有逆序）与完全不一致（如果序列是下降的次序，那么每对数构
15、成一个逆竖，并且因此存在个序列）之间。23常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计3.3.3 投资问题投资问题有一个高计算的投资公司咨询员，有下面类型的问题想要一次又一次的求解，这个问题的一个典型实例如下所述。他们正在做一项模拟，在这项模拟中他们从过去的某点开始对一支给定的股票连续看天，让我们把这些天的纪录为数；对每天，他们有当天这支股票每股的价格（为简单起见，假设这个价格在每一天之内是固定的）。假设在这个时间区间内，某天他们想买1000股并且在以后的某天卖出所有的这支股。他们想知道：为了挣到最多的钱，他们应该什么时候买并且应该什么时候卖？24常用算法与程序设计
16、常用算法与程序设计常用算法与程序设计常用算法与程序设计举例，假设那么你应该返回“2买，3卖”。通过分治策略我们可以把在元素对上的蛮力搜索减少到时间。这里由于面对的是类似情况，让我们考虑可以怎样应用分治策略。25常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计一种简单的方法将是分别考虑前天和后天，对这两个集合中的每一个问题递归的求解，然后指出怎样从这些用时间得到一个全局的解。这将给出常用的递推式，因此得到。此外，为了使得事情更容易，将使用n是2的幂，这个通常的假定，这并不减少一般性：如果是比n大的下一个2的幂，我们可以对在n与之间的所有i，令，以这种方式，我们不用改变答案
17、，至多使输入的规模加倍。26常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计3.4 消除递归3.4.1消除递归递归算法的特点l 符合人的递推求解问题的自然思维习惯l 算法的结构简单，代码精炼，可读性好l 效率低27常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计消除递归的一般步骤 例例1：写一个递归函数 reverse(char*s)，按逆序输出一个字符串，并将此递归算法改写成相应的迭代算法。28常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计递归算法 void reverse(char*s)if(*s!=0)revers
18、e(s+1);putchar(*s);return;29常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计输出s=”abc”的递归过程进入递归调用,top=0递归调用返回,top=6顺序条件栈中元素top=,s=顺序条件addr,s 1*s=astack1=s,(a)stack2=L2,(putchar)2,s+11top=6addr=stack6s=stack52*s=bstack3=s,(b)stack4=L2,(putchar)4,s+22top=4addr=stack4s=stack33*s=cstack5=s,(c)stack6=L2,(putchar)6,s+
19、33top=2addr=stack2s=stack14*s=0调用结束，转返回处理4top=0完全返回30常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计改写的迭代算法 void reverse(char*s)extern ElemType stack2*n+1,top=0;L1:if(*s!=0)stack+top=s;stack+top=L2;s=s+1;goto L1;L2:putchar(*s);/接下来处理返回语句 if(top=0)return;/栈为空 else addr=stacktop-;/恢复地址 s=stacktop-;/恢复参数 if(addr=
20、L2)goto L2;31常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计优化后的迭代算法 void reverse(char*s)int top=0;while(*s!=0)top+;s+;while(top!=0)putchar(*s);s-;top-;32常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 例2：写一个求数组an中的最大元素的递归算法并将其改写成迭代算法。分治的思路递归：ai ai+1 an-1int max(int i)int j=i,k;if(iaj)k=i;else k=j;else k=n-1;return k;33常
21、用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计(0)开始，照搬（所有不涉及递归调用和返回语句的代码都照搬）(1)定义和初始化堆栈(存储参数、局部变量、返回值和返址).int max(int i)extern stack4*n+1,top=0;int j=i,k;(2)对第一条可执行语句定义标号L1,每次递归调用执行步骤(3).(3)将所有参数和局部变量进栈.(4)建立第i个返回地址的标号Li，进栈.(5)计算本次递归调用实参的值，并赋给形参变量.(6)无条件转移到L1进入递归.(7)如果是带返回值的调用，从栈顶取回返回值并代替调用，其余代码按原方式处理，并将(4)建立的
22、标号附于该语句；如果是不带返回值的调用，则将(4)建立的标号直接附于(6)对应的语句之后的那条语句.L1:if(in-1)stack+top=i;stack+top=j;stack+top=L2;i=i+1;goto L1；L2:j=stacktop-;if(ai=i;j-)if(ajak)k=j;return k;36常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计3.4.2 分治算法中的递归转化分治算法中的递归转化抽象控制递归算法：SOLUTION DandC(p,q)/*divide and conquer*/int m;SOLUTION s1,s2,s;if(s
23、mall(p,q)s=conquer(p,q);else m=divide(p,q);s1=DandC(p,m);s2=DandC(m+1,q);s=combine(s1,s2);return s;37常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计抽象控制迭代算法：SOLUTION DandC(p,q)extern ElemType stack5*n+1,top=0;int m;SOLUTION s1,s2;L1:if(small(p,q)s=conquer(p,q);else m=divide(p,q);stack+top=p;stack+top=q;stack+t
24、op=m;stack+top=L2;p=p;q=m;goto L1;L2:s1=stacktop-;stack+top=p;stack+top=q;stack+top=m;stack+top=L3;p=m+1;q=q;goto L1;L3:s2=stacktop-;s=combine(s1,s2);if(top=0)return s；else addr=stacktop-;m=stacktop-;q=stacktop-;p=stacktop-;stack+top=s;if(addr=L2)goto L2;else goto L3;38常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计