算法设计与分析习题

1、算法设计与分析习题第一章算法引论1、 算法的定义答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法：就是解决问题的方法或过程。2、 算法的特征答：1）算法有零个或多个输入；2 ）算法有一个或多个输出；3）确定性；4）有穷性3、 算法的描述方法有几种答：自然语言、图形、伪代码、计算机程序设计语言4、 衡量算法的优劣从哪几个方面答： （1） 算法实现所耗费的时间（时间复杂度）；（2） 算法实现所所耗费的存储空间（空间复杂度）；（3） 算法应易于理解，易于编码，易于调试等等。5、 时间复杂度、空间复杂度定义答：指的是算法在运行过程中所需要的资源（时间、空间）多少。

2、6、时间复杂度计算：i=1；while （ i<=n ）i=i*2； 答：语句执行次数 1次，语句执行次数 f（n）, 2Af（n）<=n,则f（n） <=log2n;算法执行时间：T（n）= 2log2n +1时间复杂度：记为O（log2n） ；(7) 递归算法的特点答：每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件）递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式）8、算法设计中常用的算法设计策略答：蛮力法；倒推法；循环与递归；分治法；动态规划法；贪心法；回溯法；分治限界法(8) 计算法：递归法：汉诺塔问题兔子序列（上楼梯问题）整

3、数划分问题蛮力法：百鸡百钱问题倒推法：穿越沙漠问题答：算法如下：(9) 递归法汉诺塔问题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; elsereturn F(n-1)+ F(n-2); 上楼梯问题Int F(int n) if(n=1) return 1if(n=2) return 2;elsereturn F(n-1

4、)+ F(n-2);整数划分问题问题描述：将正整数 n表示成一系列正整数之和，n=n1+n1+n3+将最大加数不大于m的划分个数，记作 q(n,m)。正整数 n的划分数p(n)=q(n,n)。可以建立q(n,m)的如下递归关系：1n 1,m 1q(n,m)递归算法:q(n,n)1 q(n,n 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<m) return q(n,n);If(n=m) return q(n,m-1)+1; else ret

5、urn q(n,m-1)+q(n-m,m);(10) 蛮力法：百鸡百钱问题算法设计1:设x, y, z分别为公鸡、母鸡、小鸡的数量。约束条件：x+y+z=100且5*x+3*y+z/3=100main() 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",x) ;print(the hen number is", y);print(the chic

6、k number is "z); 算法分析：以上算法需要枚举尝试20*34*100=68000次。算法的效率显然太低算法设计2:在公鸡(x)、母鸡(y)的数量确定后，小鸡的数量 z就固定为100-x-y ,无需再进行枚举了。此时约束条件只有一个：5*x+3*y+z/3=100main() 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 and5*x+3*y+z/3=100)print(the cock number is",x) ;print(the hen nu

7、mber is", y);print(the chick number is "z); 算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定Z能被3整除时，才会判断“ 5*x+3*y+z/3=100 ”。这样省去了 z不整除3时的算术计算和条件判断，进一步 提高了算法的效率。(3)倒推法：穿越沙漠问题desert () int dis , k, oil,k; 2)相同：都是将原问题分解成小问题，通过小问 题求解得到原问题解。不同：用分治法求解时，分解的子问题是互相独立的，且与原问题类型一致。分治 算法实现一般用递归；动态规划方法经分解得到的子问题往往不

8、是互相独立的；动态规划算法实 现一般用循环；3）基本要素：具有最优子结构；子问题具有重叠性4）步骤：1）分析最优解的性质，并刻划其结构特征。2） 递推地定义最优值。3） 以自底向上的方式计算出最优值.4）根据计算最优值时得到的信息，构造问题的最优解2、序列 X=X1, X2,Xm 和Y=Y1,Y2Yn的最长公共子序列为 Z=Z1,Z2,Zk 用动态规划的方法求序列X和Y的最长公共子序列长度（要求按照动态规划写出动态规划求解问题的步骤分析最优子结构写出递归方程算法描述）注：C m n记录序列X与Y的最长公共子序列的长度答：最优子结构设序列 X= X 1, X2, -X m 与序列Y= y i,

9、y2,y n 的一个最长公共子序列 Z= Z1, Z2,z k I、若 xm= y n, 则 Zk=xm= y n, 且 z 1, Z2,z k-i 是序歹U Xm-i与 序列Yn-i的最长公共自序列；II、若XmWy n,且XmW Z k,则Z是Xm-1与Y的最长公共子序列；出、若XmWy n,且ynW Z k,则Z是X与Yn-1的最长公共子序列；由此可见，2个序列的最长公共子序列包含了这2个序列的前缀（去掉一个元素）的最长公共子序列。即，原问题最优解，包含子问题最优解；因此，最长公共子序列问题具有最优子结构性质。写出递归方程循环实现,计算最优值C i j,算法描述Int lcsLength

10、（ x , y , b） int m=;n=;for（int i=1; i<m;i+）Ci0=0;游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r（i , j）,其中1<=i<j<=n ;试设计一个算法，计算出游艇从出租站1到出租站n所需最少租金（见习题集第三章算法设计与计算题T2）4、掌握动态规划方法求解0 - 1背包问题答：分析问题的最优解结构设（y1,y2,丫口）所给01背包容量为M的解；则，（y2,丫 n）相应子问题背包容量为M- w的解；（即原问题最优解，包含了子问题最优解）递归定义最优值计算最优值

11、m（i , j）int n=;if ( M<w n )取下一扩展结点i+/double bound(int i)/ 计算当前价值与剩余价值和double cleft = c - cw; /void knapsack( int v , int w , int M, int m )ntValue();ntValue(); ntValue(); ntValue(); /进入下一层计算上界函数剩余容量double b = cp; /当前物品价值while （i <= n && w i <= cleft） /剩余物品单位重量价值递减序装入物品 cleft = cleft

12、 -w i;b= b + pi;i+;/ w i> cleft跳出循环，物品部分装入背包if （i <= n） b += pi/wi * cleft;return b; /当前物品价值与剩余物品价值之和时间复杂度分析：计算上界时间为O（n）;在最坏的情况下，有2n个右孩子节点需要计算上界；故该算法的时间复杂度为O（n*2 n）5、利用FIFO 分支限界算法, 给出下列0 1 背包最优装载的求解步骤背包载重：Ml= 10; 物品重量：w1=6、w2= 5、w3= 5; 物品价值：p1 = 42、p2 = 25、 p3= 30解： 1） 解空间：2）求解过程：第 8 章 NP 完全性理

13、论1、什么是易解问题什么是难解问题难解问题分为哪两类答： 1）易解问题：人们将存在多项式时间算法的问题称为易解问题;2）难解问题：将需要在指数时间内解决的问题称为难解问题；3）难解问题有两类：1 ）不可判定问题2 ）非决定的难处理问题。2、什么是不可判定问题什么是非决定的难处理问题答： 1）不可判定问题：该类问题是不能解问题，它们太难了，以至于根本就不存在能求解它们的任何算法。2）非决定的难处理问题：这类问题是可判定的（即可解的）。 但是，这类问题即使使用非决定的计算机，也不能在多项式时间内求解它们。3、什么是P类问题什么是NP完全问题答：1） P 类问题：是一类能够用确定性算法在多项式时间内求解的判断问题。事实上，所有易解问题都属于P 类问题。2） NP完全问题：对于某问题，很难找到其多项式时间的算法（或许根本不存在），但是如果给了该问题的一个答案，则可以在多项式时间内判