哈工大（威海）算法实验一：分治算法实验大作业

题目

某一高等院校有汽车学院、材料学院、计算机学院、软件学院；每个学院的一年级第一学期都开英语、高数、线代课程。每个学院每学期的成绩已经分别登录在同一个Excel文件的不同Sheet（表）中，没有排序，人数分别为，N1,N2,N3,N4 （2020年朱东杰老师的算法课，实验一大作业，仅供参考） （具体的python jupyter notebook文件和数据Excel文件已经打包上传资源到了，链接：哈工大（威海） 算法设计与分析 朱东杰老师 实验一（分治算法实验））

任务

1.按单科成绩排序算法 2.输出在全校英语成绩前k名的学生名单（学院、学号、姓名、英语成绩） 3.输出在全校英语、高数、线代成绩都是前k名的学生名单（学院、学号、姓名、英语、高数、线代成绩）

题解

任务一：使用归并排序。首先将各个表中的数据读入到一个数组中（笔者使用python的openpyxl库来实现Excel的读取，并使用list来存储每个学生的信息），之后实现divide函数和merge函数。 使用递归法实现归并排序： 1.将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素 2.将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素 3.重复步骤2，直到所有元素排序完毕 merge函数 （将子序列合并）

def merge(arr, left, right, flag): mid = int((right - left)/2 + left) temp = [] i = left j = mid + 1 while i < mid + 1 and j < right + 1: # 合并两个有序的子序列 if arr[i][flag] < arr[j][flag]: temp.append(arr[j]) j = j + 1 else: temp.append(arr[i]) i = i + 1 while i < mid + 1: temp.append(arr[i]) i = i + 1 while j < right + 1: temp.append(arr[j]) j = j + 1 index = 0 for k in range(left, right + 1): # 使用合并后的有序序列更新原序列 arr[k] = temp[index] index = index + 1

divide函数 （将原序列拆分，并进行递归，调用merge函数）

def divide(arr, left, right, flag): # flag = 2英语； flag = 3高数; flag = 4代数 if right - left < 1: return 0 else: mid = int((right - left) / 2 + left) divide(arr, left, mid, flag) divide(arr, mid + 1, right, flag) merge(arr, left, right, flag)

任务二：使用分治法求最大值的算法。 传统的求序列中最大值和最小值的算法是很直接对序列进行扫描，需要2n-2次比较操作，使用分治的思想，可以优化到比较3n/2-2次比较操作

如上图，不断划分序列，直到每一小段只有两个元素，一个为此小序列的最大值，一个为此小序列的最大值，之后再将两个有序的小序列合并，不断重复此过程，只需要比较合并的两个序列的最大值和最小值，并不断更新这两个值即可。具体伪代码可参考下图：

findMax函数

def findMax(arr, left, right, flag): #分治法求最大值 max_temp1 = [10001, '无名氏', 0, 0, 0, '未知学院'] #初始化 max_temp2 = [10002, '无名氏', 0, 0, 0, '未知学院'] #初始化 if left == right: return arr[left] elif left == right - 1: #获得最大值，并返回 if arr[left][flag] > arr[right][flag]: return arr[left] else: return arr[right] else: mid = (left + right) // 2 max_temp1 = findMax(arr, left, mid, flag) #继续分段 max_temp2 = findMax(arr, mid + 1, right, flag) if max_temp1[flag] > max_temp2[flag]: #比较左右两端哪个的最大值更大 return max_temp1 else: return max_temp2

在有了这个可以求得最大值的算法后，想要求得序列的前k大值，只需要每次使用这个算法，求得当前序列的最大值，之后从序列中删除这个最大值即可。 findKMax函数

def findKMax(arr, ans, k, flag): #求前K大个值 for i in range(0, k): tempAns = findMax(arr, 0, len(arr) - 1, flag) ans.append(tempAns) arr.remove(tempAns)

任务三：要获得各项成绩都是前k名的学生名单，那么可以用一个set存储某项科目成绩前k名的学生姓名，之后在获得下一项科目成绩前k名的学生姓名名单后，新建一个临时的set，如果此名单中的姓名出现在了前一个set中，将名字添加到这个临时的set中去，之后使用临时的set的值更新原来的set的值，重复此过程即可获得各项成绩都是前k名的学生姓名集合。然后遍历一遍整个成绩表，寻找集合中的学生姓名对应的成绩信息即可。 getAllKMax函数

