《算法设计与分析》习题第一章算法引论1、算法的定义答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。
通俗讲，算法：就是解决问题的方法或过程。
2、算法的特征答：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性；４)有穷性3、算法的描述方法有几种答：自然语言、图形、伪代码、计算机程序设计语言4、衡量算法的优劣从哪几个方面答：(1) 算法实现所耗费的时间（时间复杂度）；(2) 算法实现所所耗费的存储空间（空间复杂度）；(3) 算法应易于理解，易于编码，易于调试等等。
5、时间复杂度、空间复杂度定义答：指的是算法在运行过程中所需要的资源（时间、空间）多少。
6、时间复杂度计算：{i=1；while（i<=n）i=i*2； }答：语句①执行次数1次，语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n;算法执行时间： T(n)= 2log2n +1时间复杂度：记为O(log2n) ；7.递归算法的特点答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件）②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式）8、算法设计中常用的算法设计策略答：①蛮力法；②倒推法；③循环与递归；④分治法；⑤动态规划法；⑥贪心法；⑦回溯法；⑧分治限界法9、设计算法：递归法：汉诺塔问题兔子序列（上楼梯问题）整数划分问题蛮力法：百鸡百钱问题倒推法：穿越沙漠问题答：算法如下：（1） 递归法汉诺塔问题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)+ F(n-2);}整数划分问题问题描述：将正整数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(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;elsereturn q(n,m-1)+q(n-m,m);}⎪⎪⎩⎪⎪⎨⎧>>=<==-+--+=11,1),()1,()1,(1),(1),(m n m n m n m n m m n q m n q n n q n n q m n q（2）蛮力法：百鸡百钱问题算法设计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次。
算法的效率显然太低算法设计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能被3整除时，才会判断“5*x+3*y+z/3=100”。
这样省去了z不整除3时的算术计算和条件判断，进一步提高了算法的效率。
(3) 倒推法：穿越沙漠问题desert（）{ int dis，k，oil,k; 2）相同：都是将原问题分解成小问题，通过小问题求解得到原问题解。
不同：用分治法求解时,分解的子问题是互相独立的,且与原问题类型一致。
分治算法实现一般用递归；动态规划方法经分解得到的子问题往往不是互相独立的；动态规划算法实现一般用循环;3）基本要素：具有最优子结构；子问题具有重叠性4）步骤：1)分析最优解的性质，并刻划其结构特征。
2)递推地定义最优值。
3)以自底向上的方式计算出最优值.4)根据计算最优值时得到的信息，构造问题的最优解.２、序列X={X1，X2,…Xm }和 Y={Y1,Y2…Yn}的最长公共子序列为Z={Z1,Z2,…Zk}用动态规划的方法求序列 X 和Y的最长公共子序列长度（要求按照动态规划写出动态规划求解问题的步骤分析①最优子结构②写出递归方程③算法描述）注：C[ ｍ][ ｎ]记录序列X与Y的最长公共子序列的长度答：①最优子结构设序列X={ x1，x2，…x m } 与序列Y={ y1，y2，…y n }的一个最长公共子序列Z={ z1，z2，…z k }Ⅰ、若x m= y n, 则z k=x m= y n, 且{ z1，z2，…z k-1 }是序列X m-1与序列Y n-1的最长公共自序列；Ⅱ、若x m≠y n, 且x m≠ z k, 则Z是X m-1与Y的最长公共子序列；Ⅲ、若x m≠y n, 且y n≠ z k, 则Z是X与Y n-1的最长公共子序列;由此可见，2个序列的最长公共子序列包含了这2个序列的前缀（去掉一个元素）的最长公共子序列。
即，原问题最优解，包含子问题最优解；因此，最长公共子序列问题具有最优子结构性质。
②写出递归方程③循环实现，计算最优值C[ i][ j]，算法描述Int lcsLength( x[ ], y[ ], b[ ][ ]){ int m=;n=;for(int i=1; i<m;i++) C[i][0]=0; 游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。
游艇出租站i到游艇出租站j之间的租金为r(i，j)，其中1<=i<j<=n；试设计一个算法，计算出游艇从出租站1到出租站n所需最少租金（见习题集第三章算法设计与计算题T2）4、掌握动态规划方法求解０－１背包问题答：①分析问题的最优解结构设（y1,y2,…y n）所给0－1背包容量为M的解；则，（y2,…y n）相应子问题背包容量为M－w1的解；（即原问题最优解，包含了子问题最优解）②递归定义最优值③计算最优值m(i，j)void knapsack( int v[ ], int w[ ], int M, int m[ ] [ ] ){int n=;if ( M<w[ n] ) ntValue();ntValue(); ntValue(); ntValue(); // 取下一扩展结点i++ // 进入下一层 }}}double bound(int i) // 计算上界函数{// 计算当前价值与剩余价值和double cleft = c - cw; // 剩余容量double b = cp; // 当前物品价值while (i <= n && w[ i] <= cleft) // 剩余物品单位重量价值递减序装入物品{ cleft = cleft -w[ i];b= b + p[i];i++;} // w[ i]> cleft 跳出循环，物品部分装入背包if (i <= n) b += p[i]/w[i] * cleft;return b; // 当前物品价值与剩余物品价值之和}时间复杂度分析：计算上界时间为O(n)；在最坏的情况下，有2n个右孩子节点需要计算上界；故该算法的时间复杂度为O(n*2n)5、利用FIFO分支限界算法,给出下列0－1背包最优装载的求解步骤背包载重：M＝10；物品重量：w1＝6、w2＝5、w3＝5；物品价值：p1＝42、p2＝25、p3＝30解：1)解空间：2）求解过程：第8章 NP完全性理论1、什么是易解问题什么是难解问题难解问题分为哪两类答：1）易解问题：人们将存在多项式时间算法的问题称为易解问题;2）难解问题：将需要在指数时间内解决的问题称为难解问题；3）难解问题有两类： 1）不可判定问题 2）非决定的难处理问题。
2、什么是不可判定问题什么是非决定的难处理问题答：1）不可判定问题：该类问题是不能解问题，它们太难了，以至于根本就不存在能求解它们的任何算法。
2）非决定的难处理问题：这类问题是可判定的（即可解的）。
但是，这类问题即使使用非决定的计算机，也不能在多项式时间内求解它们。
3、什么是P类问题什么是NP完全问题答：1）P类问题：是一类能够用确定性算法在多项式时间内求解的判断问题。
事实上，所有易解问题都属于P类问题。
2）NP完全问题：对于某问题，很难找到其多项式时间的算法(或许根本不存在)，但是如果给了该问题的一个答案，则可以在多项式时间内判定或验证这个答案是否正确。
这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。
4、列出几个典型的NP完全问题答：（1）图着色问题COLORING（2）路径问题LONG-PATH（3）顶点覆盖问题VERTEX-COVER（4）子集和问题SUBSET-SUM（5）哈密尔顿回路问题HAM-CYCLE（6）旅行商问题TSP（7）装箱问题BIN-PACKING ，能否用k个箱子来装n个物品；。