西安的网站设计与制作首页,住房城乡建设部官网,app开发与网站开发的区别,wordpress自动过滤html标签一、 实验目的
1#xff0e;加深学生对算法设计方法的基本思想、基本步骤、基本方法的理解与掌握#xff1b; 2#xff0e;提高学生利用课堂所学知识解决实际问题的能力#xff1b; 3#xff0e;提高学生综合应用所学知识解决实际问题的能力。
二、实验任务
1、串匹配问…一、 实验目的
1加深学生对算法设计方法的基本思想、基本步骤、基本方法的理解与掌握 2提高学生利用课堂所学知识解决实际问题的能力 3提高学生综合应用所学知识解决实际问题的能力。
二、实验任务
1、串匹配问题 给定一段文本在该文本中查找并定位任意给定字符串。 要求 1实现BF算法 2 实现BF算法的改进算法KMP算法 2、采用分治法求解最大连续子序列和问题 给定一个有nn≥1个整数的序列要求求出其中最大连续子序列的和。 例如 序列-211-413-5-2的最大子序列和为20序列-624-7532-16-910-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.7Pycharm
四、实验过程设计算法思路及描述代码设计
1、串匹配问题
给定一段文本在该文本中查找并定位任意给定字符串。 要求 1实现BF算法 2实现BF算法的改进算法KMP算法
1解题思路 BF算法就是暴力求解用所求字符串s2与主串s1做匹配当不匹配时从本次主串循环的下一个字符开始重新匹配。
代码
def BF_algorithm(s1,s2): n1 len(s1) n2 len(s2)i,j 0,0while i n1 and j n2:if (s1[i] s2[j]):i 1j 1else:i i - j 1j 0if j n2:return i - n2else:return -12解题思路
KMP算法需要一个next数组next数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。当匹配失败时数组下标会移动到最长前缀的后一个位置从而减少了重复匹配。
代码
def get_next(p):i, k, m 0, -1, len(p)p_next [-1] * mwhile i m-1:if k -1 or p[i] p[k]:i, k i1, k1if p[i] p[k]:p_next[i] p_next[k]else:p_next[i] kelse:k p_next[k]return p_nextdef KMP_algorithm(t,p):j, i 0, 0n, 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 j1, i1else:i p_next[i]if i m:return j-ireturn -1# 测试
t abbcabcaabbcaa # 目标串
p abbcaa # 模式串
print(KMP_algorithm(t, p))
2、采用分治法求解最大连续子序列和问题
给定一个有nn≥1个整数的序列要求求出其中最大连续子序列的和。 例如 序列-211-413-5-2的最大子序列和为20序列-624-7532-16-910-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,0for i in range(n//2 - 1,-1,-1):temp temp nums[i]max_leftsum max(temp,max_leftsum)temp,max_rightsum 0,0for 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,qz_max,k_max,left,right split(nums)if k_max q:q k_maxp z_maxif left q:ZhongShu(nums[0:left])if n - right q:ZhongShu(nums[right:n])return p,qdef split(nums):n len(nums)low, high 0, n//2 1while low n:if nums[low] nums[n//2]:breakelse:low 1while high n:if nums[high] nums[n//2]:high 1else:breakz nums[low]k high - lowreturn z,k,low,highprint(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 Falsefor i in range(1,n):j 1while 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 1return 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 mathdef 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, Noneelif n 2:return distance(points[0], points[1]), points[0], points[1]points sorted(points)half (n - 1) // 2d1, 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, keylambda x: (x[1], x[0]))res dfor u in left:l, r -1, len(right) - 1while r - l 1:m (l r) 1if right[m][1] u[1] - d:l melse:r midx rfor j in range(7):if j idx len(right):breakif distance(u, right[idx j]) res:res distance(u, right[idx j])a, b u, right[idx j]return res, a, bprint(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 On^2 On2分治法由公式有 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 Onlogn Onlogn
通过设置100100010000个随机点对测试蛮力策略和分治策略的用时从而比较各自的时间复杂度。 实验结果如下 由此可见蛮力法的时间大致沿着 n 2 n^2 n2的速率增长而分治法大致沿着 n l o g n nlogn nlogn增长符合我们的计算结果。
六、实验小结包括问题和解决方法、心得体会等
本次作业是分治算法的一个应用分治和递归相辅相成通过编写分治算法让我深刻了解了递归的含义并且熟悉应用了分治算法解决问题。 串匹配问题是我们在数据结构中就遇到的老朋友其中的BF算法思想很简单就是蛮力策略而KMP算法主要思想是减少重复比较的时间所以定义了一个next的方法用来寻找最长前后缀从而达到不移动主串只移动子串的快速匹配。 寻找最长连续子序列问题难点在于想到如果所求序列正好被划分的情况而后续在三个值中寻找最大值不难分析。 分治策略求众数也是很典型的分治策略的应用但是和上一题不一样我们需要先行找到当前最大的众数然后再应用递归到左、右两个序列中。 最近点对问题应该是最有难度的一道题蛮力策略很简单但是分治方法在考虑了左、右两边各自的最近点对之后还需要考虑是否会有最近的点对穿过了我们的划分线。这其实和寻找最长连续子序列有异曲同工之处但是在考虑这个问题上我们只需要从划分线向两侧分别延展已求的最近点对长度就可以然后寻找在这个区域内的最近点对。 通过本次作业我对算法有了更进一步的认知也锻炼了我的编程能力。
