个人精品文档资料
《算法设计与分析》习题
第一章算法引论
1、 算法的定义？
答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。
通俗讲，算法：就是解决问题的方法或过程。
2、 算法的特征？
答：1)算法有零个或多个输入； ２)算法有一个或多个输出； 3)确定性 ； ４)有穷性
3、 算法的描述方法有几种？
答：自然语言、图形、伪代码、计算机程序设计语言
4、 衡量算法的优劣从哪几个方面？
答：(1) 算法实现所耗费的时间（时间复杂度）； (2) 算法实现所所耗费的存储空间（空间复杂度）； (3) 算法应易于理解，易于编码，易于调试等等。
5、 时间复杂度、空间复杂度定义？
答：指的是算法在运行过程中所需要的资源（时间、空间）多少。
6、时间复杂度计算：
{i=1； while（i<=n）
i=i*2； } 答：语句①执行次数1次，
语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n; 算法执行时间： T(n)= 2log2n +1 时间复杂度：记为O(log2n) ；
7.递归算法的特点？
答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件）
②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式）
8、算法设计中常用的算法设计策略？
答：①蛮力法； ②倒推法； ③循环与递归； ④分治法； ⑤动态规划法； ⑥贪心法； ⑦回溯法； ⑧分治限界法
9、设计算法：
递归法：汉诺塔问题？兔子序列（上楼梯问题）？ 整数划分问题？
蛮力法：百鸡百钱问题？
倒推法：穿越沙漠问题？
欢迎大家下载学习
1
个人精品文档资料
答：算法如下： （1） 递归法
? 汉诺塔问题
void hanoi(int n, int a, int b, int c) {if (n > 0) {
hanoi(n-1, a, c, b); move(a,b);
hanoi(n-1, c, b, a); } }
? 兔子序列（fibonaci数列 ）
递归实现：
Int F(int n) {
if(n<=2) return 1; else
return F(n-1)+ F(n-2); }
? 上楼梯问题 Int F(int n) {
if(n=1) return 1 if(n=2) return 2; else
return F(n-1)+ F(n-2); }
? 整数划分问题
问题描述：将正整数n表示成一系列正整数之和，n=n1+n1+n3+…
将最大加数不大于m的划分个数，记作q(n,m)。正整数n的划分数p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系： 1n?1,m?1? ?q(n,n)n?m?q( n,m)??1?q(n,n?1)n?m?
?n?m?1?q(n,m?1)?q(n?m,m)
递归算法：
Int q( int n, int m){
if(n<1||m<1) return 0; If((n=1)||(m=1)) return 1; If (n return q(n,m-1)+q(n-m,m); } 欢迎大家下载学习 2 个人精品文档资料 （2） 蛮力法：百鸡百钱问题 算法设计1： 设x，y，z分别为公鸡、母鸡、小鸡的数量。 约束条件： x+y+z=100 且 5*x+3*y+z/3=100 main( ) { 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\； print(the hen number is\； print(the chick number is \} 算法分析：以上算法需要枚举尝试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\； print(the hen number is\； print(the chick number is \ } } 算法分析：以上算法只需要枚举尝试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 ( dis<1000) { print(“storepoint”,k,”distance”, 1000-dis,”oilquantity”,oil) //1000- dis则表示距起点的距离， 欢迎大家下载学习 3 个人精品文档资料 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、改写二分查找算法：设a[1…n]是一个已经排好序的数组，改写二分查找算法: ? 当搜索元素x不在数组中时，返回小于x的最大元素位置i，和大于x的最小元素位置j； (即返回x的左、右2个元素) ? 当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。 并计算其时间复杂度？ 答： 欢迎大家下载学习 4 个人精品文档资料 ３、设计一个合并排序的算法？（分治法解） 并计算其时间复杂度？(要求写出递推公式，及其求解过程) 答： 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） 欢迎大家下载学习 5 个人精品文档资料 ４、金块问题（求最大最小元问题） 老板有一袋金块(共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 个人精品文档资料 ③计算最优值m(i，j) void knapsack( int v[ ], int w[ ], int M, int m[ ] [ ] ) {int n=v.length; if ( M { m[ n][ M]=v[ n]; M=M-w[ n]; } for( int i=n-1; i>=1; i--) // i m[ i] [M]=m[ i+1][ M]; else if (M>=w[ n]) { m[ i][ M]=math.max( m[ i+1][ M], m[ i+1][M-w[ i]+v[i]); M=M-w[ i]; } } } ? 该算法时间复杂度：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; i { x[ i]=1; M=M-w[ i]; } } x[ n]=(m[ n][ M]>0)? 1:0 ; //判断第n个物体是否放入背包 } ? 该算法时间复杂度：O(n) 第 4 章 贪心算法 1、 贪心算法基本思想？ 答：从问题的初始解出发逐步逼近给定的目标，每一步都做出当前看来是最优的选择（贪心选择），最终得到整个问题的最优解 2、 贪心算法的基本要素？ 答：贪心选择性； 最优子结构 3、 贪心算法与动态规划算法的异同? 答：1 ） 相同点： 对于要求解的问题都具有最优子结构； 2 ）不同点： 算法的基本思想不同； 求解问题的类型不同； 例：普通背包问题 贪心算法求解 欢迎大家下载学习 11 个人精品文档资料 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 mm＝M; //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[ ]按活动结束时间递增排序；//便于贪心选择 a[1]=true; //活动１被选中 欢迎大家下载学习 12 个人精品文档资料 int j=1; //j记录最近加入活动集合A的活动j int count=1; //count存储相容活动个数 for(int i=2; i<=n; i++)//贪心选择从活动j=2…n判是否可加入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 ); //按活动结束时间排序，便于贪心选择 a[1]=true; //活动１被选中 int j=1; //j记录最近依次加入活动集合A的活动j int count=1; //count存储相容活动个数 for(int i=2; i<=n; i++) //贪心选择从活动i=2…n判是否可加入A { if( s[ i]>=f[ j] ) { a[ i]=true; //将活动i加入活动集合A j=i; //活动i作为最近加入活动集合A的最近活动 count++; } else a[ i]=false; // s[ i] return count; } 该算法主要包括２部分： ? 按照按活动结束时间对活动排序时间，其时间复杂度为：O(n*logn)； ? 贪心选择时间，其需要经过n-1次的比较（s[ i]>=f[ j]） 时间复杂度为：O(n-1); 故本算法的时间复杂度： O(n*logn＋n-1)； 记为： O(n*logn)。 7、掌握例dijkstra算法的求单源最短路径问题。 算法设计？求解过程？答: void dijkstra (int v, float a[][], float dist[]) { //v表示源,a[i][j]表示边i到j的权值 //dist[i]记录源到顶点i的最短路径长度 //prev[i]记录顶点i的前一个点,可以找出最短路径 int n=dist.length; boolean s[ ]; //s[i]标记顶点i是否加入顶点集合s if( v<1 || v>n) return; //源点v不存在 for(int i=1;i<=n;i++) 欢迎大家下载学习 13 个人精品文档资料 { dist[i]=a[v][i]; //初始化数组dist[i]、s[i] s[i]=false; if(dist[i]=max-value) //源到顶点i没有边 prev[i]=0; else prev[i]=v; } dist[v]=0; s[v]=true; //把源v加入到集合s中 for(int i=1; i for(int j=1;j<=n;j++) //贪心选择，计算V-S中顶点的dist[ ]值，选择最小的那个顶点j if( (!s[j]) &&(dist[j] s[u]=true; //源到顶点u的最短路径已经确定，u加入到s中 for(int j=2;j<=n;j++) //根据u重新计算dist[ ] if( (!s[j]) &&(a[u][j]< max-value) //u到j有边 float newdist=dist[u]+a[u][j]; if(newdist 该算法主体有两重循环，故该算法的时间复杂度记为O(n2 ) 8、P126图４－８求最小生成树，写出其prim算法？ 并给出其选边过程? 答： prim算法描述(伪代码) void prim(int n, float c[][])//c[][]存储边权值 { T=空集； //T表示最小生成树的边集合 S={ 1 }; //S表示最小生成树包含的顶点集合 while( S!=V ) {选择边（i，j），i∈S 且j ∈V-S；且权值c[i][j]最小； //贪心选择 T=T∪ {（i，j）}; S=S∪{ j }； } } 欢迎大家下载学习 14 个人精品文档资料 prim算法描述(程序设计语言) Void prim (int n, float c[][]) {float lowcost[ ]; float closest[ ]; boolean s[ ]; s[1]=true; //初始化，顶点1加入生成树集合s for(int i=2;i<=n;i++) //初始化，计算与顶点1相邻顶点边权值 { lowcost[i]=c[1][i]; colsest[i]=1; s[i]=false; } for(int i=1;i for( int k=2;k<=n; k++) //贪心选择,v-s中找使lowcost[]最小的顶点k if((lowcost[k] s[j]=true; //把找到的顶点j加入到生成树集合s中 for(int k=2;k<=n; k++) //根据刚加入的顶点修改lowcost, closest if((c[j][k] {lowcost[k]=c[j][k]; closest[k]=j;} } } 该算法主体有两重循环，故该算法的时间复杂度记为O(n2 ) Prim算法执行过程： 首先，找出V-S中使lowcost值最小的顶点j(距离s最近的顶点j); 然后，根据数组closest选取边(j,closest[j］)； 最后，将j添加到S中，并对closest和lowcost作必要的修改。 选边过程： 9、P126图４－８，利用kruskal算法求最小生成树， 给出其选边过程？ 答：伪代码： void krustral(int n, float c[][])//c[][]存储边权值 { mergesort（float c[][], T[]）; //按边权值排序 T=空集； //T表示最小生成树的边集合 while( |T| 欢迎大家下载学习 15 个人精品文档资料 {选择最小权值边（i，j）； //贪心选择 if(i∈T1&&j ∈T2) //边(i,j)一端i在T1分支,一端j在T２分支 { union(i,j); T=T∪{（i，j)} } else T=T∪{（i，j)}; } } 选边过程： 第５章 回溯算法 1、回溯法基本思想？回溯法解题步骤？ 答：基本思想：在搜索尝试中找问题的解，当不满足条件就”回溯”返回，尝试别的路径。 解题步骤：(1)针对所给问题，定义问题的解空间； (2)并确定易于搜索的解空间结构(排列树，子集树); (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数，剪去无效的枝，避免无效搜索。 2、什么叫子集树？什么叫排列树？ 什么叫满m叉树？ 答：1）子集树 ：当所给问题是在n个元素的集合S中找出S满足某种性质的子集时，其相应的解空间树称作子集树。 2）排列树 ： 当所给问题是在确定的n个元素满足某种性质的排列中搜索问题的解时，相应的解空间树被称作排列树。 3）满m叉树： 当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合。 这类问题的解空间树称为满m叉树。 3、利用回溯法，求解0－1背包问题，要求设计出相应算法？并分析其时间复杂度？ 答：算法描述（递归实现） double knaspack(double p[ ], double w[ ], double c) //c是背包载重 欢迎大家下载学习 16 个人精品文档资料 {double cw=0; //当前重量 double cp=0; //当前价值 double bestp=0; //当前最优装载价值 backtrack(1); //深度优先搜索解空间 return bestp; } double backtrack( int i) //搜索解空间函数 {double n=p.length; if ( i>n ) // i表示深度（层），i>n搜索到叶子节点 { bestp=cp; return bestp; } //否则，进入左子树向下深度搜索 else if (cw+w[ i]<=c) //当前物品放入背包不超载 { cw=cw+w[ i]; cp=cp+p[ i]; c=c-w[i]; backtrack(i+1); } //继续向下深度搜索 else //超载，则回溯进入右子树 if ( bound(i+1)>bestp ) //通过限界函数知道右子树可能包含最优解 //即，当前价值＋剩余物品价值大于bestp，进入右子树 backtrack( i+1 ); } double bound(int i) // 限界函数计算当前价值与剩余价值和 { double cleft = c - cw; // 剩余容量 double b = cp; // 当前物品价值 while (i <= n && w[ i] <= cleft) // 装载剩下的物品 { cleft = cleft -w[ i]; b= b + p[i]; i++; } // w[ i]> cleft 跳出循环，背包装满,物品部分装入背包 if (i <= n) b += p[i]/w[i] * cleft; return b; // 当前物品价值与剩余物品价值之和 } 算法分析： n 该算法计算上界函数bound时间复杂度为O(n); 在最坏的情况下，有2个右孩子节点 n 需要计算上界； 故该算法的时间复杂度为O(n*2) 4、利用回溯法，求解n后问题，要求设计出相应算法，并分析其时间复杂度？ 答：算法描述（递归实现） double nqueen(int nn) { int n=nn; int sum=0; // 放置皇后的方案数 int x[ n]; // x[ i]表示皇后i放在棋盘的第i行，第x[ i]列 欢迎大家下载学习 17 个人精品文档资料 for (int i=0;i<=n; i++;) x[ i]=0; // 初始化 backtrack(1); // 深度优先搜索解空间 return sum; } void backtrack ( int t) { if( t>n ) // 搜索到叶子节点，方案数＋1，t是层数 sum++; else for( int i=1; i<=n; i++) // for循环一一判断皇后所在列 { x[ t]=i; // 将第t个皇后放在t行(t不同)，i列 if( place(t) ) // 约束函数，判断是否有冲突 backtrack (t+1); // 放下一个皇后 } } void place( int k) // 约束函数 { for( int j=1;j if( (math.abs(k-j)=math.abs(x[ k]-x[ j])) || (x[ k]=x[ j]) ) //k与之前的皇后1…k-1不能在同一斜线 或 同一列 return false; else return true; } 算法分析 ： 对于n皇后问题的解空间共有n!个叶子节点，故排列树最多有n* n!个节点； 最坏的情况下每个节点都要用place函数判断是否可行，每一个节点判断时间为O(n)； 故该算法的时间复杂度记为O(n* n* n!) 第六章 分支限界算法 1、分支限界算法的解题步骤？ 答：1）针对所给问题，定义问题的解空间; 2）确定易于搜索的解空间结构(排列树，子集树); 3）以广度优先方式搜索问题的解空间； 4)在搜索过程中用限界函数，剪去无效的枝，避免无效搜索。 2、常用的两种分支限界算法？并说明其思想？ 答：1）队列式（FIFO先进先出）分支限界算法 将活动结点表组织成一个队列，并按照队列先进先出原则取下一个结点作为扩展结点 基本思想： ①开始，根结点是唯一的活结点，根结点入队列； 从活结点队中取出根结点后，作为当前扩展结点。 ②对当前扩展结点，先从左到右地产生它的所有儿子(分支)，用约束条件检查（限界），把所有满足约束函数的儿子结点加入活结点队列中。 欢迎大家下载学习 18 个人精品文档资料 ③再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。 2）优先队列式分支限界算法 将活结点表组织成一个优先队列（堆），并按照优先队列中规定的结点优先级，选取优先级最高的结点作为当前扩展结点。 基本思想： ①根结点是唯一的活结点，根结点入堆； 从活结点队中取出根结点后，作为当前扩展结点。 ②对当前扩展结点，先从左到右地产生它的所有儿子节点； 用约束条件检查（限界），把所有满足约束函数的儿子结点加入活结点表中（堆），并给每个结点设置优先级。 ③再从活结点表(堆)中取出堆顶结点(堆中优先级最高结点)为当前扩展结点，……，直到活结点表(堆)为空。 3、分支限界算法与回溯法异同？ 答：相同点：都属于搜索算法； 都需要在问题的解空间中搜索问题的解； 不同点： 1）求解目标不同： 回溯法求解目标是找出解空间树中满足约束条件所有解； 分支限界法求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2）搜索方式的不同： 回溯法以深度优先的方式搜索解空间树； 分支限界法则以广度优先的方式搜索解空间树。 4、 利用优先队列分支限界算法，设计0－1背包问题算法？ 答：队列式分支限界算法（无限界函数） double knaspack(double p[ ], double w[ ], double c) {double cw=0; //当前重量 double cp=0; //当前价值 double bestp=0; //当前最优装载价值 backtrack(1); //分支限界法搜索 解空间 return bestp; } double backtrack( int i) { while (true) //队列不空 { // 检查左儿子结点 if (ew + w[i] <= c) enQueue(ew + w[i], i); // 左儿子加入队列 //进入右孩子，右儿子结点总是可行的，无上界函数 enQueue(ew, i); // 右儿子加入队列 ew = ((Integer) queue.remove()).intValue();// 取队首下一扩展结点 if (ew == -1) // 同一层尾部标记ew = -1：同一层结点处理结束 { if (queue.isEmpty()) return bestw; //判断队列是否为空 欢迎大家下载学习 19 个人精品文档资料 else { queue.put(new Integer(-1)); } // 同层结点尾部标志 ew = ((Integer) queue.remove()).intValue(); // 取下一扩展结点 i++; // 进入下一层 } } } 队列式分支限界法（带上界函数） double knaspack(double p[ ], double w[ ], double c) {double cw=0; //当前重量 double cp=0; //当前价值 double bestp=0; //当前最优装载价值 backtrack(1); //分支限界法搜索解空间 return bestp; } double backtrack( int i) { while (true) //队列不空 { // 检查左儿子结点 if (ew + w[i] <= c) enQueue(ew + w[i], i); // 左儿子加入队列 //进入右孩子，计算上界函数，检查当前扩展结点的右儿子结点 up = Bound(i+1); if (up >= bestp) //右子树可能含最优解 enQueue(ew, i); //右儿子结点加入队列 ew = ((Integer) queue.remove()).intValue(); // 取队首下一扩展结点 if (ew == -1) // 同一层尾部标记ew = -1：同一层结点处理结束 { if (queue.isEmpty()) return bestw; //判断队列是否为空 else { queue.put(new Integer(-1)); } // 同层结点尾部标志 ew = ((Integer) queue.remove()).intValue(); // 取下一扩展结点 i++ // 进入下一层 } } } double bound(int i) // 计算上界函数 {// 计算当前价值与剩余价值和 double cleft = c - cw; // 剩余容量 double b = cp; // 当前物品价值 while (i <= n && w[ i] <= cleft) // 剩余物品单位重量价值递减序装入物品 { cleft = cleft -w[ i]; b= b + p[i]; i++; } // w[ i]> cleft 跳出循环，物品部分装入背包 if (i <= n) b += p[i]/w[i] * cleft; return b; // 当前物品价值与剩余物品价值之和 } n 时间复杂度分析：计算上界时间为O(n)；在最坏的情况下，有2个右孩子节点需要计算上 n 界； 故该算法的时间复杂度为O(n*2) 欢迎大家下载学习 20 个人精品文档资料 5、利用FIFO分支限界算法,给出下列0－1背包最优装载的求解步骤？ 背包载重：M＝10； 物品重量：w1＝6、w2＝5、w3＝5； 物品价值：p1＝42、p2＝25、p3＝30 解：1)解空间： 2）求解过程： 欢迎大家下载学习 21 个人精品文档资料 第8章 NP完全性理论 1、什么是易解问题？什么是难解问题？难解问题分为哪两类？ 答：1）易解问题：人们将存在多项式时间 算法的问题称为易解问题; 2）难解问题：将需要在指数时间内解决的问题称为难解问题； 3）难解问题有两类： 1）不可判定问题 2）非决定的难处理问题 。 2、什么是不可判定问题？什么是非决定的难处理问题？ 答：1）不可判定问题 ：该类问题是不能解问题，它们太难了，以至于根本就不存在能求解它们的任何算法。 2）非决定的难处理问题： 这类问题是可判定的（即可解的）。 但是，这类问题即使使用非决定的计算机，也不能在多项式时间内求解它们。 3、什么是P类问题？什么是NP完全问题？ 答：1）P类问题：是一类能够用确定性算法在多项式时间内求解的判断问题。事实上，所有易解问题都属于P类问题。 2）NP完全问题：对于某问题，很难找到其多项式时间的算法(或许根本不存在)，但是如果给了该问题的一个答案，则可以在多项式时间内判定或验证这个答案是否正确。 这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。 4、列出几个典型的NP完全问题？ 答：（1）图着色问题COLORING （2）路径问题LONG-PATH （3）顶点覆盖问题VERTEX-COVER （4）子集和问题SUBSET-SUM （5）哈密尔顿回路问题HAM-CYCLE （6）旅行商问题TSP （7）装箱问题BIN-PACKING ， 能否用k个箱子来装n个物品； 欢迎大家下载学习 22
算法设计与分析习题
