第八章数据结构与算法算法篇PPT讲稿.ppt

《第八章数据结构与算法算法篇PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第八章数据结构与算法算法篇PPT讲稿.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章数据结构与算法算法篇第1页，共54页，编辑于2022年，星期三一、算法概述算法的概念算法的特征算法的表示算法的复杂性第2页，共54页，编辑于2022年，星期三1、算法概念：、算法概念：是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。第3页，共54页，编辑于2022年，星期三2、算法特征、算法特征一个算法应该具有以下五个重要的特征：1.1.有穷性：有穷性：一个算法必须保证执行有限步之后结束；2.2.确切性：确切性：算法的每一步骤必须有确切的定义

2、；3.3.输入：输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；4.4.输出：输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；5.5.可行性：可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。第4页，共54页，编辑于2022年，星期三3、算法表示、算法表示文字描述用纯粹的文件描述一个算法。优点较易理解，缺点是难于用计算机语言实现。程序流程图用图形的方式描述算法过程。优点是较为直观，缺点与具体语言相关，编写代码不易。程序源代码写出的算法。优点是能直接运行，缺点是难于阅读。伪语言用类

3、似程序语言的风格写出算法，克服了上述各种方法的缺点。第5页，共54页，编辑于2022年，星期三3、算法的复杂性（算法效率）、算法的复杂性（算法效率）时间上即描述算法在执行中的运行效率，原则上要求算法尽可能地少花时间，即在短时间内得到结果，一个算法的时间效率与该算法处理的问题的规模及算法程序中的循环与递归的量有关。一般而言，规模越大，处理所花的时间就越长；算法中循环与递归越多，效率就成指数级下降。空间上即算法在运行中消耗的存储容量。原则上要求算法尽可能地少占用存储单元。时空上，程序算法是一个矛盾的对立统一。一般来说，两者成反比。有时是以空间换效率，有时用牺牲效率换空间，视具体情形而言第6页，共5

4、4页，编辑于2022年，星期三二、程序流程图NS盒图PAD图程序流程图ER图第7页，共54页，编辑于2022年，星期三1、NS盒图盒图N-S图也被称为盒图或CHAPIN图。流程图流程图由一些特定意义的图形、流程线及简要的文字说明构成，它能清晰明确地表示程序的运行过程。在使用过程中，人们发现流程线不一定是必需的，为此，人们设计了一种新的流程图，它把整个程序写在一个大框图内，这个大框图由若干个小的基本框图构成，这种流程图简称N-S图.第8页，共54页，编辑于2022年，星期三N-S图结构图结构1.顺序结构N-S图2.选择结构N-S图AB条件真假A块B块3.循环结构N-S图1)当型循环2)直到型循环

5、循环体当条件为真时循环体直到条件为真时第9页，共54页，编辑于2022年，星期三PAD图PAD是问题分析图（ProblemAnalysisDiagram）的英文缩写，自1973年由日本日立公司发明以来，已经得到一定程度的推广。它用二维数形结构的图表示程序的控制流，将这种图转换为程序代码比较容易。第10页，共54页，编辑于2022年，星期三第11页，共54页，编辑于2022年，星期三程序流程图 1程序流程图的作用程序流程图是人们对解决问题的方法、思路或算法的一种描述。2流程图采用的符号（1）起始框（2）终止框（3）执行框（4）判别框（5）进程框（6）数据框主要元素：（1）方框：表示一个处理步骤（

6、2）菱形框：表示一个逻辑条件（3）箭头：表示控制流向第12页，共54页，编辑于2022年，星期三第13页，共54页，编辑于2022年，星期三E-R图即实体-联系图(EntityRelationshipDiagram)，提供了表示实体型、属性和联系的方法，用来描述现实世界的概念模型。构成E-R图的基本要素是实体型、属性和联系，其表示方法为：实体型(Entity)：用矩形表示，矩形框内写明实体名；比如学生张三丰、学生李寻欢都是实体。如果是弱实体的话，在矩形外面再套实线矩形。属性(Attribute)：用椭圆形表示，并用无向边将其与相应的实体连接起来；比如学生的姓名、学号、性别、都是属性。如果是多值

