算法第二章习题.doc

第2章习题1. 证明当时，任何多项式属于集合解：0所以2. 对于下列每一种函数，指出它们属于哪一种类型（尽量使用最简单的g(n)），并给出证明。a. b. c. d. e. 解： a. 所以 b. 所以 c. 由于，。显然，当n时，nlgn，所以d. 由于，。显然，当n时，所以e. +1, 又，+1所以3. 写出下列表达式的结果：a. b. c. a.解：b.解：c.解：4. 计算增长次数（即写出下列和的）a. b c d 解：a. b. c. d.5. 的采样方差n可以这样计算：，其中或者 根据每个公式，对求方差时需要用到的除法、乘法和加/减运算的次数进行计算和比较。解：第一个公式： 除法：2次， 乘法：n次， 加/减法：3n-1次第二个公式：除法：2次， 乘法：n+1次， 加/减法：2n次6. 考虑下面的算法算法 secret(A0.n-1) /输入：包含n个实数的数组A minval A0; maxval A0 for i 0 to n-1 do if Ai maxvalmaxval Ai return maxval-minval对于本算法，试回答下述问题：1） 该算法求的是什么？2） 它的基本操作是什么？3） 该基本操作执行了多少次？4） 该算法的效率类型是什么？5） 对该算法进行改进，若不可能，试证明之。解：1）数组中最大的元素与最小元素之差2）比较大小3）2n次4) 5) 可以使用if Ai maxvalmaxval Ai替换if Ai maxvalmaxval Ai在输入并非最糟糕的情况下，能在一定程度上提升算法的效率。7. 已知算法GE如下： 算法GE(A0.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 Aj,k Aj,k Ai,k * Aj,i/Ai,i 试问：1） 该算法的时间效率类型2） 该算法有何性能缺陷，试改进之。解：1）将循环最内层的Aj,k Aj,k Ai,k * Aj,i/Ai,i中的乘法M（n）或除法D(n)作为基本操作M(n)=D(n) = 故该算法的时间效率类型为2）由于在最内层循环Aj,k Aj,k Ai,k * Aj,i/Ai,i中，Aj,i/Ai,i并不包含最内层循环变量k。所以我们可以使用temp= Aj,i/Ai,i, Aj,k Aj,k Ai,k * temp来减少除法的操作次数。8. 求解下列递归关系1） x(n)= 3x(n-1)，其中n1，x(1)=42） x(n)= x(n/3)+ n，其中n1，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)= 33x(n 2) = 32x(n 2)= 323x(n 3) = 33x(n 3)= = 3ix(n i)= .= 3n1x(1) = 43n1.2）x(n) = x(n/3) + n for n 1, x(1) = 1 (solve for n = 2k)x(3k) = x(3k1) + 3k= x(3k2) +3k1 + 3k = x(3k2) + 3k1 +3k= x(3k3) + 3k2 + 3k1 + 3k = x(3k3) + 3k2 +3k1 +3k= .= x(3ki) + 3ki+1 +3ki+2 + . + 3k= .= x(3kk) + 31 + 32 + . + 3k = 1 + 31 + 32 + . +3k= =3）9. 试证明，对于一个任意十进制正整数n，下述算法BinRec(n)所做的加法运算的精确次数是： 算法 BinRec(n) /输入：一个正的十进制整数n /输出：n的二进制表示的位数 if n=1 return 1 else return BinRec() + 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= A(n) = 10. 给定算法Min1(Afirst.last)和Min2(Afirst.last) 算法1 Min1(Afirst.last) /输入last= first且包含last-first+1个实数数组A if first= last return Afirst; else temp Min1(Afirst.last-1) if temp= first且包含last-first+1个实数数组A if first = last return Afirst; else temp1 Min2(Afirst. ) temp2 Min2(A+1.last ) if temp1 = temp2 return temp1 else return temp2试给出1）算法1和算法2所做的基本操作次数的递推关系并求解。2）算法1和算法2哪个更快。自已能否提出一个算法，使新算法效率胜过算法1和算法2。解：1）1. 基本操作temp= Alast； 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. 试证明： 当1时，解：用数学归纳法证明：当n=1时，成立；设 当n=k时，成立；则 当n=k+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. 试证明：当1时, F(n+1)F(n-1) (F(n)2 = (-1)n解：由11题得：当1时，展