5.4.2 查找算法的应用-教学设计（表格式）
文档属性
| 名称 | 5.4.2 查找算法的应用-教学设计（表格式） |  | |
| 格式 | docx | ||
| 文件大小 | 370.6KB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 浙教版（2019） | ||
| 科目 | 信息技术（信息科技） | ||
| 更新时间 | 2024-04-29 20:58:23 | ||
图片预览
文档简介
教学设计
课程基本信息
课题 5.4 数 据 查 找 ——查找算法的应用
教学目标
1.通过查找应用回顾，引导学生能对给定的文件中的数据进行抽象并建立模型。 2.引导学生能合理选用数据结构，设计查找算法。 3.引导学生能用Python语言编写具体的查找程序。 4.引导学生能自觉对学习生活具体问题抽象建模、设计算法并编写程序及调试程序。
指向的核心素养
●信息意识：学生能够结合实例对给定的文件中的数据进行抽象并建立模型，有意识地选择恰当的数据结构表达数据比较。 ●计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（查找、迭代等）编程实现、解决问题。 ●数字化学习与创新：要使学生较为熟练地运用查找解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择 ●信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。
教学内容
教学重点： 1.二分查找的算法思想。
2.能熟练用自然语言、流程图与Python语言来描述查找排序。
教学难点： Python语言描述变式二分查找。
教学过程
情景引入 平时在Excel查找信息，并体验vip号码的excel查找 航空公司VIP会员积分查询部分数据（Excel数据） 抽象与建模
问题：从表中的数据可以看出，每个会员的信息是一条记录，包括VIP号、姓名、飞行里程、积分等数据项。 实践体验：Excel表格中，对记录快速查询会员积分，查找应当如何进行？ 设计算法与数据结构
数据组织形式有两种： 方法一是采用4个一维数组按列存储，即每个数组分别存储每个用户的VIP号、姓名、飞行里程（KM） 、积分等，如定义a数组存储表中每个用户的VIP号，其对应的值为[“600214”,” 601278 ” ,” 600815 ” ,” 607854” , ” 605719” ……];
定义b数组存储表中姓名；
定义c数组存储表中飞行里程（KM）；
定义d数组存储表中积分信息。 方法二是采用1个一维数组按行存储，每个数组元素对应某个国家的一条记录信息，如a[1]为[600214，韩江辉，16801 ，519]对应第一条记录的相关信息。 数据查找算法有两种：
查找可采用顺序查找算法或二分查找算法, 对数据进行一次查找，采用顺序查找算法。 对数据重复查找，二分查找算法的效率高于顺序查找算法， 但二分查找提前：被查找的数据序列必须是有序，即在查找VIP号前要按VIP号为关键字进行排序。 (三）编写程序并调试
算法一:顺序查找 程序1： #数据读入 import csv #导入csv模块 csvFile = open("vip.csv", "r") #打开vip.csv数据文件 reader = csv.reader(csvFile) )#建立一个读入数据的对象reader a = [] #定义空列表a for item in reader: #每一行为a列表一个元素 a.append(item) #csv通过这种样式读入的数据为字符串 csvFile.close() #关闭vip.csv数据文件 for i in range(len(a)): #输出VIP表信息 print(a[i]) key=input('请输入要查询的VIP号：') #输入要查询的VIP号：key为字符串 #顺序查找 f=False #设置没查找标记 for i in range(1,len(a)): #查询范围不包含第一行数据 if a[i][0]==key: #逐一比较 m=i #记录找到了的位置 f=True #标记查找成功 break #结束查找 if f==True: #标记查找成功，输出信息 print(a[m][1],"先生/女士，',您的积分为：",a[m][3]) else: #查找不成功，输出信息 print('找不到VIP号对应的用户信息！') 程序2： #数据读入 import csv #导入csv模块 csvFile = open("vip.csv", "r") #打开vip.csv数据文件 reader = csv.reader(csvFile) #建立一个读入数据的对象reader a = [] #定义空列表a for item in reader: #每一行为a列表一个元素,此元素为字符串 a.append(item) #csv通过这种样式读入的数据为字符串 csvFile.close() #关闭vip.csv数据文件 for i in range(len(a)): #输出VIP表信息 print(a[i]) key=input('请输入要查询的VIP号：') #输入要查询的VIP号：key为字符 #顺序查找 def seq_search(a,key): global m #定义全局变量m f=False #设置没查找标记 for i in range(1,len(a)): #查询范围不包含第一行数据 if a[i][0] ==key: #逐一比较 f=True #标记查找成功 m=i #记录找到了的位置 break #结束查找 return f #返回f f=seq_search(a,key) if f==True: #标记查找成功，输出信息 print(a[m][1],"先生/女士，',您的积分为：",a[m][3]) else: #查找不成功，输出信息 print('找不到VIP号对应的用户信息！') 观看运行程序 算法二:二分查找 程序1：
import csv #导入csv模块 #数据读入 csvFile = open("vip.csv", "r") #打开vip.csv数据文件 reader = csv.reader(csvFile)#建立一个读入数据的对象reader a = [] #定义空列表a for item in reader:#每一行为a列表一个元素,此元素为字符串 a.append(item) #csv通过这种样式读入的数据为字符串 csvFile.close() #关闭vip.csv数据文件 #冒泡排序 for i in range(1,len(a)): for j in range(1,len(a)-i): if int(a[j][0])>int(a[j+1][0]): #升序排序 a[j],a[j+1]=a[j+1],a[j] print('排序后:') for i in range(len(a)):#输出排序后的VIP表信息 print(a[i])
key=int(input('请输入要查询的VIP号：')) #二分查找 i = 1 #查找范围不包含第一行数据，左端点初值1 j = len(a)-1 #右端点初值为最后一个元素索引值 f=False #设置查找标记 while i <= j: m = (i+j) //2 #确定中点 if int(a[m][0]) ==key:#key与中点VIP号相等 f=True #标记查找成功 break #结束查找 if key < int(a[m][0]): #key<中点VIP号 j = m-1 #到左半区间找 else: #key>中点VIP号 i = m+1 #到右边区间找 if f==True: #标记查找成功，输出信息 print(a[m][1],"先生/女士,您的积分为：",a[m][3]) else: print('找不到VIP号对应的用户信息！') 程序2：
import csv #导入csv模块 #数据读入 csvFile = open("vip.csv", "r") #打开vip.csv数据文件 reader = csv.reader(csvFile)#建立一个读入数据的对象reader a = [] #定义空列表a for item in reader:#每一行为a列表一个元素,此元素为字符串 a.append(item) #csv通过这种样式读入的数据为字符串 csvFile.close() #关闭vip.csv数据文件 #冒泡排序函数 def bubble_sort(d): for i in range(1,len(d)): for j in range(1,len(d)-i): if int(d[j][0])>int(d[j+1][0]):#升序排序 d[j],d[j+1]=d[j+1],d[j] #二分查找函数 def bsearch(s,array): i = 1 #查找范围不包含第一行数据，左端点初值1 j = len(array)-1#右端点初值为最后一个元素索引值 f=False #设置查找标记 while i <= j: m = (i+j) //2 #确定中点 if int(array[m][0]) ==s:#key与中点VIP号相等 return m #找到就结束查找，返回中点m if s < int(array[m][0]):#key<中点VIP号 j = m-1 #到左边区间找 else: #key>中点VIP号 i = m + 1 #到右边区间找 return -1 #未找到返回-1 #主程序 bubble_sort(a) #调用冒泡排序 print('排序后:') for i in range(len(a)):#输出排序后的VIP表信息 print(a[i]) key=int(input('请输入要查询的VIP号：')) m=bsearch(key,a) #调用二分查找函数 if m !=-1: #标记查找成功，输出信息 print(a[m][1],"先生/女士，',您的积分为：",a[m][3]) else: #未找到 print('找不到VIP号对应的用户信息！') 观看运行程序 学习生活中的应用实践： 校园一卡通号码查询。某校共n名学生，严老师编写了一个校园一卡通号码查询程序，输入号码就能查询该号码所属的班级和学生姓名。如右图所示所有学生数据存储在“校园一卡通.csv”表格中，该表格分别保存了本校所有学生的号码、所在班级和姓名的信息，号码的编码规则为入学年份+班级加身份证号后三位。第i个学生的号码保存在第1列中，对应的班级和姓名保存在第2列和第3列中。输入号码，电脑开始查找该号码的信息，如果找到对应的信息，就显示所属班级和姓名，如果没有找到，则显示“没有查询到该号码信息!”。（以填空形式说明） 相应程序如下，请在程序划线①②③处填入相应的代码，把程序补充完整。 import csv flie1=open('校园一卡通.csv','r') reader=csv.reader(flie1) st=[] for it in reader: ① flie1.close() # 冒泡排序 for i in range(1,len(st)-1): for j in range(len(st)-1,i,-1): if ② : st[j],st[j-1]=st[j-1],st[j] for i in range(len(st)): print(st[i])
# 二分查找 key=input(‘请输入需要查找的卡号：') i=1;j=len(st)-1 while i<=j: m=(i+j)//2 if ③ : i=m+1 else: j=m-1 if st[i][0]==key: print(st[0]) print(st[i]) else: print("没有该号码信息！")
10
课程基本信息
课题 5.4 数 据 查 找 ——查找算法的应用
教学目标
1.通过查找应用回顾，引导学生能对给定的文件中的数据进行抽象并建立模型。 2.引导学生能合理选用数据结构，设计查找算法。 3.引导学生能用Python语言编写具体的查找程序。 4.引导学生能自觉对学习生活具体问题抽象建模、设计算法并编写程序及调试程序。
指向的核心素养
●信息意识：学生能够结合实例对给定的文件中的数据进行抽象并建立模型，有意识地选择恰当的数据结构表达数据比较。 ●计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（查找、迭代等）编程实现、解决问题。 ●数字化学习与创新：要使学生较为熟练地运用查找解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择 ●信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。
教学内容
教学重点： 1.二分查找的算法思想。
2.能熟练用自然语言、流程图与Python语言来描述查找排序。
教学难点： Python语言描述变式二分查找。
教学过程
情景引入 平时在Excel查找信息，并体验vip号码的excel查找 航空公司VIP会员积分查询部分数据（Excel数据） 抽象与建模
问题：从表中的数据可以看出，每个会员的信息是一条记录，包括VIP号、姓名、飞行里程、积分等数据项。 实践体验：Excel表格中，对记录快速查询会员积分，查找应当如何进行？ 设计算法与数据结构
数据组织形式有两种： 方法一是采用4个一维数组按列存储，即每个数组分别存储每个用户的VIP号、姓名、飞行里程（KM） 、积分等，如定义a数组存储表中每个用户的VIP号，其对应的值为[“600214”,” 601278 ” ,” 600815 ” ,” 607854” , ” 605719” ……];
定义b数组存储表中姓名；
定义c数组存储表中飞行里程（KM）；
定义d数组存储表中积分信息。 方法二是采用1个一维数组按行存储，每个数组元素对应某个国家的一条记录信息，如a[1]为[600214，韩江辉，16801 ，519]对应第一条记录的相关信息。 数据查找算法有两种：
查找可采用顺序查找算法或二分查找算法, 对数据进行一次查找，采用顺序查找算法。 对数据重复查找，二分查找算法的效率高于顺序查找算法， 但二分查找提前：被查找的数据序列必须是有序，即在查找VIP号前要按VIP号为关键字进行排序。 (三）编写程序并调试
算法一:顺序查找 程序1： #数据读入 import csv #导入csv模块 csvFile = open("vip.csv", "r") #打开vip.csv数据文件 reader = csv.reader(csvFile) )#建立一个读入数据的对象reader a = [] #定义空列表a for item in reader: #每一行为a列表一个元素 a.append(item) #csv通过这种样式读入的数据为字符串 csvFile.close() #关闭vip.csv数据文件 for i in range(len(a)): #输出VIP表信息 print(a[i]) key=input('请输入要查询的VIP号：') #输入要查询的VIP号：key为字符串 #顺序查找 f=False #设置没查找标记 for i in range(1,len(a)): #查询范围不包含第一行数据 if a[i][0]==key: #逐一比较 m=i #记录找到了的位置 f=True #标记查找成功 break #结束查找 if f==True: #标记查找成功，输出信息 print(a[m][1],"先生/女士，',您的积分为：",a[m][3]) else: #查找不成功，输出信息 print('找不到VIP号对应的用户信息！') 程序2： #数据读入 import csv #导入csv模块 csvFile = open("vip.csv", "r") #打开vip.csv数据文件 reader = csv.reader(csvFile) #建立一个读入数据的对象reader a = [] #定义空列表a for item in reader: #每一行为a列表一个元素,此元素为字符串 a.append(item) #csv通过这种样式读入的数据为字符串 csvFile.close() #关闭vip.csv数据文件 for i in range(len(a)): #输出VIP表信息 print(a[i]) key=input('请输入要查询的VIP号：') #输入要查询的VIP号：key为字符 #顺序查找 def seq_search(a,key): global m #定义全局变量m f=False #设置没查找标记 for i in range(1,len(a)): #查询范围不包含第一行数据 if a[i][0] ==key: #逐一比较 f=True #标记查找成功 m=i #记录找到了的位置 break #结束查找 return f #返回f f=seq_search(a,key) if f==True: #标记查找成功，输出信息 print(a[m][1],"先生/女士，',您的积分为：",a[m][3]) else: #查找不成功，输出信息 print('找不到VIP号对应的用户信息！') 观看运行程序 算法二:二分查找 程序1：
import csv #导入csv模块 #数据读入 csvFile = open("vip.csv", "r") #打开vip.csv数据文件 reader = csv.reader(csvFile)#建立一个读入数据的对象reader a = [] #定义空列表a for item in reader:#每一行为a列表一个元素,此元素为字符串 a.append(item) #csv通过这种样式读入的数据为字符串 csvFile.close() #关闭vip.csv数据文件 #冒泡排序 for i in range(1,len(a)): for j in range(1,len(a)-i): if int(a[j][0])>int(a[j+1][0]): #升序排序 a[j],a[j+1]=a[j+1],a[j] print('排序后:') for i in range(len(a)):#输出排序后的VIP表信息 print(a[i])
key=int(input('请输入要查询的VIP号：')) #二分查找 i = 1 #查找范围不包含第一行数据，左端点初值1 j = len(a)-1 #右端点初值为最后一个元素索引值 f=False #设置查找标记 while i <= j: m = (i+j) //2 #确定中点 if int(a[m][0]) ==key:#key与中点VIP号相等 f=True #标记查找成功 break #结束查找 if key < int(a[m][0]): #key<中点VIP号 j = m-1 #到左半区间找 else: #key>中点VIP号 i = m+1 #到右边区间找 if f==True: #标记查找成功，输出信息 print(a[m][1],"先生/女士,您的积分为：",a[m][3]) else: print('找不到VIP号对应的用户信息！') 程序2：
import csv #导入csv模块 #数据读入 csvFile = open("vip.csv", "r") #打开vip.csv数据文件 reader = csv.reader(csvFile)#建立一个读入数据的对象reader a = [] #定义空列表a for item in reader:#每一行为a列表一个元素,此元素为字符串 a.append(item) #csv通过这种样式读入的数据为字符串 csvFile.close() #关闭vip.csv数据文件 #冒泡排序函数 def bubble_sort(d): for i in range(1,len(d)): for j in range(1,len(d)-i): if int(d[j][0])>int(d[j+1][0]):#升序排序 d[j],d[j+1]=d[j+1],d[j] #二分查找函数 def bsearch(s,array): i = 1 #查找范围不包含第一行数据，左端点初值1 j = len(array)-1#右端点初值为最后一个元素索引值 f=False #设置查找标记 while i <= j: m = (i+j) //2 #确定中点 if int(array[m][0]) ==s:#key与中点VIP号相等 return m #找到就结束查找，返回中点m if s < int(array[m][0]):#key<中点VIP号 j = m-1 #到左边区间找 else: #key>中点VIP号 i = m + 1 #到右边区间找 return -1 #未找到返回-1 #主程序 bubble_sort(a) #调用冒泡排序 print('排序后:') for i in range(len(a)):#输出排序后的VIP表信息 print(a[i]) key=int(input('请输入要查询的VIP号：')) m=bsearch(key,a) #调用二分查找函数 if m !=-1: #标记查找成功，输出信息 print(a[m][1],"先生/女士，',您的积分为：",a[m][3]) else: #未找到 print('找不到VIP号对应的用户信息！') 观看运行程序 学习生活中的应用实践： 校园一卡通号码查询。某校共n名学生，严老师编写了一个校园一卡通号码查询程序，输入号码就能查询该号码所属的班级和学生姓名。如右图所示所有学生数据存储在“校园一卡通.csv”表格中，该表格分别保存了本校所有学生的号码、所在班级和姓名的信息，号码的编码规则为入学年份+班级加身份证号后三位。第i个学生的号码保存在第1列中，对应的班级和姓名保存在第2列和第3列中。输入号码，电脑开始查找该号码的信息，如果找到对应的信息，就显示所属班级和姓名，如果没有找到，则显示“没有查询到该号码信息!”。（以填空形式说明） 相应程序如下，请在程序划线①②③处填入相应的代码，把程序补充完整。 import csv flie1=open('校园一卡通.csv','r') reader=csv.reader(flie1) st=[] for it in reader: ① flie1.close() # 冒泡排序 for i in range(1,len(st)-1): for j in range(len(st)-1,i,-1): if ② : st[j],st[j-1]=st[j-1],st[j] for i in range(len(st)): print(st[i])
# 二分查找 key=input(‘请输入需要查找的卡号：') i=1;j=len(st)-1 while i<=j: m=(i+j)//2 if ③ : i=m+1 else: j=m-1 if st[i][0]==key: print(st[0]) print(st[i]) else: print("没有该号码信息！")
10