辽阳网站建设多少钱,温州网站优化搜索,企业网站开发哪家专业,网站建设合同解除函一、 实验目的
1#xff0e;加深学生对算法设计方法的基本思想、基本步骤、基本方法的理解与掌握#xff1b; 2#xff0e;提高学生利用课堂所学知识解决实际问题的能力#xff1b; 3#xff0e;提高学生综合应用所学知识解决实际问题的能力。
二、实验任务
1、排序算法…一、 实验目的
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.7Pycharm
四、实验过程设计算法思路及描述代码设计
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) 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) 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) 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) 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) 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) 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) 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) 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) 3、交替放置的碟子
输入碟子的总数n产生一个01交错的列表其中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) 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)
