江大算法设计方案期末复习

1、A、考试范围一、基本题（20%）排序、分治、动态规划、贪心、回溯和分枝限界；渐进性符号及定义，求解递推关 系二、简答解答（30 %）： 2题三、 算法设计（50%）:分治、动态规划、贪心、回溯，2题，B第二部分例题：1.考虑在序列A仁n中找最大最小元的问题。一个分治算法描述如下：如果n=2就直接求解；否则，将序列等分成两个子序列A仁n/2和An /2+仁n, 分别找出这两个子序列的最大最小元素，据此求出A1.n的最大和最小元。请给出该算法计算时间T（n）的递归方程，并解方程来确定算法的时间复杂度假设n=2k（k为正整数）2.简述基数排序的基本思想和算法时间复杂度；考虑使用基数排序对下列 8个数

2、据进行排序，给出排序的中间过程和最终结果2756, 7352, 3725, 3762, 5273, 2375, 5732, 56273.快速排序是根据分治策略来设计的，其基本思想是什么？快速排序的最坏及平均情况的 时间复杂度是多少？4.考虑用动态规划法求解矩阵M.MzMsMqMs的最优运算（即乘法次数最少）的次序,其中 M/5 6,M2 :6 4,M3:4 8,M4：8 3,M5：3 5（1 ）设Ci,j表示MjMj JI|M j按照最优次序运算所需要的元素乘法次数。请给出Ci,j递推计算的表达式（2 ）根据递推公式填写下表，包括Ci,j的值及对应的最优计算次序的加括号方式C1,1=0M1C1

3、,2=120M1 M2C1,3=280 (M1 M2) M3C1,4=258 M1 (M2 (M3 M4)C1,5=333(M1 (M2 (M3 M4 )M5C2,2=0 M2C2,3=192 M2 M3C2,4=168 M2 (M3 M4)C2,5=258 (M2 (M3 M4 )M5C3,3=0M3C3,4=96M3 M4C3,5=156 (M3M4)M5C4,4=0M4C4,5=120M4 M5C5,5=0M5C第三部分例题其中 ni _ 巳 IHnk , k _ 1。正整数n的这种表示称为正整数n的的划分。正整数 n的的不同的划分个数称为正整数n的的划分数，记作 p(n)。试推导出p(

4、n)的求解方法。2.设n个不同的整数按由小到大顺序存于T1.n中。1) .若存在下标 i , 1 ： i ： n , Ti ： i,证明：对 1 n) then记录目前最优。bestP = P。bestle n = len。elsefor (int i=t 。 i=n。 i+) swap(Pt, Pi)。if i=1 the ndist = 0。elsedist = P(t)点与P(t-1)点之间的距离。len += dist。if (lenbestlen) backtrack(t+1)。len -= dist。swap（xt, xi）。 主程序 对P, len初始化 对bestlen初始化（

5、） backtrackbacktrack （1）。输出 bestP 和 bestlen6、凸包问题（GRAHA算法）算法A首先，找到所有点中最左边的（y坐标最小的），如果y坐标相同，找x坐标最小的；以这个点为基准求所有点的极角（atan2（y-y0,x-x0），并 按照极角对这些点排序，前述基准点在最前面，设这些点为PO.Pn-1;建立一个栈，初始时 P0、P1、P2进栈，对于P3.n-1的每个点，若栈顶的两个点与它不构成“向左转”的关系，则将栈顶的点出栈，直至没有点需要出栈以后将当前点进栈；所有点处理完之后栈中保存的点就是凸包了。如何判断 A、B C构成的关系不是向左转呢？如果 b-a与c-a的叉乘小于 0就不是。a与b的叉乘就是a.x*b.y-a.y*b.x 。算法B（分治方法）第一步：把给定点集中的点按横坐标大小排序，如下图所示，p和pn必定是凸多边形的两个顶点。第二步：在上凸包点集 S1中找到一个距离直线最远点Pmax，如下图所示，显然直线段P! Pmax和PnPmax把点集S1分成三个集合，有凸包的性质可知，PPmax Pn三点围成的三角形中的点不可能作为凸包的顶点，所以只需考虑直线P1 Pmax左边的