算法复习材料1

1、.算法复习练习题一计算题与简答题1. 用表示函数f与g之间的关系。(1) f(n)=10000n g(n)=n-10000(2) f(n)=2n g(n)=3n/n(3) f(n)=n3log2n g(n)=n2log3n(4) f(n)=log2n g(n)=log3n(5) f(n)=100n+n100 g(n)=n!2.估计下列算法的时间复杂性的阶。(1)算法A的时间复杂性为，(2)算法B的时间复杂性为3. 计算下面算法中count=count+1的执行次数算法1.10 COUNT3 输入：，k为正整数 输出：count=count+1的执行次数 count=0 for i=1 to n

2、 j=2 while j1 and not sorted sorted=true for j=2 to i if AjAj-1 then Aj Aj-1 sorted=false end if end for i=i-1end while end BUBBLESORT5. 用两种方法证明log n!= (n log n)。(1)用代数方法(2)用积分方法6. 求解递推关系式 f(n)=-6f(n-1)-9f(n-2)。 7. 分治算法由哪些基本步骤组成？分治算法的时间复杂性常满足什么样的递归方程，写出该方程的一般形式，并指出其中各参数的意义。8. 算法有哪五个特性？9. 什么是最优子结构？10

3、. 贪心法与动态规划有何根本区别？11. 设计回溯算法通常包括哪些步骤？12. 随机算法分成那几类，各有什么特点？三算法填空1. 以下是计算xm的值的过程power ( x, m )/计算xm的值并返回。if m=0 then y=_else y=_ y=y*y if m为奇数 then y=x*yend if_end power2. 以下是关于矩阵链乘的算法MATCHAIN1和MATCHAIN_PRODUCT算法 MATCHAIN1输入：矩阵链长度n, n个矩阵的阶r1.n+1, 其中r1.n为n个矩阵的行数，rn+1为第n个矩阵的列数。输出：n个矩阵相乘的数量乘法的最小次数，最优顺序的信息

4、数组S1.n, 1.n。for i=1 to n Ci, i=0 /对角线d0置 for d=1 to n-1 /逐条计算对角线d0dn-1 for i=1 to n-d / 计算对角线dd的n-d个元素。 _ Ci, j= for k=i+1 to j x= _ if _ then Ci, j=x; Si, j=k end if end for end for end for return C1, n, Send MATCHAIN1根据S中的信息递归确定最优乘法顺序。算法 MATCHAIN_PRODUCT输入：矩阵链长度n, n个矩阵M1, M2, , Mn , 最优乘法顺序的信息数组S1.

5、n, 1.n。输出：按最优顺序计算的矩阵链乘积M=M1M2Mn 。 M=matchain_product( 1, n ) return Mend MATCHAIN_PRODUCT 过程 matchain_product (i, j) / 求按最优顺序计算的矩阵链乘积MiMi+1Mj并返回。if _ then return Mi else A=matchain_product _ B=matchain_product _ C=multiply( A , B) /计算两个矩阵乘积C=AB。 return C end ifend matchain_product3. 以下是迷宫问题的算法算法 MAZ

6、E 输入：正整数m, n，表示迷宫的数组M0.m+1, 0.n+1 (迷宫数据存于M1.m, 1.n中)，迷宫的入口位置(ix, iy),出口位置(ox, oy)。 输出：迷宫中入口至出口的一条通路，若无通路，则输出no solution。 M0, 0.n+1=Mm+1, 0.n+1=1 M0.m+1, 0=M0.m+1, n+1=1 /设置迷宫边界。 tag1.m, 1.n=0 为dx1.4, dy1.4置值 flag=false /flag表示是否存在通路。 x=ix; y=iy ; tagx, y=1 /进入入口, (x, y)表示当前位置。 i=1; ki=0 while _ and

7、not flag while _ and not flag _ /试沿着下一个方向搜索。 x1= x+dxki; y1= y+dyki if Mx1, y1=0 and tagx1, y1=0 then /位置(x1,y1)可走 if x1=ox and y1=oy then _ /找到一条通路 else x=x1; y=y1; tagx, y=1 /进入新位置。 i=i+1 ； ki= _ /准备搜索下一个位置。 end if end if /否则，剪枝 end while_; x=x-dxki; y=y-dyki/回溯 end while if flag then outputroute(

8、k, i) /输出由k1.i表示的通路。 else output “no solution”/输出无解end MAZE4. 下面是求一个序列的多数元素的递归算法算法 MAJORITY输入：n个元素的数组A1.n。输出：若A1.n存在多数元素，则输出；否则输出none。 c=candidate ( 1 ) / 求A1.n中的候选多数元素。count=0 /以下验证c是否为A1.n中的多数元素。 for j=1 to n if Aj=c then count=count+1 end for if _ then return c else return noneend MAJORITY过程 cand

