算法第二章习题

第2章习题

1. 证明当ak?0时，任何多项式p(n)?aknk?ak?1nk?1?...?a0属于集合?(nk)

aknk?ak?1nk?1?...?a0p(n)?ak>0 解：limk?limkn??nn??n

所以p(n)?aknk?ak?1nk?1?...?a0??(nk)

2. 对于下列每一种函数，指出它们属于哪一种?(g(n))类型（尽量使用最简单的g(n)），并给出证明。

a. (n2?1)10 b. 10n2?7n?3 c. 2nlg(n?2)2?(n?2)2lgd. 2n?1?3n?1 e. ?log2n?

118216n20?C20n?C20n?...?1(n2?1)10?lim?1 解： a. lim2020n??n??nnn2

所以 (n2?1)10??(n20)

10n2?7n?310n2?7n?3 b. lim?lim?1

n??n??nn2

所以

10n2?7n?3??(n)

nc. 由于2nlg(n?2)2??(nlgn)，(n?2)2lg??(n2lgn)。显然，当n??2

2时，nlgn>nlgn，所以2nlg(n?2)?(n?2)lg22n2??(n2lgn)

时，3>2，所

nnd. 由于2n?1??(2n)，3n?1??(lgn)。显然，当n??

以2n?1?3n?1??(3n)

e. log2n??log2n?

所以?log2n???(lgn)

3. 写出下列表达式的结果：

a.

ij b. ?1/i(i?1) c. ?i(i?1) ??ij?1?1i?1i?1nnnn?1a.解：

ij??ij?1?1nn?i?1?nn(n?1)n(n?1)nn(n?1)n(n?1)n2(n?1)2 i????i?22i?1224b.解：

i?1?1/i(i?1)??1?n11111111??...??1????...??1?22?3n(n?1)223nn?11n?n?1n?1n?1n?1c.解：

i?1?i(i?1)?n?1i?1?i?2i?1?i?(n?1)n(2n?1)n(n?1)(n?1)n(n?1) ??623

4. 计算增长次数（即写出下列和的?(g(n))） a.

?(ii?0n?12?1) b

?lgii?2nn?12 c

?(i?1)2i?2ni?1 d

??(i?j)

i?0j?0n?1i?1解：a. ?(n) b. ???1??(n3)

3i?0j?i?1k?in?2n?1

c. ?(n?2)

n

d. (?n)

3

5. x1,...,xn的采样方差n可以这样计算：

?xi?i?1n?x?2n?1或者

，其中x??xi?1nin

?n?2?x?x?i??i??ni?1?i?1?

n?1根据每个公式，对求方差时需要用到的除法、乘法和加/减运算的次数进行计算和比较。

解：第一个公式： 除法：2次， 乘法：n次， 加/减法：3n-1次 第二个公式：除法：2次， 乘法：n+1次， 加/减法：2n次

6. 考虑下面的算法

n2算法 secret(A[0..n-1])

//输入：包含n个实数的数组A minval ? A[0]; maxval ? A[0] for i ? 0 to n-1 do if A[i] < minval

minval ? A[i]

if A[j] > maxval

maxval ? A[i]

return maxval-minval 对于本算法，试回答下述问题： 1）该算法求的是什么？ 2）它的基本操作是什么？

3）该基本操作执行了多少次？ 4）该算法的效率类型是什么？

5）对该算法进行改进，若不可能，试证明之。 解：1）数组中最大的元素与最小元素之差 2）比较大小 3）2n次

4) ?(n)

5) 可以使用

if A[i] < minval

minval ? A[i]

else if A[j] > maxval

maxval ? A[i]

替换 if A[i] < minval

minval ? A[i]

if A[j] > maxval

maxval ? A[i]

在输入并非最糟糕的情况下，能在一定程度上提升算法的效率。

7. 已知算法GE如下：

算法GE(A[0..n-1, 0..n])

// 输入: 一个n行n+1列的实数矩阵A for i ?0 to n-2 do

for j ? i+1 to n-1 do for k ? i to n do

A[j,k] ? A[j,k] – A[i,k] * A[j,i]/A[i,i] 试问：

1）该算法的时间效率类型

2）该算法有何性能缺陷，试改进之。 解：1）将循环最内层的A[j,k] ? A[j,k] – A[i,k] * A[j,i]/A[i,i]中的乘法M（n）

或除法D(n)作为基本操作

53k?1M(n)=D(n) = ?

22故该算法的时间效率类型为?(n3)

2）由于在最内层循环A[j,k] ? A[j,k] – A[i,k] * A[j,i]/A[i,i]中，

A[j,i]/A[i,i]并不包含最内层循环变量k。所以我们可以使用temp= A[j,i]/A[i,i], A[j,k] ? A[j,k] – A[i,k] * temp来减少除法的操作次数。

8. 求解下列递归关系

1） x(n)= 3x(n-1)，其中n>1，x(1)=4

2） x(n)= x(n/3)+ n，其中n>1，x(1)=1（给出n=3k的情况求解） 3） x(n)= 4x(n-1) + x(n-2) - 4，其中n>=0, x(0)=0, x(1)=1。

解：1）x(n) = 3x(n ? 1)

= 3[3x(n ? 2)] = 3x(n ? 2)

= 32[3x(n ? 3)] = 33x(n ? 3) = …

= 3ix(n ? i) = ...

