东北大学数据结构期末复习ppt课件.ppt

火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去期末复习期末复习火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去题型题型选择题（选择题（10分）分）填空题（填空题（10分）分）算法应用题（算法填空，简单问题回答）算法应用题（算法填空，简单问题回答）（3-4个题，个题，35-40分）分）算法设计（按照已知条件设计算法或为算算法设计（按照已知条件设计算法或为算法补充完整）（法补充完整）（3个题，个题，45-50分）分）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去第第1章章算法的性质及其与程序的区别算法的性质及其与程序的区别算法复杂性分析算法复杂性分析渐进意义下的四种记号渐进意义下的四种记号简单的程序段的复杂度分析简单的程序段的复杂度分析火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去算法的五个重要特征输入输入 有有零个或多个零个或多个由外部提供的量作为算法的输入由外部提供的量作为算法的输入输出输出 算法产生算法产生至少一个量至少一个量作为输出作为输出.确定性确定性 组成算法的每条指令是清晰的组成算法的每条指令是清晰的,无歧义的无歧义的.有限性有限性 在执行了有穷步骤后运算终止在执行了有穷步骤后运算终止可行性可行性 运算都是基本运算，原理上能在有限时间内完成。运算都是基本运算，原理上能在有限时间内完成。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去渐进意义下的记号：O,f(N)和和g(N)是定义在正整数上的正函数是定义在正整数上的正函数定义定义1.1 1.1 如果存在两个正常数如果存在两个正常数c和和N0,对于所有的对于所有的NN0，有，有f(N)Cg(N)，则记则记作：作：f(N)=O(g(N)。N0f(N)g(N)当说一个算法具有当说一个算法具有O(g(n)的计算时间时，指的的计算时间时，指的就是如果此算法用就是如果此算法用n值不变的同一类数据在某台值不变的同一类数据在某台机器上运行时，所用的时间总是小于机器上运行时，所用的时间总是小于g(n)的一个的一个常数倍。常数倍。g(n)是计算时间是计算时间f(n)的一个上界函数，的一个上界函数，f(n)的数的数量级就是量级就是g(n)火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去符号符号的定义的定义定义定义1.2 如果存在两个正常数如果存在两个正常数C和自然数和自然数N0，使得当使得当N N0时有时有f(N)Cg(N)，则称函数，则称函数f(N)当当N充分大时下有界；且充分大时下有界；且g(N)是它的一个下界，是它的一个下界，记为记为f(N)=(g(N)。这时我们说。这时我们说f(N)的阶不低的阶不低于于g(N)的阶。的阶。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去，o 的定义 定义定义f(N)=(g(N)当且仅当当且仅当f(N)=O(g(N)且且f(N)=(g(N)。这时，我们说。这时，我们说f(N)与与g(N)同阶同阶o 如果对于任意给定的如果对于任意给定的0，都存在正整数，都存在正整数N0，使得当使得当N N0时有时有f(N)/g(N)，则称函数，则称函数f(N)当当N充分大时的阶比充分大时的阶比g(N)低，记为低，记为f(N)=o(g(N)例如：例如：4NlogN+7=o(3N2+4NlogN+7)火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去1.2 算法分析初步多项式时间算法多项式时间算法(polynomial time algorithm):可用多项式可用多项式来对其计算时间限界的来对其计算时间限界的算法算法O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间算法指数时间算法(exponential time algorithm):计算时间用计算时间用指数函数限界的算法指数函数限界的算法O(2n)O(n!)O(nn)火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去作业作业1-7火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去第第2章章 递归递归分治法基本思想分治法基本思想二分搜索算法二分搜索算法Strassen矩阵乘法矩阵乘法合并排序和快速排序合并排序和快速排序火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去递归复杂度分析火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去汉诺塔移动次数M(1)=1M(n)=2M(n-1)+1 =22M(n-2)+1+1 =22M(n-2)+2+1 =23M(n-3)+22+2+1 =2iM(n-i)+2i-1+2i-2+2+1 =2iM(n-i)+2i-1令令i=n-1 则则M(n)=2n-1+2n-1-1=2n-12.1 递归递归火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去分治法的基本思想分治法的基本思想分而治之方法与软件设计的模块化方法非常分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：相似。为了解决一个大的问题，可以：1)把它分成两个或多个更小的问题；把它分成两个或多个更小的问题；2)分别解决每个小问题；分别解决每个小问题；3)把各小问题的解答组合起来，即可得到原把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。可以递归地使用分而治之策略来解决。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去例例2-6 在在9,12,15,27,39中分别查找中分别查找27，12，149 12 15 27 390 1 2 3 4 left right midmid=(left+right)/2=(0+4)/2=2mid=(3+4)/2=39 12 15 27 39leftrightmid查找查找27成功返成功返回回3，leftrightmid9 12 15 27 39leftright火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去template intint BinarySearch(T a,T a,const T&xconst T&x,int nint n)/在在a0=a1=amiddle)left=;else right=;return 1;/未找到未找到xn-1n-10 0left=rightleft1时，时，Tw(n)=Tw(n/2)+1,T(1)=1Tw(n)=Tw(n/2)+1 =Tw(n/4)+1+1 =Tw(1)+1+.+1=1+k=1+logn火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去二分搜索的时间复杂度 最坏情况下的成功检索计算时间最坏情况下的成功检索计算时间(logn)最坏情况下的不成功检索计算时间最坏情况下的不成功检索计算时间(logn)最好情况下的成功检索计算时间最好情况下的成功检索计算时间(1)最好情况下的不成功检索计算时间最好情况下的不成功检索计算时间(logn)每种不成功的检索时间都为每种不成功的检索时间都为(logn)2.2二分搜索技术二分搜索技术火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去作业：1.P34，2-2 中第二个和第中第二个和第五个算法的正确性，错误五个算法的正确性，错误的说明原因或者给出反例的说明原因或者给出反例2.P35,2-3火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去2-3：二分搜索中当程序停止时，左右指针或者指向同一个元素，此时该元素等于待查找元素或者left=right+1，此时right指向的为比待找元素小的元素，left为比待找元素大的元素火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 归并排序主程序伪代码归并排序主程序伪代码templatevoid MergeSort(Type a,int left,int right)/Aleft:right是一个全程数组，含有是一个全程数组，含有 right-left+1个待排个待排序的元素。序的元素。if()/至少有至少有2个元素个元素 int mid=(left+right)/2;/求当前数组的分割点求当前数组的分割点 MergeSort(a，left,mid);MergeSort(a，mid+1,right);Merge(a，b，left,mid,right);copy（a，b，left，right）；）；left right递归调用，分别对分递归调用，分别对分解出来的两个子问题解出来的两个子问题排序排序合并两个排好序的子合并两个排好序的子问题，放入另一个数问题，放入另一个数组组b中中2.4合并排序合并排序火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去考虑数组a的两段为1,7,8,9和2,3,4,51,7,8,92,3,4,51,7,8,92,3,4,511,21,7,8,92,3,4,51,2,31,7,8,92,3,4,51,2,3,41,7,8,92,3,4,51,2,3,4,5数组数组a的两部分的两部分数组数组b1,2,3,4,5,71,2,3,4,5,7,81,2,3,4,5,7,8,9在移动扫描指针的同时，在移动扫描指针的同时，要判断其是否已经到达数要判断其是否已经到达数组的尾部，如到达，则停组的尾部，如到达，则停止扫描，把未参加排序的止扫描，把未参加排序的数全部放入备用数组中数全部放入备用数组中2.4合并排序合并排序火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去合并函数templatevoid Merge(Type a,Type b,int l,int m,int r)/合并合并al:m和和am+1:r到到bl:r int i=l;j=m+1,k=l;while()&()if(a i m)for(int q=j;q=r;q+)b k+=a q;else for(int q=I;q=m;q+)b k+=a q;把把al:m和和am+1:r中的数中的数据进行比较，按顺据进行比较，按顺序放入序放入b中中如果前一段数据如果前一段数据小于后一段的多，小于后一段的多，则先排完，把后则先排完，把后段剩余数赋给段剩余数赋给bn,否则将前段否则将前段数据赋给数据赋给bn前半段指针前半段指针后半段指针后半段指针数组数组b的下标指针的下标指针i=mj=r2.4合并排序合并排序火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去作业分析分析merge函数最好与最坏的键值比较次函数最好与最坏的键值比较次数。数。最好比较最好比较1次次最差比较最差比较m+n-1，m和和n分别为两段数组的长度分别为两段数组的长度火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去快速排序Templatevoid QuickSort(Type a,int p,int r)if(pr)int q=Partition(a,p,r);QuickSort(a,p,q-1);/对左半段排序 QuickSort(a,q+1,r);/对右半段排序 a的起始位的起始位置置A的终止位置的终止位置Partition函数负责将函数负责将a进行一次分割，返回进行一次分割，返回分割元素的位置分割元素的位置快速排序问题快速排序问题火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去划分程序 templateint Partition(Type a,int p,int r)int i=,j=;Type x=;while(true)while(a+i x);if()break;Swap(a i,a j );a p =;a j =;return j;快速排序问题快速排序问题pr+1a p i=ja j x左侧扫描指针起左侧扫描指针起始始右侧扫描指针起右侧扫描指针起始始中轴元素中轴元素移动左侧扫描指移动左侧扫描指针针移动右侧扫描指针移动右侧扫描指针火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去算法分析算法分析最坏情况：划分的两个区域分别包含最坏情况：划分的两个区域分别包含n1个元素和个元素和1个元素，如果每一步都出现这种个元素，如果每一步都出现这种情况，其复杂性情况，其复杂性T(n)O(1)n1 T(n)=T(n-1)+O(n)n1解得：解得：T(n)=O(n2)快速排序问题快速排序问题火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去最好情况最好情况每次划分所取的基准都恰好为中值，即每每次划分所取的基准都恰好为中值，即每次划分都产生两个大小为次划分都产生两个大小为n/2的区域，的区域，O(1)n1 T(n)=2T(n/2)+O(n)n1T(n)=O(nlogn)快速排序问题快速排序问题火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去2-19将算法Partition中的不等号反向火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去第第3章章动态规划思想，基本要素动态规划思想，基本要素矩阵连乘算法及最优解构造矩阵连乘算法及最优解构造0-1背包问题最优值及最优解背包问题最优值及最优解最优二叉搜索树最优二叉搜索树（通过具体实例弄清每个算法的流程及算法（通过具体实例弄清每个算法的流程及算法的具体实现）的具体实现）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去动态规划算法动态规划算法 将待求解的问题分解成若干个子问题，将待求解的问题分解成若干个子问题，先求解子问题，并存储子问题的解先求解子问题，并存储子问题的解而而避免计算重复的子问题避免计算重复的子问题，再由子，再由子问题的解得到原问题的解。问题的解得到原问题的解。算法思想算法思想火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去动态规划算法的基本要素动态规划算法的基本要素1 最优子结构性质最优子结构性质2 重叠子问题性质重叠子问题性质火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去1.最优子结构最优子结构当问题的最优解包含了其子问题的最优解当问题的最优解包含了其子问题的最优解时，称该问题具有时，称该问题具有最优子结构性质最优子结构性质。分析最优子结构性质时，一般假设由问题分析最优子结构性质时，一般假设由问题的最优解导出的子问题不是最优的，然后的最优解导出的子问题不是最优的，然后再设法说明在这个假设下可以构造出一个再设法说明在这个假设下可以构造出一个比原问题更优解更好的解，从而导出矛盾。比原问题更优解更好的解，从而导出矛盾。动态规划算法的基本要素动态规划算法的基本要素火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去2.重叠子问题重叠子问题在用递归算法自顶向下解此问题时，每次在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法对每个题被反复计算多次。动态规划算法对每个问题只解一次，而后将其解保存在一个表问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，用常数时格中，当再次需要解此问题时，用常数时间查看一下结果。因此，用动态规划算法间查看一下结果。因此，用动态规划算法通常只需要多项式时间。通常只需要多项式时间。动态规划算法的基本要素动态规划算法的基本要素火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去动态规划与分治的联系区别动态规划与分治的联系区别都是分解成子问题，由子问题的解得到原都是分解成子问题，由子问题的解得到原问题的解。问题的解。分治中子问题相互独立，而动态规划中子分治中子问题相互独立，而动态规划中子问题互相有联系，且存在重复计算，即存问题互相有联系，且存在重复计算，即存在在重叠子问题重叠子问题。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去动态规划算法设计步骤动态规划算法设计步骤（1）找出最优解的性质，刻画其结构特征）找出最优解的性质，刻画其结构特征（2）递归地定义最优值）递归地定义最优值（3）以自底向上的方式计算出最优值）以自底向上的方式计算出最优值（4）根据计算最优值时得到的信息，构造一）根据计算最优值时得到的信息，构造一个最优解个最优解火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去矩阵连乘问题矩阵连乘问题给定给定n个矩阵个矩阵A1,A2,An，其中，其中Ai 是一个是一个ri-1ri 矩阵矩阵(1in)，即，即AiAi+1是是可乘的，求出可乘的，求出n个矩阵相乘的最优计算个矩阵相乘的最优计算次序，使得计算量最小。次序，使得计算量最小。问题提出问题提出设三个矩阵设三个矩阵A1,A2,A3大小分别为大小分别为10100，1005，550，考虑，考虑(A1(A2 A3),(A1A2)A3的的结果与相乘的次数。结果与相乘的次数。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去最优子结构特征最优子结构特征计算计算A1:n的一个最优次序所包含的计算矩的一个最优次序所包含的计算矩阵子链阵子链A1:k和和Ak+1:n的次序也是最优的的次序也是最优的矩阵连乘积计算次序问题的最优解包含着矩阵连乘积计算次序问题的最优解包含着其子问题的最优解，也就是最优子结构性其子问题的最优解，也就是最优子结构性质。质。矩阵连乘问题矩阵连乘问题考虑考虑A1:k 和和Ak+1:n相乘所需的相乘所需的计算量，计算量，A i:k 和和A k+1:j 相乘呢相乘呢A1:k 的结果为的结果为r0*rk的的矩阵，矩阵，Ak+1:n的结果的结果为为rk*rn的矩阵，则它们的矩阵，则它们相乘的计算量为相乘的计算量为p0*pk*pn火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去2.建立递归关系建立递归关系设计算设计算A i:j 所需的最少次数为所需的最少次数为mij,原问题的最优解原问题的最优解为为m1n。当当 i=j 时，时，A i:j=Ai,m i i =0,i=1,2,n。当当 i j 时时m i j=m i k +m k+1 j +pi-1pkpj k i,i+1,j-1 矩阵连乘问题矩阵连乘问题火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去采用递归方法计算采用递归方法计算int RecurMatrixChain(int i,int,j,int p)if()return 0;int u=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j,p)+pi-1*pi*pj;sij=i;for(int k=i+1;kj;k+)int t=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j,p)+pi-1*pi*pj;if(tu)u=t;sij=k;return u;参加运算矩阵链起始位置参加运算矩阵链起始位置矩阵链终止位置矩阵链终止位置i=j取第一个断开位取第一个断开位置时计算量置时计算量记记录录当当前前断断开开位位置置循环取循环取k的可取的可取断开位置断开位置矩阵连乘问题矩阵连乘问题火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去递归树递归树1411241234134422 342344 11 22 33 441123 12333344223322 33 11 22矩阵连乘问题矩阵连乘问题火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去24223412334411141323矩阵连乘问题矩阵连乘问题3.计算最优值计算最优值火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去3.计算最优值计算最优值置所有只有一个矩阵的矩阵链计算量为置所有只有一个矩阵的矩阵链计算量为0，即，即mii=0，i=1,2,n。通过上一步的结果可以得到所有矩阵链长度为通过上一步的结果可以得到所有矩阵链长度为2的子的子问题的最优计算量。问题的最优计算量。通过上两步的结果可以得到所有矩阵链长度为通过上两步的结果可以得到所有矩阵链长度为3的子的子问题的最优计算量问题的最优计算量 矩阵连乘问题矩阵连乘问题计算计算m i j 时，只用到已计算出的时，只用到已计算出的m i k 和和m k+1 j 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 A1 A2 A3 A4 A5 A6 3035 3515 155 510 1020 2025例例32设要计算矩阵连乘积设要计算矩阵连乘积A1A2A3A4A5A6,其中各矩阵的维数分别为其中各矩阵的维数分别为 1 2 3 4 5 6 1.2.3.4.5.6.00000015750262575010005000 m11+m23+p0p1p3=7875m13=min m12+m33+p0p2p3=157509375118751512543757125105002500537535007875ij火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去3.计算最优值计算最优值void MatrixChain(int p,int n,int*m,int*s)for(int i=1;i=n;i+)mii=;/单个矩阵的计算量单个矩阵的计算量 for(int r=2;r=n;r+)/r为每次循环矩阵链的长度为每次循环矩阵链的长度 for(int i=1;i=;i+)int j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;kj;k+)int t=mik+mk+1j+;if(t mij)mij=t;sij=k;矩阵连乘问题矩阵连乘问题0n r+1取第一个可取第一个可取位置，即取位置，即断开位置为断开位置为i循环取循环取k的可取的可取位置位置pi-1*pk*pj火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去算法复杂度算法复杂度算法算法MatrixChain 的主要计算量取决于程的主要计算量取决于程序中对序中对r,i 和和k 的三重循环，的三重循环，循环体内的计算量为循环体内的计算量为O(1)，三重循环的总，三重循环的总次数是次数是O(n3)，所以，算法的计算时间上界，所以，算法的计算时间上界为为O(n3)。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去4.构造最优解构造最优解上述算法只是明确给出了矩阵最优连乘次上述算法只是明确给出了矩阵最优连乘次序所用的数乘次数序所用的数乘次数m1n，并未明确给出，并未明确给出最优连乘次序，即完全加括号方法。但是最优连乘次序，即完全加括号方法。但是以以sij为元素的为元素的2 维数组却给出了足够的维数组却给出了足够的信息。事实上，信息。事实上，sij=k说明，计算连乘积说明，计算连乘积Ai:j的最佳方式应该在矩阵的最佳方式应该在矩阵Ak 和和Ak+1 之之间断开，即最优加括号方式为间断开，即最优加括号方式为(Ai:k)(Ak+1:j)。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 1 2 3 4 5 610 1 1 3 3 32 0 2 3 3 33 0 3 3 34 0 4 55 0 56 0考虑计算考虑计算A16时的顺序时的顺序S16(A1A3)(A4A6)S13 A1(A2A3)S46(A4A5)A6S11=0 S23=0 A1(A2)(A3)S22=S33=0 S66=0 S45=0(A4)(A5)A6S44=S55=0 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去根据最优值算法构造最优解根据最优值算法构造最优解Void Traceback(int i,int j,int*s)if(i=j)return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout “Multiply A”i “,”sij;cout “and A”(sij+1)“,”j;endl;调用调用Traceback(1,n,s)即可得到即可得到A1:n火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去作业作业 1 当当A1 A2 A3 A4 A5 分别为分别为2025，2510，105，515，1520的矩阵时，填写相应的矩阵时，填写相应的的mij和和sij，并给出最优计算次序。，并给出最优计算次序。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去备忘录方法备忘录方法用一个表格来保存已解决的子问题的答案，用的用一个表格来保存已解决的子问题的答案，用的时候查表即可。时候查表即可。采用的递归方式是采用的递归方式是自顶向下自顶向下，动态规划是，动态规划是自低向自低向上上控制结构与直接递归相同，区别在于备忘录方式控制结构与直接递归相同，区别在于备忘录方式为每个解过的子问题建立备忘录。为每个解过的子问题建立备忘录。初始化为每个子问题的记录存入一个特殊的值，初始化为每个子问题的记录存入一个特殊的值，表示并未求解。在求解过程中，查看相应记录如表示并未求解。在求解过程中，查看相应记录如果是特殊值，表示未求解，否则只要取出该子问果是特殊值，表示未求解，否则只要取出该子问题的解答即可。题的解答即可。动态规划算法的基本要素动态规划算法的基本要素火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去备忘录方法解矩阵乘备忘录方法解矩阵乘int MemoizedMatrixChain(int n,int*m,int*s)for(int i=1;i=n;i+)for(int j=i;j0)return mij;if(i=j)return 0;int u=LookupChain(i,i)+LookupChain(i+1,j)+pi-1*pk*pj;sij=i;for(int k=i+1;kj;k+)int t=LookupChain(i,k)+LookupChain(k+1,j)+pi-1*pk*pj;if(t0，其其价价值值为为vi0，背背包包的的容容量量为为c。问问应应如如何何选选择择装装入入背背包包中中的的物物品品，使使得得装装入入背背包包中中物物品品的的总总价价值值最最大大？要求一组数要求一组数i (i=0 0 或或，i=0 0表表示示物物体体不不放放入入背背包包，i 1表示把表示把物体物体放入背包），放入背包），使得使得 vixi 最大，即将尽量多的价值装入背包。最大，即将尽量多的价值装入背包。1 i n火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去1.最优子结构性质最优子结构性质证明证明0/1 背包问题具有最优子结构性质背包问题具有最优子结构性质即即若若背背包包容容量量为为c时时，(y1,y2,yn)为为待待选选物物品品为为1到到n时时knap(1,n,c)的的最最优优解解，则则(y2,yn)将将是是物物 品品1作作 出出 选选 择择 后后 的的 子子 问问 题题 的的 最最 优优 解解当第一个物品做出决策后，有两种状态当第一个物品做出决策后，有两种状态 y1=0，则背包容量没有影响，则背包容量没有影响，(y2,yn)是是 的最优解的最优解 y1=1，则背包减少，则背包减少w1，价值增长，价值增长v1，(y2,yn)是是 的最优解的最优解x1vixiknap(2,n,c-w1*y1)knap(2,n,c)knap(2,n,c w1)火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去2.递归关系设背包问题的子问题的最优值为设背包问题的子问题的最优值为m(i,j),即即m(i,j)是背是背包容量为包容量为j，可选择物品为，可选择物品为i，i1，,n时的最优时的最优值。值。当选择第当选择第i个物品时，个物品时，。如果不选择第如果不选择第i个物品，则个物品，则 。由问题的最优子结构性质，我们可以建立计算由问题的最优子结构性质，我们可以建立计算m(i,j)的递归式如的递归式如下：下：m(i,j)=m(i+1,j-wi)+vim(i,j)=m(i+1,j)火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去例例:四个物品，背包容积为四个物品，背包容积为5，w4=2,1,3,2，v4=12,10,20,15，求最大价值，求最大价值m1c及选取的物品编号及选取的物品编号43214321050000010 1515 15 151515 2020 3535302537ijx4 X3 X2 X11m15m25所以物品所以物品1被选被选c w1=3,查看查看m23m331j w2=2,查看查看m32=m420查看查看m4201火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去3.算法描述templatevoid Knapsack(Type v,int w,int c,int n,Type*m)int jMax=min(wn-1,c);for(int j=0;j=jMax;j+)/出口出口 m n j =;for(int j=wn;j 1;i-)jMax=min(w i -1,c);for(int j=0;j=jMax;j+)m i j =;for(int j=w i;j=w1)m1c=max(m1c,m2c-w1+v1);0vnm i+1 j m 2 c 初始化初始化mnj只剩下第一个物品只剩下第一个物品时，如果剩余背包时，如果剩余背包容积大于容积大于w1时，时，要进行选择要进行选择火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去m15 m2543214321050000010 1015 15 151515 2020 3535302537ij构造最优解x1=1 c=5-w1=3m23 m33x2=1 c=3-w2=2m32=m42x3=0 c=2m42 0 x4=1火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去构造最优解TemplateVoid Traceback(Type*m,int w,int c,int n,int x)for(int i=1;i2n时，算法需要时，算法需要(n2n)n=3,(w1,w2,w3)=(2,3,4),v1,v2,v3=(1,2,5),c=5火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去3-4 钱币问题火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去3.5 最优二叉搜索树最优二叉搜索树Optimal Binary Search Trees火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去最优二叉搜索树最优二叉搜索树利用动态规划构造对标识符集合利用动态规划构造对标识符集合a1,a2,an的的最优二叉搜索树最优二叉搜索树算法算法包包括括成功检索成功检索和和不成功检索不成功检索）。）。最优二叉搜索树最优二叉搜索树火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去3、最优二叉搜索树问题、最优二叉搜索树问题对于有序集对于有序集S及其存取概率分布及其存取概率分布 （a0,b1,a1,bn,an），在所有表示），在所有表示有序集有序集S的二叉搜索树中找出一棵具有最小的二叉搜索树中找出一棵具有最小平均路长的二叉搜索树。平均路长的二叉搜索树。结点在二叉搜索树中的层次越深，需要比结点在二叉搜索树中的层次越深，需要比较的次数就越多，因此要构造一棵最小二较的次数就越多，因此要构造一棵最小二叉树，一般尽量把搜索概率较高的结点放叉树，一般尽量把搜索概率较高的结点放在较高的层次。在较高的层次。最优二叉搜索树问题最优二叉搜索树问题火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去4、最优子结构性质、最优子结构性质假设选择假设选择 k为树根，则为树根，则 1,2,k-1 和和a0,a1,ak-1 都将位于左子树都将位于左子树 L 上，上，其余结点其余结点(k+1,n 和和 ak,ak+1,an)位于右子树位于右子树 R 上。上。k L R 1,2,k-1 a0,a1,ak-1k+1,n ak,ak+1,an最优子结构性质最优子结构性质火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去4、最优子结构性质、最优子结构性质二叉搜索树二叉搜索树T 的一棵含有顶点的一棵含有顶点xi,xj和叶顶点和叶顶点 (xi-1,xi),(xj,xj+1)的子树可以看作是有序集的子树可以看作是有序集 xi,xj 关于全集为关于全集为 xi-1,xj1 的一棵二叉搜索的一棵二叉搜索树（树（T 自身可以看作是有序集自身可以看作是有序集)。根据。根据S 的存取分布概率，的存取分布概率，在子树的顶点处被搜索到的概率是在子树的顶点处被搜