def getAllKMax(arr, k): #各项成绩都是前k名 nameSet = set() for i in range(2, 5): tempSet = set() # 临时的集合 ans = [] arr_temp = arr[:] findKMax(arr_temp, ans, k, i) for j in range(0, len(ans)): if i == 2: nameSet.add(ans[j][1]) else: if ans[j][1] in nameSet: tempSet.add(ans[j][1]) if i != 2: nameSet = tempSet return nameSet

代码

from openpyxl import load_workbook import copy workbook = load_workbook('2020算法实验1：分治算法实验.xlsx') sheet_car = workbook['汽车学院'] sheet_material = workbook['材料学院'] sheet_computer = workbook['计算机学院'] sheet_software = workbook['软件学院'] data_car_temp = sheet_car['C5':'G11'] data_material_temp = sheet_material['C5':'G13'] data_computer_temp = sheet_computer['C5':'G11'] data_software_temp = sheet_software['C5':'G11'] def dataProcess(data_temp, data, flag): for i in range(0, len(data_temp)): temp = [] for j in range(0, 5): temp.append(data_temp[i][j].value) if flag == 1: temp.append("汽车学院") if flag == 2: temp.append("材料学院") if flag == 3: temp.append("计算机学院") if flag == 4: temp.append("软件学院") data.append(temp) data_all = [] dataProcess(data_car_temp, data_all, 1) dataProcess(data_material_temp, data_all, 2) dataProcess(data_computer_temp, data_all, 3) dataProcess(data_software_temp, data_all, 4) def merge(arr, left, right, flag): mid = int((right - left)/2 + left) temp = [] i = left j = mid + 1 while i < mid + 1 and j < right + 1: if arr[i][flag] < arr[j][flag]: temp.append(arr[j]) j = j + 1 else: temp.append(arr[i]) i = i + 1 while i < mid + 1: temp.append(arr[i]) i = i + 1 while j < right + 1: temp.append(arr[j]) j = j + 1 index = 0 for k in range(left, right + 1): arr[k] = temp[index] index = index + 1 def divide(arr, left, right, flag): # flag = 2英语； flag = 3高数; flag = 4代数 if right - left < 1: return 0 else: mid = int((right - left) / 2 + left) divide(arr, left, mid, flag) divide(arr, mid + 1, right, flag) merge(arr, left, right, flag) # 打印降序排序后的单科成绩名单 divide(data_all, 0, len(data_all) - 1, 2) print(data_all) def findMax(arr, left, right, flag): #分治法求最大值 max_temp1 = [10001, '无名氏', 0, 0, 0, '未知学院'] max_temp2 = [10002, '无名氏', 0, 0, 0, '未知学院'] if left == right: return arr[left] elif left == right - 1: if arr[left][flag] > arr[right][flag]: return arr[left] else: return arr[right] else: mid = (left + right) // 2 max_temp1 = findMax(arr, left, mid, flag) max_temp2 = findMax(arr, mid + 1, right, flag) if max_temp1[flag] > max_temp2[flag]: return max_temp1 else: return max_temp2 def findKMax(arr, ans, k, flag): #求前K大个值 for i in range(0, k): tempAns = findMax(arr, 0, len(arr) - 1, flag) ans.append(tempAns) arr.remove(tempAns) # 打印单项成绩是前k名的学生名单 data_temp = data_all[:] ans = [] findKMax(data_temp, ans, 5, 2) for i in range(len(ans)): print(ans[i][0],ans[i][1],ans[i][2],ans[i][5]) def getAllKMax(arr, k): #各项成绩都是前k名 nameSet = set() for i in range(2, 5): tempSet = set() ans = [] arr_temp = arr[:] findKMax(arr_temp, ans, k, i) for j in range(0, len(ans)): if i == 2: nameSet.add(ans[j][1]) else: if ans[j][1] in nameSet: tempSet.add(ans[j][1]) if i != 2: nameSet = tempSet return nameSet # 打印各项成绩都是前k名的学生名单 data_temp = data_all[:] nameSet = getAllKMax(data_temp, 5) for i in range(0, len(data_all)): if data_all[i][1] in nameSet: print(data_all[i])