= 3n?1x(1) = 4·3n?1.

2）x(n) = x(n/3) + n for n > 1, x(1) = 1 (solve for n = 2k)

x(3k) = x(3k?1) + 3k

= [x(3k?2) +3k?1] + 3k = x(3k?2) + 3k?1 +3k

= [x(3k?3) + 3k?2] + 3k?1 + 3k = x(3k?3) + 3k?2 +3k?1 +3k = ...

= x(3k?i) + 3k?i+1 +3k?i+2 + ... + 3k = ...

= x(3k?k) + 31 + 32 + ... + 3k = 1 + 31 + 32 + ... +3k 3n?1=

23n?1= 22

3）

9. 试证明，对于一个任意十进制正整数n，下述算法BinRec(n)所做的加法运算的精确次数是?log2n?：

算法 BinRec(n)

//输入：一个正的十进制整数n

//输出：n的二进制表示的位数 if n=1 return 1

else return BinRec(?n/2?) + 1

解：由题知A(1)=0 当n=2k时；

A(n) = A(2k) = A(2 k-1)+1 = A(2k-2)+2

······ =A(2k-k)+k =A(1)+k

因为n=2k；所以k=log2n A(n) = log2n

10. 给定算法Min1(A[first..last])和Min2(A[first..last])

算法1 Min1(A[first..last])

//输入last>= first且包含last-first+1个实数数组A

if first= last return A[first];

else temp ? Min1(A[first..last-1]) if temp<= A[last] return temp else return A[last]

算法2 Min2(A[first..last])

//输入last>= first且包含last-first+1个实数数组A

if first = last return A[first];

else temp1 ? Min2(A[first..??first?last?/2?] ) temp2 ? Min2(A[??first?last?/2?+1..last] )

if temp1 <= temp2 return temp1 else return temp2 试给出

1）算法1和算法2所做的基本操作次数的递推关系并求解。

2）算法1和算法2哪个更快。自已能否提出一个算法，使新算法效率胜过算法1和算法2。

解：1）1. 基本操作temp<= A[last]；

M(n)=M(n-1)+1&M(1)=0 可知 M(n) = n； 2. 基本操作temp1<=temp2；

M(n)=2*M(n/2)+1&M(1)=0可知 M(n)=n；

2) 一样快，求最小值比较方法就是线性方法。

除此之外，可以考虑位运算。

11. 试证明：

F(n)??01??F?n?1? 当n?1时，????11? F(n)F(n?1)????n

解：用数学归纳法证明：

?F(0)F(1)??01?当n=1时，????12?成立； F(1)F(2)????F(k)??01??F(k?1)设 当n=k时，????11?成立； F(k)F(k?1)????kF(k?1)??F(k)F(k)?F(k?1)??F(k)则 当n=k+1时，????F(k)?F(k?1)F(k?1)?F(k)?

F(k?1)F(k?2)????F(k)??01??01??01??01??F(k?1) ???*?11???11?*?11???11?F(k)F(k?1)??????????kk?1

也就是说，当n=k+1时，成立，证毕。

12. 考虑基于定义计算第n个Fibonacci数的递归算法F(n):

算法 F(n)

//根据定义，递归计算第n个Fibonacci数 //输入：一个非负整数n //输出：第n个Fibonacci数 if n <= 1 return n

else return F(n-1) + F(n-2)

令C(n)和Z(n)分别是F(n)调用F(1)和F(0)的次数，试证明： 1）C(n) = F(n) 2）Z(n) = F(n-1)

解：用数学归纳法证明：

当n=1时，C（n）= 1 = F（1）， Z（n） = 0 = F（0）成立； n=2时，C（n）= 2 = F（2）， Z（n） = 1 = F（1）成立； 假设 当n=k-1时，有C(k-1) = F(k-1)， Z(k-1) = F(k-2) 成立；

当n=k时，有C(k) = F(k)， Z(k) = F(k-1) 成立；

则 当n=k+1时，F（k+1）= F（k）+ F（k-1），

那么， C（k+1）= C（k）+ C（k-1）= F（k）+ F（k-1） = F（k+1） Z（k+1）= Z（k）+ Z（k-1）= F（k-1）+ F（k-2） = F（k） 也就是说，当n=k+1时，成立，证毕。

13. 当两个连续Fibonacci数F(n)和F(n-1)作为Euclidean algorithm for greatest common divisor (GCD)的输入时，该算法需要做多少次求模运算？

解：F（n）= F（n-1）+ F（n-2）， 也就是说

m <- F（n)、 n <- F（n-1）、 r <- F（n-2）； 又F（n）mod F（n-1）= F（n-2）；于是， r从F（n-2）一直倒退到0 求模运算做了 n-2+1=n-1 次。

14. 试证明：

当n?1时, F(n+1)?F(n-1) – (F(n))2 = (-1)n

解：由11题得：

F(n)??01??F?n?1???当n?1时，? ??F(n?1)??11??F(n)n

展开即得：当n?1时, F(n+1)?F(n-1) – (F(n))2 = (-1)n

15. 给定n，试问有多少个仅由1和2组成的序列（每个序列的和为n）。如当n=4时，有5个序列（每个序列和为4）：

1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2

解：多次计算可知 F(n)?F(n?1)?F(n?2)，

也就是说，他们的个数组成Fibonacci数列；

个数为：

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