算法设计及解析总结计划练习习题x
时间：2020-11-20 07:40:12 来源：小苹果范文网 本文已影响 人 
《算法设计与分析》习题
第一章算法引论
1、 算法的定义
答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。
通俗讲，算法：就是解决问题的方法或过程。
2、 算法的特征
答： 1) 算法有零个或多个输入；
２ ) 算法有一个或多个输出；
3) 确定性 ； ４) 有穷性
3、 算法的描述方法有几种
答：自然语言、图形、伪代码、计算机程序设计语言
4、 衡量算法的优劣从哪几个方面
答： (1) 算法实现所耗费的时间（时间复杂度） ；
(2) 算法实现所所耗费的存储空间（空间复杂度） ；
算法应易于理解，易于编码，易于调试等等。
5、 时间复杂度、空间复杂度定义
答：指的是算法在运行过程中所需要的资源（时间、空间）多少。
6、时间复杂度计算：
{i=1
；
while
i=i*2
（ i<=n ）；
}
答：语句①执行次数 1 次，
语句②③执行次数 f(n), 2^f(n)<=n,
算法执行时间： T(n)= 2log2n +1
时间复杂度：记为 O(log2n) ；
则
f(n) <=log2n;
递归算法的特点
答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；件）
（递归终止条
②递归中用较小自变量函数值来表达较大自变量函数值；
（递归方程式）
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;
else
return F(n-1)+ F(n-2);
}
上楼梯
Int F(int n)
{
if(n=1) return 1
if(n=2) return 2;
else
return F(n-1)+ F(n-2);
}
整数划分
描述：将正整数
n 表示成一系列正整数之和， n=n1+n1+n3+?
将最大加数不大于
m 的划分个数， 作
q(n,m) 。正整数 n 的划分数
p(n)=q(n,n) 。
可以建立 q(n,m) 的如下 关系：
1
n
1, m
1
q( n, m)
q(n, n)
n
m
q( n,n
1)
n
m
1
q(n, m
1) q(n
m, m)n
m
1
算法：
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
return q(n,m-1)+q(n-m,m);
}
2） 蛮力法：百鸡百钱问题算法设计 1：
设 x ， y ， z 分 别为 公鸡 、母 鸡、 小鸡 的数量。 约束条 件： x+y+z=100 且
5*x+3*y+z/3=100
main( )
{ 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=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 ”。这样省去了 z
提高了算法的效率。
(3) 倒推法：穿越沙漠问题
desert （ ）
不整除 3 时的算术计算和条件判断，进一步
{
int dis
， k， oil,k;
2 ）相同： 都是将原问题分解成小问题，通过小问
题求解得到原问题解。
不同：
用分治法求解时 , 分解的子问题是互相独立的 , 且与原问题类型一致。分治算法实现一般用递归；
动态规划方法经分解得到的子问题往往不是互相独立的；动态规划算法实现一般用循环 ;
3）基本要素 ：具有最 子 构；子 具有重叠性
4）步 ： 1) 分析最 解的性 ，并刻划其 构特征。
推地定 最 。
以自底向上的方式 算出最 .
根据 算最 得到的信息，构造 的最 解.
２、序列 X={X1， X2, ? Xm } 和 Y={Y1,Y2 ? Yn} 的最 公共子序列 Z={Z1,Z2, ? Zk}
用 划的方法求序列
X 和 Y 的最 公共子序列 度
（要求按照 划写出 划求解 的步 分析①最 子 构②写出 方程
③算法描述）
注： C[ ｍ ][
ｎ] 序列 X 与 Y 的最 公共子序列的 度
答：①最 子 构
序列 X={ x 1， x2，?xm }
与
序列 Y={ y
1
，y
，?y } 的一个
2
n
最 公共子序列
Z={ z 1， z2，?zk }
Ⅰ、若 xm= y n,
zk =xm= y n,
且 { z
1， z2，?zk-1
} 是序列 Xm-1 与
序列 Y
的最 公共自序列；
n-1
Ⅱ、若 x ≠y,
且 x ≠ z
k
,
Z 是 X
与 Y 的最 公共子序列；
m
n
m
m-1
Ⅲ、若 xm≠yn,
且 yn≠ z k,
Z 是 X 与 Yn-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,y 2, ?yn）所 0－ 1 背包容量 M的解；
，（ y2, ?yn）相 子 背包容量 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)；在最坏的情况下，有
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 个物品；
- 下载文档
- 收藏
- 0
