期末总结ppt课件

1、期末总结基础知识点,1、概念（见教材） 2、渐进分析 例题：写出下列函数之间的大O、大或关系。,期末总结基础知识点,3、用展开法求解下列递归方程，将结果表示成大O形式。,1、最大子段和问题：最大子段和问题：给定由n个整数组成的序列(a1, a2, , an)（可能有负数），最大子段和问题要求该序列形如ai+aj的最大值（1ijn）。分别用蛮力法和分治法设计求解最大子段和问题，写出算法的伪代码描述，并分析每种方法的渐进复杂性。 参考解答：（蛮力法） 时间复杂性：O（n2）,期末总结算法设计,2、设计分治算法求一个数组中最大元素的位置，建立该算法的递推式并求解。（课后题P74,5） 参考解答：,期

2、末总结算法设计,期末总结算法设计,3、在一个序列中出现次数最多的元素称为众数。请设计分治算法寻找众数并分析算法的时间复杂性。 （课后题P75,10） 参考解答（时间复杂性略）：,期末总结算法设计,4、设M是一个nn的整数矩阵，其中每一行（从左到右）和每一列（从上到下）的元素都按升序排列。设计分治算法确定一个给定的整数x是否在M中，并分析算法的时间复杂性。 （课后题P75,11，算法略）,期末总结算法设计,5、修改下面的折半查找算法，使其正确进行查找。并设计写出折半查找的递归形式算法，分析时间性能。（解答略） int BinSearch(int r, int n, int k) int low=

3、0, high=n-1; int mid; while(lowrmid) low=mid; else return mid; return 0; ,期末总结算法设计,6、修改折半查找算法，使之能够进行范围查找。所谓范围查找是要找出在给定值a和b之间的所有元素（ab）。参考解答（复杂性分析略）：,期末总结算法设计,7、请写出背包问题的贪心算法伪代码描述，并进行时间复杂性分析。并用贪心法求解下列背包问题：有7个物品，重量分别为（2,3,5,7,1,4,1），价值分别为（10,5,15,7,6,18,3），背包容量W=15，要求写出求解过程（P146,1）。 （参考解答略。）,期末总结算法设计,8、

4、请写出活动安排问题的贪心算法伪代码描述，并进行时间复杂性分析。并求解下列活动安排问题：有11个活动等待安排，这些活动的起止时间如下表所示，要求写出求解过程。（参考解答略）,期末总结算法设计,9、设计用回溯法求解0/1背包问题的剪枝函数，并给出相应算法的伪代码描述。 参考解答：,剪枝函数 设搜索至第i层，背包容量为c，当前获得的物品重量为cw，当前获得的价值为cv，当前获得的最大价值为bestv。 左子树：用约束函数剪枝，当cw+wic，则对左子树进行剪枝。 右子树：设计上界函数剪枝，cp+vi+1+vnbestv，则对右子树进行剪枝。,主程序： 1、初始化bestv=0,cv=0,cw=0,bestx=0,0; 2、调用Backtrack(1); 3、输出bestx1,n和bestv;,void Backtrack(int t) if(tn) if(bestvbestv) Backtrack(t+1); ,int Bound(int i) int b=cv; for(j=i;j=n;j+) b+=vj; return b; ,期末总结算法设计,10、给定一个正整数集合X=x1,x2,xn和一个正整数y，设计回溯算法，求集合