算法设计与分析习题解答

第一章 作业

1. 证明下列Ο、Ω和Θ的性质 1）

f=Ο(g)当且仅当g=Ω(f)

证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n?n0，有f? c1*g(n)。由于c1?0，故g(n) ? 1/ c1 *f(n)，故g=Ω(f)。

必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n?n0，有g(n) ? c2 *f(n).由于c2?0，故f(n) ? 1/ c2*f(n)，故f=Ο(g)。 2）

若f=Θ(g)则g=Θ(f)

证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n?n0，有c1*g(n) ?f(n) ? c2*g(n)。由于c1?0，c2?0，f(n) ?c1*g(n)可得g(n) ? 1/c1*f(n)，同时，f(n) ?c2*g(n)，有g(n) ? 1/c2*f(n)，即1/c2*f(n) ?g(n) ? 1/c1*f(n)，故g=Θ(f)。 3）

Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。

证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n?n1，有

F(n) ? c1 (f(n)+g(n)) = c1 f(n) + c1g(n)

? c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g}

所以，F(n)= Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。

4）

log(n!)= Θ(nlogn)

1

证明：

?由于log(n!)=?logi ??logn=nlogn，所以可得log(n!)= Ο(nlogn)。

i?1i?1nn?由于对所有的偶数n有，

log(n!)= ?logi??logi??logn/2?(n/2)log(n/2)=(nlogn)/2-n/2。

i?1i?n/2i?n/2nnn当n?4，(nlogn)/2-n/2?(nlogn)/4，故可得?n?4，log(n!) ?(nlogn)/4，即log(n!)= Ω(nlogn)。

综合以上两点可得log(n!)= Θ(nlogn)

2. 设计一个算法，求给定n个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法：

Void findsecond(ElemType A[]) {

for (i=2; i<=n;i++) if (A[1]

temp=A[1];

A[1]=A[i]; A[i]=temp;

}

for (i=3; i<=n;i++) if (A[2]

2

{

temp=A[1];

A[1]=A[i]; A[i]=temp;

} return A[2]; }

该算法使用的比较次数为：2n-3

3. 设计一个算法，求给定n个元素的最大和最小元素。（要求算法的复杂度至多为1.5n） 算法：

void Maxmin2(A;l,r;int x;int y); {

if (l=r) { x=A[l]; y=A[r]; return;} if (r-l=1)

{ if (A[l]

else { mid:=(l+r) div 2;

Maxmin2(A,l,mid,x1,y1); Maxmin2(A,mid+1,r,x2,y2);

3

x=min(x1,x2); y=max(y1,y2); } }

该算法使用的比较次数为：1.5n-2

4. 给定多项式p(x)=anxn+ an-1xn-1+…+a1x+a0，假设使用以下方法求解： p=a0; xpower=1; for (i=1; i<=n; i++) { xpower=x * xpower; p=p+ai * xpower; }

求（1）该算法最坏情况下使用的加法和乘法分别为多少次？ （2）能不能对算法的性能进行提高？

解：（1）该算法最坏情况下使用的加法n次，乘法2n次 （2）改进的算法为：

float Horner(A, float x) {

p=A[n+1]; for (j=1; j<=n; j++) p=x*p+A[n-j]; return p;

}

该算法中使用加法n次，乘法n次

4

第二章

1．求解下列递推关系：

1）当n≥1时，f(n)=3f(n-1)；f(0)=5

解：f(n)=3f(n-1)=32f(n-2)=…=3nf(n-n)= 3n *5=5*3n

2) 当n≥2时，f(n)=5f(n-1)-6f(n-2)； f(0)=1；f(1)=0 解：该递推关系的特征方程为：x2-5x+6=0 特征根为：r1=2；r2=3 故f(n)=c1*2n+c2*3n

有f(0)= c1*20+c2*30== c1+c2=1 且f(1)= c1*21+c2*31== 2c1+c32=0 可得c1 =3， c2=-2 故f(n)=3*2n-2*3n

3) 当n≥1时，f(n)=f(n-1)+n2； f(0)=0 解：f(n)= f(n-1)+n2 = f(n-2)+ (n-1)2+n2 =….

= f(0)+12+22+…+ (n-1)2+n2 =12+22+…+ (n-1)2+n2 =1/6 n(n+1)(2n+1)

4) 当n≥1时，f(n)=2f(n-1)+n2； f(0)=1 解：设f(n)=2nf’(n)，且f’(0)= f(0)=1

