算法导论第2章

练习

2.1-1

开始 :<31, 41, 59, 26, 41, 58>
1 :<31, 41, 59, 26, 41, 58>
2 :<31, 41, 59, 26, 41, 58>
3 :<31, 41, 59, 26, 41, 58>
4 :<26, 31, 41, 59, 41, 58>
5 :<26, 31, 41, 41, 59, 58>
6 :<26, 31, 41, 41, 58, 59>

2.1-3

1
2
3
4
5
search(v, A)
for j = 1 to A.length
if A[i] == v
return i
return NIL

初始化 : 在第一轮循环迭代,当j = 1的时候,循环不变式成立。
保持 : for循环体将A[2],A[3],A[4] …..右移一个位置,与关键值v进行比较。
终止 : j = A.length+1 或者找到了与v值相等的数值。

2.1-4

这题练习好像可以用数字逻辑中的全加器来求解,首先列出i位进行运算的真值表

1
2
3
4
5
6
7
8
9
A  B  C  S  S+1
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

S = \overline{A}\overline{B}C + \overline{A}B\overline{C} + A\overline{B}\overline{C}
S+1 = \overline{A}BC + A\overline{B}C + AB\overline{C} + ABC
用卡诺图化简 : BC + A\overline{B}C + AB\overline{C}
那么可以设一个长度为n+1的数组C,并且初值全为0.

1
2
3
4
5
6
7
8
binaryplus(A, B)
for j = 1 to n
C[j] = (~A[j] and ~B[j] and C[j])
or (~A[j] and B[j] and C[j])
or (A[j] and ~B[j] and ~C[j])
c[j+1] = (B[j] and C[j])
or (A[j] and ~B[j] and C[j])
or (A[j] and B[j] and ~C[j])

2.2-1

theta n^2

2.2-2

1
2
3
4
5
6
7
8
9
Select-sort(A)
for j = 1 to A.length-1
min = A[j]
for i = j to A.length
if A[i] < min
min = A[i]
index = i
A[index] = A[j]
A[j] = min

2.2-3

2.2-4

2. 3-1

2. 3-2

MERGE函数稍作修改,将其循环判断条件(L13)改为:

1
2
3
4
if i <= n1 and L[i] <= R[j]
...
else
...

2.3-2

2.3-3

2.3-4

T(n) = T(n-1) + C(n-1)
其中C(n)为进行插入排序需要的时间,根据提议可以写出伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
insert(v, n)
insert-sort(v, n)
if (n > 0)
insert(v. n-1)

insert-sort(v, n)
for k = 1 to v.length-n+1
key = v[n]
i = k - 1
while i > 0 and v[i] > key
v[i+1] = key
i = i - 1
A[i+1] = key

2.3-6

1
2
3
4
5
6
7
8
9
10
Binarysearch(A, v, p, q)
if p == q and A[p] == v
return p
else if p == q and A[p] != v
return -1

if v <= A[(p+q)/2]
return Binarysearch(A, v, p, (p+q)/2)
else
return Binarysearch(A, v, (p+q)/2+1, q)

试着改成了python代码,是非常方便的,是要稍做修改就能完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A = [1, 2, 3, 4, 5, 6, 7, 8 ,9 ,10]

def Binarysearch(v, p, q):
print(p, " ", q)
if p == q and A[p] == v:
return p
elif p == q and A[p] != v:
return -1

if v <= A[(p+q)//2]:
return Binarysearch(v, p, (p+q)//2)
else:
return Binarysearch(v, (p+q)//2+1, q)

print(Binarysearch(42, 0, 9))