当前位置：文档之家 › 《算法分析与设计》作业答案

《算法分析与设计》作业答案

  • 格式：doc
  • 大小：332.00 KB
  • 文档页数：15

《算法分析与设计》作业1、考虑,10≤≤i x 而不是x i ∈{0，1}的连续背包问题。

一种可行的贪婪策略是：按价值密度非递减的顺序检查物品，若剩余容量能容下正在考察的物品，将其装入；否则，往背包内装如此物品的一部分。

(a) 对于n=3，w=[100,10,10]，p=[20,15,15]，以及c=105，上述装入法获得结果是什么？(b)证明这种贪婪算法总能获得最优解。

(c) 用伪代码描述此算法。

答：（a ）利用贪婪算法，按价值密度考察的背包为w2，w3，w1；背包w2和w3重20，还可以容纳85，由于10≤≤i x ，背包w1还可以装入x1=0.85，则背包内物品总价值为15+15+20*0.85＝47.（b ）假设已按价值密度排好序，考察w1,w2,……,wi ，……，对应的价值为p1,p2,……,pi,……如果装到pi-1再装pi 时，恰好要取xi 个wi 。

（,10≤≤i x ） 因为比它价值密度大的都已装载完，所以此时获得的为最优解。

（c ）算法描述如下： template <class T>int ContainerLoading( int x[], T w[], T c, int n ) {int *t = new int[n+1]; IndirectSort(w, t, n); for( int i=1; i<=n; i++) x[i] = 0;for(i=1; i<=n && w[t[i]]<=c; i++){ x[t[i]] = 1; c += w[t[i]]; } delete []t; }2、证明当且仅当二分图没有覆盖时，下述算法找不到覆盖。

m＝0; //当前覆盖的大小对于A中的所有i，New[i]=Degree[i]对于B中的所有i，Cov[i]=falsewhile(对于A中的某些i，New[i]>0) {设v是具有最大的New[i]的顶点；C[m++]=v;for(所有邻接于v的顶点j) {If(!Cov[j]) {Cov[j] = true;对于所有邻接于j的顶点，使其New[k]减1}}}if (有些顶点未被覆盖) 失败else 找到一个覆盖2）给出一个具有覆盖的二分图，使得上述算法找不到最小覆盖。

证明：如果二分图有覆盖，则通过以上贪婪算法，总能得到最小覆盖A’。

首先假定A’为空集当更多的顶点可被覆盖时，把能覆盖未被覆盖的顶点数目最多的顶点加入A’如果有些顶点未被覆盖，则失败，否则总能找到一个覆盖。

所以只有当二分图没有覆盖时，才会失败而找不到覆盖，否则总能找到一个覆盖A’。

2）令S= {S1，. . .，S5 },U= { 4，5，. . .，15},S1 = { 4，6，7，8，9，1 3 }，S2 = { 4，5，6，8 }，S3 = { 8，1 0，1 2，1 4，1 5 }，S4 = { 5，6，8，1 2，1 4，1 5 }，S5 = { 4，9，1 0，11 }。

通过以上算法，得S ' = {S1，S2，S4，S5 }实际最小覆盖为{S1，S4，S5 }3、对于二分图覆盖问题设计另一种贪婪启发算法，贪婪准则是：如果B中某一个顶点被A中一个顶点覆盖，选择A中这个顶点；否则，从A中选择一个顶点，使得它所覆盖的未被覆盖的顶点数目最多。

给出这种贪婪算法的伪代码。

解答：贪婪算法的伪代码为:m=0 // 当前覆盖的大小对于A 中的所有i, Out[i]=outdegree[i];对于B 中的所有i, In[i]=indegree[i];对于B 中的所有i, Cov[i]=false;for (对于B中所有入度为1的顶点i) {设v是邻接于B[i]的顶点C[m++]=v;for (所有邻接于v的顶点j) {if (!Cov[j]) { Cov[j]=true;对于所有邻接于j的顶点，使其Out[k]减1} } }while (对于A 中的某些i, Out[i]>0) {设v是具有最大Out[i]的顶点C[m++]=v;for (所有邻接于v的顶点j) {if (!Cov[j]) { Cov[j]=true;对于所有邻接于j的顶点，使其Out[k]减1} } }if (有些顶点未被覆盖) 失败else 找到一个覆盖4、有n个硬币，其中1个是假币，且假币较轻。

