第1页 / 共103页
第2页 / 共103页
第3页 / 共103页
第4页 / 共103页
第5页 / 共103页
第6页 / 共103页
第7页 / 共103页
第8页 / 共103页
算法概论课后习题答案.pdf
Cover
0 Prologue
Ex.0.1
Ex.0.2
Ex.0.3
Ex.0.4
1 Algorithms with numbers
Ex.1.1
Ex.1.2
Ex.1.3
Ex.1.4
Ex.1.5
Ex.1.6
Ex.1.7
Ex.1.8
Ex.1.9
Ex.1.10
Ex.1.11
Ex.1.12
Ex.1.13
Ex.1.14
Ex.1.15
Ex.1.16
Ex.1.17
Ex.1.18
Ex.1.19
Ex.1.20
Ex.1.21
Ex.1.22
Ex.1.23
Ex.1.24
Ex.1.25
Ex.1.26
Ex.1.27
Ex.1.28
Ex.1.29
Ex.1.30
Ex.1.31
Ex.1.32
Ex.1.33
Ex.1.34
Ex.1.35
Ex.1.36
Ex.1.37
Ex.1.38
Ex.1.39
Ex.1.40
Ex.1.41
Ex.1.42
Ex.1.43
Ex.1.44
Ex.1.45
Ex.1.46
2 Divide-and-conquer Algorithms
Ex.2.1
Ex.2.2
Ex.2.3
Ex.2.4
Ex.2.5
Ex.2.6
Ex.2.7
Ex.2.8
Ex.2.9
Ex.2.10
Ex.2.11
Ex.2.12
Ex.2.13
Ex.2.14
Ex.2.15
Ex.2.16
Ex.2.17
Ex.2.18
Ex.2.19
Ex.2.20
Ex.2.21
Ex.2.22
Ex.2.23
Ex.2.24
Ex.2.25
Ex.2.26
Ex.2.27
Ex.2.28
Ex.2.29
Ex.2.30
Ex.2.31
Ex.2.32
3 Decompositions of graphs
Ex.3.1
Ex.3.2
Ex.3.3
Ex.3.4
Ex.3.5
Ex.3.6
Ex.3.7
Ex.3.8
Ex.3.9
Ex.3.10
Ex.3.11
Ex.3.12
Ex.3.13
Ex.3.14
Ex.3.15
Ex.3.16
Ex.3.17
Ex.3.18
Ex.3.19
Ex.3.20
Ex.3.21
Ex.3.22
Ex.3.23
Ex.3.24
Ex.3.25
Ex.3.26
Ex.3.27
Ex.3.28
Ex.3.29
Ex.3.30
Ex.3.31
4 Paths in graphs
Ex.4.1
Ex.4.2
Ex.4.3
Ex.4.4
Ex.4.5
Ex.4.6
Ex.4.7
Ex.4.8
Ex.4.9
Ex.4.10
Ex.4.11
Ex.4.12
Ex.4.13
Ex.4.14
Ex.4.15
Ex.4.16
Ex.4.17
Ex.4.18
Ex.4.19
Ex.4.20
Ex.4.21
Ex.4.22
5 Greedy algorithms
Ex.5.1
Ex.5.2
Ex.5.3
Ex.5.4
Ex.5.5
Ex.5.6
Ex.5.7
Ex.5.8
Ex.5.9
Ex.5.10
Ex.5.11
Ex.5.12
Ex.5.13
Ex.5.14
Ex.5.15
Ex.5.16
Ex.5.17
Ex.5.18
Ex.5.19
Ex.5.20
Ex.5.21
Ex.5.22
Ex.5.23
Ex.5.24
Ex.5.25
Ex.5.26
Ex.5.27
Ex.5.28
Ex.5.29
Ex.5.30
Ex.5.31
Ex.5.32
Ex.5.33
6 Dynamic programming
Ex.6.1
Ex.6.2
Ex.6.3
Ex.6.4
Ex.6.5
Ex.6.6
Ex.6.7
Ex.6.8
Ex.6.9
Ex.6.10
Ex.6.11
Ex.6.12
Ex.6.13
Ex.6.14
Ex.6.15
Ex.6.16
Ex.6.17
Ex.6.18
Ex.6.19
Ex.6.20
Ex.6.21
Ex.6.22
Ex.6.23
Ex.6.24
Ex.6.25
Ex.6.26
Ex.6.27
Ex.6.28
Ex.6.29
Ex.6.30
7 Linear programming and reductions
Ex.7.1
Ex.7.2
Ex.7.3
Ex.7.4
Ex.7.5
Ex.7.6
Ex.7.7
Ex.7.8
Ex.7.9
Ex.7.10
Ex.7.11
Ex.7.12
Ex.7.13
Ex.7.14
Ex.7.15
Ex.7.16
Ex.7.17
Ex.7.18
Ex.7.19
Ex.7.20
Ex.7.21
Ex.7.22
Ex.7.23
Ex.7.24
Ex.7.25
Ex.7.26
Ex.7.27
Ex.7.28
Ex.7.29
Ex.7.30
Ex.7.31
8 NP-complete problems
Ex.8.1
Ex.8.2
Ex.8.3
Ex.8.4
Ex.8.5
Ex.8.6
Ex.8.7
Ex.8.8
Ex.8.9
Ex.8.10
Ex.8.11
Ex.8.12
Ex.8.13
Ex.8.14
Ex.8.15
Ex.8.16
Ex.8.17
Ex.8.18
Ex.8.19
Ex.8.20
Ex.8.21
Ex.8.22
Ex.8.23
9 Coping with NP-completeness
Ex.9.1
Ex.9.2
Ex.9.3
Ex.9.4
Ex.9.5
Ex.9.6
Ex.9.7
Ex.9.8
Ex.9.9
Ex.9.10
10 Quantum algorithms
Ex.10.1
Ex.10.2
Ex.10.3
Ex.10.4
Ex.10.5
Ex.10.6
Ex.10.7
Ex.10.8
Algorithms
算法概论
习题试解 β
吴彧文（atyuwen）
atyuwen@gmail.com
http://hi.baidu.com/atyuwen
（如有错误，敬请指正）
0 Prologue
Ex.0.1
( )g
f Θ=
a)
b)
( )gOf =
c)
f Θ=
( )g
d)
f Θ=
( )g
e)
f Θ=
( )g
f)
( )gOf =
g)
f Ω=
( )g
h)
f Ω=
( )g
i)
j)
f Ω=
( )g
f Ω=
( )g
k)
f Ω=
( )g
l)
( )gOf =
m)
( )gOf =
n)
f Θ=
( )g
o)
f Ω=
( )g
p)
( )gOf =
q)
( )gOf =
Ex.0.2
根据等比数列求和公式：
( )
nS
( )
nS
=
=
a
1
a
1
n
,
×
c
1(
−
c
1
−
cif
n
)
,
=
1
cif
≠
1
易得结论。
Ex.0.3
a) 数学归纳法，显然有：
F
6
F
7
65.0
×
2
8
≥=
13
2
=
≥
8
=
3.11
75.0
×
≈
若
nF
− ≥
1
2
5.0
(
)1
n
−×
，
nF
− ≥
2
2
5.0
(
n
−×
)2
成立，则有：
F
n
=
F
n
1
−
+
F
n
−
2
≥
2
(5.0
n
−×
)1
(5.0
n
−×
)2
+
2
×>
22
(5.0
n
−×
)2
5.0
×
n
=
2
得证。
b) 同样是数学归纳法，显然，对任意 0>c
21
≤=
21
≤=
F
1
F
2
，有：
c
2
c
考虑归纳的递推过程，若
nF
− ≤
1
(
)1
2 −
nc
,
nF
− ≤
2
(
2 −
nc
)2
成立，有：
F
n
=
F
n
1
−
+
F
n
−
2
≤
2
(
nc
1
−
)
(
nc
−
2
)
+
2
=
cn
2
×
1
2
c
⎛
⎜
⎝
+
1
2
2
c
⎞
⎟
⎠
于是只需要
1
c
2
+
1
2 ≤
c
2
1
即可，令
x
= ，即有
1
c
2
2
x
≤−+ x
01
，于是有：
1
−−
2
5
≤≤
x
1
+−
2
5
将
x
= 代入上式，可解得：
1
c
2
≥c
log 2φ
,
其中
=φ
5
1+
2
，为黄金分割率，从
这里也可以看到 Fibonacci 数列与黄金分割之间的奇妙联系。用计算器可以算得
c
694
。
min ≈
.0
c) 即上面的
c
min ≈
.0
694
Ex.0.4
a) 两个 22× 的矩阵相乘，仍然得一个 22× 的矩阵，其中计算每个元素都分别需
要两次乘法和一次加法，所以总共需要 8 次乘法和 4 次加法。
b) 分治，若 n 为偶数，有
n
X
=
(
X
n
)22/
，若 n 为奇数，有
X
n
=
XX
•
1-n
。显然
计算 nX 只需要 (
O log 次矩阵乘法。
)n
c) 若某次的中间结果为
a
11
a
21
⎡
⎢
⎣
a
12
a
22
⎤
⎥
⎦
，则有：
a
11
a
21
⎡
⎢
⎣
a
12
a
22
⎤
×⎥
⎦
10
⎤
=⎥
11
⎦
⎡
⎢
⎣
a
12
a
21
⎡
⎢
⎣
a
11
a
21
+
+
a
12
a
22
⎤
⎥
⎦
由上式可知，任意中间结果矩阵，与 X 相乘后，其最大元素不会大于原先的最大
的，因此 bit 数是 ( )nO 的。
元素的 2 倍，所以可得，所有的中间结果都是
)2( nO
d)
(
O log 次矩阵乘法，每次相乘为 ( )nM ，当然总共是
)n
(
( )
nMO
log 。
( )
)n
e) 设总的计算次数为 nC ，则有以下递归式：
C
n
=
C
n
2/
( )nM
+
，由主定理知
Cn =
( )
(
)nMO
。
因 ( )
)2nOnM =
(
1 Algorithms with numbers
Ex.1.1
n 位数所能表示的最大值为
1nb − ，根据下列关系式：
b
2 1 3
− ≥
(
b
)
1
− =
b
3
− ⇔ −
3
b
(
)(
1
b
−
2
)
0
≥
b ≥ 时，有 3 个 1 位数的和不超过 2 位。
知，当 2
Ex.1.2
=
16 10
> ，所以可知一个数的 2 进制位数不超过 10 进制位数的 4 倍。
因为 42
设b 为 2 进制表示的位数， d 为 10 进制表示的位数，则有：
b
d
≈
2
log
log
10
n
n
=
log 10 3.322
≈
2
Ex.1.3
设只含根节点的树的高度为 1，则高度为 h 的满树的节点数为：
( )
N h
= + +
1
d
2
d
+
d
h
1
−
=
d
1
h
−
d
1
−
于是由 ( )
N h
≥ ⇒ = Ω
n
h
(
logd
n
)
。
准确表示的话有：
h
=
log (
d
⎡
⎢
dn n
− +
1)
⎥ 。
⎤
Ex.1.4
Hint 很强大：
log
(
n
)
!
=
O
log
(
n
)
!
= Ω
(
⎛
⎜
⎜
⎝
log
n
n
(
⎛
⎜
⎜
⎝
⎛
⎜
⎝
)
n
2
)
⎞
⎟
⎠
=
n
/2
(
O n
⎞
⎟
⎟
⎠
⎞
⎟
⎟
⎠
log
log
n
)
n
2
⎛
⎜
⎝
= Ω •
于是有： (
log
n
)
!
= Θ
(
n
log
n
)
。
= Ω
(
n
log
n
)
log
n
2
⎞
⎟
⎠
Ex.1.5
这题的 Hint 更强大，考虑调和级数
1
3
将每个分母约束到不大于它的 2 的幂形式，有：
1
4
1 1
1 2
H O H
1
4
=
(
u
) 1 1
= + + + + + + +
1 2
1
1
4 8
1
4
1
2
1
4
1
5
1
6
H = + + + + + + +
1
7
1
8
将这个新的级数想象成一颗二叉树的层序遍历，则每层和为 1，由 Ex.1.3 我们知道
树的高度是 (
Θ
然后，将每个分母约束到不小于它自身的 2 的幂，有：
的，即 uH 也是 (
Θ
H O
log n
log n
，于是
log
。
=
n
)
)
(
)
H
= Ω
(
H
l
) 1 1
= + + + + + + +
1 2
1
1 1 1 1
4 8 8 8 8
1
4
忽略到第一项 1，后面又是一颗二叉树的层序遍历，且每层和为 1/2，以上同理可
得，
H
= Ω
n
(log )
，于是得到
H
= Θ
n
(log )
。
Ex.1.6
设有两二进制数 a ，b ，其中
a
=
a a
n n
1
−
a a a a
3 2 1 0
，则有：
a b
× =
n
∑
i
=
0
(
a
i
)
b
× ×
n
2
=
n
∑
i
=
0
(
a
i
×
b
)
<<
n
这正是 Grade-School 方法的数学意义，于是得证。
Ex.1.7
)
设 (
换一下两个乘数即可），则有：
,
(
T n m T n m
)
1
− +
=
)
(
,
,
( )
O n
T n m 为计算 n 位数乘 m 位数所需步数，且假设 n m≥ ，（如果不满足的话交
后面的 ( )O n 包含了一些不超过 mn + 位数的加法和移位操作，（前面之所以需要
n m≥ 就是为了保证在这里的所有操作都是 ( )O n 的，因为
mn
+
2≤
n
），于是可
以得到： (
)nmOmnT
=
)
(
,
。
Ex.1.8
关于正确性：
a) 当 0=x 时该算法显然是正确的。
b) 因 y
r < ，所以
21
<+
2
y
r
总是成立。
c) 当 x 为偶数时，有
x
⎢=
⎢⎣
x
2
⎥
2
=×⎥⎦
(
yq
+
r
2)
=×
2
yp
+
2
r
d) 当 x 为奇数时，有
x
⎢=
⎢⎣
x
2
⎥
(12
=+×⎥⎦
yq
+
r
212)
=+×
yp
+
2
r
+
1
希望我已经“证明”了它的正确性了，下面来看时间复杂度：总共迭代 n 次，每次
迭代需要 ( )O n 次操作，于是 ( )
Ex.1.9
根据同余的定义，有：
(
T n O n
)2
。
=
x
y
≡
≡
x
y
'mod
'mod
N
N
x
'
⇒ = +
y
'
⇒ = +
x
y
rN
sN
于是：
x
x
)
(
s N
r
'
+ = + +
+
ry
sx
'
'
(
+
+
× =
x
'
x y
'
y
'
+
y
y
y
x
'
⇒ + ≡ +
rsN N
)
⇒ ≡
x
xy
y
'mod
x y
'
N
'mod
N
Ex.1.10
a
≡
b
mod
N
⇒ = +
b rN b rsM a
= +
⇒ ≡
a
b
mod
M
Ex.1.11
一般解这种题的思路就是要想方设法的凑 1，注意到：
1536
4
≡
64
512
(
−≡
6
512
)
≡
36
256
≡
1
256
≡
，有：
66
=×
(
mod
35
1
+
)35
1
4824
9
≡
(
999
××
1608
)
(
−≡
6
1608
)
≡
36
804
≡
1
804
≡
1
(
mod
)35
即：
1536
4
−
9
4824
≡−≡
011
(
mod
)35
。
Ex.1.12
这题很简单：
2006
2
2
≡
2
4
2005
≡
1
2
2005
≡
1
(
)3mod
Ex.1.13
同样是凑 1，注意到：
5
≡
(
−≡
30000
5
65
1
31
=×
−
，有：
5
25
5
20000
10000
10000
10000
×
≡
×
)
(
10000
1
mod
10000
30
≡
≡
1
)31
(
−≡
6
10000
)
×
5
10000
123456
6
≡
≡
6
×
41152
82304
6
(
30
)
41152
(
−≡
≡
)
1
36
41152
41152
41152
6
×
(
mod
1
≡
)31
≡
41152
5
×
6
41152
即：
30000
5
−
6
123456
≡−≡
011
(
mod
)31
。
Ex.1.14
采用 Ex.0.4 中的矩阵形式，但是对每一步的中间结果都进行模 p 操作，这样使得
)2
(
)
所有的中间结果都小于 p 。每一步的乘法以及求模运算均是 (
p ，于是得
到总的时间复杂度为：
log
O
(
T n p O
=
)
,
log
n
(
log
p
)
)2
(
log
n
)
。
如果 p 为一常数，则有： ( )
Ex.1.15
T n O
=
(
欲使得
ax bx
≡
mod
c
⇒ ≡
a
b
mod
c
成立，只需要保证 1 mod
x
−
c
存在：
ax bx
≡
mod
c
⇒
axx
1
−
≡
bxx
1
−
mod
c
⇒ ≡
a b
mod
c
由书可知， 1 mod
x
−
c
存在的条件是 (
gcd
x c = ，即： x ， c 互素。
,
1
)
另 外 可 以 看 出 来 ， 这 个 条 件 其 实 是 充 分 必 要 的 ， 下 面 来 换 个 方 式 证 明 ， 设
ax bx
，则有：
mod
c
≡
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
