一、 实验目的
1．加深学生对算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。
二、实验任务
1、串匹配问题
给定一段文本，在该文本中查找并定位任意给定字符串。
要求：
（1）实现BF算法；
（2） 实现BF算法的改进算法：KMP算法
2、采用分治法求解最大连续子序列和问题
给定一个有n（n≥1）个整数的序列，要求求出其中最大连续子序列的和。
例如： 序列（-2，11，-4，13，-5，-2）的最大子序列和为20序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大子序列和为16。
3、用分治策略求众数问题
问题描述：给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。要求对给定的又n个自然数的组成的多重集S，计算S的众数及其重数。
4、最近点对问题
设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。
（1）分别用蛮力法和分治法求解最近对问题；
（2）分析算法的时间性能，设计实验程序验证分析结论。
三、实验设备及编程开发工具
实验设备：Win10电脑
开发工具：Python 3.7，Pycharm
四、实验过程设计（算法思路及描述，代码设计）
1、串匹配问题
给定一段文本，在该文本中查找并定位任意给定字符串。
要求：
（1）实现BF算法；
（2）实现BF算法的改进算法：KMP算法
（1）解题思路：
BF算法就是暴力求解，用所求字符串s2与主串s1做匹配，当不匹配时，从本次主串循环的下一个字符开始重新匹配。
代码：
def BF_algorithm(s1,s2):
n1 = len(s1)
n2 = len(s2)
i,j = 0,0
while i < n1 and j < n2:
if (s1[i] == s2[j]):
i += 1
j += 1
else:
i = i - j + 1
j = 0
if j >= n2:
return i - n2
else:
return -1
（2）解题思路：
KMP算法需要一个next数组，next数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。当匹配失败时，数组下标会移动到最长前缀的后一个位置，从而减少了重复匹配。
代码：
def get_next(p):
i, k, m = 0, -1, len(p)
p_next = [-1] * m
while i < m-1:
if k == -1 or p[i] == p[k]:
i, k = i+1, k+1
if p[i] == p[k]:
p_next[i] = p_next[k]
else:
p_next[i] = k
else:
k = p_next[k]
return p_next
def KMP_algorithm(t,p):
j, i = 0, 0
n, m = len(t), len(p)
p_next = get_next(p)
while j < n and i < m:
if i == -1 or t[j] == p[i]:
j, i = j+1, i+1
else:
i = p_next[i]
if i == m:
return j-i
return -1
# 测试
t = "abbcabcaabbcaa" # 目标串
p = "abbcaa" # 模式串
print(KMP_algorithm(t, p))
2、采用分治法求解最大连续子序列和问题
给定一个有n（n≥1）个整数的序列，要求求出其中最大连续子序列的和。
例如： 序列（-2，11，-4，13，-5，-2）的最大子序列和为20序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大子序列和为16。
解题思路：
分治法求最大连续子序列问题，可以先从序列的中间分开，分别求左序列和右序列的最大连续子序列，但是还需要考虑如果最大连续子序列正好越过序列的划分线的情况。如果最大连续子序列刚好越过划分线，那么它必然是左边最大连续子序列和右边连续最大子序列的和。所以我们只需要比较左边最大连续子序列，右边最大连续子序列，左边最大连续子序列加上右边最大连续子序列的和，从这三者中取最大值就可以求出整个序列的最大连续子序列。
代码：
def Max_zixulie(nums):
n = len(nums)
if n == 1:
return nums[0]
else:
max_left = Max_zixulie(nums[0:n//2])
max_right = Max_zixulie(nums[n//2:n])
temp,max_leftsum = 0,0
for i in range(n//2 - 1,-1,-1):
temp = temp + nums[i]
max_leftsum = max(temp,max_leftsum)
temp,max_rightsum = 0,0
for i in range(n//2,n):
temp = temp + nums[i]
max_rightsum = max(temp,max_rightsum)
return max(max_left,max_right,max_leftsum + max_rightsum)
print(Max_zixulie([-2,11,-4,13,-5,-2]))
3、用分治策略求众数问题
问题描述：给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。要求对给定的又n个自然数的组成的多重集S，计算S的众数及其重数。
解题思路：
首先需要用分治策略解题，所以需要对元素进行排序，然后选取序列中间的元素，由它出发向前和向后寻找和它一样的元素，从而记录众数和重数。接下来从左侧和右侧分别继续递归比较，并在比较过程中判断是否大于已知的重数。在递归比较规程中，我们需要用众数比较剩下的左右剩余序列长度，如果众数大于等于左/右剩余序列长度，那么就不需要进行比较，直接输出就可以。
代码：
p, q = 0, 0
def ZhongShu(nums):
n = len(nums)
global p,q
z_max,k_max,left,right = split(nums)
if k_max > q:
q = k_max
p = z_max
if left > q:
ZhongShu(nums[0:left])
if n - right > q:
ZhongShu(nums[right:n])
return p,q
def split(nums):
n = len(nums)
low, high = 0, n//2 + 1
while low < n:
if nums[low] == nums[n//2]:
break
else:
low += 1
while high < n:
if nums[high] == nums[n//2]:
high += 1
else:
break
z = nums[low]
k = high - low
return z,k,low,high
print(ZhongShu([1,1,1,1,1,1,2,3,3,4,4,5,5,5,6,6,6,8,8,8,8,8,8,8]))
4、最近点对问题
设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。
（1）分别用蛮力法和分治法求解最近对问题；
（2） 分析算法的时间性能，设计实验程序验证分析结论。
（1）解题思路：
蛮力法直接用for循环遍历，对每两个点都做运算，并且比较记录最小值，最后输出最短距离和最近的点对。
分治方法在考虑了左、右两边各自的最近点对之后，还需要考虑是否会有最近的点对穿过了我们的划分线。这其实和寻找最长连续子序列有异曲同工之处，但是在考虑这个问题上，我们只需要从划分线向两侧分别延展已求的最近点对长度就可以，然后寻找在这个区域内的最近点对。
代码：（蛮力法）
def ManLi(nums):
n = len(nums)
x = float('inf')
if n <= 1:
return False
for i in range(1,n):
j = 1
while j <= i:
y = pow((nums[i][0] - nums[i - j][0]) ** 2 + (nums[i][1] - nums[i - j][1]) ** 2,0.5)
x = min(x,y)
if x == y:
l = []
l.append(nums[i])
l.append(nums[i - j])
j += 1
return x,l[0],l[1]
print(ManLi([[0,4],[1,1],[1,5],[2,4],[3,2],[3,5],[4,0],[4,3],[5,2],[5,5]]))
代码：（分治法）
import sys
import math
def distance(x, y):
return math.sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1])** 2)
def FenZhi(points):
n = len(points)
if n < 2:
return sys.maxsize, None, None
elif n == 2:
return distance(points[0], points[1]), points[0], points[1]
points = sorted(points)
half = (n - 1) // 2
d1, a1, b1 = FenZhi(points[:half])
d2, a2, b2 = FenZhi(points[half:])
d, a, b = (d1, a1, b1) if d1 < d2 else (d2, a2, b2)
calibration = points[half][0]
left, right = [], []
for u in points:
if calibration - d < u[0] < calibration:
left.append(u)
elif calibration <= u[0] < calibration + d:
right.append(u)
right = sorted(right, key=lambda x: (x[1], x[0]))
res = d
for u in left:
l, r = -1, len(right) - 1
while r - l > 1:
m = (l + r) >> 1
if right[m][1] <= u[1] - d:
l = m
else:
r = m
idx = r
for j in range(7):
if j + idx >= len(right):
break
if distance(u, right[idx + j]) < res:
res = distance(u, right[idx + j])
a, b = u, right[idx + j]
return res, a, b
print(FenZhi([[0,4],[1,1],[1,5],[2,4],[3,2],[3,5],[4,0],[4,3],[5,2],[5,5]]))
（2）蛮力法用了两个循环，因而其时间复杂度是 O （ n 2 ） O（n^2） O（n2），分治法由公式有 T ( n ) = T ( n / 2 ) + O ( n ) T(n) = T(n/2) + O(n) T(n)=T(n/2)+O(n)，由主定理可以得出其时间复杂度是 O （ n l o g n ） O（nlogn） O（nlogn）
通过设置100，1000，10000个随机点对，测试蛮力策略和分治策略的用时，从而比较各自的时间复杂度。
实验结果如下：
由此可见蛮力法的时间大致沿着 n 2 n^2 n2的速率增长，而分治法大致沿着 n l o g n nlogn nlogn增长，符合我们的计算结果。
六、实验小结（包括问题和解决方法、心得体会等）
本次作业是分治算法的一个应用，分治和递归相辅相成，通过编写分治算法，让我深刻了解了递归的含义，并且熟悉应用了分治算法解决问题。
串匹配问题是我们在数据结构中就遇到的老朋友，其中的BF算法思想很简单，就是蛮力策略，而KMP算法主要思想是减少重复比较的时间，所以定义了一个next的方法，用来寻找最长前后缀，从而达到不移动主串，只移动子串的快速匹配。
寻找最长连续子序列问题，难点在于想到如果所求序列正好被划分的情况，而后续在三个值中寻找最大值不难分析。
分治策略求众数也是很典型的分治策略的应用，但是和上一题不一样，我们需要先行找到当前最大的众数，然后再应用递归到左、右两个序列中。
最近点对问题应该是最有难度的一道题，蛮力策略很简单，但是分治方法在考虑了左、右两边各自的最近点对之后，还需要考虑是否会有最近的点对穿过了我们的划分线。这其实和寻找最长连续子序列有异曲同工之处，但是在考虑这个问题上，我们只需要从划分线向两侧分别延展已求的最近点对长度就可以，然后寻找在这个区域内的最近点对。
通过本次作业，我对算法有了更进一步的认知，也锻炼了我的编程能力。