9、idate ( m )/求Am.n中的候选多数元素并返回。j=m; c=Am; count=1while j0 j=j+1 if _ then _ else _ /除去两个不同的元素。end whileif j=n then return c /此时序列已扫描完毕。else return _ end candidate5. 下面是0-1背包问题的算法算法 KNAPSACKREC输入：物品数n, n种物品的体积数组s1.n和价值数组v1.n, 背包容量C。输出：装入背包物品的最大总价值，以及最优解的信息数组H0.n, 0.C。 for i=0 to n for j=0 to C Vi, j=-1

10、 maxv=knapsack(n, C) return maxv , Hend KNAPSACKREC过程 knapsack(i, j) /从i种物品中选择物品装入容量为j的背包中，求背包中/物品所能达到的最大总价值并返回，同时将最优解的相应/信息存入数组H0.n, 0.C。 if Vi, j=-1 then /相应的子问题未解过。 if i=0 or j=0 then Vi,j=0 else if sij then Vi, j= _ Hi, j= _ else a1=_ a2=knapsack(i-1, j) if a1=a2 then Vi, j=a1; Hi, j= _ else Vi,

11、 j=a2; Hi, j=0 end if end if end if end if return _end knapsack算法 KNAPSACK_SOLUTION输入：物品数n , 背包容量C, n种物品的体积数组s1.n, 相应的0/1背包问题的最优解信息数组H0.n, 0.C。输出：相应的0/1背包问题的最优解X1.n。 y=C / y表示当前背包的剩余容量Xn=Hn, Cfor i=n to 2 if Xi=1 then y=_ Xi-1= _end forreturn Xend KNAPSACK_SOLUTION6. 以下是随机化的线性选择算法算法 RANDOMIZEDSELECT

12、输入：整数n, k, 1=k=n, 以及n个元素的数组A1.n。输出：A中的第k小元素s。 s=rselect ( A , 1, n, k )end RANDOMIZEDSELECT过程 rselect ( A , low, high, k ) /求Alow.high中的第k小元素并返回。 v=random(low, high) mm= _ 将Alow.high分成三个数组： A1=a|amm/以下选择一个子问题递归或直接解。 case|A1|=k: return _ /求A1的第k小元素。|A1|+|A2|=k: return mm /此时mm为Alow.high的第k小元素。 |A1|+|

13、A2|k: return rselect _ /求A3的第k-|A1|-|A2|小元素 end caseend rselect7. 以下是归并排序的分治算法MERGESORT 输入：n个元素的数组A1.n。 输出：按非降序排序的数组A1.n。 mergesort(A , 1, n) end MERGESORT 过程 mergersort( A , low, high ) /将Alow.high 按非降序归并排序。 if low=yd2=ydn。 d=sort(y, n) for i=1 to n xi=0 /对x1.n初始化。 i=1; maxv=0; rc=C /以下rc表示当前背包的剩余容

14、量。while _ and i=nj=di / uj为当前考虑选择的物品 if sj=rc then xj= _; rc= _ /物品uj全部装入背包。 else xj= _ /选择物品uj的一部分将背包填满。 rc=0 end if maxv= _i= _ end while return maxv, x1.nend GREEDY_KNAPSACK9. 以下是子集合问题的回溯算法算法 SUBSETSUM 输入:正整数n,正实数b,表示含有n个正实数的集合S的数组a1.n。 输出:集合S的元素之和等于b的所有子集，若无解，则输出“no solution”。 for i=1 to n xi=0

15、/用x1.n表示子集，初始化为空集。 r=0 for i=1 to n r=r+ai flag=subset(0, 0, r)if not flag then output “no solution” end SUBSETSUM 过程：subset(k, sum, r) /在已经求出的部分解x1.k固定的情况下，求关于S, b的/子集和问题的所有解并输出，有解返回true, 否则返回/false。 / sum= 表示当前子集的元素之和，r= 表示剩/余元素之和。 if sum=b then /找到一个解。output x1.n; t=true /输出当前解。 elseif kn and sum

16、=b then /可继续往下搜索。r=_ xk+1=0t1=subset_ /搜索左子树（对应xk+1=0）xk+1= _t2=setsub_ /搜索右子树t=t1 or t2else t=_end if end if _ return tend subset10. 下面是一个求n个元素全排列的算法算法 PERMUTATION 输入：正整数n和存储n个元素a1 , a2, an的数组P1.n。输出：a1 , a2, an的全排列。 perml ( 1 )end PERMUTATION过程 perml ( m )/在P1.m-1中元素固定不变的情况下，求Pm.n中元素/的全排列，并输出P1.n中

