发布时间 : 星期一 文章算法设计与分析习题 - 图文更新完毕开始阅读4a2af42ba300a6c30c229f7f
公式，及其求解过程)
答：
void MergeSort (int A[]，int low，int high) { int middle;
if (low 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 int[high-low+1]; i=low; j=middle+1; k=low; while(i<=middle&&j<=high) { //两个子序列非空 if(A[i]<=A[j]) B[k++]=A[i++]; else B[k++]=A[j++]; } while (i<=middle) B[k++]=A[i++]; //子序列A[low，middle]非空，将A复制到B while (j<=high) B[k++]=A[j++]; /子序列A[middle+1， high]非空，将A复制到B for(i=low;i<=high;i++) A[i++]=B[i++]; //将合并后的序列复制回A } ? 合并排序算法运行时间T(n)的递归形式为： O(1)n=1?T(n)=? n>1?2T(n/2)+O(n) ? 分析该算法时间复杂度： 令T(n)为元素个数为n时所需比较次数（时间）： 当n=１时， 时间复杂度记为O(1)。 当n>１时，T(n)=2 T(n/2) + O(n) 2 =2 (2T(n/2)+O(n/2) ) + O(n) 22 =2T(n/2) + 2 O(n) 33 =2T(n/2) + 3O(n) =?? xx =2 T(n/2) + x*O(n) x 分解到最后只有2个元素可以求解，n/2＝1， 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= 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次比较，T(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 =?? xxxx-1 =2 T(n/2) + 2 +2+?+8+4+2 x 分解到最后只有2个元素可以求解，n/2＝2， xxx-12 1 T(n)= 2 *1 + 2 +2? + 2+ 2 xx = 2 *1 +(2- 2*2 )/(1-2） xx+1 = 2 + 2 - 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; } nn/2 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; } } ６、设计一棋盘覆盖问题算法（分治法）？ 并计算其时间复杂度？（要求写出递推公式，及其求解过程） 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) // 特殊方格在此棋盘中 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）基本思想：将待求解问题分解成若干个子问题；由于子问题有重叠，动态规划算法能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算.