5

则2nf’(n)=2*（2n-1f’(n-1)）+ n2 即

n2f’(n)= f’(n-1)+n2n

i2= f’(0)+?ii?12i2=1+?ii?12n

n 所以f(n)= 2

n

i2*(1+?ii?12)=2n*(10-n?n6)=10*2n-(n+6)

25) 当n≥1时，f(n)=nf(n-1)+1； f(0)=1 解：f(n)=n!*( f’(0)+ ?1)

i!i?1n= n!*( 1+ ?1)

i!i?1n

2.求解下面的递推式：当n≥2时，f(n)=4f(n/2)+n； f(1)=1。假设n为2的幂，用直接展开法求解递推式。 解：令n?2k f(n)=4f(n/2)+n =4*(4f(nn)?)?n 222n=42f(2)?2n?n

2n=43f(3)?22n?2n?n

2

=…. =4kf(n)?2k?1n???2n?n k2 =4kf(1)?(2k?1???2?1)n =n2?(2k?1)n

6

=2n2?n

3.求解下面的递推式：当n≥2时，f(n)=9f(n/3)+n2； f(1)=1。假设n为3的幂，用直接展开法求解递推式。 解：令n?3k f(n) =9f(n3)?n2

=9(9f(n232)?(n3))?n2

=92f(n232)?n2?n

=93f(n3)?n2?n2?n23

=…. =9kf(n3k)?kn2 =n2?n2log3n

4. 法求解递推式的上界：当n≥4时，f(n)?f(??n??4??)?f(??3n??4??)?n；f(n)=4。 解：

由于递推式为?f(n)??4???f(??n?n?4?4??)?f(??3n??4??)?nn?4 这里

14?34?1 故作猜想f(n)?2f(n2)?n的解为：f(n)?nlogn?4n 故对原递推式做猜想f(n)?cnlogn?4n 由于f(n)?f(??n??3n??4??)?f(??4??)?n 7

n<4时，

当 ?c??n??4??log??n??4???4??n??4???c??3n??4??log??3n??3n??4???4??4???n ?cnnn3n3n3n4log4?44?c4log4?44?n =14cn(logn?log4)?34cn(logn?log34)?5n

?cnlogn?(2?34log3)cn?5n

若使f(n)满足上界为cnlogn?4n则必有

cnlogn?(2?34log3)cn?5n?cnlogn?4n

即?(2?34log3)cn?n?0

所以c?1?1.23

2?34log3故f(n)?1.23nlogn?4n，即上界为1.23nlogn?4n

4. 设计算法，求解问题：有一楼梯共M级，刚开始时你再第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？ int fa(int m) {

int z;

if (m==1) z=1; else if (m==2) z=2;、 else z=fa(n-1)+fa(n-2); return z; }

8

5. 设计算法，一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？

这道题的思路与字符串的组合很像，用递归解决。一次射击有11种可能，命中1环至10环，或脱靶。 函数功能 ： 求解number次打中sum环的种数

函数参数 ： number为打靶次数，sum为需要命中的环数，result用来保存中间结果，total记录种数

void ShootProblem_Solution(int number, int sum, vector &result, int &total) { I

if(sum < 0 || number * 10 < sum)

//加number * 10 < sum非常重要，它可以减少大量的递归，类似剪枝操作 return;

if(number == 1) //最后一枪 {

if(sum <= 10) //如果剩余环数小于10，只要最后一枪打sum环就

可以了

{

for(unsigned i = 0; i < result.size(); i++) cout<

9

}

return;

else

return;

}

