算法设计与分析基础习题参考答案.doc

习题 1.1

5..证明等式 gcd(m,n)=gcd(n,m mod n)对每一对正整数 m,n 都成立.

Hint:

根据除法的定义不难证明:

如果 d 整除 u 和 v, 那么 d 一定能整除 u±v;

如果 d 整除 u,那么 d 也能够整除 u 的任何整数倍 ku.

对于任意一对正整数 m,n,若 d 能整除 m 和 n,那么 d 一定能整除 n 和 r=m mod n=m-qn；显然，若 d

gcd(m,n)=gcd(n,m)

并且这种交换处理只发生一次.

7.a.对于所有 1≤m,n≤10 的输入, Euclid 算法最少要做几次除法?(1 次)

b. 对于所有 1≤m,n≤10 的输入, Euclid 算法最多要做几次除法?(5 次)

gcd(5,8)

习题 1.2

1.(农夫过河)

P—农夫 W—狼 G—山羊 C—白菜

2.(过桥问题)

1,2,5,10---分别代表 4 个人, f—手电筒

If a≠0

D←b*b-4*a*c

If D>0

temp←2*a

x1←(-b+sqrt(D))/temp

x2←(-b-sqrt(D))/temp

return x1,x2

else if D=0 return –b/(2*a)

else return “no real roots”

else //a=0

else //a=b=0

else return “no real roots”

5. 描述将十进制整数表达为二进制整数的标准算法

a.用文字描述

b.用伪代码描述

解答：

a.将十进制整数转换为二进制整数的算法

输入：一个正整数 n

第二步：如果 n=0，则到第三步，否则重复第一步

//输入：正整数 n

//输出：该正整数相应的二进制数，该数存放于数组 Bin[1...n]中

i=1

while n!=0 do {

Bin[i]=n%2;

n=(int)n/2;

i++;

}

while i!=0 do{

print Bin[i];

i--;

}

a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:

4.(古老的七桥问题)

习题 1.4

1.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.

a.删除数组的第 i 个元素(1<=i<=n)

b.删除有序数组的第 i 个元素(依然有序)

hints:

a. Replace the ith element with the last element and decrease the array size of 1

b. Replace the ith element with a special symbol that cannot be a value of the array’s element(e.g., 0 for

an array of positive numbers ) to mark the ith position is empty.

(“lazy deletion”)

习题 2.1

1

欧几里得算法的时间复杂度

欧几里得算法, 又称辗转相除法, 用于求两个自然数的最大公约数. 算法的思想很简单, 基于下面

的数论等式

gcd(a, b) = gcd(b, a mod b)

输出: a 和 b 的最大公约数

function gcd(a, b:integer):integer;

if b=0 return a;

else return gcd(b, a mod b);

我们不妨设 a>b>=1(若 a<b 我们只需多做一次模运算, 若 b=0 或 a=b 模运算的次数分别为 0 和 1),

un=gcd(a, b), un+1=0. 我们比较数列{un}和菲波那契数列{Fn}, F0=1<=un, F1=1<=un-1, 又因为由

uk mod uk+1=uk+2, 可得 uk>=uk+1+uk+2, 由数学归纳法容易得到 uk>=Fn-k, 于是得到 a=u0>=Fn,

b=u0>=Fn-1. 也就是说如果欧几里得算法需要做 n 次模运算, 则 b 必定不小于 Fn-1. 换句话说, 若

b<Fn-1, 则算法所需模运算的次数必定小于 n. 根据菲波那契数列的性质, 有 Fn-1>(1.618)n/sqrt(5),

即 b>(1.618)n/sqrt(5), 所以模运算的次数为 O(lgb)---以 b 为底数 = O(lg(2)b)---以 2 为底数，输入规

模也可以看作是 b 的 bit 位数。

a. 如果 t(n)∈O(g(n),则 g(n)∈Ω(t(n))

解:

a. 这个断言是正确的。它指出如果 t(n)的增长率小于或等于 g(n)的增长率，那么 g(n)的增长率大

于或等于 t(n)的增长率

由 t(n)≤c·g(n) for all n≥n0, where c>0

则： for all n≥n0

设 f(n)∈Θ(αg(n)),则有：

a.Ω符号

g2(n)})。