没有合适的资源?快使用搜索试试~ 我知道了~
Algorithms.算法概论.习题答案
5星 · 超过95%的资源 需积分: 50 2.5k 下载量 94 浏览量
2009-10-21
21:42:55
上传
评论 51
收藏 689KB PDF 举报
温馨提示
试读
103页
Algorithms.算法概论.习题试解
资源详情
资源评论
资源推荐
Algorithms
算法概论
习题试解
β
吴彧文(atyuwen)
atyuwen@gmail.com
http://hi.baidu.com/atyuwen
(如有错误,敬请指正)
0 Prologue
Ex.0.1
a)
()
gf Θ=
b)
()
gOf =
c)
()
gf Θ=
d)
()
gf Θ=
e)
()
gf Θ=
f)
()
gOf =
g)
()
gf Ω=
h)
()
gf Ω=
i)
()
gf Ω=
j)
()
gf Ω=
k)
()
gf Ω=
l)
()
gOf =
m)
()
gOf =
n)
()
gf Θ=
o)
()
gf Ω=
p)
()
gOf =
q)
()
gOf =
Ex.0.2
根据等比数列求和公式:
(
)
()
1,
1
1(
1,
)
1
1
≠
−
−
=
=×=
cif
c
ca
nS
cifnanS
n
易得结论。
Ex.0.3
a) 数学归纳法,显然有:
3.11213
828
75.0
7
65.0
6
≈≥=
=≥=
×
×
F
F
若
()
15.0
1
2
−×
−
≥
n
n
F
,
()
25.0
2
2
−×
−
≥
n
n
F
成立,则有:
nnnn
nnn
FFF
×−×−×−×
−−
=×>+≥+=
5.0)2(5.0)2(5.0)1(5.0
21
22222
得证。
b) 同样是数学归纳法,显然,对任意 0>c ,有:
c
c
F
F
2
2
1
21
21
≤=
≤=
考虑归纳的递推过程,若
()
1
1
2
−
−
≤
nc
n
F
,
(
)
2
2
2
−
−
≤
nc
n
F
成立,有:
() ( )
⎟
⎠
⎞
⎜
⎝
⎛
+×=+≤+=
−−
−−
cc
cnncnc
nnn
FFF
2
21
21
2
1
2
1
222
于是只需要
1
2
1
2
1
2
≤+
cc
即可,令
c
x
2
1
=
,即有
01
2
≤−+ xx
,于是有:
2
51
2
51 +−
≤≤
−−
x
将
c
x
2
1
=
代入上式,可解得: ,log
2
φ
≥c 其中
2
51+
=
φ
,为黄金分割率,从
这里也可以看到 Fibonacci 数列与黄金分割之间的奇妙联系。用计算器可以算得
694.0
min
≈c 。
c) 即上面的
694.0
min
≈
c
Ex.0.4
a) 两个
22 ×
的矩阵相乘,仍然得一个
22
×
的矩阵,其中计算每个元素都分别需
要两次乘法和一次加法,所以总共需要 8 次乘法和 4 次加法。
b) 分治,若
n
为偶数,有
()
2
2/n
XX
n
= ,若
n
为奇数,有
1-nn
XXX •
=
。显然
计算
n
X 只需要
(
)
nO log 次矩阵乘法。
c) 若某次的中间结果为
⎥
⎦
⎤
⎢
⎣
⎡
2221
1211
aa
aa
,则有:
⎥
⎦
⎤
⎢
⎣
⎡
+
+
=
⎥
⎦
⎤
⎢
⎣
⎡
×
⎥
⎦
⎤
⎢
⎣
⎡
222121
121112
2221
1211
11
10
aaa
aaa
aa
aa
由上式可知,任意中间结果矩阵,与
X
相乘后,其最大元素不会大于原先的最大
元素的 2 倍,所以可得,所有的中间结果都是
)2(
n
O 的,因此 bit 数是
()
nO 的。
d)
()
nO log 次矩阵乘法,每次相乘为
(
)
nM ,当然总共是
(
)()
(
)
nnMO log 。
e) 设总的计算次数为
n
C ,则有以下递归式:
(
)
nMCC
nn
+
=
2/
因
()
(
)
2
nOnM = ,由主定理知
(
)
(
)
nMOC
n
=
。
1 Algorithms with numbers
Ex.1.1
n 位数所能表示的最大值为 1
n
b
−
,根据下列关系式:
(
)
(
)
(
)
2
13 1 3 3 1 2 0bbbbb
−
≥−=−⇔− −≥
知,当
2b ≥
时,有 3 个 1 位数的和不超过 2 位。
Ex.1.2
因为
4
21610=>,所以可知一个数的 2 进制位数不超过 10 进制位数的 4 倍。
设
b
为 2 进制表示的位数,
d
为 10 进制表示的位数,则有:
2
2
10
log
log 10 3.322
log
nb
dn
≈=≈
Ex.1.3
设只含根节点的树的高度为 1,则高度为
h
的满树的节点数为:
()
21
1
1
1
h
h
d
Nh d d d
d
−
−
=+ + + =
−
于是由
() ( )
log
d
Nh n h n≥⇒=Ω 。
准确表示的话有:
log ( 1)
d
hdnn=−+
⎡
⎤
⎢
⎥
。
Ex.1.4
Hint 很强大:
()
(
)
(
)
()
()
()
/2
log ! log log
log ! log log log
222
n
n
nO n Onn
nnn
nnn
==
⎛⎞
⎛⎞
⎛⎞ ⎛ ⎞
=Ω =Ω • =Ω
⎜⎟
⎜⎟
⎜⎟ ⎜ ⎟
⎜⎟
⎜⎟
⎝⎠ ⎝ ⎠
⎝⎠
⎝⎠
于是有:
()
(
)
log ! lognnn=Θ 。
剩余102页未读,继续阅读
atyuwen
- 粉丝: 12
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论30