logo资料库

python算法分析与设计实验报告.docx

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.18M 资料格式：docx 举报 版权申诉
第1页 / 共20页
第2页 / 共20页
第3页 / 共20页
第4页 / 共20页
第5页 / 共20页
第6页 / 共20页
第7页 / 共20页
第8页 / 共20页
资料共20页，剩余部分请下载后查看
    算法分析与设计实验 一、实验目的 1、熟悉 python 编程环境，包括程序安装 2、熟悉 python 基本语法 3、递归算法程序分析与调试 二、实验工具 Win10 操作系统、python3.7 编译环境、IDLE 编译器 三、实验内容 本次实验是利用递归算法，用 python 中的绘图库 turtle，实现画出科赫雪花。雪 花曲线的构造从一个正三角形开始，把每条边分成三等份，然后以各边的中间长 度为底边，分别向外作正三角形，再把“底边”线段抹掉，这样就得到一个六角 形，它共有 12 条边，再把每条边分成三等份，以各中间部分的长度为底边，向 外作正三角形后，抹掉底边线段，反复进行这一过程，就会得到有个“雪花”样 子的科赫曲线。 四、实验过程 本实验采用递归算法完成曲线绘制：如果 n=0，直接画出长度为 L 的直线。如果 n=1（第一次迭代），画出长度为 L/3 的线段；画笔向左转 60 度再画长度为 L/3 长的线段；画笔向右转 120 度画长度为 L/3 长的线段；画笔再向左转 60 度画出 长度为 L/3 的线段。如果 n>1，第 n 次迭代相当于：第 n-1 次迭代；画笔左转 60 度；n-1 次迭代；画笔右转 120 度；第 n-1 次迭代；画笔左转 60 度；第 n-1 次迭 代。本次实验设 n=3，用 for 遍历循环角度，在最外层的循环执行后，再调用下 一阶及相应的长度。程序代码如下： import turtle as t def koch(size, order): def main(): t.setup(800, 800) t.penup() t.goto(-120, 100) t.pendown() t.pensize(2) if order == 0: t.forward(size) else: for angle in [0, 60, -120, 60]: t.left(angle) koch(size/3, order-1)
    t.pencolor('green') koch(300, 3) t.right(120) koch(300, 3) t.right(120) koch(300, 3) t.done() t.hideturtle() main() 五、实验结果与分析
    实验二、快速排序算法 一、实验目的 1、熟悉 python 编程环境，独立编写程序实验代码 2、熟悉 python 基本语法 3、快速排序算法程序分析与调试 二、实验工具 Win10 操作系统、python3.7 编译环境、IDLE 编译器 三、实验要求 1、数据可以预充设定，也可以由程序产生随机数，数据个数不限 2、要求给出算法思想或原理 3、要求分析算法复杂度，并与选择排序、插入排序、或合并排序的复杂度作对 比对照 四、实验内容 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据 都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快 速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。如序列 [6，8，1，4，3，9]，选择 6 作为基准数。从右向左扫描，寻找比基准数小的数 字为 3，交换 6 和 3 的位置，[3，8，1，4，6，9]，接着从左向右扫描，寻找比 基准数大的数字为 8，交换 6 和 8 的位置，[3，6，1，4，8，9]。重复上述过程， 直到基准数左边的数字都比其小，右边的数字都比其大。然后分别对基准数左边 和右边的序列递归进行上述方法。 五、实验步骤 1、设置两个变量 i、j，排序开始的时候：i=0，j=N-1； 2、以第一个数组元素作为关键数据，赋值给 key，即 key=A[0]； 3、从 j 开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于 key 的值 A[j]，将 A[j]和 A[i]互换； 4、从 i 开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于 key 的 A[i]， 将 A[i]和 A[j]互换； 5、重复第 3、4 步，直到 i=j； (3,4 步中，没找到符合条件的值，即 3 中 A[j] 不小于 key,4 中 A[i]不大于 key 的时候改变 j、i 的值，使得 j=j-1，i=i+1，直 至找到为止。找到符合条件的值，进行交换的时候 i， j 指针位置不变。另外， i==j 这一过程一定正好是 i+或 j-完成的时候，此时令循环结束）。
    六、实验心得 通过本次实验，我更深一步熟悉了 python 的编程环境，python 的基本语法， 了解了快速排序算法的基本思想，即选取数组中一个数为基准数，一次排序过程 中，将比基准数小的都放在它左边，比基准数大的不动。然后经过一次排序，左 边部分都比基准数小，右边都比基准数大，然后对左右两边分别进行同样的排序。 并对快速排序算法程序进行了分析和调试。 七、实验结果截图 八、实验源码 def QuickSort(myList, start, end): if start < end: i, j = start, end base = myList[i] while i < j: while (i < j) and (myList[j] >= base): j = j - 1 myList[i] = myList[j] while (i < j) and (myList[i] <= base): i = i + 1 myList[j] = myList[i] myList[i] = base QuickSort(myList, start, i - 1) QuickSort(myList, j + 1, end) return myList myList = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8] print("快速算法排序结果:") QuickSort(myList, 0, len(myList)-1) print(myList)
    实验三、分治算法 一、实验目的 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] d = td # 修改最小距离 # 记录 p，q 点对 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))
    实验四：宽度优先查找最短路径 一、实验目的 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 来记 录结点的父结点。
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料