算法简述加强版

1、算法简述：第一章：1考试分值30%，题型选择、填空占90%，其他以附属形式出现2了解四个渐近阶（ 、）含义，运算，简单判断简单描述如下，设有正函数f(n)和g(n)，I、存在正常数、，使得当n时，有f(n) *g(n) 记为f(n)= (g(n)，函数的 一般上界II、存在正常数、，使得当n时，有f(n) *g(n) 记为f(n)= (g(n)，函数的一般下界III、同时满足上两条，记为f(n)= (g(n)，IV、至于，即，记为f()=(g();参考习题1.1， 1.3, 1.6(重点，答案不全，理由自己补充)。习题1.6理由参照以上说明即可搞定第二章：分治思想第一部分：课堂笔记一：二：递归

2、树：计算时间最后一层1 1 1 1 1 1 1 1完全二叉树，推得层数为logn，那么时间复杂度为不对称递归树解法与上述一致，只是对不对称处理注一点即可分治法，将一个规模为n的问题分为k个的子问题，这些子问题相互独立且与原问题相同递归的求解的这些子问题；不妨设k个子问题规模为n/m,分解发值为n0=1，设k个子问题解合并为原问题的解需f(n)个单位时间递归式：=推导式1：，简化一下注简化式只在求时间复杂度使用，其他状况勿用！以分治发派生出：大整数的乘法、棋盘覆盖、矩阵乘法、合并排序、快速排序、线性时间排序，这些虽然不会原题出现，但其中两个的思想方法会在考试中出现，分析分析，他们的思想递归式、时

3、间复杂度即可最好会用！(以上面递归式和推导式1很容易搞定)参考习题2.3 ，2.9习题2.9第三章：解题形式，四步一、 算法策略（以什么思想解题，是动态规划还是贪心算法或是分治算法）；二、 算法思想（按第一步往下分析，按套路走下去。列如，第一步说是动态规划，那么把题目带进动态规划套路，段分成多少子问题，假定某个方向最优，自低向上分析等等相似的贪心算法也如此，最后最好加一点递归式推导式什么等等，）；三、 算法实现；（程序，比一般程序简单多，不要求写出得合乎语法结构，形式化东西，汉语加程序语言叙述）四、 算法时间复杂度分析（即大O()多少什么）。3.1矩阵相乘33最长公共子序列3.4最大子段和3.

4、7图像压缩3.10 0-1背包问题（课堂有例子，找出来！做做！）课后参考习题算法分析题第三章，算法实现题：习题.3.2算法实现题3.3.注以上解法勿用：简洁解法如下：注意时间复杂度算法实现题3.5算法实现题3.6分析：给出的算法是自低向上，那么递归式必定为自上而下，其实就是上三角问题，贪心确实很好用，每次选取的都是最大的，整个不就最大。但这题要动态解，换个角度，这也是最优子结构问题，采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n, 则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径

5、。即在上三角每行选个数求，row代表行，col代表列；以一个二维数组来trangle保存当前最大和，递归式如下：算法描述如下：（原答案有误，已改！）算法实现：（c版）#include stdio.h#include math.hmain()FILE *fp1,*fp2;int a105105;int i,j;int n;char c105;fp1=fopen(numr.txt,rt);fscanf(fp1,%d,&n);for(i=1;i=n;i+) for(j=1;j=1;i-) for(j=1;j=ai+1j+1) aij=aij+ai+1j;ci=L;elseaij=aij+ai+1j+

6、1;ci=R;/*倒推。判断从（i，j）这个点开始往下走的最大的和，并存在这个点上。*/fp2=fopen(numw.txt,wt);fprintf(fp2,%dn,a11);/*循环完毕后，三角形最顶端的点所存的值即为最大的和，输出这个值*/for(i=1;i=n;i+)fprintf(fp2,%c,ci);fclose(fp2);时间复杂度第四章：贪心算法考试分值20%左右第四题问答题出现，加一道选择题或一题填空考试内容：活动安排、哈弗曼编码、单源最短路径，最小生成树、多级调度虽然列了多条，分开来看：多级调度调度必考，但是只是一道填空或是选择，解题方法书P121哈弗曼编码、单源最短路径，最

7、小生成树此三者，数据结构，翻开看看，加一点算法知识（即上课老师说的思想分析，着重点，看看笔记），解决最后一个，活动安排，考到按部就班解，解- 贪心算法解此题一般步骤：一、 按某种属性排序二、 贪心选择这种属性（最大、最小或是最长之类的）三、 对于活动安排采取的贪心为迭代法，选取的是最大相容子集（即最优解）四、 时间复杂度什么滴简述一下。参考习题算法实现题4.1说明：此程序是调用活动安排算法（函数，书103页），每次求一个最大相容子集，放入一会场，函数名与书上不相同注意改写!以下是扩展：算法实现题4.9 汽车加油问题算法描述：1.贪心算法解决方案l 贪心算法的基本思想该题目求加油最少次数，即求最

8、优解的问题，可分成几个步骤，一般来说，每个步骤的最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）。不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生一个全局得最优解。l 贪心算法的适用的问题贪心算法适用的问题必须满足两个属性：（） 贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前做出的选择，但不能依赖于以后的选择。（） 最优子结构：

9、问题的整体最优解包含着它的子问题的最优解。l 贪心算法的基本步骤（） 分解：将原问题分解为若干相互独立的阶段。（） 解决：对于每一个阶段求局部的最优解。（） 合并：将各个阶段的解合并为原问题的解。问题分析由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为原

10、问题的解得到我们原问题的求解。加油站贪心算法设计（C）：includeincludeint add(int b ,int m,int n) /求一个从m到n的数列的和 int sb; for(int i=m;iN) return ERROR; /如果某相邻的两个加油站间的距离大于N，则不能到达终点 if(add(ai, 0, n)N) /如果这段距离小于N，则不需要加油 bi=0; return add(bi,0,n); if(ai=aj&ai=N) /如果每相邻的两个加油站间的距离都是N，则每个加油站都需要加油 bi=1; return add(bi,0,n); if(ai=aj&aiN)

11、/如果每相邻的两个加油站间的距离相等且都小于N if( add(ai,m,k) N ) bk=1; m+=k; return add(bi,0,n); if(ai!=aj) /如果每相邻的两个加油站间的距离不相等且都小于N if( add(ai,m,k) N ) bk=1; m+=k; return add(bi,0,n); viod main( ) int a ; scanf(%d,a); scanf(/n); scanf(/d,&N); Tanxin(a ,0,n);以下也是这题程序，C+模板形式贪心算法正确性证明：l 贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部

12、最优的选择，即贪心选择来达到。对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的N千米这段路程上任取两个加油站、，且距离始点比距离始点近，则若在加油不能到达终点那么在加油一定不能到达终点，如图：由图知：因为m+Nn+N，即在B点加油可行驶的路程比在A点加油可行驶的路程要长n-m千米，所以只要终点不在B、C之间且在C的右边的话，根据贪心选择，为使加油次数最少就会选择距离加满油得点远一些的加油站去加油，因此，加油次数最少满足贪心选择性质。l 最优子结构性质：当一个问题大的最优解包含着它的子问题的最优解时，称该问题具有

13、最优子结构性质。由于（b1,b2,bn）是这段路程加油次数最少的一个满足贪心选择性质的最优解，则易知若在第一个加油站加油时，b1=1,则（b2,b3,bn）是从 a2到an这段路程上加油次数最少且这段路程上的加油站个数为（a2,a3,an）的最优解,即每次汽车中剩下的油不能在行驶到下一个加油站时我们才在这个加油站加一次油，每个过程从加油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。贪心算法时间复杂度分析由于若想知道该在哪个加油站加油就必须遍历所有的加油站，且不需要重复遍历，所以时间复杂度为O(n)。算法实现题

14、4.10 区间覆盖问题（待续）贪心策略：每次覆盖尽可能多的点算法思想：对n个点坐标排序，从小到大，每次选取未被覆盖且坐标最小的点，以此点为起始位置，用长度K覆盖，直到所有点被覆盖。#include#includeint cmp(const void*a,const void*b) return *(int*)a-*(int*)b;int main() int i,j=0,a100000,m=1,n,k; cinnk; for(i=0;iai; qsort(a,n,sizeof(int),cmp); for(i=0;iaj+k) m+; j=i; coutmendl;；另版#include #i

15、nclude #include using namespace std;int n , m , i ;double greedy(vector x , int s )vector st(s+1,0);vector su(s+1,0);int n = x.size();sort(x.begin(),x.end() );int i = 0 , j = 0 ;while(in)stj += xi;suj +=stj;i + ; j + ;if( j = s ) j = 0 ;double t = 0 ;for ( i = 0 ; i n m ;vector x;for ( i = 0 ; i ai;

16、 x.push_back(ai);coutgreedy(x,m)endl; return 0;算法实现题4.12 删数问题（待续）n n位数a可表示为：x1x2x3xixjxkxm xn 要删去k位数，使得剩下的数字组成的整数最小。设本问题位T，其最优解A=(y1,y2, ,yk)表示依次删去k个数，在删去k个数后剩下的数字按原次序排成的新数。即，最优值极为TA。贪心选择策略求解n 对于a的前r位数： x1x2xpxq；若xqxr 则删去xq，即得到一个n-1位的数a1，a1为a去掉一位后，数字按原次序排列最小的一个新正整数，可表示为：x1x2x3xpxrxs xn n 例:a=45372，其

17、中453，则删去5，得a1=4372n a=45732，其中4573，则删去7，得a1=4532 n 对于a1，原问题T变成了对n-1位数删去k-1位数的新问题T，新问题与原问题相同，只是规模减一。基于此种删数策略，对新问题T，仍可按照上述采用最近下降点删除的贪心选择策略，如此进行下去，直至删去k个数为止。n 设问题T已按照最近下降点的方法删除，A=(y1,y2, ,yk)是删数问题的一个最优解。易知，若问题有解，则1 k n。n (1)当k=1时，由前得证，A=(y1,A)是问题的最优解；n (2)当k=q时，由反证法，可得 A=(y1,y2 ,yq)是最优解； 当k=q+1时，由前得证，

18、A=(y1,y2 ,yq+ yq+1)是最优解。所以，最优装在问题具有贪心选择性质。时间复杂度分析：O（n）第五章、第六章回溯法与分支界限法的异同点，及优缺点二者相同点：都是解空间树上搜索解的算法。不同点：一、 一般情况下，二者求解的目标不同。回溯法求解的目标是找出树中满足约束条件的所有解，二分治界限发求解目标是找出满足约束条件的一个解，或是在满足约束条件找出使用某一目标函数达到极大或极小的解，即某种意义下的最优解。二、 回溯法只通过约束条件减去非可行解，而分支界限法不仅通过约束条件，也通过目标函数的界限来减少无效搜索。三、 搜索方式：回溯法，采用深度优先搜索，开始结点为活结点，也为当前扩展节点搜索纵向生成一个新结点，新结点为活结点，也为当前扩展结点，不能纵向移动时，此点定为死结点，回移到最近的结点，直到没有活结点为止；分支界限法，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。 策略是：在扩展节点处，先生成其所有的儿子节点（分支），然后再从当前的活结点