7、属性的话，再椭圆形外面再套实线椭圆。如果是派生属性则用虚线椭圆表示。联系(Relationship)：用菱形表示，菱形框内写明联系名，并用无向边分别与有关实体连接起来，同时在无向边旁标上联系的类型（1:1，1:n或m:n）。比如老师给学生授课存在授课关系，学生选课存在选课关系。如果是弱实体的联系则在菱形外面再套菱形。第14页，共54页，编辑于2022年，星期三第15页，共54页，编辑于2022年，星期三三、程序算法要使计算机能完成人们预定 的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数 据结构和变

8、量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法，数据结构是程序的两个重算法，数据结构是程序的两个重要方面要方面。算法是问题求解过程的精确描述算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。第16页，共54页，编辑

9、于2022年，星期三主要算法：迭代法穷举搜索法递推法贪婪法回溯法分治法动态规划法etc第17页，共54页，编辑于2022年，星期三1、迭代法迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：（1）选一个方程的近似根，赋给变量x0；（2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；（3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。第18页，共54页，编辑于2022年

10、，星期三【算法】迭代法求方程的根 x0=初始近似根；do x1=x0；x0=g(x1)；/*按特定的方程计算新的近似根*/while(fabs(x0-x1)Epsilon)；printf(“方程的近似根是%fn”，x0)；第19页，共54页，编辑于2022年，星期三2、穷举搜索法穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。【问题】将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六个变量分别取1，6上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。程 序引入变量a、b、c、d、e、f，并让它们

11、分别顺序取1至6的证书，在它们互不相同的条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否 相等，如相等即为一种满足要求的排列，把它们输出。当这些变量取尽所有的组合后，程序就可得到全部可能的解。细节见下面的程序。第20页，共54页，编辑于2022年，星期三【程序1】#includevoid main()int a,b,c,d,e,f;for(a=1;a=6;a+)for(b=1;b=6;b+)if(b=a)continue;for(c=1;c=6;c+)if(c=a)|(c=b)continue;for(d=1;d=6;d+)if(d=a)|(d=b)|(d=c)continue;

12、for(e=1;e=6;e+)if(e=a)|(e=b)|(e=c)|(e=d)continue;f=21-(a+b+c+d+e);if(a+b+c=c+d+e)&(a+b+c=e+f+a)printf(“%6d,a);printf(“%4d%4d”,b,f);printf(“%2d%4d%4d”,c,d,e);scanf(“%*c”);第21页，共54页，编辑于2022年，星期三3、递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造 算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问

13、题的递推性质，能从已求得的规模为1，2，i-1的一系列解，构造出问题规模为 I的解。这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。第22页，共54页，编辑于2022年，星期三【问题】阶乘计算问题描述：编写程序，对给定的n（n100），计算并输出k的阶乘k！（k=1，2，n）的全部有效数字。由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整数，存储长整数数组的每个元素只存储长整数的一位数字。如有m位成整数N用数组a 存储：N=am10m-1+am-110m-2+a2101+a1100并用a0存储长整数N的位数m，

14、即a0=m。按上述约定，数组的每个元素存储k的阶乘k！的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素。例如，5！=120，在数组中的存储形式为：3 0 2 1 首元素3表示长整数是一个3位数，接着是低位到高位依次是0、2、1，表示成整数120。计算阶乘k！可采用对已求得的阶乘(k-1)！连续累加k-1次后求得。例如，已知4！=24，计算5！，可对原来的24累加4次24后得到120。第23页，共54页，编辑于2022年，星期三#include#include#define MAXN 1000void pnext(int a,int k)int*b,m=a0,i,j,r,carry

