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个矩阵的阶r[1..n+1], 其中r[1..n]为n个矩阵的行数，r[n+1]为第n个矩阵的列数输出：n个矩阵相乘的数量乘法的最小次数，最优顺序的信息数组S[1..n, 1..n] for i=1 to n C[i, i]=0 //对角线d0置０ for d=1 to n-1 //逐条计算对角线d0~dn-1 for i=1 to n-d // 计算对角线dd的n-d个元素 ____________ C[i, j]= ∞ for k=i+1 to j x= ____________ if ____________ then C[i, j]=x; S[i, j]=k end if end for end for end for return C[1, n], Send MATCHAIN1 根据S中的信息递归确定最优乘法顺序。
算法 MATCHAIN_PRODUCT输入：矩阵链长度n, n个矩阵M1, M2, …, Mn , 最优乘法顺序的信息数组S[1..n, 1..n]输出：按最优顺序计算的矩阵链乘积M=M1M2…Mn M=matchain_product( 1, n ) return Mend MATCHAIN_PRODUCT 过程 matchain_product (i, j) // 求按最优顺序计算的矩阵链乘积MiMi+1…Mj并返回 if ____________ then return Mi else A=matchain_product ____________ B=matchain_product ____________ C=multiply( A , B) //计算两个矩阵乘积C=AB return C end ifend matchain_product3. 以下是迷宫问题的算法算法 MAZE 输入：正整数m, n，表示迷宫的数组M[0..m+1, 0..n+1] (迷宫数据存于M[1..m, 1..n]中)，迷宫的入口位置(ix, iy),出口位置(ox, oy)。
输出：迷宫中入口至出口的一条通路，若无通路，则输出no solution M[0, 0..n+1]=M[m+1, 0..n+1]=1 M[0..m+1, 0]=M[0..m+1, n+1]=1 //设置迷宫边界 tag[1..m, 1..n]=0 为dx[1..4], dy[1..4]置值 flag=false //flag表示是否存在通路 x=ix; y=iy ; tag[x, y]=1 //进入入口, (x, y)表示当前位置 i=1; k[i]=0 while ____________ and not flag while ____________ and not flag ____________ //试沿着下一个方向搜索 x1= x+dx[k[i]]; y1= y+dy[k[i]] if M[x1, y1]=0 and tag[x1, y1]=0 then //位置(x1,y1)可走 if x1=ox and y1=oy then ____________ //找到一条通路 else x=x1; y=y1; tag[x, y]=1 //进入新位置。
i=i+1 ； k[i]= ____________ //准备搜索下一个位置 end if end if //否则，剪枝 end while____________; x=x-dx[k[i]]; y=y-dy[k[i]] //回溯 end while if flag then outputroute(k, i) //输出由k[1..i]表示的通路 else output “no solution” //输出无解end MAZE4. 下面是求一个序列的多数元素的递归算法算法 MAJORITY输入：n个元素的数组A[1..n]输出：若A[1..n]存在多数元素，则输出；否则输出none c=candidate ( 1 ) // 求A[1..n]中的候选多数元素count=0 //以下验证c是否为A[1..n]中的多数元素 for j=1 to n if A[j]=c then count=count+1 end for if ____________ then return c else return noneend MAJORITY过程 candidate ( m )//求A[m..n]中的候选多数元素并返回。
j=m; c=A[m]; 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种物品的体积数组s[1..n]和价值数组v[1..n], 背包容量C输出：装入背包物品的最大总价值，以及最优解的信息数组H[0..n, 0..C] for i=0 to n for j=0 to C V[i, j]=-1 maxv=knapsack(n, C) return maxv , Hend KNAPSACKREC过程 knapsack(i, j) //从i种物品中选择物品装入容量为j的背包中，求背包中//物品所能达到的最大总价值并返回，同时将最优解的相应//信息存入数组H[0..n, 0..C]。
if V[i, j]=-1 then //相应的子问题未解过 if i=0 or j=0 then V[i,j]=0 else if s[i]>j then V[i, j]= ____________ H[i, j]= ____________ else a1=____________ a2=knapsack(i-1, j) if a1>=a2 then V[i, j]=a1; H[i, j]= ____________ else V[i, j]=a2; H[i, j]=0 end if end if end if end if return ____________end knapsack算法 KNAPSACK_SOLUTION输入：物品数n , 背包容量C, n种物品的体积数组s[1..n], 相应的0/1背包问题的最优解信息数组H[0..n, 0..C]输出：相应的0/1背包问题的最优解X[1..n]。
y=C // y表示当前背包的剩余容量X[n]=H[n, C]for i=n to 2 if X[i]=1 then y=____________ X[i-1]= ____________end forreturn Xend KNAPSACK_SOLUTION6. 以下是随机化的线性选择算法算法 RANDOMIZEDSELECT输入：整数n, k, 1<=k<=n, 以及n个元素的数组A[1..n]输出：A中的第k小元素s s=rselect ( A , 1, n, k )end RANDOMIZEDSELECT过程 rselect ( A , low, high, k ) //求A[low..high]中的第k小元素并返回 v=random(low, high) mm= ____________ 将A[low..high]分成三个数组： A1={a|amm} //以下选择一个子问题递归或直接解 case|A1|>=k: return ____________ //求A1的第k小元素。
A1|+|A2|>=k: return mm //此时mm为A[low..high]的第k小元素 |A1|+|A2|
输出：装入背包物品的最大总价值maxv和相应的最优解x[1..n] for i=1 to n y[i]=v[i]/s[i] //求n个物品的单位体积价值y[1..n] end for //对y[1..n]按降序地址排序，排序结果返回到数组d[1..n] //中, 使得y[d[1]]>=y[d[2]]>=…>=y[d[n]] d=sort(y, n) for i=1 to n x[i]=0 //对x[1..n]初始化 i=1; maxv=0; rc=C //以下rc表示当前背包的剩余容量while ____________ and i<=nj=d[i] // uj为当前考虑选择的物品 if s[j]<=rc then x[j]= ____________; rc= ____________ //物品uj全部装入背包 else x[j]= ____________ //选择物品uj的一部分将背包填满 rc=0 end if maxv= ____________i= ____________ end while return maxv, x[1..n]end GREEDY_KNAPSACK9. 以下是子集合问题的回溯算法算法 SUBSETSUM 输入:正整数n,正实数b,表示含有n个正实数的集合S的数组a[1..n]。
输出:集合S的元素之和等于b的所有子集，若无解，则输出“no solution” for i=1 to n x[i]=0 //用x[1..n]表示子集，初始化为空集 r=0 for i=1 to n r=r+a[i] flag=subset(0, 0, r)if not flag then output “no solution” end SUBSETSUM 过程：subset(k, sum, r) //在已经求出的部分解x[1..k]固定的情况下，求关于S, b的//子集和问题的所有解并输出，有解返回true, 否则返回//false // sum= 表示当前子集的元素之和，r= 表示剩//余元素之和 if sum=b then //找到一个解output x[1..n]; t=true //输出当前解 elseif k=b then //可继续往下搜索r=____________ x[k+1]=0t1=subset____________ //搜索左子树（对应x[k+1]=0）x[k+1]= ____________t2=setsub____________ //搜索右子树t=t1 or t2else t=____________end if end if ____________ return tend subset10. 下面是一个求n个元素全排列的算法算法 PERMUTATION 输入：正整数n和存储n个元素a1 , a2,…, an的数组P[1..n]。
输出：a1 , a2,…, an的全排列 perml ( 1 )end PERMUTATION过程 perml ( m )//在P[1..m-1]中元素固定不变的情况下，求P[m..n]中元素//的全排列，并输出P[1..n]中元素的相应排列if ____________ then // 此时只求一个元素P[n]的全排列 output P[1..n]; // 输出P[1..n]中元素的一个新排列else for j=m to n P[m]↔P[j] ____________ ____________ end for end if end perml11. 以下是求最长公共子序列的算法算法 LCS 输入：非负整数n、m, 长度分别为n和m的序列A= a1a2…an和B=b1b2…bn 输出：A和B的最长公共子序列长度L[n, m]和存储最长公共子序列的有关信息的数组H[1..n, 1..m] for i=0 to n L[i, 0]=0 for j=0 to m L[0, j]=0 for i=1 to n for j=1 to m if ai=bj then L[i, j]= ____________ ; H[i, j]=0 else if L[i-1, j]>=L[i, j-1] then L[i, j]= ____________ ; H[i, j]=1 else L[i, j]=L[i, j-1] ; H[i, j]= ____________ end if end if end for end for return L[n, m], H end LCS算法 LCSS输入：非负整数n、m, 长度分别为n和m的序列A和B的最长公共子序列的有关信息数组H[1..n, 1..m], 序列A= a1a2…an 。
输出: 序列A和B的最长公共子序列C C=Φ //Φ表示空序列 i=n; j=m while i>0 and j>0 if H[i, j]=0 then 在C的前面插入ai i=____________; j=____________ else if H[i, j]= ____________ then i=i-1 else j=j-1 end if end while return C end LCSS12. 以下是0-1背包问题的回溯算法算法 KNAPSACK01输入: 物品数n, n种物品的体积数组s[1..n]和价值数组v1..n],背包容量C输出：装入背包物品的最大总价值maxv和最优解x0[1..n] //用x[1..n]表示选择的物品子集，初始化为空集。
rv=0; rs=0for i=1 to nrv=rv+v[i] ; rs=rs+s[i] maxv=0; x0[1..n]=x[1..n]=0 // x0表示当前最优解knapsack01(0, C, 0, rv, rs)output maxv, x0[1..n] end KNAPSACK01 过程：knapsack(k, r, cv, rv, rs) //在已知当前最优值为maxv且已经求出的部分解x[1..k]固//定的情况下，求 0/1背包问题的最优值和最优解，并更新//maxv和x0 r表示当前背包的剩余容量, cv表示当前背//包中物品的总价值为，rv= , rs= if r>=0 and cv>maxv then //找到更优的解，更新当前最优值 maxv=____________; x0=x end if if rs<=r then if cv+rv>maxv then maxv=cv+rv; x0[1..k]=x[1..k]; x0[k+1..n]=1; end if else if r>0 and cv+rv>maxv then //可继续往下搜索。
rv=____________; rs=____________ x[k+1]=0 knapsack____________ //搜索左子树（对应x[k+1]=0） x[k+1]=1 knapsack____________ //搜索右子树end if end if ____________end knapsack13. 下面是求第k小元素的算法算法 SELECT输入：整数n, k, 1<=k<=n, 以及n个元素的数组A[1..n]输出：A中的第k小元素s s=select ( A , 1, n, k )end SELECT过程 select ( A , low, high, k ) //求A[low..high]中的第k小元素并返回 p=high-low+1 //p为当前处理的元素个数 if p<44 then // 当元素个数<44时，直接求解 将A[low..high]排序 return(A[low+k-1]) end if // 以下分解子问题 q=；//将A[low..high]每5个分组，剩余的被排除。
将A[low..low+5q-1]分为q组, 每组5个元素； 将q组中的每一组单独排序并找出中项，所有的中项存于数组M[1..q]中； mm=select(____________) //求中项序列M的中项mm 将A[low..high]分成三组： A1={a|amm} //以下选择一个子问题递归或直接解 case|A1|>=k: return select (____________) |A1|+|A2|>=k: return mm |A1|+|A2|=p[a[2]]>=…>=p[a[n]]。
a=sort(p, n) d[0]=0; J[0]=0 //设一个虚拟作业编号为０，期限为０ J[1]=a[1] //直接安排收益最高的作业ja[i] k=1 //以下k总是表示当前已被安排的作业数for t=2 to n i= ____________ // ji为当前考虑安排的作业 r=k while ____________ and d[J[r]]>r ____________ end whileif d[J[r]]<=d[i] and ____________ then //把i插入到J中的r+1位置上 for s=k to r+1 J[s+1]=J[s] J[r+1]= ____________ k= ____________end if end for return k, J[1..k]end JOB_ARRANGEMENT15. 以下是关于矩阵链乘的算法MATCHAIN1和MATCHAIN_PRODUCT算法 MATCHAIN1输入：矩阵链长度n, n个矩阵的阶r[1..n+1], 其中r[1..n]为n个矩阵的行数，r[n+1]为第n个矩阵的列数。
输出：n个矩阵相乘的数量乘法的最小次数，最优顺序的信息数组S[1..n, 1..n] for i=1 to n C[i, i]=0 //对角线d0置０ for d=1 to n-1 //逐条计算对角线d0~dn-1 for i=1 to n-d // 计算对角线dd的n-d个元素 ____________ C[i, j]= ∞ for k=i+1 to j x= ____________ if ____________ then C[i, j]=x; S[i, j]=k end if end for end for end for return C[1, n], Send MATCHAIN1 根据S中的信息递归确定最优乘法顺序算法 MATCHAIN_PRODUCT输入：矩阵链长度n, n个矩阵M1, M2, …, Mn , 最优乘法顺序的信息数组S[1..n, 1..n]。
输出：按最优顺序计算的矩阵链乘积M=M1M2…Mn M=matchain_product( 1, n ) return Mend MATCHAIN_PRODUCT 过程 matchain_product (i, j) // 求按最优顺序计算的矩阵链乘积MiMi+1…Mj并返回 if ____________ then return Mi else A=matchain_product ____________ B=matchain_product ____________ C=multiply( A , B) //计算两个矩阵乘积C=AB return C end ifend matchain_product四．算法设计与分析1. 格雷码问题对于给定的正整数n，格雷码为满足如下条件的一个编码序列：(1) 序列由2n个编码组成，每个编码都是长度为n的二进制位串2) 序列中无相同的编码3) 序列中位置相邻的两个编码恰有一位不同例如：n=2时的格雷码为：{00, 01, 11, 10}设计求格雷码的递归算法。
2. 给出一个分治算法，在一个具有n个数的数组中找出第二个最大元素给出你的算法的时间复杂性3. 考虑金钱兑换问题有一个货币系统，它有n种硬币，它们的面值为v1,v2,…,vn,其中v1=1我们想这样来兑换价值为y的钱,要让硬币的数目最少更形式地，我们要让下面的量在约束条件下极小其中，x1,x2,…,xn是非负整数（xi可能是0）4. 线段覆盖问题：在实轴上有n个点x1, x2,…, xn , 要求用最少数量的单位长线段覆盖这些点写出求该问题的最优值和最优解的贪心算法5. 马的周游问题：给出一个nxn棋盘，一个中国象棋马在某个起点位置（x0, y0），求一条访问每个棋盘格点恰好一次，最后回到起点的周游路线 12 -。