请用分而治之方法设计一个找出假币的算法。

1）用伪代码描述你的算法；2）用C程序描述你的算法；3）分析你的算法的时间复杂性。

解答：代码如下Feit_money(low, high) // 假定伪币较真币轻{float mid;if high-low=1 thenif A[low]<A[high] then return A[low];else if A[low]>A[high] return A[high];elsemid=(low+high)/2;if (high-low+1)%2==0 thensum1=sum(low, mid);sum2=sum(mid+1, high);elsesum1=sum(low, mid-1);sum2=sum(mid+1, high);end ifif sum1=sum2 then return A[mid];else if sum1<sum2 then(high-low+1)%2==0? Feit_money(low, mid) : Feit_money(low, mid-1);elseFeit_money(mid+1, high);end ifend ifreturn 0;}其时间复杂度为：O(log n).用分而治之算法计算4823*9715；2）假设两个大整数都是n=2k位，请用伪代码描述两个大整数乘积的分而治之算法。

解答：1) 设X=4823, Y=9715，用上述算法计算XY的计算过程可列表如下，其中带'号的数值是在计算完成AC，BD，和(A-B)(D-C)之后才填入的。

X=4823 A=48 B=23 A-B=15Y=9715 C=97 D=15 D-C=82AC=(1643)' BD=(1107)' (A-B)(D-C)=(260)'XY=(4496)'104+[(4496)'+(345)'+(1230)']102 +(345)'=(45567445)'进一步拆分A=48 A1=4 B1=8 A1-B1=-4C=97 C1=9 D1=7 D1-C1=2A1C1=36 B1D1=56 (A1-B1)(D1-C1)=-8AC=3600+(36+56-8)10+56=4496B=23 A2=2 B2=3 A2-B2=-1D=15 C2=1 D2=5 D2-C2=4A2C2=2 B2D2=15 (A2-B2)(D2-C2)=-4BD=200+(2+15-4)10+15=345|A-B|=15 A3=1 B3=5 A3-B3=-4 |D-C|=82 C3=8 D3=2 D3-C3=-6 A3C3=8 B3D3=10 (A3-B3)(D3-C3)=24 (A-B)(D-C)=800+(8+10+24)10+10=1230 2)mul(x, y, n) {if (2<=n && x!=0 && y!=0) { k=n/2;p = power(10, k); b= x % p; a=x/p; d=y % p; c=y/p;ac=mul(a, c, k); bd=mul(b, d, k);mix=mul(a-b, d-c, k);return (ac*p+(mix+ac+bd)*p+bd); }else if (x==0||y==0) return 0;else x*y; }该算法的运行时间满足的递归方程为： ， 计算得其时间复杂度为：T(n)=O(3log2n)。

7、设计一个分而治之算法来计算二叉树中分支结点的个数。

请用伪代码描述你的算法。

请分析算法的时间复杂度。

解答：算法伪代码如下：int MaxSubSum(int a, int left, int right) { int sum=0;if (left==right)sum=a[left]>0?a[left]:0; else{int center=(left+right)/2;int leftsum=MaxSubSum(a,left,center);int rightsum=MaxSubSum(a,center+1,right); int s1=0;lefts=0;for (int i=center;i>=left;i--) { lefts+=a[i];if (lefts>s1) s1=lefts; }int s2=0;rights=0;for (int i=center+1;i<=right;i++) { rights+=a[i];if (rights>s2) s2=rights; }sum=s1+s2;11)()2/(3)1()(>=⎩⎨⎧+=n n n O n T O n Tif (sum<leftsum) sum=leftsum;if (sum<sightsum) sum=rightsum;}return sum;}算法时间复杂度为：8、货物装箱问题：设有一艘货船装货箱。

共有n=6件货箱，它们的重量如下表示：[w1,…, w6] = [100, 200, 50, 90, 50, 20]，船的限载重量是c=300。

试用贪婪算法装船，要求货箱装得最多。

贪婪准则：从剩下的货箱中选择重量最小的货箱。

1）请给出问题的解；2）对一般的n，重量为w=[w1,…, wn]，船的限载重量是c>0，要求船的货箱装得最多，请用伪代码描述你的算法；3）考虑有两条船的情况，即有两条船，船的限载重量是分别是c1和c2；共n件货箱，重量为w=[w1,…, wn]，试用贪婪算法装船，要求两条船的货箱装得最多。

请描述你的算法，该算法总能产生最优解吗？请说明你的理由。

解答：1）货箱按重量从小到大排列，得{20,50,50,90,100,200}.根据选择最小重量货箱的贪婪准则，则准箱顺序为{w6,w3,w5,w4,w1,w2}，因为船限载重量c=300，故实际装箱为w6,w3,w5,w4共4个货箱重210。

2）算法如下template <class T>int ContainerLoading( int x[], T w[], T c, int n ){ i nt *t = new int[n+1];IndirectSort(w, t, n);//对重量按间接寻址方式排序for( int i=1; i<=n; i++) x[i] = 0;for(i=1; i<=n && w[t[i]]<=c; i++){ x[t[i]] = 1; //t[i]是间接寻址表c -= w[t[i]]; }delete t[];}3）伪代码如下：void knapsack(int v[ ], int w[ ], int c, int m[ ][ ]) { int n=v.length-1;int jMax=min(w[n]-1,c);for( int j=0; j<=jMax; j++) m[n][j]=0;for( int j=w[n]; j<=2*w[n]-1; j++) m[n][j]=v[n];for( int j=2*w[n]; j<=c; j++) m[n][j]=2*v[n];for( int i=n-1; i>1; i--) { jMax=min(w[i]-1,c);for( int j=0; j<=jMax; j++) m[i][j]=m[i+1][j];for(int j=w[i]; j<=2*w[i]; j++)m[i][j]=max(m[i+1][j], m[i+1][j-w[i]]+v[i]);for(int j=2*w[i]; j<=c; j++)m[i][j]=max(m[i+1][j], m[i+1][j-w[i]]+v[i], m[i+1][j-2*w[i]]+2*v[i] ); }m[1][c]=m[2][c]; if (c>=2*w[1])m[1][c]=max(m[1][c], m[2][c-w[1]]+v[1], m[2][c-2*w[1]]+2*v[1]); else if (c>=w[1])m[1][c]=max(m[1][c], m[2][c-w[1]]+v[1]);} 显然，该算法能产生最优解。

合集下载

算法分析与设计作业参考答案

算法分析与设计作业参考答案

算法分析与设计作业参考答案《算法分析与设计》作业参考答案作业⼀⼀、名词解释：1.递归算法：直接或间接地调⽤⾃⾝的算法称为递归算法。

2.程序：程序是算法⽤某种程序设计语⾔的具体实现。

⼆、简答题：1.算法需要满⾜哪些性质？简述之。

答：算法是若⼲指令的有穷序列，满⾜性质：（1）输⼊：有零个或多个外部量作为算法的输⼊。

（2）输出：算法产⽣⾄少⼀个量作为输出。

（3）确定性：组成算法的每条指令清晰、⽆歧义。

（4）有限性：算法中每条指令的执⾏次数有限，执⾏每条指令的时间也有限。

2.简要分析分治法能解决的问题具有的特征。

答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩⼩到⼀定的程度就可以容易地解决；（2）该问题可以分解为若⼲个规模较⼩的相同问题，即该问题具有最优⼦结构性质；（3）利⽤该问题分解出的⼦问题的解可以合并为该问题的解；（4）该问题所分解出的各个⼦问题是相互独⽴的，即⼦问题之间不包含公共的⼦问题。

3.简要分析在递归算法中消除递归调⽤，将递归算法转化为⾮递归算法的⽅法。

答：将递归算法转化为⾮递归算法的⽅法主要有：（1）采⽤⼀个⽤户定义的栈来模拟系统的递归调⽤⼯作栈。

该⽅法通⽤性强，但本质上还是递归，只不过⼈⼯做了本来由编译器做的事情，优化效果不明显。

（2）⽤递推来实现递归函数。

（3）通过Cooper 变换、反演变换能将⼀些递归转化为尾递归，从⽽迭代求出结果。

后两种⽅法在时空复杂度上均有较⼤改善，但其适⽤范围有限。

三、算法编写及算法应⽤分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 dofor j ←1 to n-i do if a[j]交换a[j]、a[j+1]；分析该算法的时间复杂性。

答：排序算法的基本运算步为元素⽐较，冒泡排序算法的时间复杂性就是求⽐较次数与n 的关系。

（1）设⽐较⼀次花时间1；（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=in j i n 1)(1（3）外循环次数为：n-1，花时间为：2.设计⼀个分治算法计算⼀棵⼆叉树的⾼度。

算法分析与设计 第1章习题答案 1-1,1-2,1-3,1-6

算法分析与设计 第1章习题答案 1-1,1-2,1-3,1-6

第一章习题（1-1,1-2,1-3,1-6）1-1 求下列函数的渐进表达式3n2+10n = O(n2)n2/10+2n = O(2n)21+1/n = O(1)logn3 = O(logn)10log3n = O(n)知识点：如果存在正的常数C和自然数N0，使得：当N>=N0时有f(N)<=Cg(N)，则称f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)).这时，可以说f(N)的阶不高于g(N)的阶。