15、;b=(int*)malloc(sizeof(int)*(m+1);for(i=1;i=m;i+)bi=ai;for(j=1;j=k;j+)for(carry=0,i=1;i0;i)printf(“%d”,ai);printf(“nn”);void main()int aMAXN,n,k;printf(“Enter the number n:“);scanf(“%d”,&n);a0=1;a1=1;write(a,1);for(k=2;k1时）。写成递归函数有：int fib(int n)if(n=0)return 0;if(n=1)return 1;if(n1)return fib(n-1)+

16、fib(n-2);递 归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如上例中，求 解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分 别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。在回归阶段，当获得最简单情况的解后，逐级返回，依次得

17、到稍复杂问题的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。第26页，共54页，编辑于2022年，星期三5、回溯法回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个 候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的 所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程

18、称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前 试探。第27页，共54页，编辑于2022年，星期三1）、回溯法的一般描述可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，xn）组成的一个状态空间 E=（x1，x2，xn）xiSi，i=1，2，n，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且|Si|有限，i=1，2，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但

19、显然，其计算量是相当大的。我 们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，xi）满足D中仅涉及到x1，x2，xi的所有约束意味着j（jj。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，xj）违反D中仅涉及x1，x2，xj的一个约束，就可以 肯定，以（x1，x2，xj）为前缀的任何n元组（x1，x2，xj，xj+1，xn）都不会是问题P的解，因而就不必去搜索它们、检测它 们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。第28页，共54页，编辑于2022年，星期三回溯法首先将问题P的n元组的状态空间E表示成

20、一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造：设Si 中的元素可排成xi(1)，xi(2)，xi(mi-1)，|Si|=mi，i=1，2，n。从根开始，让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权xi+1(1)，xi+1(2)，xi+1(mi)，i=0，1，2，n-1。照这种构造方式，E中的一个n元组（x1，x2，xn）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次 的n条边的权分别为x1，x2，xn，反之亦然。另外，对于任意的0in-1，E中n元组（x1，x2

21、，xn）的一个前缀I元组（x1，x2，xi）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为x1，x2，xi，反之亦然。特别，E中的任意 一个n元组的空前缀（），对应于T的根。因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的 n条边相应带的n个权x1，x2，xn满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深 入，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1，x2）、，前缀I元组（x1，x2，xi），直到i=n为止。第29页，共54页，编辑于

22、2022年，星期三在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。【问题】组合问题问题描述：找出从自然数1、2、n中任取r个数的所有组合。例如n=5，r=3的所有组合为：（1）1、2、3（2）1、2、4（3）1、2、5（4）1、3、4（5）1、3、5（6）1、4、5（7）2、3、4（8）2、3、5（9）2、4、5（10）3、4、5则该问题的状态空间为：E=（x1，x2，x3）xiS，i=1，2，3

23、 其中：S=1，2，3，4，5约束集为：x1显然该约束集具有完备性。第30页，共54页，编辑于2022年，星期三2）、回溯法的方法对于具有完备约束集D的一般问题P及其相应的状态空间树T，利用T的层次结构和D的完备性，在T中搜索问题P的所有解的回溯法可以形象地描述为：从T 的根出发，按深度优先的策略，系统地搜索以其为根的子树中可能包含着回答结点的所有状态结点，而跳过对肯定不含回答结点的所有子树的搜索，以提高搜索效 率。具体地说，当搜索按深度优先策略到达一个满足D中所有有关约束的状态结点时，即“激活”该状态结点，以便继续往深层搜索；否则跳过对以该状态结点为根 的子树的搜索，而一边逐层地向该状态结点

24、的祖先结点回溯，一边“杀死”其儿子结点已被搜索遍的祖先结点，直到遇到其儿子结点未被搜索遍的祖先结点，即转向 其未被搜索的一个儿子结点继续搜索。第31页，共54页，编辑于2022年，星期三在搜索过程中，只要所激活的状态结点又满足终结条件，那么它就是回答结点，应该把它输出或保存。由于在回溯法求解问题时，一般要求出问题的所有解，因此在得到回答结点后，同时也要进行回溯，以便得到问题的其他解，直至回溯到T的根且根的所有儿子结点均已被搜索过为止。例 如在组合问题中，从T的根出发深度优先遍历该树。当遍历到结点（1，2）时，虽然它满足约束条件，但还不是回答结点，则应继续深度遍历；当遍历到叶子结点（1，2，5）

25、时，由于它已是一个回答结点，则保存（或输出）该结点，并回溯到其双亲结点，继续深度遍历；当遍历到结点（1，5）时，由于它已是叶子结 点，但不满足约束条件，故也需回溯。第32页，共54页，编辑于2022年，星期三3、回溯法的一般流程和技术在用回溯法求解有关问题的过程中，一般是一边建树，一边遍历该树。在回溯法中我们一般采用非递归方法。下面，我们给出回溯法的非递归算法的一般流程：在用回溯法求解问题，也即在遍历状态空间树的过程中，如果采用非递归方法，则我们一般要用到栈的数据结构。这时，不仅可以用栈来表示正在遍历的树的结点，而且可以很方便地表示建立孩子结点和回溯过程。例 如在组合问题中，我们用一个一维数组

26、Stack 表示栈。开始栈空，则表示了树的根结点。如果元素1进栈，则表示建立并遍历（1）结点；这时如果元素2进栈，则表示建立并遍历（1，2）结点；元素3再 进栈，则表示建立并遍历（1，2，3）结点。这时可以判断它满足所有约束条件，是问题的一个解，输出（或保存）。这时只要栈顶元素（3）出栈，即表示从结 点（1，2，3）回溯到结点（1，2）。第33页，共54页，编辑于2022年，星期三【问题】组合问题问题描述：找出从自然数1，2，n中任取r个数的所有组合。采用回溯法找问题的解，将找到的组合以从小到大顺序存于a0，a1，ar-1中，组合的元素满足以下性质：（1）ai+1ai，后一个数字比前一个大；（

27、2）ai-i=n-r+1。按回溯法的思想，找解过程可以叙述如下：首 先放弃组合数个数为r的条件，候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件（1），候选组合 改为1，2。继续这一过程，得到候选组合1，2，3。该候选解满足包括问题规模在内的全部条件，因而是一个解。在该解的基础上，选下一个候选解，因a 2上的3调整为4，以及以后调整为5都满足问题的全部要求，得到解1，2，4和1，2，5。由于对5不能再作调整，就要从a2回溯到a1，这 时，a1=2，可以调整为3，并向前试探，得到解1，3，4。重复上述向前试探和向后回溯，直至要从a0再回溯时，说

28、明已经找完问题的全部解。第34页，共54页，编辑于2022年，星期三【程序】#define MAXN 100int aMAXN;void comb(int m,int r)int i,j;i=0;ai=1;do if(ai-ivno=i;for(j=box_h;j!=NULL;j=j-next)if(j-remainder=a)break;if(j=NULL)j=(HNODE*)malloc(sizeof(HNODE);j-remainder=box_volume-a;j-head=NULL;if(box_h=NULL)box_h=box_t=j;else box_t=boix_t-next=

29、j;j-next=NULL;box_count+;else j-remainder-=a;第40页，共54页，编辑于2022年，星期三for(q=j-next;q!=NULL&q-link!=NULL;q=q-link);if(q=NULL)p-link=j-head;j-head=p;else p-link=NULL;q-link=p;printf(“共使用了%d只箱子”，box_count);printf(“各箱子装物品情况如下：”);for(j=box_h,i=1;j!=NULL;j=j-next,i+)printf(“第%2d只箱子，还剩余容积%4d，所装物品有；n”,I,j-rema

30、inder);for(p=j-head;p!=NULL;p=p-link)printf(“%4d”,p-vno+1);printf(“n”);第41页，共54页，编辑于2022年，星期三七、分治法 1、分治法的基本思想任 何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问 题，当n=1时，不需任何计算；n=2时，只要作一次比较即可排好序；n=3时只要作3次比较即可，。而当n较大时，问题就不那么容易处理了。要想直接 解决一个规模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的大问题

31、，分割成一些规模较小的相同问题，以便各个击破，分而治之。第42页，共54页，编辑于2022年，星期三2、分治法的适用条件分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。上 述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以 满足的，此特征反映了递归

32、思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三 条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。第43页，共54页，编辑于2022年，星期三3、分治法的基本步骤分治法在每一层递归上都有三个步骤：（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；（3）合并：将各个子问题的解合并为原问题

33、的解。它的一般的算法设计模式如下：Divide_and_Conquer（P）if|P|n0then return（ADHOC（P）将P分解为较小的子问题P1、P2、Pkfor i1 to kdoyi Divide-and-Conquer（Pi）递归解决PiT MERGE（y1，y2，yk）合并子问题Return（T）第44页，共54页，编辑于2022年，星期三【问题】大整数乘法问题描述：通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理，即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。这 个假定仅在计算机硬件能对参加运算的整数直接表示和

34、处理时才是合理的。然而，在某些情况下，我们要处理很大的整数，它无法在计算机硬件能直接表示的范围内 进行处理。若用浮点数来表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数 上的数字，就必须用软件的方法来实现大整数的算术运算。请设计一个有效的算法，可以进行两个n位大整数的乘法运算。设X和Y都是n位的二 进制整数，现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。如果将每2个1位 数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积XY。下

35、面我们用分治法来设计一个更有效的大整数乘积算法。第45页，共54页，编辑于2022年，星期三function MULT(X，Y，n);X和Y为2个小于2n的整数，返回结果为X和Y的乘积XYbeginS=SIGN(X)*SIGN(Y);S为X和Y的符号乘积X=ABS(X);Y=ABS(Y);X和Y分别取绝对值if n=1 thenif(X=1)and(Y=1)then return(S)else return(0)else beginA=X的左边n/2位;B=X的右边n/2位;C=Y的左边n/2位;D=Y的右边n/2位;ml=MULT(A,C,n/2);m2=MULT(A-B,D-C,n/2);

36、m3=MULT(B,D,n/2);S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);return(S);end;end;第46页，共54页，编辑于2022年，星期三八、动态规划法 经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。以下先用实例说明动态规划方法的使用。第47页，共54页，编辑于2022年，星期三【问题】求两

37、字符序列的最长公共字符子序列问 题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，xm-1”，序列Y=“y0，y1，yk-1”是X的子序列，存在X的一个严格递增下标序列，使得对所有的j=0，1，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。第48页，共54页，编辑于2022年，星期三如采用列举A的所有子序列，并一一检查其是否又是B的子序

38、列，并随时记录所发现的子序列，最终求出最长公共子序列。这种方法因耗时太多而不可取。考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，am-1”，B=“b0，b1，bm-1”，并Z=“z0，z1，zk-1”为它们的最长公共子序列。不难证明有以下性质：（1）如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，zk-2”是“a0，a1，am-2”和“b0，b1，bn-2”的一个最长公共子序列；（2）如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，zk-1”是“a0，a1，am-2”和“b0，b1，bn-1”的一个最长公共子序列；（3）如果am-1!

39、=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，zk-1”是“a0，a1，am-1”和“b0，b1，bn-2”的一个最长公共子序列。这 样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，am-2”和“b0，b1，bm-2”的一个 最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，am-2”和“b0，b1，bn-1”的一个最长公共子序列 和找出“a0，a1，am-1”和“b0，b1，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。第49页，共54页，编辑于2022年，星期三定义cij为序

40、列“a0，a1，ai-2”和“b0，b1，bj-1”的最长公共子序列的长度，计算cij可递归地表述如下：（1）cij=0 如果i=0或j=0；（2）cij=ci-1j-1+1 如果I，j0，且ai-1=bj-1；（3）cij=max（cij-1，ci-1j）如果I，j0，且ai-1!=bj-1。按此算式可写出计算两个序列的最长公共子序列的长度函数。由于cij的产生仅依赖于ci-1j-1、ci-1j和cij-1，故可以从cmn开始，跟踪cij的产生过程，逆向构造出最长公共子序列。第50页，共54页，编辑于2022年，星期三#include#include#define N 100char aN,

41、bN,strN;int lcs_len(char*a,char*b,int c N)int m=strlen(a),n=strlen(b),i,j;for(i=0;i=m;i+)ci0=0;for(i=0;i=n;i+)c0i=0;for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;elsecij=cij-1;return cmn;char*buile_lcs(char s,char*a,char*b)int k,i=strlen(a),j=strlen(b);k=lcs_len(a,b,c);sk=0;while(k0)if(cij=ci-1j)i;else i

42、f(cij=cij-1)j;else s-k=ai-1;i;j;return s;void main()printf(“Enter two string（%d）!n”,N);scanf(“%s%s”,a,b);printf(“LCS=%sn”,build_lcs(str,a,b);第51页，共54页，编辑于2022年，星期三第52页，共54页，编辑于2022年，星期三习题：1、汽车加油问题：设有路程长度为L公里的公路上，分布着m个加油站，它们的位置分别为pi（i=1，2，m），而汽车油箱加满油后（油箱最多可以加油k升），可以行驶n公里。设计一个方案，使汽车经过此公路的加油次数尽量少（汽车出发时

43、是加满油的）。2、最短路径：设有一个网络，要求从某个顶点出发到其他顶点的最短路径3、跳马问题：在8*8方格的棋盘上，从任意指定的方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。4、二叉树的遍历5、背包问题6、用分治法实现两个大整数相乘第53页，共54页，编辑于2022年，星期三7、设x1，x2，xn是直线上的n个点，若要用单位长度的闭区间去覆盖这n个点，至少需要多少个这样的单位闭区间？8、用关系“”和“”将3个数A、B和C依次排列时，有13种不同的序关系：ABC，ABC，ABC，ABC，ACB，ACB，BAC，BAC，BCA，BCA，CAB，CAB，CAB。若要将n个数依序进行排列，试设计一个动态规划算法，计算出有多少钟不同的序关系。第54页，共54页，编辑于2022年，星期三