斯坦福算法专项课程Course1 week1算法实现

这个系列的课程之前学过一遍,但是笔记没有整理完,最近在复习,准备把内容再学习一遍,这次准备实现每周所介绍的全部算法,这里是第一周的内容。

课程地址:https://www.coursera.org/specializations/algorithms

Karatsuba Mulplication

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import numpy as np

def Karatsuba_Mulplication(x, y):
'''
输入x, y为字符串,首先补0,使得数字长度一样
'''
#预处理,使得长度一样
n1 = len(x)
n2 = len(y)
n = max(n1, n2)
if (n1 < n2):
x = "0" * (n2 - n1) + x
else:
y = "0" * (n1 - n2) + y

#个位数
if (n == 1):
return int(x) * int(y)
else:
k = n // 2
#将数分为前l位和剩余部分
l = n - k
u = 10 ** k
a = x[:l]
b = x[l:]
c = y[:l]
d = y[l:]
ab = str(int(a) + int(b))
cd = str(int(c) + int(d))
#递归
ac = Karatsuba_Mulplication(a, c)
bd = Karatsuba_Mulplication(b, d)
abcd = Karatsuba_Mulplication(ab, cd)
#合并结果
adbc = abcd - ac - bd
res = u ** 2 * ac + u * adbc + bd

return res

#测试
N = 1000
Max = 1e5

for i in range(N):
x = np.random.randint(0, Max)
y = np.random.randint(0, Max)
z = x * y
#转换为字符串
x1 = str(x)
y1 = str(y)
z1 = Karatsuba_Mulplication(x1, y1)

print(z == z1)

Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import numpy as np

def Merge(A, l, m, r):
"""
l, ..., m为第一部分
m + 1, ..., r为第二部分
"""
#存储结果
C = []
#索引
i = l
j = m + 1
while ((i <= m) and (j <= r)):
if (A[i] < A[j]):
C.append(A[i])
i += 1
else:
C.append(A[j])
j += 1
#处理剩余部分
while (i <= m):
C.append(A[i])
i += 1
while (j <= r):
C.append(A[j])
j += 1
#更新
A[l: (r + 1)] = C

def MSort(A, l, r):
'''
对l, ... , r排序
'''
if (l < r):
#print(l, r)
m = (l + r) // 2
MSort(A, l, m)
MSort(A, m + 1, r)
Merge(A, l, m, r)

def Merge_Sort(A):
n = len(A)
MSort(A, 0, n - 1)

#测试
N = 1000
Max = 1e5
data = np.random.randint(0, Max, size=N)
data_sort = np.sort(data)
#排序
Merge_Sort(data)
#测试结果
print(np.sum(data != data_sort))