for(unsigned i = 0; i <= 10; i++) //命中0-10环 {

result.push_back(i);

ShootProblem_Solution(number-1, sum-i, result, total); //针对剩余

环数递归求解 }

void ShootProblem(int number, int sum) { }

int main()

10

result.pop_back();

}

int total = 0; vector result;

ShootProblem_Solution(number, sum, result, total); cout<<\

{ }

6. 设计算法，求解猴子吃桃问题：有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，依此类推），第九天正好吃完，问猴子们摘来了多少桃子？

思路：可假设有第十天，则第十天剩余的桃子数目为0，由此递推可得每一天剩余的桃子数目。第一天的桃子数目即为猴子摘桃子的总数。假设有第10天，则第10天吃0个桃子，倒推出前一天的个数x，x[9]=2(x[10]+1)。 void main() { }

第三章

11

ShootProblem(10, 90); return 0;

int i=0; int num[11]; num[10]=0; for(i=9;i<=1;i--)

num[i]=2*(num[i+1]+1);

cout<

1.设计一个分治算法，判定两棵给定的二叉树T1和T2是否相同。

采用先序遍历算法来实现，其中访问结点的操作为“判断两个结点是否相同”，如果t1和t2所指的结点均为空或均不为空且数据域的值相等，则继续先序比较它们的左、右子树，否则返回0。具体算法如下：

int EqualBtr(bitreptr t1, bitreptr t2) {

if(t1 == NULL && t2 == NULL)

return (1);

if((t1==NULL && t2!=NULL) || t1!=NULL && t2== NULL) ||

(t1->data!= t2->data))

return (0);

hl = EqualBtr (t1->Lchild, t2->Lchild); hr = EqualBtr (t1->Rchild, t2->Rchild); if(hl == 1 && hr == 1) return 1; else

return 0;

} 2.设计一个分治算法，求给定二叉树的高度。

设根结点为第一层的结点，所有k层结点的左、右孩子结点在k+1层。因此，可以通过先序遍历计算二叉树中每个结点的层次，其中最大值即为该二叉树的深度。具体算法如下：

void Btdepth(bitreptr t, int k, int &h)

//指针t指向二叉树的根结点，k, h的初值均设为0 {

if (t! = NULL) {

k++; //表示结点的层次 if (k > h) h = k;

Btdepth(t->Lchild, k, h); Btdepth(t->Rchild, k, h); } } 3.设计一个分治算法，在一个具有n个数的数组中找出第二大元素，并给

12

出算法的复杂度。

typedef struct MyTwoMax { int Max; int SecMax; }MyMax;

MyMax getSecMax(int A[],int low,int high)//分治求数值中最大的两个元素

{

MyMax lm,rm,mm; int mid; if(high-low<=1) {

if(high-low==1) {

mm.Max=max(A[low],A[high]); mm.SecMax=min(A[low],A[high]); return mm; } else {

mm.Max=A[low]; mm.SecMax=0;

13

return mm; } } else {

mid=(low+high)/2;

lm=getSecMax(A[],low,mid); rm=getSecMax(MyInt,mid+1,high); }

mm.Max=max(lm.Max,rm.Max);

mm.SecMax=max(min(lm.Max,rm.Max),max(lm.SecMax,rm.SecMa

x));

return mm; }

算法复杂度为：

1n?2??nf(n)??，故算法复杂度为2n?3 2f()?3n?2?2?5. 设计一个算法，求出给定5个元素的中间元素。要求最坏情况下使用6次比较。 (课上讲过)

6. 用分治法，求两个大整数X=5287，Y=3462的乘积。 解： 1）

14

x=5287 a=52 b=87 a-b= -35 y=3462 c=34 d=62 d-c= 28 ac=( 1768) bd=(5394 ) (a-b)(d-c)=(-980)

