算法第二章习题

第2章习题

1. 证明当0>k a 时，任何多项式011...)(a n a n a n p k k k k +++=--属于集合)(k n Θ

解：110...()

lim lim k k k k k k k n n a n a n a p n a n n

--→∞→∞+++==>0 所以011...)(a n a n a n p k k k k +++=--∈)(k n Θ

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

a. 102)1(+n b. 37102++n n c. 2

lg )2()2lg(222n n n n +++ d. 1132-++n n e. ??n 2log 解： a. 20118216 210

20202020...1(1)lim lim 1n n n C n C n n n n →∞→∞+++++== 所以 102)1(+n ∈20()n Θ b. lim 1n n n →∞==

所以

37102++n n ∈()n Θ

c. 由于22lg(2)n n +∈(lg )n n Θ，2(2)lg 2

n

n +∈2(lg )n n Θ。显然，当n →∞ 时，2

lg n n >nlgn ，所以2 lg )2()2lg(22 2 n

n n n +++∈2(lg )n n Θ

d. 由于12+n ∈(2)n Θ，13-n ∈(lg )n Θ。显然，当n →∞ 时，3n >2n ，所 以11 32

-++n n ∈(3)n Θ

e. n 2log ≤??n 2log <=\"\" θ，n=\"\" ∈(lg=\"\" 又n=\"\"> 所以??n 2log ∈(lg )n Θ 3. 写出下列表达式的结果： a.

∑∑==n i n j ij 1 1

b. ∑=+n i i i 1 )1(/1 c. ∑-=+1 1

)1(n i i i a.解： 4

)1(2)1(2)1(2 )1(2

)1(2 21 1 1 1 +=+?+= +=+= ∑∑

∑∑====n n n n n n i n n i n n ij n i n i n i n j b.解： 1 1111 1

1...3121211)1(1...321211)1(/11 +=+-

=+-++-+-=+++?+?= +∑=n n n n n n n i i n i c.解： 3 )

1()1(2)1(6)12()1()1(1 1 1 1 2 1 1 +-=

-+--= + =

+∑∑∑-=-=-=n n n n n n n n i i i i n i n i n i 4. 计算增长次数（即写出下列和的))((n g Θ） a. ∑-=+1 2 )1(n i i b ∑-=1 2 2 lg n i i c ∑=-+n i i i 2 1 2 )1( d ∑∑-=-=+101 )(n i i j j i 解：a. 3 ()n Θ b. 21 301 1()n n n i j i k i

n --==+==Θ∑∑∑ c. (2)n n Θ? d.3 ()n Θ

5. n x x ,...,1的采样方差n 可以这样计算： () 1 1 2

--∑=n x x n i

i ，其中n x x n i i ∑== 1 或者 1 2 112

-???? ??-∑∑==n n x x n i i n i i

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

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

6. 考虑下面的算法 算法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]

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

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

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

7.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)作为基本操作 M(n)=D(n) = 1 53 22 k+ +

故该算法的时间效率类型为3 () n Θ

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)] = 32x(n ?2) = 32[3x(n ?3)] = 33x(n ?3) = …

= 3i x(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 + (3) =31 2 n- =31 2 n- 3）

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

的精确次数是[]n2 log：

算法BinRec(n)

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

//输出：n 的二进制表示的位数 if n=1 return 1 else return BinRec(??2/n ) + 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=2log n A(n) = 2log n

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..()??2/last first +] ) temp2 ← Min2(A[()??2/last first ++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. 试证明： 当≥ n1时， ()n n F n F n F n F

= + - 1 1 1 )1 ( ) ( ) ( 1

解：用数学归纳法证明： 当n=1时， (0)(1)01 (1)(2)12 F F F F

= 成立； 设当n=k时， (1)()01 ()(1)11 k F k F k F k F k - = + 成立；

则当n=k+1时， ()(1)()()(1) (1)(2)()(1)(1)() F k F k F k F k F k F k F k F k F k F k F k ++- = +++-++ 1

(1)()01010101

**

()(1)11111111 k k F k F k F k F k + - === +

也就是说，当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.试证明： 当≥

n1时, F(n+1)?F(n-1) – (F(n))2 = (-1)n 解：由11题得： 当≥ n1时， ()n n F n F n F n F =

+ - 1 1 1 )1 ( ) ( ) ( 1

展开即得：当≥

n1时, 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 解：多次计算可知()(1)(2) F n F n F n =-+-，

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

个数为：