1-2 论O(1)和O(2)的区别O(1)和O(2)差别仅在于其中的常数因子，根据渐进上界记号O的定义可知，O(1)=O(2)。

1-3 从低到高排列以下表达式（按渐进阶排列以下表达式）结果：2 logn n2/320n 4n23n n! 分析：当n>=1时，有logn< n2/3当n>=7时，有3n < n!补充：当n>=4时，有logn> n1/31-6 对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=Θ(g(n))。

知识点：f(n)的阶不高于g(n)的阶：f(n)=O(g(n))；f(n)的阶不低于g(n)的阶：f(n)=Ω(g(n))；f(n)与g(n) 同阶：f(n)=Θ(g(n)) (1)f(n)= logn2 ; g(n)= logn+5f(n)与g(n)同阶，故f(n)=Θ(g(n)) (2) f(n)= logn2 ; g(n)= n1/2当n>=8时，f(n)<=g(n)，故f(n)=O(g(n))分析：此类题目不易直接看出阶的高低，可用几个数字代入观察结果。

如依次用n=1, 21, 22, 23, 26, 28, 210 (3) f(n)= n ; g(n)= log2nf(n)=Ω(g(n))(4) f(n)= nlogn+n; g(n)= lognf(n)=Ω(g(n))(5) f(n)= 10 ; g(n)= log10f(n)=Θ(g(n))(6) f(n)= log2n ; g(n)= lognf(n)=Ω(g(n))(7) f(n)= 2n ; g(n)= 100 n2f(n)=Ω(g(n))(8) f(n)= 2n ; g(n)= 3nf(n)=O(g(n))。

