算法设计与分析实验报告python实现(排序算法、三壶谜题、交替放置的碟子、带锁的门)

2024-04-04 18:04
文章标签 python 算法 分析 实现 设计 放置 排序 谜题 实验报告 交替 三壶 带锁 碟子

本文主要是介绍算法设计与分析实验报告python实现(排序算法、三壶谜题、交替放置的碟子、带锁的门)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、 实验目的

1．加深学生对算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。

二、实验任务

1、排序算法
目前已知有几十种排序算法，请查找资料，并尽可能多地实现多种排序算法（至少实现8种）并分析算法的时间复杂度。比较各种算法的优劣。
2、三壶谜题：
有一个充满水的8品脱的水壶和两个空水壶（容积分别是5品脱和3品脱）。通过将水壶完全倒满水和将水壶的水完全倒空这两种方式，在其中的一个水壶中得到4品脱的水。
3、交替放置的碟子
我们有数量为2n的一排碟子，n黑n白交替放置：黑，白，黑，白…
现在要把黑碟子都放在右边，白碟子都放在左边，但只允许通过互换相邻碟子的位置来实现。为该谜题写个算法，并确定该算法需要执行的换位次数。
4、带锁的门：
在走廊上有n个带锁的门，从1到n依次编号。最初所有的门都是关着的。我们从门前经过n次，每次都从1号门开始。在第i次经过时（i = 1,2，…, n)我们改变i的整数倍号锁的状态；如果门是关的，就打开它；如果门是打开的，就关上它。在最后一次经过后，哪些门是打开的，哪些门是关上的？有多少打开的门？

三、实验设备及编程开发工具

实验设备：Win10电脑
开发工具：Python 3.7，Pycharm

四、实验过程设计（算法思路及描述，代码设计）

1、排序算法

（1）冒泡排序

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个

2、对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上

3、针对所有的元素重复以上的步骤，除了最后一个

4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

代码：

def BubbleSort(sums):n = len(sums)for i in range(n):for j in range(1,n - i):if sums[j - 1] > sums[j]:sums[j - 1],sums[j] = sums[j],sums[j - 1]return sumsimport random
import timeList = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()BubbleSort(List)b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

冒泡排序

最好时间复杂度为O(n2)，最坏时间复杂度为O(n2)，平均时间复杂度为O(n^2)

img

（2）选择排序

1、在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

2、再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾

3、以此类推，直到所有元素均排序完毕

代码：

def SelectSort(sums):n = len(sums)for i in range(0,n):min = ifor j in range(i + 1,n):if sums[j] < sums[min]:min = jsums[min],sums[i] = sums[i],sums[min]return sumsimport random
import timeList = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()SelectSort(List)b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

选择排序

最好时间复杂度为O(n2)，最坏时间复杂度为O(n2)，平均时间复杂度为O(n^2)

img

（3）插入排序

1、从第一个元素开始，该元素可以认为已经被排序

2、取出下一个元素，在已经排序的元素序列中从后向前扫描

3、如果被扫描的元素（已排序）大于新元素，将该元素后移一位

4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

5、将新元素插入到该位置后

6、重复步骤2~5

代码：

def InsertSort(sums):n = len(sums)for i in range(1,n):temp = sums[i]j = i - 1while j >= 0 and sums[j] > temp:sums[j + 1] = sums[j]j -= 1sums[j + 1] = tempreturn sumsimport random
import timeList = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()InsertSort(List)b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

插入排序

最好时间复杂度为O(n)，最坏时间复杂度为O(n2)，平均时间复杂度为O(n2)

img

（4）希尔排序

1、比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，算法先将要排序的一组数按某个增量d分成若干组

2、对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序

3、当增量减到1时，整个要排序的数被分成一组，排序完成

4、一般的初次取序列的一半为增量，以后每次减半，直到增量为1

代码：

def ShellSort(sums):n = len(sums)mid = n//2while mid >= 1:for i in range(mid,n):temp = sums[i]j = iwhile j - mid >= 0 and sums[j - mid] > temp:sums[j] = sums[j - mid]j -= midsums[j] = tempmid //= 2return sumsimport random
import timeList = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()ShellSort(List)b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

希尔排序

最好时间复杂度为O(nlog n)，最坏时间复杂度为O(nlogn)，平均时间复杂度为O(nlogn)

img

（5）归并排序

1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2、设定两个指针，最初位置分别为两个已经排序序列的起始位置

3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4、重复步骤 3 直到某一指针达到序列尾

5、 将另一序列剩下的所有元素直接复制到合并序列尾

代码：

def MergeSort(sums):if len(sums) <= 1:return sumsn = len(sums)//2left = MergeSort(sums[:n])right = MergeSort(sums[n + 1:])return Merge(left,right)def Merge(left,right):new_sums = []i,j = 0,0while i < len(left) and j < len(right):if left[i] < right[j]:new_sums.append(left[i])i += 1else:new_sums.append(right[j])j += 1new_sums = new_sums + left[i:] + right[j:]return new_sumsimport random
import timeList = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()MergeSort(List)b = time.time()
print(MergeSort(List))
print("算法消耗时间为：",(b - a)*100,"毫秒")

归并排序

最好时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)，平均时间复杂度为O(nlogn)

img

（6）快速排序

1、从数列中挑出一个元素作为基准数

2、分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边

3、再对左右区间递归执行第二步，直至各区间只有一个数

代码：

def QuickSort(sums,left,right):if left >= right:return Falselow = lefthigh = righttemp = sums[low]while left < right:while left < right and sums[right] > temp:right -= 1sums[left] = sums[right]while left < right and sums[left] <= temp:left += 1sums[right] = sums[left]sums[right] = tempQuickSort(sums,low,left - 1)QuickSort(sums,left + 1,high)return sumsimport random
import timeList = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()QuickSort(List,0,len(List) - 1)b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