xy=ac104+[( ac + bd + (a-b)(d-c) ]102+ bd =17680000+（1768+5394-980）*100+5394 =18303594 2）

a=52 a1=5 b1=2 a1-b1=3 c=34 c1=3 d1=4 d1-c1=1 a1c1=15 b1d1=8 (a1-b1)(d1-c1)=3 ac=1500+(15+8+3)10+8=1768 3）

b=87 a2=8 b2=7 a2-b2=1 d=62 c2=6 d2=2 d2-c2= -4 a2c2=48 b2d2=14 (a2-b2)(d2-c2)= -4 bd=4800+(48+14-4)10+14=5394 4）

|a-b|=35 a3=3 b3=5 a3-b3= -2 |d-c|=28 c3=2 d3=8 d3-c3=6 a3c3=6 b3d3=40 (a3-b3)(d3-c3)= -12 | (a-b)(d-c) |=600+(6+40-12)10+40=980

15

16

第四章

1.求下列两个序列的最长公共子序列A=“xzyzzyx”， B=“zxyyzxz”，并给出一个最优解。

?0 if i?0 or j?0?解：L[i,j]??L[i-1,j-1]?1 if i?0 , j?0 and ai?bj

?if i?0 , j?0 and ai?bj?max{L[i,j?1],L[i?1,j] 相等时取←优先。故由下图可知其中一个最优解为：zyyx；最长公共子序列的长度为4。

yj

z

x 2

y 3

y 4

z

x 6

z 7

i 0 j 0 x 1 z 2 y 3 z 4 z 5

1 5

0

0 0

0

0

0

0

0

↑ ↖ 0

↖

0

1 ← 1 ← 1 ← 1

↖

1 ← 1

↖

0

1 ← 1 ← 1 ← 1 ↑

↖

↖

2 ← 2 ← 2

0

1 ← 1

2 ↑

2 ← 2 ← 2 ← 2

↖

↖

3

↖

0

1 ← 1

2 ← 2 ↑

3 ← 3

↖ ↖ ↖

4 ↑

0

1 ← 1 ↑

2 ← 2

↖

17

3 ← 3

↖

y 6 x 7

0

1 ← 1 ↑ ↖ 1

2

3 ← 3 ← 3 ↑ 3

↑ ↖ 3

4

0 2 ← 2 4 ← 4

2. 求对下列5个矩阵连乘：M1:4?5；M2:5 ?4 ；M3:4 ?6；M4:6 ?4；M5:4 ?5

1）求这5个矩阵连乘时所需要的最少乘法次数； 2）给出一个最优解。

{C[i,k?1]?C[k,j]?rirkrj?1} 解：C[i,j]?mini?k?j1）单个矩阵相乘：C[1,1]==C[2,2]=0 ……=C[5,5]=0 2）相邻两个矩阵相乘：

C[1,2]=min (1

C[1,3]= min (1

C[2,4]= min (2

C[3,5]= min (3

18

C[1,4]= min (1

C[2,5]= min (2

C[1,5]= min (1

最优解为：（（M1*M2）*（M3*M4））*M5

3. 求解下面旅行推销员问题，并给出最优周游路线。

?02?20D???59??9?46?12?? 01??28? 80+176+4*4*5, 176+120+4*6*5,

解： 1）

f(v2:Φ)=d21=2 f(v3:Φ)=d31=5 f(v4:Φ)=d41=9 2）

19

f(v2: {v3})= d23+f(v3:Φ)=1+5=6 f(v2: v4)= d24+f(v4:Φ)=2+9=11 f(v3: {v2})= d32+f(v2:Φ)=9+2=11 f(v3: v4)= d34+f(v4:Φ)=1+9=10 f(v4: {v2})= d42+f(v2:Φ)=∞ f(v4: v3)= d43+f(v3:Φ)=2+5=7 3）

f(v2: {v3 ,v4})= min{d23+f(v3: {v4 }), d24+f(v4: {v3}) }= min{1+10, 2+7}=9 f(v3: {v2 ,v4})= min{d32+f(v2: {v4 }), d34+f(v4: {v2}) }= min{9+11, 1+∞}=20

f(v4: {v2 ,v3})= min{d42+f(v2: {v3}), d43+f(v3: {v2}) }= min{∞+6, 2+11}=13 4）

f(v1: {v2 ,v3 ,v4})= min{d12+f(v2: {v3 ,v4}), d13+f(v3: {v2 ,v4}) , d14+f(v4: {v2 ,v3}) }

= min{2+9, 4+20, 6+13}=11

最佳周游路线为：V1?V2?V4?V3?V1

4.用动态规划法，求解0-1背包问题，已知背包容量为22，5件物品的体积分别为3,5,7,8,9，价值分别为4,6,7,9,10，求该背包的最大价值及物品选择情况。

?0 if i?0 or j?0解：V[i,j]???V[i?1,j] if jsi?max{V[i?1,j],V[i?1,j?s]?v} if i0 and j?siii?

由下表可知，该背包的最大价值是25，最优解为：（0,1,0,1,1）

20

i 0 1 2 3 4 5 6 7 8 9 1j 1111111112220 1 2 3 4 5 6 7 8 9 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 2 0 0 0 4 4 6 6 6 1111111111111110 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 4 4 6 6 7 1111111111111110 0 1 1 3 3 3 7 7 7 7 7 7 7 7 4 0 0 0 4 4 6 6 7 1111111111222220 0 1 3 3 5 5 7 9 9 0 0 2 2 2 5 0 0 0 4 4 6 6 7 1111111112222220 0 1 3 4 5 6 7 9 0 0 1 3 3 5

21

第五章

1. 用贪心法求解部分背包问题，已知n=3, C=40, (w1,w2,w3)=(28,15,24), (p1,p2,p3)=(35,25,24) . 解：

r1=35/28=1.25; r2=25/15=1.67; r3=24/24=1 可知r2>r1>r3

故从第二件物品开始贪心选择：

判定条件 背包已用部分 背包剩余部分 背包总价值 物品放入情况

C>w2 15 25 25 (0, 1, 0)

C-w2

即，背包最大价值为56.25，放置情况为(0.893, 1, 0)

2. 用dijkstra算法求解下图的单源最短路径问题，设源点为1。

1 9 4 4 2 12 5 13 3 5 4 3 15 2 6

22

解： 1）

X={1}, Y={2,3,4,5,6}

?[1]=0, ?[2]=9, ?[3]=4, ?[4]=∞, ?[5]=∞, ?[6]=∞ 2）

选取Y集合中标记?[]的最小值为?[3]=4, 将顶点3加入到X集

合，即

X={1, 3}, Y={2, 4,5,6}

修改和顶点3相关顶点的?[]值，即 ?[2]=8, ?[4]=∞, ?[5]=17, ?[6]=∞ 3）

选取Y集合中标记?[]的最小值为?[2]=8, 将顶点2加入到X集

合，即

X={1, 2, 3}, Y={4,5,6}

修改和顶点2相关顶点的?[]值，即

?[4]=20, ?[5]=13, ?[6]=∞ 4）

选取Y集合中标记?[]的最小值为?[5]=13, 将顶点5加入到X集

合，即

X={1, 2, 3, 5}, Y={4, 6}

修改和顶点5相关顶点的?[]值，即

?[4]=16, ?[6]=28 5）

选取Y集合中标记?[]的最小值为?[4]=16, 将顶点4加入到X集

合，即

X={1, 2, 3, 4, 5}, Y={6}

23

修改和顶点4相关顶点的?[]值，即

?[6]=18 6）

选取Y集合中标记?[]的最小值为?[6]=18, 将顶点6加入到X集

合，即

X={1, 2, 3, 4, 5, 6}, Y=? 故从源点到各个顶点的最短路径为： 1?3?2: 8 1?3: 4 1?3?2?5: 13 1?3?2?5?4: 16 1?3?2?5?4?6: 18

3. 分别用Kruscal和Prim方法求下图的最小耗费生成树。 解：

1）Prim方法：（选取从X集合中顶点出发到Y集合中顶点终止的边里面

24

1 1 2 2 6 7 3 3 9 4 4 7 5 3 2 6 6 权值最小的，并将该终点加入到X集合） ①X={1}， Y={2, 3, 4, 5, 6}

可选边为：（1,2,1），（1,3,6），（1,4,2） 权值最小边为（1,2,1） 故X={1,2}， Y={3, 4, 5, 6} ②X={1,2}， Y={3, 4, 5, 6}

可选边为：（1,3,6），（1,4,2），（2,3,7），（2,4,2） 权值最小边为：（1,4,2） 故X={1,2,4}， Y={3, 5, 6} ③X={1,2,4}， Y={3, 5, 6}

可选边为：（1,3,6），（2,3,7），（4,3,9），（4,5,7），权值最小边为：（1,3,6） 故X={1,2,3,4}， Y={5, 6} ④X={1,2,3,4}， Y={5, 6}

可选边为：（3,5,4），（3,6,3），（4,5,7），（4,6,6） 权值最小边为：（3,6,3） 故X={1,2,3,4,6}， Y={6} ⑤X={1,2,3,4,6}， Y={6}

可选边为：（3,5,4），（4,5,7），（6,5,3） 权值最小边为：（6,5,3） 故X={1,2,3,4,5,6}， Y=?

故最小耗费生成树的总耗费为：1+2+6+3+3=15 构造的最小耗费生成树为：1 6 3 5

25 1 3 3 2 4,6,6） （

2）Kruscal方法：（每次从边集里面选取边的权值最小且不和已有边构成回路）

由图示可知：最小耗费生成树的总耗费为：1+2+3+3+6=15，共可以生成4棵最小耗费生成树。

1 3 5 1 1 2 4 3 5 6 2 4 6 1 1 2 2 3 3 5 1 1 2 3 5 4 6 2 4 6 1 1 2 2 3 3 5 3 1 1 6 3 3 5 3 2 4 6 2 4 6

26

第六章

1. 用回溯法求解{1,2,3,4,5}这5个自然数中任取3个数的组合。 解：

从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合，例如R = {1,2,3,4,5}, n = 5, r = 3则搜索空间树（略）：

无重组合为：{1,2,3}; {1,2,4}; {1,2,5};{1,3,4}; {1,3,5}; {1,4,5};{2,3,4};{2,3,5};{2,4,5};{3,4,5} int n, r; int C[5]; char used[5];

void combine(int pos, int h) {

int i; //如果已选了r个元素了，则打印它们 if (pos==r) {

for (i=0; i

27

for (i=h; i<=n-r+pos; i++) //对于所有未用的元素 if (!used[i])

{

C[pos] = i+1; //把它放置在组合中 used[i]++; //使用该元素 combine(pos+1,i+1); //搜索第i+1个元素 used[i]--; //恢复递归前的值 } }

2. 用回溯法求6皇后的解。

解：搜索空间树（略）；可行解为：X1=(2,4,6,1,3,5); X3=(4,1,5,2,6,3); X4=(5,3,1,6,4,2)

3. 设计一个回溯算法，生成1,2,3,…,n的全排列。

void Permutatons1(int n) {

for (j=1; j<=n; j++) p[j]=j; perm1(1);

}

void Perm1(int m); {

28

X2=(3,6,2,5,1,4); if (m=n) output p[1..n] else

{ for (j=m; j<=n; j++)

{ interchange p[j] and p[m]; perm1(m+1);

} }

}

//comment:At this point p[m..n]=m,m+1,…,n interchange p[j] and p[m]; 29

本文来源：https://www.bwwdw.com/article/udkr.html