算法设计与分析习题.doc

算法设计与分析习题第一章算法引论1、 算法的定义？答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法：就是解决问题的方法或过程。2、 算法的特征？答：1)算法有零个或多个输入； )算法有一个或多个输出； 3)确定性 ； )有穷性3、 算法的描述方法有几种？答：自然语言、图形、伪代码、计算机程序设计语言4、 衡量算法的优劣从哪几个方面？答：(1) 算法实现所耗费的时间（时间复杂度）； (2) 算法实现所所耗费的存储空间（空间复杂度）； (3) 算法应易于理解，易于编码，易于调试等等。5、 时间复杂度、空间复杂度定义？答：指的是算法在运行过程中所需要的资源（时间、空间）多少。6、时间复杂度计算： i=1； while（i=n） i=i*2； 答：语句执行次数1次，语句执行次数f(n), 2f(n)=n,则f(n) 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); l 兔子序列（fibonaci数列 ） 递归实现：Int F(int n) if(n=2) return 1; else return F(n-1)+ F(n-2);l 上楼梯问题Int F(int n) if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2);l 整数划分问题问题描述：将正整数n表示成一系列正整数之和，n=n1+n1+n3+将最大加数不大于m的划分个数，记作q(n,m)。正整数n的划分数p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系：递归算法：Int q( int n, int m)if(n1|m1) return 0;If(n=1)|(m=1) return 1;If (nm) return q(n,n);If(n=m) return q(n,m-1)+1;else return q(n,m-1)+q(n-m,m);（2） 蛮力法：百鸡百钱问题算法设计1：设x，y，z分别为公鸡、母鸡、小鸡的数量。 约束条件： x+y+z=100 且 5*x+3*y+z/3=100main( ) int x,y,z;for(x=1;x=20;x=x+1) for(y=1;y=34;y=y+1) for(z=1;z=100;z=z+1) if(100=x+y+z and 100=5*x+3*y+z/3) print(the cock number is,x)； print(the hen number is, y)；print(the chick number is z);算法分析：以上算法需要枚举尝试20*34*100=68000次。算法的效率显然太低 算法设计2： 在公鸡（x）、母鸡（y）的数量确定后，小鸡的数量 z就固定为100-x-y，无需再进行枚举了 。 此时约束条件只有一个： 5*x+3*y+z/3=100 main( ) int x,y,z;for(x=1;x=20;x=x+1) for(y=1;y=33;y=y+1) z=100-x-y; if(z mod 3=0 and 5*x+3*y+z/3=100)print(the cock number is,x)； print(the hen number is, y)；print(the chick number is z); 算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定Z能被3整除时，才会判断“5*x+3*y+z/3=100”。这样省去了z不整除3时的算术计算和条件判断，进一步提高了算法的效率。(3) 倒推法：穿越沙漠问题desert（ ） int dis，k，oil,k; / dis表示距终点的距离，k表示贮油点从后到前的序号 dis=500;k=1;oil=500; /初始化 while ( dis1000) print(“storepoint”,k,”distance”, 1000-dis,”oilquantity”,oil) /1000- dis则表示距起点的距离， k=k+1; /k表示储油点从后到前的序号 dis=dis+500/(2*k-1); oil= 500*k; print(“storepoint”,k,”distance”,dis,”oilquantity”,oil)； 第二章 分治算法1、分治算法基本思想是什么？ 适合用分治算法解决的问题，一般具有几个特征？ 分治算法基本步骤是什么？答：1) 基本思想: 将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。2) 特征： 该问题的规模缩小到一定的程度就可以容易解决; 该问题可以分解为若干个规模较小的相同子问题，即该问题具有最优子结构性质； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 4)利用该问题分解出子问题解可以合并为该问题解; 3）基本步骤： 分解、求小问题解、合并2、改写二分查找算法：设a1n是一个已经排好序的数组，改写二分查找算法: 当搜索元素x不在数组中时，返回小于x的最大元素位置i，和大于x的最小元素位置j； (即返回x的左、右2个元素) 当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。并计算其时间复杂度？答：、设计一个合并排序的算法？（分治法解） 并计算其时间复杂度？(要求写出递推公式，及其求解过程)答：void MergeSort (int A，int low，int high) int middle; if (lowhigh) middle=(low+high)/2; /取中点 MergeSort(A,low,middle); MergeSort(A,middle+1,high); Merge(A,low,middle,high); /合并算法 void Merge(int A，int low，int middle，int high) /合并过程描述：int i,j,k; int *B=new inthigh-low+1;i=low; j=middle+1; k=low; while(i=middle&j=high) /两个子序列非空 if(Ai=Aj) Bk+=Ai+; else Bk+=Aj+; while (i=middle) Bk+=Ai+;/子序列Alow，middle非空，将A复制到Bwhile (j=high) Bk+=Aj+; /子序列Amiddle+1， high非空，将A复制到Bfor(i=low;i时，T(n)=2 T(n/2) + O(n) =2 (2T(n/22)+O(n/2) ) + O(n) =22T(n/22) + 2 O(n) =23T(n/23) + 3O(n) = =2x T(n/2x) + x*O(n)分解到最后只有2个元素可以求解，n/2x1， x=logn; 故 T(n)=n*T(1)+n*logn ，故时间复杂度记为：O（n * logn）、金块问题（求最大最小元问题）老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。要求：）设计一算法求解该问题？ （分治法解） ）计算其时间复杂度？(要求写出递推公式，及其求解过程)答：递归求取最大和最小元素 maxmin （int i, int j ,float &fmax, float &fmin） int mid; float lmax, lmin, rmax, rmin;if (i=j) fmax= ai; fmin=ai; /只有1个元素 else if (i=j-1) /只有2个元素 if(airmax) fmax=lmax; /合并取大 else fmax=rmax; if(lminrmin) fmin=rmin; /合并取小 else fmin=lmin; u 分析该算法时间复杂度：令T(n)为元素个数为n时所需比较次数（时间）：当n=2时，查找查找最大最小元只需要1次比较，T(2)=1； 时间复杂度记为O(1)。当n2时， T(n)=2T(n/2) + 2 T(2) =4T(n/4) + 4 T(2) + 2 T(2) =8T(n/8) + 8 4 2 = =2x T(n/2x) + 2x +2x-1+8+4+2分解到最后只有2个元素可以求解，n/2x2， T(n)= 2x *1 + 2x +2x-1 + 22 + 21 = 2x *1 +(2- 2x*2 )/(1-2） = 2x + 2x+1 - 2 =3n/2 - 2故时间复杂度记为：O（n）、用分治思想设计一个有效的算法，可以进行两个n位大整数的乘法运算？ 并计算其时间复杂度？（要求写出递推公式，及其求解过程） 答： int mult( int x, int y, int n) /x, y为两个n位整数 s=sign(x)*sign(y); /s为x* y的符号 x=abs(x); y=abs(y); int mul;if( n=1) mul=s*x*y; return mul; else / 计算XY = ac 2n + (a-b)(d-c)+ac+bd) 2n/2 + bd int a=x左边n/2位； / 移位操作，把X分为2块 int b=x右边n/2位； int c=y左边n/2位； /移位操作，把Y分为2块 int d=y右边n/2位； int m1= mult( a, c, n/2); / a, c还不够小继续分为2块,直到最后11位 int m2= mult( a-b, d-c, n/2); int m3= mult( b, d, n/2); mul=s*( m1*2n+(m1+m2+m3)*2n/2+m3 ); return mul; 、设计一棋盘覆盖问题算法（分治法）？ 并计算其时间复杂度？（要求写出递推公式，及其求解过程） 在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。（该算法中可能用到的变量：tr ：棋盘中左上角方格所在行；tc ：棋盘中左上角方格所在列。 dr： 残缺方块所在行；dl ：残缺方块所在列。size:棋盘的行数或列数；用二维数组board ，模拟棋盘。）答：void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; /size:棋盘行数 int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr tr + s & dc tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else / 此棋盘中无特殊方格 boardtr + s - 1tc + s - 1 = t; / 用 t 号L型骨牌覆盖右下角 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆盖其余方格 / 覆盖右上角子棋盘 if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 boardtr + s - 1tc + s = t; / 用 t 号L型骨牌覆盖左下角 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖其余方格 / 覆盖左下角子棋盘 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else boardtr + stc + s = t; / 用 t 号L型骨牌覆盖左上角 chessBoard(tr+s, tc+s, tr+s, tc+s, s); / 覆盖其余方格 第三章动态规划算法、动态规划算法基本思想？动态规划算法与分治算法异同点？适合用动态规划算法求解问题的基本要素？动态规划算法的基本步骤？答：1）基本思想：将待求解问题分解成若干个子问题；由于子问题有重叠，动态规划算法能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算. 2）相同：都是将原问题分解成小问题，通过小问题求解得到原问题解。不同： 用分治法求解时,分解的子问题是互相独立的,且与原问题类型一致。分治算法实现一般用递归； 动态规划方法经分解得到的子问题往往不是互相独立的；动态规划算法实现一般用循环; 3）基本要素：具有最优子结构；子问题具有重叠性4）步骤：1)分析最优解的性质，并刻划其结构特征。 2)递推地定义最优值。 3)以自底向上的方式计算出最优值. 4)根据计算最优值时得到的信息，构造问题的最优解. 、序列X=X1，X2,Xm 和 Y=Y1,Y2Yn的最长公共子序列为Z=Z1,Z2,Zk用动态规划的方法求序列 X 和Y的最长公共子序列长度？（要求按照动态规划写出动态规划求解问题的步骤分析最优子结构写出递归方程算法描述） 注：C 记录序列X与Y的最长公共子序列的长度答：最优子结构设序列X= x1，x2，xm 与 序列Y= y1，y2，yn 的一个 最长公共子序列Z= z1，z2，zk 、若xm= yn, 则zk=xm= yn, 且 z1，z2，zk-1 是序列Xm-1与 序列Yn-1 的最长公共自序列；、若xmyn, 且xm zk, 则Z是Xm-1与Y的最长公共子序列；、若xmyn, 且yn zk, 则Z是X与Yn-1的最长公共子序列; 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀（去掉一个元素）的最长公共子序列。 即，原问题最优解，包含子问题最优解； 因此，最长公共子序列问题具有最优子结构性质。 写出递归方程 循环实现，计算最优值C i j，算法描述Int lcsLength( x , y , b ) int m=x.length-1; n=y.length-1; for(int i=1; im;i+) Ci0=0; /y序列空 for(int i=1; in;i+) C0i=0; /x序列空 for (int i = 1; i = m; i+) /x序列长为 for (int j = 1; j =cij-1) Cij=Ci-1j; bij=2; else Cij=Cij-1; bij=3;return Cmn;u 时间复杂度分析：该算法时间复杂度：O(m*n)构造最长公共子序列，算法描述：void LCS (char X i, Y j, int b ) if (i =0 | j=0) return; if (b i j= 1) LCS( X i-1, Y j-1, b); system.out.print( x i ); else if (b i j= 2) LCS(Xi-1，Y j，b); else if (b i j= 3) LCS(X i ，Yj-1, b);u 时间复杂度分析：此算法每一次递归调用使得i或j减，因此该算法时间复杂度为O(m+n)、长江游艇俱乐部在长江上设置了n个游艇出租站1,2n.游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i，j)，其中1=ij=n；试设计一个算法，计算出游艇从出租站1到出租站n所需最少租金？（见习题集第三章算法设计与计算题T2）4、掌握动态规划方法求解背包问题？ 答：分析问题的最优解结构设（y1,y2,yn）所给01背包容量为M的解；则，（y2,yn）相应子问题背包容量为Mw1的解； （即原问题最优解，包含了子问题最优解） 递归定义最优值计算最优值m(i，j) void knapsack( int v , int w , int M, int m )int n=v.length; if ( M=w n) m n M=v n; M=M-w n; for( int i=n-1; i=1; i-) / in时，xixn多个物品 if (M=w n) m i M=math.max( m i+1 M, m i+1M-w i+vi); M=M-w i; u 该算法时间复杂度：O(c*n) c常数构造最优解void trackack( int m , int w , int M, int x )/x i标记i是否放入背包 int n=w.length; for( int i=1; i0)? 1:0 ; /判断第n个物体是否放入背包 u 该算法时间复杂度：O(n) 第 4 章 贪心算法1、 贪心算法基本思想？答：从问题的初始解出发逐步逼近给定的目标，每一步都做出当前看来是最优的选择（贪心选择），最终得到整个问题的最优解2、 贪心算法的基本要素？答：贪心选择性； 最优子结构3、 贪心算法与动态规划算法的异同?答：1 ） 相同点：对于要求解的问题都具有最优子结构；2 ）不同点： 算法的基本思想不同； 求解问题的类型不同；例：普通背包问题贪心算法求解0-1背包问题动态规划算法求解4、设计普通背包装载问题的贪心算法? 并分析其时间复杂度？答：float greedy_knapsack ( float M, float w , float p , float x ) / M 背包载重 x 背包问题最优解, w 物品重量， P 物品价值 int n=w.length; /n物品的个数 float pp=0; /pp计算当前背包总价值 float mmM; /mm背包剩余载重for( int i=1;i=n; i+ ) float ww i= p i / w i； /计算物品单位价值ww x i=0; /初始化，所有物品没有放入背包Mergesort (w i , ww i，n ); /按单位价值将物品排序，便于贪心选择for( int i=1; i=n; i+ ) /贪心选择，总是选择价值最大放入背包 if ( w i=mm ) /当前物品小于背包剩余载重 x i=1; mm=mm - w i; pp=pp + p i; /整个放入背包 else x i=mm/w i; pp=pp + x i*p i; break; /i部分放入背包 return pp;该算法主要包括以下几部分： 计算物品单位价值时间，其时间复杂度O(n)； 按照物品单位价值排序时间，其时间复杂度为O(n*logn);(合并排序时间) 贪心选择时间，其时间复杂度为O(n)；故该算法的时间复杂度为：O(n*logn+2n)；记为： O(n*logn)5、设计找零问题的贪心算法? 并分析其时间复杂度？答：void greedy_zhaoling ( float GZ, int B , int S ) /GZ应发工资 B j初始化排序；/为了贪心选择，依次选最大币种 for( j=1, j=6;j+) S j=0； /初始化S j A=GZ/B j; /A表示对应j币种张数 S j=A; /S j存放对应j币种总张数 GZ=GZ-A*B j; /每求出一种面额所需的张数后， 一定要把这部分金额减去： for(i=1;i=6;i+) print( B i, “-”, S i); /输出币种和对应张数 6、设计活动安排问题的贪心算法? 并分析其时间复杂度？答：伪代码：Int greedyselector(int s , int f , boolean a )int n=s.length; /n活动的个数 ；a 按活动结束时间递增排序；/便于贪心选择a1=true; /活动被选中int j=1; /j记录最近加入活动集合A的活动j int count=1; /count存储相容活动个数for(int i=2; i=n; i+)/贪心选择从活动j=2n判是否可加入A if( 活动i的开始时间，大于最近活动j的结束时间 )将活动i加入活动集合A； j=i; /活动i作为最近加入活动集合A的最近活动 count+; else 活动i不加入活动集合A；return count;程序设计语言：Int greedyselector(int s , int f , boolean a ) int n=s.length; /n活动的个数 Mergesort (a ,f , n ); /按活动结束时间排序，便于贪心选择 a1=true; /活动被选中int j=1; /j记录最近依次加入活动集合A的活动j int count=1; /count存储相容活动个数for(int i=2; i=f j ) a i=true; /将活动i加入活动集合A j=i; /活动i作为最近加入活动集合A的最近活动 count+; else a i=false; / s i=f j） 时间复杂度为：O(n-1);故本算法的时间复杂度： O(n*lognn-1)；记为： O(n*logn)。7、掌握例dijkstra算法的求单源最短路径问题。算法设计？求解过程？答:void dijkstra (int v, float a, float dist) /v表示源,aij表示边i到j的权值 /disti记录源到顶点i的最短路径长度/previ记录顶点i的前一个点,可以找出最短路径int n=dist.length;boolean s ; /si标记顶点i是否加入顶点集合sif( vn) return; /源点v不存在for(int i=1;i=n;i+) disti=avi; /初始化数组disti、si si=false; if(disti=max-value) /源到顶点i没有边 previ=0; else previ=v; distv=0; sv=true; /把源v加入到集合s中for(int i=1; in; i+)/剩下n-1个顶点，每次选择一个加入s中float tempmax-value; int u=v; for(int j=1;j=n;j+) /贪心选择，计算V-S中顶点的dist 值，选择最小的那个顶点jif( (!sj) &(distjtemp) ) u=j; temp=distj; su=true; /