查找算法——顺序查找

难度:

尊敬的用户,该视频为旧版会员课程,仅限已购买的会员查看

编玩边学最新推出哈克尼斯圆桌课堂模式

更优质的课程与服务,系统的课程体系,提供国内最专业的儿童编程教育

查看新版课程

这节课我们来学习顺序查找,教大家用Scratch来实现这样一个程序:查找某个数是否属于斐波那契数列中,若属于,要求说出查找次数和所在的位置。

顺序查找定义:

   在一个已知数列(有序或无序)中找出与给定关键字相同的数.

算法流程:

    让关键字与数列中的数从第一个开始逐个比较,直到找出与给定关键字相同的数为止。

   第一步, 生成斐波那契数列

seq1.png

   注意:这里我们为避免数列中出现重复数,我们生成的斐波那契数列中不包括前面的0和第一个1.


   第二步, 构造顺序查找函数并调用

首先输入要查找的数字,然后建立一个循环从斐波那契数列中的第一个数开始,依次往下遍历斐波那契数列,直到查找成功!接着说出查找次数和所处位置。

如果全部遍历完斐波那契数列后,还没有查找到输入的数字,则查找失败!

seq2.png

调用顺序查找函数:将seqsearch嵌入到生成斐波那契数列的代码后面。

说明:变量count是用来记录所查找的次数,变量i是当前查找数在链表中的位置。



通过利用顺序查找算法,我们同样可以实现

  • 电话簿里查找电话号码

  • 在学校学生记录中查找某学号寻找对应同学信息

  • 火车站检票时查找身份证号码以验证某人是否是犯罪分子.


作业: 

   给定一个数列 { 3, 6, 2, 3, 10, 9, 7, 5, 9, 4, 1, 8} ,在该数列中用顺序查找的方法查找是否存在S(S = 9)?若存在,请给出S的个数及其对应的位置。(注意:要给出所有的S)



 登录/注册后发表或回复问题

在本系列的课程中,我们将经典算法在scratch中实现,你准备好了吗?挑战你自己的时刻到了

通过本系列课程的学习,你将会学到编程的精髓——算法,成为编程专家


###讲课老师:王代银,北大2015级硕士,算法、黑客技术高手,将艰深晦涩的算法问题用scratch讲得有趣易懂,这套scratch算法课程备受众多中小学信息技术课教师推崇,被大量用作参考教材!