中小学教育资源及组卷应用平台
项目九 实现查找指定商品
——查找算法的应用及数据结构的选择
第一课时 采用顺序查找法查找商品
教材分析
本节的主要内容是采用顺序查找法查找商品。在学习中,学生将尝试使用顺序查找法查找对应价格的商品数据。本项目的学习强调引导学生对实际问题从数据量大小、运行时间、存储空间和算法实现难易度等方面进行综合考虑,选择恰当的查找算法,使用合适的存储结构,通过编程实现问题的解决。在体验使用二分查找法查找商品的过程中,分别采用迭代法和递归法来完成算法设计,进一步提升计算思维。索引查找法虽然有一定难度,但是有助于学生进一步认识算法与数据结构的关系,从而进一步提升计算思维。
教学目标
1.掌握常用的数据查找方法——顺序查找法;
2.理解迭代概念。
3.理解递归概念。
4.进一步理解算法与数据结构的关系。
5.培养学生的信息意识和计算思维能力。
教学重点
1.掌握常用的数据查找方法、理解迭代和递归概念;
2.进一步理解算法与数据结构的关系。
教学难点
1.进一步理解算法与数据结构的关系;
2.培养学生的信息意识和计算思维能力。
教学方法
体验法、讲授法、讨论法、示例法
教学准备
计算机教室、多媒体设备、多媒体广播软件、Python编程环境、待查找的商品价格数据、教学课件等。
教学过程
一、新课导入
通常网络购物平台中出售的商品非常多,要在众多商品信息中查找某一商品,若依次翻页比对,可能要花相当长的时间。因此,平台一般都会提供查找功能,如图 5-6 所示。程序员在编程实现查找功能时,要依靠好的算法和合适的数据结构以提高查找效率。
二、查找
查找是根据给定的某个值,在查找表中找到一个其关键字等于给定值(也称待查关键字)的数据元素。
查找表是由同一类型的数据元素(或记录)构成的集合,是由所要查找的元素区间构成的表。查找表可以是线性表,也可以是树表(二叉查找树),如商品信息表就是一种线性的查找表。
常用的查找方法有顺序查找法、二分查找法、索引查找法等。
三、顺序查找算法
1.核心概念
查找算法是程序中经常用到的算法。假定要从n个元素中查找 x 的值是否存在,最原始的方法是从头到尾挨个查找,这种查找的方法叫顺序查找方法。
2.顺序查找基本思路
在一组数据中,从第一个数据开始,按照这组数据的排列顺序将每个数据逐个与给定的值进行比较。若某个数据与给定值相等,则查找成功,找到所查数据的位置;反之查找不成功。
假定有n个记录存放在数组r[1],r[2],…,r[n]中,其中第i个记录的关键字值为r[i].key。待查关键字为k,将k依次与r[n].key,r[n-1].key,...,r[1].key 进行比较,一旦某个r[i]. key等于k,查找成功,返回下标i,若所有的数据元素都与k值不相等,则给出查找失败(i=0)的信息。
3.顺序查找示例
输入查找的元素值,key=32
例如:Dim d(1 To 4) As Integer ‘定义一个数组d
定义一个变量i,让i由1变化到4,判断d(i)是否等于key。
顺序查找法的特点是算法比较简单,但查找一个数据元素的比较次数多,算法效率较低,一以数据量n很大,查找时间就相对较长。
顺序查找有三种情形可能发生:最好的情况,第一项就是要查找的数据对象,只有一次比较,最差的情况,需要 n 次比较,全部比较完之后找不到数据。平均情况下,比较次数为 n/2 次。算法的时间复杂度是 O(n) 。
例 : 在列表中查找 x 是否存在
def sequest(alist, item):
pos=0 #初始查找位置
found=False #未找到数据对象
while posif alist[pos] == item: # 找到匹配对象,返回TRUE
found=True
else: #否则查找位置 + 1
pos = pos+1
return found
def main():
testlist=[1,3,5,6,7,8,9,11,23,44]
print(sequest(testlist,11))
if __name__=='__main__':
main()
例 : 在列表顺序中 查找最大值和最小值
def Max(alist):
pos = 0 #初始位置
imax=alist[0] #假设第一个元素是最大值
while pos < len(alist): #在列表中循环
if alist[pos] > imax: #当前列表的值大于最大值 ,则为最大值
imax=alist[pos]
pos = pos+1 #查找位置 +1
return imax
def Min(alist):
pos = 0 # 初始位置
imin = alist[0] #假设第一个元素是最小值
for item in alist: #对于列表中的每一个值
if item < imin: #当前的值小于最小的值 则为最小值
imin = item
return imin
def main():
testlist=[2,3,4,5,6,8,34,23,55,234]
print('最大值是:',Max(testlist))
print('最小值是:',Min(testlist))
if __name__=='__main__':
main()
4.流程图
5.Python顺序算法实现:
def sequaential_search(lis, key):
length = len(lis)
for i in range(length):
if lis[i] == key:
return i
else:
return False
if __name__ == '__main__':
LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
result = sequential_search(LIST, 123)
print(result)
四、采用顺序查找法查找商品
假设某店铺出售的某品种商品有11种不同的价格15.83.19.88.37.96.64.5.80,18,92,要在其中查找价格为64的商品,最简单、最基本的方法是将商品价格序列存放在数组中,将待查元素64依次与数组中的每个元素一一比较,这种方法称为顺序查找法,如图5-7所示。
5-7顺序查找过程示意
图中所示的是从数组最后往前依次比较,当i为7时查找成功,此时共比较了5次。为编程方便,将待查元素64放在数组的0号空间,若序列中没有64,那i会移到0,查找失败。把0号空间称为监视哨,即i不可能越过0为负数。
思考与讨论?
顺序查找法的特点是什么?
顺序查找法的特点是算法比较简单,但查找一个数据元素的比较次数多,算法效率较低,一旦数据量很大查找时间就相对较长。
五、课堂活动
在右部的流程框图(局部)中,完成顺序查找算法(假设n个数据在数组r中,待查关键字k);编程实现,并运行测试。
参考答案:
程序:
r=[64,15,83,19,88,37,96,64,5,80,18,92]
i=11
while i>=0 and r[i]! =r[0]:
i=i+1
print(i) #输出为待查找数据在列表中的下标
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 (共 2 页)
HYPERLINK "http://21世纪教育网(www.21cnjy.com)
" 21世纪教育网(www.21cnjy.com)(共31张PPT)
第一课时 采用顺序查找法查找商品
信息技术沪教版 选择性必修1
第五单元 排序与查找
项目九 实现查找指定商品
——查找算法的应用及数据结构的选择
一、新课导入
二、查找
三、顺序查找算法
四、采用顺序查找法查找商品
五、课堂活动
一、新课导入
通常网络购物平台中出售的商品非常多,要在众多商品信息中查找某一商品,若依次翻页比对,可能要花相当长的时间。因此,平台一般都会提供查找功能,如图 5-6 所示。程序员在编程实现查找功能时,要依靠好的算法和合适的数据结构以提高查找效率。
二、查找
查找是根据给定的某个值,在查找表中找到一个其关键字等于给定值(也称待查关键字)的数据元素。
查找表是由同一类型的数据元素(或记录)构成的集合,是由所要查找的元素区间构成的表。查找表可以是线性表,也可以是树表(二叉查找树),如商品信息表就是一种线性的查找表。
01
02
03
索引查找法
二分查找法
顺序查找法
三、顺序查找算法
1.核心概念
查找算法是程序中经常用到的算法。假定要从n个元素中查找 x 的值是否存在,最原始的方法是从头到尾挨个查找,这种查找的方法叫顺序查找方法。
2.顺序查找基本思路
在一组数据中,从第一个数据开始,按照这组数据的排列顺序将每个数据逐个与给定的值进行比较。若某个数据与给定值相等,则查找成功,找到所查数据的位置;反之查找不成功。
假定有n个记录存放在数组r[1],r[2],…,r[n]中,其中第i个记录的关键字值为r[i].key。待查关键字为k,将k依次与r[n].key,r[n-1].key,...,r[1].key 进行比较,一旦某个r[i]. key等于k,查找成功,返回下标i,若所有的数据元素都与k值不相等,则给出查找失败(i=0)的信息。
3.顺序查找示例
输入查找的元素值,key=32
例如:Dim d(1 To 4) As Integer ,定义一个数组d,定义一个变量i,让i由1变化到4,判断d(i)是否等于key。
3.顺序查找示例
顺序查找法的特点是算法比较简单,但查找一个数据元素的比较次数多,算法效率较低,一以数据量n很大,查找时间就相对较长。
顺序查找有三种情形可能发生:最好的情况,第一项就是要查找的数据对象,只有一次比较,最差的情况,需要 n 次比较,全部比较完之后找不到数据。平均情况下,比较次数为 n/2 次。算法的时间复杂度是 O(n) 。
3.顺序查找示例
例1: 在列表中查找 x 是否存在
def sequest(alist, item):
pos=0 #初始查找位置
found=False #未找到数据对象
while posif alist[pos] == item: # 找到匹配对象,返回TRUE
found=True
else: #否则查找位置 + 1
pos = pos+1
return found
3.顺序查找示例
例1: 在列表中查找 x 是否存在
def main():
testlist=[1,3,5,6,7,8,9,11,23,44]
print(sequest(testlist,11))
if __name__=='__main__':
main()
3.顺序查找示例
例2: 在列表顺序中 查找最大值和最小值
def Max(alist):
pos = 0 #初始位置
imax=alist[0] #假设第一个元素是最大值
while pos < len(alist): #在列表中循环
if alist[pos] > imax: #当前列表的值大于最大值 ,则为最大值
imax=alist[pos]
pos = pos+1 #查找位置 +1
return imax
3.顺序查找示例
例2: 在列表顺序中 查找最大值和最小值
def Min(alist):
pos = 0 # 初始位置
imin = alist[0] #假设第一个元素是最小值
for item in alist: #对于列表中的每一个值
if item < imin: #当前的值小于最小的值 则为最小值
imin = item
return imin
3.顺序查找示例
例2: 在列表顺序中 查找最大值和最小值
def main():
testlist=[2,3,4,5,6,8,34,23,55,234]
print('最大值是:',Max(testlist))
print('最小值是:',Min(testlist))
if __name__=='__main__':
main()
4.流程图
5.Python顺序算法实现:
def sequaential_search(lis, key):
length = len(lis)
for i in range(length):
if lis[i] == key:
return i
else:
return False
if __name__ == '__main__':
LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
result = sequential_search(LIST, 123)
print(result)
四、采用顺序查找法查找商品
假设某店铺出售的某品种商品有11种不同的价格15、83、19、88、37、96、64、5、80、18、92,要在其中查找价格为64的商品,最简单、最基本的方法是将商品价格序列存放在数组中,将待查元素64依次与数组中的每个元素一一比较,这种方法称为顺序查找法,如图所示。
图中所示的是从数组最后往前依次比较,当i为7时查找成功,此时共比较了5次。为编程方便,将待查元素64放在数组的0号空间,若序列中没有64,那i会移到0,查找失败。把0号空间称为监视哨,即i不可能越过0为负数。
思考与讨论
顺序查找法的特点是什么?
思考与讨论
顺序查找法的特点是什么?
顺序查找法的特点是算法比较简单,但查找一个数据元素的比较次数多,算法效率较低,一旦数据量很大查找时间就相对较长。
五、课堂活动
在右部的流程框图(局部)中,完成顺序查找算法(假设n个数据在数组r中,待查关键字k);编程实现,并运行测试。
参考答案:
参考答案:
r=[64,15,83,19,88,37,96,64,5,80,18,92]
i=11
while i>=0 and r[i]! =r[0]:
i=i+1
print(i) #输出为待查找数据在列表中的下标
谢谢
21世纪教育网(www.21cnjy.com) 中小学教育资源网站
有大把高质量资料?一线教师?一线教研员?
欢迎加入21世纪教育网教师合作团队!!月薪过万不是梦!!
详情请看:
https://www.21cnjy.com/help/help_extract.php