算法分析与设计作业(一)及参考答案

算法分析与设计作业(一)及参考答案

《算法分析与设计》作业（一）本课程作业由两部分组成。

第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。

第二部分为“主观题部分”，由简答题和论述题组成，共15分。

作业总分30分，将作为平时成绩记入课程总成绩。

客观题部分：一、选择题（每题1分，共15题）1、递归算法：（C ）A、直接调用自身B、间接调用自身C、直接或间接调用自身D、不调用自身2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同3、备忘录方法的递归方式是：（C ）A、自顶向下B、自底向上C、和动态规划算法相同D、非递归的4、回溯法的求解目标是找出解空间中满足约束条件的：（A ）A、所有解B、一些解C、极大解D、极小解5、贪心算法和动态规划算法共有特点是：（A ）A、最优子结构B、重叠子问题C、贪心选择D、形函数6、哈夫曼编码是：（B）A、定长编码B、变长编码C、随机编码D、定长或变长编码7、多机调度的贪心策略是：（A）A、最长处理时间作业优先B、最短处理时间作业优先C、随机调度D、最优调度8、程序可以不满足如下性质：（D ）A、零个或多个外部输入B、至少一个输出C、指令的确定性D、指令的有限性9、用分治法设计出的程序一般是：（A ）A、递归算法B、动态规划算法C、贪心算法D、回溯法10、采用动态规划算法分解得到的子问题：（ C ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同11、回溯法搜索解空间的方法是：（A ）A、深度优先B、广度优先C、最小耗费优先D、随机搜索12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ）A、所需时间变化B、一定找到解C、找不到所需的解D、性能变差13、贪心算法能得到：（C ）A、全局最优解B、0-1背包问题的解C、背包问题的解D、无解14、能求解单源最短路径问题的算法是：（A ）A、分支限界法B、动态规划C、线形规划D、蒙特卡罗算法15、快速排序算法和线性时间选择算法的随机化版本是：（ A ）A、舍伍德算法B、蒙特卡罗算法C、拉斯维加斯算法D、数值随机化算法主观题部分：二、写出下列程序的答案（每题2.5分，共2题）1、请写出批处理作业调度的回溯算法。

