个人精品文档资料
４、金块问题（求最大最小元问题）
老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。
要求：１）设计一算法求解该问题？ （分治法解）
２）计算其时间复杂度？(要求写出递推公式，及其求解过程) 答：递归求取最大和最小元素
maxmin （int i, int j ,float &fmax, float &fmin） { int mid; float lmax, lmin, rmax, rmin;
if (i=j) {fmax= a[i]; fmin=a[i];} //只有1个元素 else if (i=j-1) //只有2个元素
if(a[i] maxmin （i，mid，lmax，lmin）;//递归调用算法求最大最小 maxmin （mid+1，j，rmax，rmin）;//递归调用算法求最大最小 if(lmax>rmax) fmax=lmax; //合并取大 else fmax=rmax; if(lmin>rmin) fmin=rmin; //合并取小 else fmin=lmin; } ? 分析该算法时间复杂度： 令T(n)为元素个数为n时所需比较次数（时间）： 当n=2时，查找查找最大最小元只需要1次比较，时间复杂度记为O(1)。 当n>2时， 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/2x ＝2， 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; } 欢迎大家下载学习 T(2)=1； 并计算6 个人精品文档资料 else // 计算XY = ac 2 + ((a-b)(d-c)+ac+bd) 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块,直到最后1×1位 int m2= mult( a-b, d-c, n/2); int m3= mult( b, d, n/2); nn/2 mul=s*( m1*2+(m1+m2+m3)*2+m3 ); return mul; } } nn/2 ６、设计一棋盘覆盖问题算法（分治法）？ 并计算其时间复杂度？（要求写出递推公式，及其求解过程） kk 在一个2×2 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的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) // 特殊方格在此棋盘中 欢迎大家下载学习 7 个人精品文档资料 chessBoard(tr, tc, dr, dc, s); else {// 此棋盘中无特殊方格 board[tr + s - 1][tc + s - 1] = t; // 用 t 号L型骨牌覆盖右下角 chessBoard(tr, tc, tr+s-1, tc+s-1, s);} // 覆盖其余方格 // 覆盖右上角子棋盘 if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else {// 此棋盘中无特殊方格 board[tr + s - 1][tc + s] = t; // 用 t 号L型骨牌覆盖左下角 chessBoard(tr, tc+s, tr+s-1, tc+s, s);} // 覆盖其余方格 // 覆盖左下角子棋盘 if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s); else { board[tr + s][tc + s - 1] = t; // 用 t 号L型骨牌覆盖右上角 chessBoard(tr+s, tc, tr+s, tc+s-1, s);} // 覆盖其余方格 // 覆盖右下角子棋盘 if (dr >= tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else { board[tr + s][tc + s] = t; // 用 t 号L型骨牌覆盖左上角 chessBoard(tr+s, tc+s, tr+s, tc+s, s);} // 覆盖其余方格 } 第三章动态规划算法 １、动态规划算法基本思想？ 动态规划算法与分治算法异同点？ 适合用动态规划算法求解问题的基本要素？ 动态规划算法的基本步骤？ 答：1）基本思想：将待求解问题分解成若干个子问题；由于子问题有重叠，动态规划 欢迎大家下载学习 8 个人精品文档资料 算法能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算. 2）相同：都是将原问题分解成小问题，通过小问题求解得到原问题解。 不同： ? 用分治法求解时,分解的子问题是互相独立的,且与原问题类型一致。分治 算法实现一般用递归； ? 动态规划方法经分解得到的子问题往往不是互相独立的；动态规划算法实 现一般用循环; 3）基本要素：具有最优子结构；子问题具有重叠性 4）步骤：1)分析最优解的性质，并刻划其结构特征。 2)递推地定义最优值。 3)以自底向上的方式计算出最优值. 4)根据计算最优值时得到的信息，构造问题的最优解. ２、序列X={X1，X2,…Xm }和 Y={Y1,Y2…Yn}的最长公共子序列为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 的最长公共自序列； Ⅱ、若xm≠yn, 且xm≠ zk, 则Z是Xm-1与Y的最长公共子序列； Ⅲ、若xm≠yn, 且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; i 欢迎大家下载学习 9 个人精品文档资料 for (int j = 1; j <= n; j++) //ｙ序列长为n if (x[i]==y[j]) { C[i][j]=C[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { C[i][j]=C[i-1][j]; b[i][j]=2;} else { C[i][j]=C[i][j-1]; b[i][j]=3;} return C[m][n]; } ? 时间复杂度分析：该算法时间复杂度：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(X[i-1]，Y[ j]，b); else if (b[ i][ j]== 3) LCS(X[ i] ，Y[j-1], b); } ? 时间复杂度分析： 此算法每一次递归调用使得i或j减１，因此该算法时间复杂度为O(m+n) ３、长江游艇俱乐部在长江上设置了n个游艇出租站1,2…n. 游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。 游艇出租站i到游艇出租站j之间的租金为r(i，j)，其中1<=i （见习题集第三章算法设计与计算题T2） 4、掌握动态规划方法求解０－１背包问题？ 答：①分析问题的最优解结构 设（y1,y2,…yn）所给0－1背包容量为M的解； 则，（y2,…yn）相应子问题背包容量为M－w1的解； （即原问题最优解，包含了子问题最优解） ②递归定义最优值 欢迎大家下载学习 10
算法设计与分析习题 - 图文
