查找算法的应用-学习任务单 (2)

学习任务单 课程基本信息 课题 查找算法的应用 学习目标 1. 能对生活中的具体问题进行抽象建模。 2. 能根据问题的特点选择合适的数据结构，设计查找算法。 3. 通过解决实际问题，理解并掌握查找算法的实现过程，体会查找算法在生活中的应用。 课前学习任务 复习冒泡排序的实现过程。 复习顺序查找和二分查找的实现过程，总结二者的时间复杂度和应用场景。 体验学习生活中的查找应用。 课上学习任务 “航空公司VIP会员积分查询”问题部分数据如右图所示： 【学习任务一】 抽象与建模：如何根据VIP号码快速查询到会员积分？ 【学习任务二】 设计算法与数据结构：如何用Python实现根据VIP号码找到该会员的记录。 1.对于会员记录的存储，按列存储或者按行存储哪个更方便后续数据处理？ 2. 根据右表思考，实现快速查询 采用哪种查找算法效率更高？ 【学习任务三】 编写程序并上机调试：在算法实现的过程中，冒泡排序和二分查找分别实现了独立的功能，为了提高代码的复用性，可将其封装成函数，请同学们根据流程图和教材P155-P156页例程自主实现函数的封装并上机调试运行。 【学习任务四】 学生“七选三”选课信息查询： 某校高一学期结束，学生进行了“七选三”预选课，选课信息存储在“course.csv”中，如图1所示，前3列分别存储学生的学号、姓名、班号，第4列到第10列分别表示物理、化学、生物、政治、历史、地理和技术的选课情况，其中“1”表示选择，“0”表示未选择。李老师编写了一个查询程序，此程序有以下功能：程序运行后自动从“course.csv”中读取学生信息，按照学号从小到大的顺序将所有学生信息排序，并打印输出。输入一个学生的学号，程序自动查找是否存在该学生，若找到，输出该生的“七选三”科目，如果没有找到，则显示“没有查询到该学号信息!”。查询结果如图2所示。 图 1 图 2 查询程序如下，根据代码注释，将横线处缺失的代码补充完整。 #读入csv中数据保存到列表a中 import csv csvFile=open("course.csv","r") #打开文件 reader=csv.reader(csvFile) a=[] for item in reader: #将每行数据（列表）依次追加到列表a中 a.append(item) csvFile.close() #冒泡排序 for i in range(1,len(a)): for j in range(1,len(a)-i): #从第1条记录开始比较 if _____: #按照每条记录的第0个元素学号进行升序排列 temp=a[j] a[j]=a[j+1] a[j+1]=temp #打印排序后的学生信息 print('排序后：') for i in range(len(a)): print(a[i]) #二分查找 key=int(input("请输入要查找的学号：")) i=1;j=len(a)-1 #查找范围不包含第一行数据 flag=False #设置查找标记 while i<=j: m=(i+j)//2 #取中间索引 if int(a[m][0])==key: _____ #查找成功，结束查找 break if _____: #若查找学号<当前学号，查询左区间 j=m-1 else: i=m+1 #根据查找结果输出学生的选考科目 b=['物理','化学','生物','政治','历史','地理','技术'] if flag==True: #查找成功 print(a[m][1],"同学，您的7选3科目为：") for j in range(3,10): if a[m][j]=='1': print(b[j-3],end=" ") else: print("找不到此学号对应的同学信息！") ... ...