快速排序

最好时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)，平均时间复杂度为O(nlogn)

img

（7）堆排序

1、最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点

2、创建最大堆：将堆中的所有数据重新排序

3、堆排序：移除位在第一个数据的根节点，并做最大堆调整的递归运算

代码：

def HeapSort(sums):n = len(sums)first = n//2 - 1for start in range(first,-1,-1):HeapSort_Max(sums,start,n - 1)for end in range(n - 1,0,-1):temp = sums[end]sums[end] = sums[0]sums[0] = tempHeapSort_Max(sums,0,end - 1)return sumsdef HeapSort_Max(sums,start,end):root = startwhile True:child = 2 * root + 1if child > end:breakif child + 1 <= end and sums[child] < sums[child + 1]:child = child + 1if sums[root] < sums[child]:temp = sums[root]sums[root] = sums[child]sums[child] = temproot = childelse:breakimport random
import timeList = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()HeapSort(List)b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

堆排序

最好时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)，平均时间复杂度为O(nlogn)

img

（8）计数排序

1、找出待排序的数组中最大和最小的元素，新开辟一个长度为 最大值-最小值+1 的数组

2、统计原数组中每个元素出现的次数，存入到新开辟的数组中

3、根据每个元素出现的次数，按照新开辟数组中从小到大的秩序，依次填充到原来待排序的数组中，完成排序

代码：

def RadixSort(sums):Min = min(sums)Max = max(sums)List = [0 for i in range(Max - Min + 2)]for i in range(len(sums)):List[sums[i] - Min] += 1j,k = 0,0while j < (len(List)):if List[j] > 0:sums[k] = j + MinList[j] -= 1k += 1else:j += 1return sumsimport random
import timeList = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()RadixSort(List)b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

计数排序

最好时间复杂度为O(n)，最坏时间复杂度为O(n)，平均时间复杂度为O(n)

img

2、三壶谜题

将某个时刻水壶中水的数量看作一个状态，用一个长度为3的数组表示，初始状态便为[8,0,0],再拓展他的下一结点的可能结构，若下一结点的结构已经被拓展过了便放弃，若没有拓展过则加入拓展列表中。然后递归上述操作，直到拓展列表为空或者找到目标为止。

代码：

class node: def __init__(self, data):self.data = dataself.per = None def pour(n):r_list = n.data max_list = [8, 5, 3]  for i, j in ((0, 1), (0, 2), (1, 2), (1, 0), (2, 0), (2, 1)):if r_list[i] != 0:n_list = r_list.copy()  if r_list[i] + r_list[j] > max_list[j]:n_list[i] = r_list[i] - (max_list[j] - r_list[j])n_list[j] = max_list[j]else:n_list[j] = r_list[i] + r_list[j]n_list[i] = 0flag = True for one in closed_list:if one.data == n_list:  flag = Falseif flag:print("扩展的新节点是：",n_list)new_node = node(n_list)  new_node.per = nopen_list.append(new_node)def BFS_node(root_1):  n = root_1print("当前节点：",n.data)if open_list is None:return "没有找到4品脱的水"nodelist = n.dataif 4 in nodelist:print("找到了4品脱的水")print_node(n)return "找到了4品脱的水"closed_list.append(open_list.pop(0))pour(n)print("*******")BFS_node(open_list[0])def print_node(n): if n.per == None:return ""print(n.data)print_node(n.per)# 初始化数据
root = node([8, 0, 0])
open_list = [root]  
closed_list = []
BFS_node(open_list[0])

三壶谜题：

时间复杂度为O(n^2)

img

3、交替放置的碟子

输入碟子的总数n，产生一个0，1交错的列表，其中1代表黑碟子，0代表白碟子，通过冒泡排序将碟子分开。
代码：

def Black_White(s):sums = [0 for i in range(s)]i = 0while i * 2 < s:sums[i * 2] = 1i += 1print(sums)k = 0n = len(sums)for i in range(n):for j in range(1, n - i):if sums[j - 1] > sums[j]:sums[j - 1], sums[j] = sums[j], sums[j - 1]k += 1print(sums)print("次数为：", k, "次")# 黑碟子为1，白碟子为0
Black_White(40)

交替放置的碟子：

时间复杂度为O(n^2)

img

4、带锁的门

输入门的总数n，产生两个列表表示开门和关门的状态，同过循环遍历，将各位表示反复重置，最终得到门的状态并输出。其中1表示开门，0表示关门。
代码：

# 1表示开门，0表示关门
def LockDoor(n):List = [0 for i in range(n)]List_open = []List_close = []k,s = 0,0for i in range(1,n + 1):m = n // ifor j in range(1,m + 1):if List[i * j - 1] == 0:List[i * j - 1] = 1else:List[i * j - 1] = 0for i in range(n):if List[i] == 1:List_open.append(i + 1)k += 1else:List_close.append(i + 1)s += 1print('门的状态：',List,List_open,List_close,k,s)print('开门的编号：',List_open)print('开门的数量为：', k)print('关门的编号：',List_close)print('关门的数量为：',s) LockDoor(100)

带锁的门：

时间复杂度为O(n^2)

img

这篇关于算法设计与分析实验报告python实现(排序算法、三壶谜题、交替放置的碟子、带锁的门)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/876478。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
python: 多模块(.py)中全局变量的导入

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别： 当你在一个模块（文件）中使用 global 声明变量时，这个变量只在该模块的全局命名空
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2