17、元素的相应排列。if _ then / 此时只求一个元素Pn的全排列。 output P1.n; / 输出P1.n中元素的一个新排列。else for j=m to n PmPj _ _ end for end if end perml11. 以下是求最长公共子序列的算法算法 LCS 输入：非负整数n、m, 长度分别为n和m的序列A= a1a2an和B=b1b2bn 。 输出：A和B的最长公共子序列长度Ln, m和存储最长公共子序列的有关信息的数组H1.n, 1.m。 for i=0 to n Li, 0=0 for j=0 to m L0, j=0 for i=1 to n for j=1

18、to m if ai=bj then Li, j= _ ; Hi, j=0 else if Li-1, j=Li, j-1 then Li, j= _ ; Hi, j=1 else Li, j=Li, j-1 ; Hi, j= _ end if end if end for end for return Ln, m, H end LCS算法 LCSS输入：非负整数n、m, 长度分别为n和m的序列A和B的最长公共子序列的有关信息数组H1.n, 1.m, 序列A= a1a2an 。输出: 序列A和B的最长公共子序列C 。 C= /表示空序列。 i=n; j=m while i0 and j0 if

19、 Hi, j=0 then 在C的前面插入ai i=_; j=_ else if Hi, j= _ then i=i-1 else j=j-1 end if end while return C end LCSS12. 以下是0-1背包问题的回溯算法算法 KNAPSACK01输入: 物品数n, n种物品的体积数组s1.n和价值数组v1.n,背包容量C。输出：装入背包物品的最大总价值maxv和最优解x01.n。 /用x1.n表示选择的物品子集，初始化为空集。 rv=0; rs=0for i=1 to nrv=rv+vi ; rs=rs+si maxv=0; x01.n=x1.n=0 / x0表示

20、当前最优解。knapsack01(0, C, 0, rv, rs)output maxv, x01.n end KNAPSACK01 过程：knapsack(k, r, cv, rv, rs) /在已知当前最优值为maxv且已经求出的部分解x1.k固/定的情况下，求 0/1背包问题的最优值和最优解，并更新/maxv和x0。 r表示当前背包的剩余容量, cv表示当前背/包中物品的总价值为，rv= , rs= 。 if r=0 and cvmaxv then /找到更优的解，更新当前最优值。 maxv=_; x0=x end if if rsmaxv then maxv=cv+rv; x01.k=

21、x1.k; x0k+1.n=1; end if else if r0 and cv+rvmaxv then /可继续往下搜索。 rv=_; rs=_ xk+1=0 knapsack_ /搜索左子树（对应xk+1=0） xk+1=1 knapsack_ /搜索右子树end if end if _end knapsack13. 下面是求第k小元素的算法算法 SELECT输入：整数n, k, 1=k=n, 以及n个元素的数组A1.n。输出：A中的第k小元素s。 s=select ( A , 1, n, k )end SELECT过程 select ( A , low, high, k ) /求Alo

22、w.high中的第k小元素并返回。 p=high-low+1 /p为当前处理的元素个数。 if p44 then / 当元素个数44时，直接求解。 将Alow.high排序 return(Alow+k-1) end if / 以下分解子问题。 q=；/将Alow.high每5个分组，剩余的被排除。 将Alow.low+5q-1分为q组, 每组5个元素； 将q组中的每一组单独排序并找出中项，所有的中项存于数组M1.q中； mm=select(_) /求中项序列M的中项mm 将Alow.high分成三组： A1=a|amm/以下选择一个子问题递归或直接解。 case|A1|=k: return s

23、elect (_) |A1|+|A2|=k: return mm |A1|+|A2|=pa2=pan。 a=sort(p, n) d0=0; J0=0 /设一个虚拟作业编号为，期限为 J1=a1 /直接安排收益最高的作业jaik=1 /以下k总是表示当前已被安排的作业数。for t=2 to ni= _ / ji为当前考虑安排的作业。 r=k while _ and dJrr _ end whileif dJr=di and _ then /把i插入到J中的r+1位置上。 for s=k to r+1 Js+1=Js Jr+1= _ k= _end if end for return k, J

24、1.kend JOB_ARRANGEMENT15. 以下是关于矩阵链乘的算法MATCHAIN1和MATCHAIN_PRODUCT算法 MATCHAIN1输入：矩阵链长度n, n个矩阵的阶r1.n+1, 其中r1.n为n个矩阵的行数，rn+1为第n个矩阵的列数。输出：n个矩阵相乘的数量乘法的最小次数，最优顺序的信息数组S1.n, 1.n。for i=1 to n Ci, i=0 /对角线d0置 for d=1 to n-1 /逐条计算对角线d0dn-1 for i=1 to n-d / 计算对角线dd的n-d个元素。 _ Ci, j= for k=i+1 to j x= _ if _ then Ci, j=x; Si, j=k end if end for end for end for return C1, n, Send MATCHAIN1根据S中的信息递归确定最优乘