一、实验目的
1、熟悉双指针在遍历数组中的应用。
2、熟练掌握双指针算法及其算法复杂度分析，了解利用双指针解决计算问题。
二、实验工具
Win10操作系统、python3.7编译环境、IDLE编译器
三、实验内容
1、有序数组的 Two Sum
题目描述：在有序数组中找出两个数，使它们的和为 target。
输入: numbers={2, 7, 11, 15}, target=9
输出: [1,2]
思路：使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
如果两个指针指向元素的和 sum == target，那么得到要求的结果；
如果 sum > target，移动较大的元素，使 sum 变小一些；
如果 sum < target，移动较小的元素，使 sum 变大一些。
class Solution:
def twoSum(self,nums,target):
i,j = 0,len(nums)-1
while i<j:
sum = nums[i]+nums[j]
if sum < target:
i += 1
elif sum > target:
j -= 1
else:
return [i+1,j+1]
return None
————————————————
2、两数平方和
题目描述：判断一个数是否为两个数的平方和。
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5
123
思路：使用双指针，因为为两个数的平方和，一个指针指向较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
较小元素自定义为0，较大元素自定义为目标值的开平方
如果两个指针指向元素的和 sum == target，那么得到要求的结果；
如果 sum > target，减小较大元素的值，使 sum 变小一些；
如果 sum < target，增大较小元素的值，使 sum 变大一些。
class Solution:
def judgeSquareSum(self,target):
i,j = 0,int(target**0.5)
while i <= j:
sum = i*i + j*j
if sum < target:
i += 1
elif sum > target:
j -= 1
else:
return True
return False
————————————————
一、实验目的
1、熟悉图的两种常见表示方法，熟练掌握如何在计算机中存储图。了解图在计算机应用领域常见的应用场景。
2、熟练掌握图上宽度优先搜索算法及其算法复杂度分析，了解利用宽度优先搜索解决计算问题的建模过程。
3、熟练掌握图上深度优先搜索算法及其算法复杂度分析，了解深度优先算法的建模过程。
二、实验工具
Win10操作系统、python3.7编译环境、IDLE编译器
三、实验内容
给定无向图G=(V,E)，求从源点s到图中各个结点v∈V的最近距离。如图1所示，从源点s到结点d，c和z的最短距离均为2，而到结点f和v的最短距离则为3。
四、实验过程
图的存储依然采用邻接列表的方式存储，通过设计一个Graph类来表示图。Graph类中的成员变量为字典类型变量adj，用于存储图中每一个结点的邻边，成员函数add_edge(u,v)将两个结点u和v建立连接。设计一个BFSResult类来存储BFS的输出结果，一个字典类型的变量level来存储各层结点。level的key对应层的结点，level的value则是层的标号。使用一个字典变量parent来记录结点的父结点。
BFS的实现的函数bfs的输入参数为图G和初始结点s。bfs先初始化输出对象r。变量i索引参数，列表变量frontier存储当前层的结点，列表变量next存储frontier中的所有下一层的结点。
五、实验结果分析
按照BFS遍历该图的过程如下：首先，将初始结点s设置为第0层，然后找出结点s的所有邻居结点，其中还没有被遍历到的结点就将它们作为第1层的结点。再找出第1层的结点的邻居结点，所有未遍历的结点作为第2层的结点。依次遍历完图中所有结点，可得BFS的流程为：
·将源点置为第0层
·从源点s到该第i层每一个结点需要经过i条边
·第i层的每一个结点均来自前一层i-1。i为层数索引
BFS的实现函数bfs，对于frontier中每一个结点u，找出u的所有邻居节点v，如果邻居结点没有遍历，则该结点v是下一层的结点。处理完frontier中所有结点后，用next对它重置。通过判断frontier是否为空来作为循环是否继续的条件。用bfs对图1进行宽度优先搜索，frontier0的初始值等于{s}，下标0表示循环次数。第一次循环后，frontier1={a,x}。第二次循环后，frontier2={z,d,c}。第三次循环后，frontier3={f,v}。第四次循环时，frontier等于空，循环结束。
六、附：实验代码
class Graph:
def __init__(self):
self.adj={}
def add_edge(self, u, v):
if self.adj[u] is None:
self.adj[u] = []
self.adj[u].append(v)
class BFSResult:
def __init__(self):
self.level = {}
self.parent = {}
def bfs(g,s):
r = BFSResult()
r.parent = {s:None}
r.level = {s:0}
i = 1
frontier = [s]
while frontier:
next = []
for u in frontier:
for v in g.adj[u]:
if v not in r.level:
r.level[v] = i
r.parent[v] = u
next.append(v)
frontier = next
i += 1
return r
def find_shortest_path(result,v):
source_vertex = [verterx for verterx, level in result.level.items() if level ==0]
v_parent_list = []
if v != source_vertex[0]:
v_parent = result.parent[v]
v_parent_list.append(v_parent)
while v_parent != source_vertex[0] and v_parent != None:
v_parent = result.parent[v_parent]
v_parent_list.append(v_parent)
return v_parent_list
if __name__ == "__main__":
g = Graph()
g.adj = { "s" : ["a","x"],
"a" : ["z","s"],
"d" : ["f","c","x"],
"c" : ["x","d","f","v"],
"v" : ["f","c"],
"f" : ["c","d","v"],
"x" : ["s","d","c"],
"z" : []
}
bfs_result = bfs(g,'s')
print(bfs_result.level)
print(find_shortest_path(bfs_result,'f'))
一、实验目的
1． 请用回溯法求对称的旅行商问题（TSP问题）
二、实验环境
Win10操作系统、python3.7编译环境、IDLE编译器
三、实验内容
旅行商问题的简单说明：
旅行商问题（TSP问题）是一个经典的组合优化问题。经典TSP问题可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短
从图论角度看：
该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。
TSP的数学模型为：
使用的测试数据：
使用字典的形式表示：
# 定义图的字典形式G = { '1': {'2': 30, '3': 6, '4': 4}, '2': {'1': 30, '3': 5, '4': 10}, '3': {'1': 6, '2': 5, '4': 20}, '4': {'1': 4, '2': 10, '3': 20}}
使用数据的形式表示：
# 定义图的数组形式graph = [ [0, 30, 6, 4], [30, 0, 5, 10], [6, 5, 0 , 20], [4, 10, 20, 0]]
（一）使用回溯法求解旅行商（TSP）问题
回溯法的概念：
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
在我看来，回溯法有点像图遍历中的深度优先算法，不过多了剪枝这一过程，当发现现有的解的值大于最优解的时候，就不再深入遍历下去，算法的性能取决于剪枝的多少。
下面给出回溯法的代码：
import math
n = 4
x = [0, 1, 2, 3]# 定义图的字典形式
G = { '1': {'2': 30, '3': 6, '4': 4},
'2': {'1': 30, '3': 5, '4': 10},
'3': {'1': 6, '2': 5, '4': 20},
'4': {'1': 4, '2': 10, '3': 20}}# 定义图的数组形式
graph = [ [0, 30, 6, 4],
[30, 0, 5, 10],
[6, 5, 0 , 20],
[4, 10, 20, 0]]
# bestcost = 1<<32 # 这里只要是一个很大数就行了 无穷其实也可以
bestcost = math.inf # 好吧 干脆就无穷好了
nowcost = 0 # 全局变量，现在的花费
def TSP(graph, n, s):
global nowcost, bestcost
if(s == n):
if (graph[x[n-1]][x[0]] != 0 and (nowcost +graph[x[n-1]][x[0]]<bestcost)):
print('best way:', x)
bestcost = nowcost + graph[x[n-1]][x[0]]
print('bestcost', bestcost)
else:
for i in range(s, n): # 如果下一节点不是自身 而且 求得的值小于目前的最佳值
if (graph[x[i-1]][x[i]] != 0 and nowcost+graph[x[i-1]][x[i]] < bestcost):
x[i], x[s] = x[s], x[i] # 交换一下
nowcost += graph[x[s - 1]][x[s]] # 将花费加入
TSP(graph, n, s+1)
nowcost -= graph[x[s - 1]][x[s]] # 回溯上去还需要减去 x[i], x[s] = x[s], x[i] # 别忘记交换回来
TSP(graph, n, 1)
运行的结果为：
一共输出了两个结果，说明完整路径搜索了两次，其余情况下，均在搜索到中途的时候进行了剪枝操作。
一、实验目的
1、了解贪心算法求解优化问题的过程
2、熟练掌握利用贪心算法求解典型的计算问题，如硬币找零、间隔任务规划等问题。了解利用替换法证明贪心策略是否能获得全局最优解的过程。
3、熟练掌握贪心算法在两个典型图搜索中的应用，即单源最短路径和最小生成树算法中，利用合理的数据结构优化算法复杂度的技巧。
二、实验工具
Win10操作系统、python3.7编译环境、IDLE编译器
三、实验内容
设计一个贪心算法，使得对于给定的n位正整数，在删除其中任意k<=n位数字后，剩余的数字按原来的次序排列组成的新的正整数最小
输入：第一行是一个正整数A，第二行是正整数k
输出：剩余数字组成的最小数
例如输入：169584
4
输出：14
四、实验调试过程
操作对象为n位正整数，有可能超过整数的范围，存储在数组a中，数组中每一个数组元素对应整数的一位数字。
在整数的位数固定的前提下，让高位的数字尽量小，整数的值就小。这就是所要选取的贪心策略。每次删除一个数字，选择一个使剩下的数最小的数字作为删除对象。
当k=1时，对于n位数构成的数删除哪一位，使得剩下的数据最小。删除满足如下条件的a[i]：它是第一个a[i]>a[i+1]的数，如果不存在则删除a[n]。
当k>1（当然小于n），按上述操作一个一个删除。每删除一个数字后，后面的数字向前移位。删除一个达到最小后，再从头即从串首开始，删除第2个，依此分解为k次完成。
若删除不到k个后已无左边大于右边的降序或相等，则停止删除操作，打印剩下串的左边n−k个数字即可（相当于删除了若干个最右边的数字）。
实验结果截图如下所示：
五、实验结果分析
通过本次实验，我更深一步熟悉了python的编程环境，python的基本语法，了解了贪心算法的基本思想，首先我们要知道程序体要循环n次,因为只有这样我们才能每次循环取出最小的数字;其次就是怎么取区间内的最小值。我这里用的是通过循环遍历整个区间取得最小值,最关键的是确定区间的起始位置,第一次循环的位置最好确定就是1,结束位置就是k+1,第二次循环的起始位置是第一次取出的最小值的坐标值加1,结束位置是k+2;然后继续记录最小值的坐标值,以计算下一次的起始位置。
六、实验源码
def delNum(s, k):
n = len(s)
if n < k: return None
s = list(s)
flag = 0
while k != 0:
if flag == 0:
for i in range(len(s) - 1): # 发现第一个小于后一个值的数字删除
if s[i] > s[i + 1]:
del s[i]
k -= 1
flag = 1
break
if flag == 1 and k != 0: # 已经删除，但没有结束
flag = 0
else:
n = len(s)
s = s[:n - k]
k = 0
return ''.join(s)
if __name__ == '__main__':
s, k = '169584', 4
print('剩余数字组成的最小数为：')
print(delNum(s, k))
一、实验目的
1、理解动态规划求解优化问题的典型步骤，以及动态规划算法求解计算问题的时间复杂度分析
2、熟练掌握利用动态规划算法求解一维、二维等典型优化问题，如斐波那锲数、拾捡硬币、连续子序列的最大值、矩阵的括号、0-1背包问题等。
3、对于简单问题能画出其动态规划表，并能从中得到问题的解。
二、实验工具
Win10操作系统、python3.7编译环境、IDLE编译器
三、实验内容
某种材料以长度计价，其价格表为：
长度：1 2 3 4 5 6 7 8 9 10
价格：15 8 9 10 17 17 20 24 30
现有一段长度为n的该种材料，试给出最佳切割分段方案，使其价值最大，用Python编程实现该算法。
四、实验调试过程
动态规划与分治法比较类似，都是通过求解子问题的解，最终来求出原问题的解。分治法只要是将原问题分解成为若干个独立的子问题，通过子问题来求解原问题的解。而动态规划恰恰相反，动态规划是用来求解子问题重叠的情况，即不同的子问题之间具有相同的公共子问题，在这种情况下分治法会花费大量的时间来计算已经计算过的那部分重叠子问题，效率大大降低，而动态规划权衡时间和空间的因素，将已经计算过的子问题存入一张表内，下次遇到相同的子问题时，直接查表就可以得到结果，大大加快了速度。
动态规划通常用来求解最优化问题，一般来说一个问题的最优解有多个，动态规划可以求解出其中的一个最优解，而不是最优解。
通过下面的四个步骤来设计一个动态规划问题：
1.刻画一个最优解的结构特征。
2.递归的定义最优解的值
3.计算最优解时，一般采用自下而上的方法来求解
4.利用计算出的信息构造出一个最优解
首先可以将材料分割为 i 和 n-i 两段，求这两段的最优收益 Ri 和 R(n-i) （每种方案的最优收益为两段的最优收益之和）。由于无法确定哪种方案（i 取何值时）会获得最优收益，我们必须考虑所有的i，选取其中收益最大者。若直接出售钢条会获得最大收益，可以选择不做任何切割。最优切割收益公式：Rn = max(pn,R1+Rn-1,R2+Rn-2,…,Rn-1+R1)。当完成首次切割后，我们可以将两段材料（ i 和 n-i）看成两个独立的材料切割问题实例，通过组合两个相关子问题的最优解，构成原问题的最优解。
一种相似但更为简单的递归求解方法：将长度为 n 的材料分解为左边开始一段，以及剩余部分继续分解的结果。简化后的公式：Rn = max{1≤i≤n, (pi+Rn-i)}。
五、实验结果分析
实验结果表明：当材料长度为8时，最大盈利为22。
六、实验源码
def BottomUpCutRod(p, n):
r = [0]*(n+1)
for i in range(1, n+1):
if n == 0:
return 0
q =0
for j in range(1, i+1):
q = max(q, p[j]+r[i-j])
r[i] = q
return r[n], r
p=[0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
print(BottomUpCutRod(p, 8))
一、实验目的
1、熟悉python编程环境，独立编写程序实验代码
2、熟悉python基本语法
3、分治算法程序分析与调试
二、实验工具
Win10操作系统、python3.7编译环境、IDLE编译器
三、实验内容
给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。主要思想就是分治，先把n个点按x坐标排序，然后求左边n/2个和右边n/2个的最近距离，最后合并。 首先，假设点是n个，编号为1到n。我们要分治求，则找一个中间的编号mid，先求出1到mid点的最近距离设为d1，还有mid+1到n的最近距离设为d2。这里的点需要按x坐标的顺序排好，并且假设这些点中，没有2点在同一个位置。（若有，则直接最小距离为0了）。
然后，令d为d1, d2中较小的那个点。如果说最近点对中的两点都在1-mid集合中，或者mid+1到n集合中，则d就是最小距离了。但是还有可能的是最近点对中的两点分属这两个集合，所以我们必须先检测一下这种情况是否会存在，若存在，则把这个最近点对的距离记录下来，去更新d。这样我们就可以得道最小的距离d了。
关键是要去检测最近点对，理论上每个点都要和对面集合的点匹配一次，那效率还是不能满足我们的要求。所以需要优化。假如以我们所选的分割点mid为界，如果某一点的横坐标到点mid的横坐标的绝对值超过d1并且超过d2，那么这个点到mid点的距离必然超过d1和d2中的小者，所以这个点到对方集合的任意点的距离必然不是所有点中最小的。所以我们先把在mid为界左右一个范围内的点全部筛选出来，放到一个集合里。筛选好以后，当然可以把这些点两两求距离去更新d了，不过这样效率很低，可能满足条件的点很多。继续优化。
首先把这些点按y坐标排序。假设排序好以后有cnt个点，编号为0到cnt-1。那么我们用0号去和1到cnt-1号的点求一下距离，然后1号和2到cnt-1号的点求一下距离。如果某两个点y轴距离已经超过了d，这次循环就可以直接break了，开始从下一个点查找。
四、实验步骤
1、用一条竖直的线L将所有的点分成两等份
2、递归算出左半部分的最近两点距离d1，右半部分的最近两点距离d2，取d=min(d1,d2)
3、算出“一个在左半部分，另一个在右半部分”这样的点对的最短距离d3。
3.1 删除所有到L的距离大于d的点。 O(n)
3.2 把右半平面的点按照纵坐标y排序。 O(nlogn)
3.3 对于左半平面内的每个点P1，找出右半平面内纵坐标与P1的纵坐标的差在d以内的点P2，计算距离取最小值，算出d3。
4、结果＝min(d1,d2,d3)
五、实验结果
六、实验代码
from math import sqrt
def solve(points):
n = len(points)
min_d = float("inf") # 最小距离：无穷大
min_ps = None # 最近点对
for i in range(n - 1):
for j in range(i + 1, n):
d = sqrt((points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2) # 两点距离
if d < min_d:
min_d = d # 修改最小距离
min_ps = [points[i], points[j]] # 保存最近点对
return min_ps
def nearest_dot(seq):
# 注意：seq事先已对x坐标排序
n = len(seq)
if n <= 2:
return seq # 若问题规模等于 2，直接解
left, right = seq[0:n // 2], seq[n // 2:]
print(left, right)
mid_x = (left[-1][0] + right[0][0]) / 2.0
lmin = (left, nearest_dot(left))[len(left) > 2] # 左侧最近点对
rmin = (right, nearest_dot(right))[len(right) > 2] # 右侧最近点对
dis_l = (float("inf"), get_distance(lmin))[len(lmin) > 1]
dis_r = (float("inf"), get_distance(rmin))[len(rmin) > 1]
d = min(dis_l, dis_r) # 最近点对距离
left = list(filter(lambda p: mid_x - p[0] <= d, left)) # 中间线左侧的距离<=d的点
right = list(filter(lambda p: p[0] - mid_x <= d, right)) # 中间线右侧的距离<=d的点
mid_min = []
for p in left:
for q in right:
if abs(p[0] - q[0]) <= d and abs(p[1] - q[1]) <= d: # 如果右侧部分点在p点的(d,2d)之间
td = get_distance((p, q))
if td <= d:
mid_min = [p, q] # 记录p，q点对
d = td # 修改最小距离
if mid_min:
return mid_min
elif dis_l > dis_r:
return rmin
else:
return lmin
def get_distance(min):
return sqrt((min[0][0] - min[1][0]) ** 2 + (min[0][1] - min[1][1]) ** 2)
def divide_conquer(seq):
seq.sort(key=lambda x: x[0])
res = nearest_dot(seq)
return res
测试
seq = [(0, 1), (3, 2), (4, 3), (5, 1), (1, 2), (2, 1), (6, 2), (7, 2), (8, 3), (4, 5), (9, 0), (6, 4)]
print(“空间最近距离的点对为”)
print(solve(seq))