算法设计与分析第二版课后习题及解答（可编辑）

算法设计与分析第二版课后习题及解答（可编辑）

算法设计与分析第二版课后习题及解答算法设计与分析基础课后练习答案习题1.14.设计一个计算的算法,n是任意正整数。

除了赋值和比较运算,该算法只能用到基本的四则运算操作。

算法求 //输入:一个正整数n2//输出:。

step1:a1; step2:若a*an 转step 3,否则输出a; step3:aa+1转step 2;5. a.用欧几里德算法求gcd(31415,14142)。

b. 用欧几里德算法求gcd(31415,14142),比检查min{m,n}和gcd(m,n)间连续整数的算法快多少倍?请估算一下。

a. gcd31415, 14142 gcd14142, 3131 gcd3131, 1618 gcd1618, 1513 gcd1513, 105 gcd1513, 105 gcd105, 43 gcd43, 19 gcd19, 5 gcd5, 4 gcd4, 1 gcd1, 0 1.b.有a可知计算gcd(31415,14142)欧几里德算法做了11次除法。

连续整数检测算法在14142每次迭代过程中或者做了一次除法,或者两次除法,因此这个算法做除法的次数鉴于1?14142 和 2?14142之间,所以欧几里德算法比此算法快1?14142/11 ≈1300 与2?14142/11 ≈ 2600 倍之间。

6.证明等式gcdm,ngcdn,m mod n对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和rm mod nm-qn;显然,若d能整除n和r,也一定能整除mr+qn和n。

数对m,n和n,r具有相同的公约数的有限非空集,其中也包括了最大公约数。

故gcdm,ngcdn,r7.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0mn的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcdm,ngcdn,m并且这种交换处理只发生一次.8.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?1次b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?5次gcd5,8习题1.21.农夫过河P?农夫W?狼 G?山羊 C?白菜2.过桥问题1,2,5,10---分别代表4个人, f?手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c0的实根,写出上述算法的伪代码可以假设sqrtx是求平方根的函数算法Quadratica,b,c//求方程ax^2+bx+c0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D0temp←2*ax1←-b+sqrtD/tempx2←-b-sqrtD/tempreturn x1,x2else if D0 return ?b/2*ael se return “no real roots”else //a0if b≠0 return ?c/belse //ab0if c0 return “no real numbers”else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答:a.将十进制整数转换为二进制整数的算法输入:一个正整数n输出:正整数n相应的二进制数第一步:用n除以2,余数赋给Kii0,1,2,商赋给n第二步:如果n0,则到第三步,否则重复第一步第三步:将Ki按照i从高到低的顺序输出b.伪代码算法 DectoBinn//将十进制整数n转换为二进制整数的算法//输入:正整数n//输出:该正整数相应的二进制数,该数存放于数组Bin[1n]中i1while n!0 doBin[i]n%2;nintn/2;i++;while i!0 doprint Bin[i];i--;9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.算法略对这个算法做尽可能多的改进.算法 MinDistanceA[0..n-1]//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements 习题1.3考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.古老的七桥问题第2章习题2.17.对下列断言进行证明:如果是错误的,请举例a. 如果tn∈Ogn,则gn∈Ωtnb.α0时,Θαgn Θgn解:a这个断言是正确的。