算法设计与分析d卷及答案

1、算法设计与分析试题D及答案1 .填空题：(第小题每题4分，共20分)1 .一个算法的优劣通常用 时间复杂度和空间复杂度 来度量。2 .递归函数的两大基本要素是递归方程 和 边界条件。3 .贪心算法和动态规划算法都要求问题具有共同的性质是最优子结构性质 。4 .实例特征是指_决定问题规模的因素，如输入数的大小及数据的数量等 。5 .在回溯法中，一个问题的解空间是指一个大的决策可由若干小的决策组成， 所有可能的决策序列 构成该问题的解空间。具有 限界函数 的深度优先生成法称为回溯法。2 .简答题：(每题5分，共20分)1 .分支限界法与回溯法的不同主要表现在两个方面。(1)求解目标：回溯法的求解目

2、标是找出解空间树中满足约束条件的所有解，而分支限界 法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意 义下的最优解。(2)搜索方式的不同：回溯法常以深度优先的方式搜索解空间树，而分支限界法则以广度 优先或以最小耗费优先的方式搜索解空间树。2 .给定如下二分搜索算法，请分析算法的复杂性。int BinarySearch(Type a口，const Type& x, int l, int r)while (r >= l)int m = (l+r)/2;if (x = am) return m;if (x < am) r = m-1; else l

3、= m+1;return -1;每执行一次算法的 while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了 O(logn)、次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为 O(logn)3 .什么是贪心选择性质和最优子结构性质？当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心 选择来达到。4.动态规划算法的基本思想是什么？它和分治法有什么区别和联系？答：动态规划算法的基本思想为：该方法的思路也是将待求解的大问题分成规模较小的子问题，但所得的

4、各子问题之间有重复子问题，为了避免子问题的重复计算，可依自底向上的方式计算最优值，并根据子问题的最优值合并得到更大问题的最优值，进而可 构造出所求问题的最优解。分 治 法 也是将待求解的大问题分成若干个规模较小的相同子问题，即该问题具有最优子结构性质。规模缩小到一定的程度就可以容易地解决。所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题；利用该问题分解出的子问题的解可以合 并为该问题的解。三算法分析解答题：( (每小题20 分 , 共 60 分) )1 .给定给的n个作业1 , 2, 3,，n,每个作业所需处理的时间是Ti, T2,，Tn.请设计一个算法，给出作业调度方案，使

5、n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。写出求解问题的贪心算法。解：这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题，用贪心选择策略有时可以设计出较好的近似算法。采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。int Min(int E,m)k=0;min=maxint;for(i=1;i<=m;i+) if Ei< min min=Ei;k=i return k;void treat(int T,int Q, int E,

6、int n, int m)Sort(T, t, n); / h(i)=作业 i 的排序序号, 按需要的处理时间的升序排序。for (int i = 1; i <= m; i+) Ei=0;for (int j = 1; j <=n; i+) Qij = -1; for (int i = 1; i <= n; i+) k=Min(E,m) ;Qkhi = i; / 作业 i 分配给机器k 处理Ek+=Ti; Totalt=0;for (int i = 1; i <= m; i+) if Totalt < Ei Totalt = Ei;/ Totalt= 由m台机器加

7、工处理完 n个作业所需的时间。2 .给定n种物品和一背包。物品i的重量是wi,其价值为vi ,背包的容量为 C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?请写出动态规划算法求解0-1 背 包问题。解答：1）定义最优值设m（i, j）是背包容量为j ,可选择物品为i , i+1 ,，n时0-1背包问题的最优解的值。由 0-1 背包问题的最优子结构性质，可以建立计算m（i ， j） 的递归式如下：m(i,j)maxm(i 1, j),m(i 1, j m(i 1,j)wi) vi cjwii ii (1)0 jwivnjwnm(n,j)0n 0 j nwn(2)2) 计算最优值v

8、oid knapsack(int v , int w , int c, int m )int n=v.length-1;int jMax=min(wn-1,c);/进行(1)式赋值for( int j=0; j<=jMax; j+) mnj=0;for( int j=wn; j<=c; j+) mnj=vn;/进行(2)式赋值for( int i=n-1; i>1; i-) /当0<=j<wn/ j 为背包容量/当 wn <= j ， m(n,j) 赋值jMax=min(wi-1,c);for( int j=0; j<=jMax; j+) mij=mi

9、+1j;for(int j=wi; j<=c; j+)/当0<=j<wi/当 wi <= j <= cmij=max(mi+1j, mi+1j-wi+vi);m1c=m2c;/当0<=j<w1if (c>=w1)/当w1 <= jm1c=max(m1c, m2c-w1+v1);3) 根据最优值计算最优解void traceback( int m , int w , int c, int x ) int n=w.length-1;for(int i=1; i<n; i+)if (mic=mi+1c) xi=0;else xi=1; c-=wi; xn=(mnc>0)? 1:0;/物品 i 没有被选择33 .设有n件工作分配给n个人。将工作i分配给j个人所需的费用为 Cj .现要求为每 个人都分配1件不同的工作，并使总费用达到最小。1）画出该问题的解空间树;2）设计回溯算法求解该问题解答：1）该问题的解空间树是一棵排列树，4件工作分配给4个人的排列树如下:2)参考代码如下：Void backtrack(int t)if ( t>n ) Compute。；elsefor (int j=t; j<=n; j+)swap(rt,rj);backtrack(t