《算法设计与分析习习题》由会员分享，可在线阅读，更多相关《算法设计与分析习习题（9页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析习题第一章算法引论1、 算法的定义答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法：就是解决问题的方法或过程。2、 算法的特征答：1)算法有零个或多个输入； )算法有一个或多个输出； 3)确定性 ； )有穷性3、 算法的描述方法有几种答：自然语言、图形、伪代码、计算机程序设计语言4、 衡量算法的优劣从哪几个方面答：(1) 算法实现所耗费的时间（时间复杂度）； (2) 算法实现所所耗费的存储空间（空间复杂度）； (3) 算法应易于理解，易于编码，易于调试等等。5、 时间复杂度、空间复杂度定义答：指的是算法在运行过程中所需要的资源（时间、空间）多
2、少。6、时间复杂度计算： i=1； while（i=n） i=i*2； 答：语句执行次数1次，语句执行次数f(n), 2f(n)=n,则f(n) 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); l 兔子序列（fibonaci数列 ） 递归实现：Int F(int n) if(n=2) return 1; else return F(n-1)+ F(n-2);l 上楼梯问题Int F(int n) if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2);l 整数划分
3、问题问题描述：将正整数n表示成一系列正整数之和，n=n1+n1+n3+将最大加数不大于m的划分个数，记作q(n,m)。正整数n的划分数p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系：递归算法：Int q( int n, int m)if(n1|m1) return 0;If(n=1)|(m=1) return 1;If (nm) return q(n,n);If(n=m) return q(n,m-1)+1;else return q(n,m-1)+q(n-m,m);（2） 蛮力法：百鸡百钱问题算法设计1：设x，y，z分别为公鸡、母鸡、小鸡的数量。 约束条件： x+y+z=100
4、 且 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次。算法的效率显然太低 算法设计2： 在公鸡（x）、母鸡（y）的数量确定后，小鸡的数量 z就固定为100-
5、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,x)； print(the hen number is, y)；print(the chick number is z); 算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定Z能被3整除时，才会判断“5*x+3*y+z/3=100”。这
6、样省去了z不整除3时的算术计算和条件判断，进一步提高了算法的效率。(3) 倒推法：穿越沙漠问题desert（ ） int dis，k，oil,k; 2）相同：都是将原问题分解成小问题，通过小问题求解得到原问题解。不同： 用分治法求解时,分解的子问题是互相独立的,且与原问题类型一致。分治算法实现一般用递归； 动态规划方法经分解得到的子问题往往不是互相独立的；动态规划算法实现一般用循环; 3）基本要素：具有最优子结构；子问题具有重叠性4）步骤：1)分析最优解的性质，并刻划其结构特征。 2)递推地定义最优值。 3)以自底向上的方式计算出最优值. 4)根据计算最优值时得到的信息，构造问题的最优解. 、
7、序列X=X1，X2,Xm 和 Y=Y1,Y2Yn的最长公共子序列为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 的最长公共自序列；、若xmyn, 且xm zk, 则Z是Xm-1与Y的最长公共子序列；、若xmyn, 且yn z
8、k, 则Z是X与Yn-1的最长公共子序列; 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀（去掉一个元素）的最长公共子序列。 即，原问题最优解，包含子问题最优解； 因此，最长公共子序列问题具有最优子结构性质。 写出递归方程 循环实现，计算最优值C i 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所需最少
9、租金（见习题集第三章算法设计与计算题T2）4、掌握动态规划方法求解背包问题 答：分析问题的最优解结构设（y1,y2,yn）所给01背包容量为M的解；则，（y2,yn）相应子问题背包容量为Mw1的解； （即原问题最优解，包含了子问题最优解） 递归定义最优值计算最优值m(i，j) void knapsack( int v , int w , int M, int m )int n=; if ( Mw n ) ntValue();ntValue(); ntValue(); ntValue(); / 取下一扩展结点 i+ / 进入下一层 double bound(int i) / 计算上界函数/ 计算
10、当前价值与剩余价值和 double cleft = c - cw; / 剩余容量 double b = cp; / 当前物品价值 while (i = n & w i cleft 跳出循环，物品部分装入背包 if (i = n) b += pi/wi * cleft; return b; / 当前物品价值与剩余物品价值之和时间复杂度分析：计算上界时间为O(n)；在最坏的情况下，有2n个右孩子节点需要计算上界； 故该算法的时间复杂度为O(n*2n)5、利用FIFO分支限界算法,给出下列01背包最优装载的求解步骤 背包载重：M10； 物品重量：w16、w25、w35； 物品价值：p142、p225
11、、p330解：1)解空间： 2）求解过程：第8章 NP完全性理论1、什么是易解问题什么是难解问题难解问题分为哪两类答：1）易解问题：人们将存在多项式时间 算法的问题称为易解问题;2）难解问题：将需要在指数时间内解决的问题称为难解问题；3）难解问题有两类： 1）不可判定问题 2）非决定的难处理问题 。2、什么是不可判定问题什么是非决定的难处理问题答：1）不可判定问题 ：该类问题是不能解问题，它们太难了，以至于根本就不存在能求解它们的任何算法。2）非决定的难处理问题： 这类问题是可判定的（即可解的）。 但是，这类问题即使使用非决定的计算机，也不能在多项式时间内求解它们。3、什么是P类问题什么是NP完
