《算法设计与分析习题》由会员分享，可在线阅读，更多相关《算法设计与分析习题（12页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析习题第一章算法引论1、算法的定义答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法：就是解决问题的方法或过程。4 )有穷性2、算法的特征答：1)算法有零个或多个输入；2 )算法有一个或多个输出；3)确定性；3、算法的描述方法有几种答：自然语言、图形、伪代码、计算机程序设计语言4、衡量算法的优劣从哪几个方面答：(1)算法实现所耗费的时间(时间复杂度)；(2) 算法实现所所耗费的存储空间(空间复杂度)；(3) 算法应易于理解，易于编码，易于调试等等。5、时间复杂度、空间复杂度定义答：指的是算法在运行过程中所需要的资源(时间、空间)多少。6、时间复杂
2、度计算：i=1；while (i=n )i=i*2; 答：语句执行次数 1次，语句执行次数 f(n), 2Af(n)=n,则f(n) 0)hanoi(n-1, a, c, b);move(a,b);hanoi(n-1, c, b, a); I边界条件1h=1t2F(n) Y F(n-1) * F(r-2) n2兔子序列(fibonaci 数列)递归实现：Int F(int n)递归方程if(n2递归方程上楼梯问题Int F(int n)if(n=1) return 1if(n=2) return 2;elsereturn F(n-1)+ F(n-2);整数划分问题问题描述：将正整数n表示成一系
3、列正整数之和，n=n1+n1+n3+ -将最大加数不大于m的划分个数，记作 q(n,m)。正整数 n的划分数p(n尸q(n,n)。 可以建立q(n,m)的如下递归关系：1n 1,m 1q(n,m)递归算法：Intq(n,n)n m1 q(n,n 1)n mq(n, m 1) q(n m, m) n m 1q( int n, int m)if(n1|m1) return 0;If(n=1)ll(m=1) return 1;If (nm) return q(n,n);If(n=m) return q(n,m-1)+1;elsereturn q(n,m-1)+q(n-m,m);(2)蛮力法：百鸡百钱
4、问题算法设计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 chick number is z);算法分析：以上算法需要枚举尝试20*34*100=68000次。算法的效率显然太低算法设
5、计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 number is, y);print(the chick number is z);算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定 Z
6、能被3整除时,才会判断“ 5*x+3*y+z/3=100 ”。这样省去了 z不整除3时的算术计算和条件判断，进一步 提高了算法的效率。(3)倒推法：穿越沙漠问题desert ()int dis , k , oil,k;int binarySearch(T const int left, int rightJnt &i, int &j) ,int middle;while (left aEniddle) left =uiddle II;else right =middle- 1;，:i = right;return 0;、T（n洋法算法需要经过O1如模为n/2位的乘医1以及相应的移位2T（呻+0
7、n1用解递归方程的迭代公式法：T(n)=3T(n/2)+0(n)=3(3T(n/4)+0(n/2)+0(n)二:/T(n/阴)H3*0(n/2)H)(n)第(3T(n/23) +0(n/4)+ 3*0(n/2) - 0(n)=3灯(n/炉)+3稣0(n/22)卡30 (n/2) +0(n)=3kT(n/2k)+3k 】*0(n/2k i)+* 3*0 Cn/2)+O(n)解，分解到最后n/2k=hT(n)=3k+(3/2)k，十(3/2)k z+3/2+1* 0(n)=3*3k-2*O(n解得: T(n)3*nloo3-2fl故时间复杂度记为：。(川气3尸0 aLs9)4,算法时间复杂度分析设
8、T（k）是覆盖一个#X2k棋盘所需时间：则其满 足如下递归方程:。4T(k - 1) + 0(1) A 0T(k=4*T(k-1)+1 =4T(k-2)+4+1 U 4*(4*T(k-2+1)+1 =43* T(k-3)+43 +4+1=41（）+411+4.+ 42 +4+1 分解到最后k+W）；=43加1+4川*平+4+1 士（14炉4川14）=（4M）/32 ）相同:都是将原问故该算法的时间亚杂度记为。伸丸）题分解成小问题，通过小问题求解得到原问题解。不同：用分治法求解时，分解的子问题是互相独立的，且与原问题类型一致。分治算法实现一般用递归；动态规划方法经分解得到的子问题往往不是互相独立
9、的；动态规划算法实现一般用循环；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, y2,y n的一个
10、最长公共子序列 Z= zi, Z2,z k I、若 xm= y n,则 zk=xm= y n,且 z i, Z2,z k-i 是序列 Xm-i 与序列3-i的最长公共自序列；II、若XmWy n,且XmW Z k,则Z是Xm-i与Y的最长公共子序列；出、若XmWy n,且ynW Z k,则Z是X与Yn-i的最长公共子序列；由此可见，2个序列的最长公共子序列包含了这2个序列的前缀（去掉一个元素）的最长公共子序列。即，原问题最优解，包含子问题最优解；因此，最长公共子序列问题具有最优子结构性质。写出递归方程0 = 0,/ = 0+ 10;xf =y）max 印|中一 “/循环实现,计算最优值C i
11、j ,算法描述Int lcsLength( x , y , b) int m=;n=；for(int i=1; im;i+)Ci0=0;游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i , j),其中1=ij=n ;试设计一个算法，计算出游艇从出租站1到出租站n所需最少租金(见习题集第三章算法设计与计算题T2)4、掌握动态规划方法求解0 - 1背包问题答：分析问题的最优解结构设(yi,y2,丫”所给01背包容量为M的解；则，(y2,yn)相应子问题背包容量为M- w的解；(即原问题最优解，包含了子问题最优解)递归定义最优值、硕+
12、 LJ)叱.+1J -v,00 M / v w “L，之 w e计算最优值m(i , j)void knapsack( int v , int w , int M, int m)int n=;if(MwnntValue(); ntValue(); i+/double bound(int i)/计算当前价值与剩余价值和double cleft = c - cw; /double b = cp; /T i取下一扩展结点进入下一层计算上界函数剩余容量当前物品价值while (i = n & w i cleft跳出循环，物品部分装入背包if (i = n) b += pi/wi * cleft;retur
