极客小将

您现在的位置是:首页 » scratch编程资讯

资讯内容

作为程序员,你该如何向孩子解释“什么是搜索算法”!? 用Scratch编写小游戏:超级玛丽

极客小将2021-01-16-
如今审核如此便捷,遇到不懂的事情百度一下就知道了,部分小伙伴还可以Google,会出来很多关于搜索的信息和数据。


作为程序员,如何向孩子解释有关搜索中的原理,你该怎么向他们解释?


解释太难,孩子听不懂,解释太简单,又把握不住简单的维度。

超级玛丽scratch编程图片素材包下载地址:

https://www.jikexiaojiang.cn/165.html

如今审核如此便捷,遇到不懂的事情百度一下就知道了,部分小伙伴还可以Google,会出来很多关于搜索的信息和数据。

作为程序员,如何向孩子解释有关搜索中的原理,你该怎么向他们解释?

解释太难,孩子听不懂,解释太简单,又把握不住简单的维度。

不如试试下面这样的解释方式,以现在的少儿编程工具Scratch为例。

还不太了解Scratch?可能在成年人的世界里不太流行,但在学校和少儿编程中知名度很高。如果你已经很熟悉了,请跳过此步骤。

upload/article/images/2021-01-16/9f2cac72c512f1145a66431cca8f94b7.jpg

Scratch是麻省理工媒体实验室终身幼儿园组开发的一套计算机程序开发平台,旨在让程序设计语言初学者不需先学习语言语法便能设计产品。开发者期望通过学习Scratch,启发和激励用户在愉快的环境下经由操作(如设计交互故事)去学习程序设计、数学和计算知识,同时获得创造性思考,逻辑编程和协同工作体验。

在Scratch中,“角色”是通过名为“脚本”的程序来操纵的。我们来看一下让角色边动边发出声音的脚本吧。点击绿旗图标或者脚本本身,就可以看到角色随着鼓动声动起来。

upload/article/images/2021-01-16/8864667718f15e8ef1569d3d863ed509.jpg

脚本

upload/article/images/2021-01-16/c582f0f7342a66fec2943479f3d6ac94.jpg

角色

Scratch就是像上面这样把这些有颜色的“模块”排列起来制作脚本的。

如果仔细看这些模块上写的字,就可以知道程序向角色发出了什么指令。

这些模块很像玩具积木,对吧!

upload/article/images/2021-01-16/240df53a95d62b2ef9f5fd43c09761f4.jpg

如上图所示,搜索指的就是在数组中找出符合某个条件或性质的数据。它通过搜索算法来实现的,下面我们就介绍一下两种最具有代表性的搜索算法:线性搜索和二分搜索。


小游戏:超级玛丽


线性搜索

线性搜索是在给出的数组中,按顺序逐个比较每一项,从而找到所需要数据。下面通过具体的实例(下列数据中搜索15)来逐步学习线性搜索。

upload/article/images/2021-01-16/4a14538fb0be037293775505fd66ebe1.jpg

该数组中有7个数据,首先与第一位数据17进行比较,与我们要搜索的数据15不同,因此移动到下一位。

upload/article/images/2021-01-16/baad9a8bed280ed499625950e2e7e17a.jpg

第二位数据是2,也与15不同,因此移动到下一位。

upload/article/images/2021-01-16/2444514b643861dd32cdd3ecdbb4a136.jpg

第三位数据是20,也与15不同,因此移动到下一位。

upload/article/images/2021-01-16/f7564d7bb6a547d12ac925d3cbe34ec7.jpg

第四位数据是15,正是我们要搜索的数据,因此搜索成功,操作结束。

upload/article/images/2021-01-16/1aed51c5ec591670aa456d09981bc42a.jpg

如果7个数据全部比较完毕也没有找到需要的数据,则表示搜索失败。

线性搜索算法:

  • 建立列表data,并设任意数值。

  • 建立变量key,代表要搜索的数据。

  • 建立变量a,并设为1。

  • 如果a>data的项目数,则移动到步骤7。

  • 如果key与data的第a项相同,则输出“搜索成功”并结束操作。

  • 将a加1,并移动步骤4。

  • 输出“搜索失败”并完成操作。

下面我们通过在17,8,20,15这个数组中搜索20,来进一步了解算法的运行过程。

1、将列表data设置为17,8,20,15。将变量key设置为20。将变量a设置为1。

upload/article/images/2021-01-16/a73ae4691c2ebd9232c404e9bee5aa6c.jpg

2、a不大于data的项目数(4),将key的值与第一位数据17进行比较,两者不同,因此移动到下一位。

upload/article/images/2021-01-16/1c3cb09f7961238fbda8bb48a2b82ab5.jpg

3、将a的值加上1,a(=2)不大于data的项目数(=4),将key的值与第二位数据8进行比较,两者不同,并移动到下一位。

upload/article/images/2021-01-16/6fd2676424314ce5fb4a40e89beb6d8a.jpg

4、将a的值加1,a(=3)不大于data的项目数(=4),将key的值与第三位数据20进行比较,两者相同。输出“搜索成功”并结束操作。

upload/article/images/2021-01-16/4f5bc57870a62afa10ca5dcb2341319b.jpg

编写程序

理解了线性搜索的算法,我们怎么用编程来实现呢,下面就来用Scrach编写程序。

1、建立列表name和age,删除其全部项,并将7名学生的姓名和年龄分别添加到列表name和age中。

upload/article/images/2021-01-16/0617cc7d151f3e4db31a701ed5443ca4.jpg

2、建立变量key,并设为输入的学生姓名。

upload/article/images/2021-01-16/acf5ca76a2348fa38c7fc970af676dad.jpg

3、建立变量a,设置为1。添加upload/article/images/2021-01-16/298aed5e21db6030c1687c4dd05a4f31.jpgupload/article/images/2021-01-16/58f70d561d4dd592d0d16b6be8cd5e15.jpg

4、如果在列表name中找到key,则由Scratch小猫说出相应的学生姓名和年龄,并终止程序。那么绿框1处应该填写什么内容呢?

upload/article/images/2021-01-16/c6ee27fcb2e31f8612b4e33e9bf5a393.jpg

5、将a的值加上1,并继续重复执行。

upload/article/images/2021-01-16/4472c786b4c38469658ece6090c51921.jpg

6、如果在列表name中没能找到key,则由Scratch小猫说出“没有”。程序创建完成。

upload/article/images/2021-01-16/43a451868ce1a6d04202b1687b455dbe.jpg

7、此程序运行结果

upload/article/images/2021-01-16/ee99b1e88289d69f7cc9c8281334dd5a.jpg


二分搜索

二分搜索是指在一个有序列表中,通过逐渐缩小搜索范围进行搜索。下面通过具体的实例来解释。

在下面的升序排列数据中,使用二分搜索找到数据15,。

https://cdn.china-scratch.com/timg/190729/132631A94-21.jpg

1、该数组共有7个数据,将首项和末项的位置数(即1和7)分别设置low和high。

https://cdn.china-scratch.com/timg/190729/1326311511-22.jpg

2、还需要计算数组的中间位数。使用下面的数式可以计算出中间位数为4,将其设置为mid。

https://cdn.china-scratch.com/timg/190729/132631HL-23.jpg

mid位,即第4位的数据是11,将其与15进行比较。

https://cdn.china-scratch.com/timg/190729/1326324B2-24.jpg

3、15>11,因此mid位右侧的数据成为新的搜索范围。计算可知,新范围中的low位(即mid+1)是第5位。

https://cdn.china-scratch.com/timg/190729/1326325J1-25.jpg

4、再次计算mid位是第6位。因此将第mid位数据(=17)与15进行比较。

https://cdn.china-scratch.com/timg/190729/1326324H0-26.jpg

5、15<17,因此将当前mid位左侧的数据重新设为新的搜索范围。需要重新计算新的范围中的high位,即mid-1=5。新的high位就是第5位。

https://cdn.china-scratch.com/timg/190729/1326322558-27.jpg

6、再次计算mid位是第5位。因此将第mid位的数据(=15)与15进行比较。两者相同,搜索结束。

https://cdn.china-scratch.com/timg/190729/1326334012-28.jpg

如果low>high,则不能找到所求数据,搜索失败。

二分搜索算法

  • 建立列表data,并将有序排列的任意数据添加到该列表。

  • 建立变量key,设为要搜索的数据。

  • 建立变量low,设置为1;变量high,设为列表data的项目数。

  • 如果low>high,则移动到步骤8。

  • 建立变量mid,设为(low+high)/2。

  • 如果key与列表data的第mid项目,则输出“搜索成功”,操作完成。

  • 如果key< p="">

  • 输出“搜索失败”,操作完成。

下面在数组 8、10、13、15、20 中搜索 15,借此实例了解算法的运行过程。

1. 将 8、10、13、15、20 添加到列表 data。 将变量 key 设为 15。分别将变量 low和 high  设为 1 和 5,low 不大于 high,因此移动到下一步。

https://cdn.china-scratch.com/timg/190729/1326332J4-29.jpg

2. 将变量 mid 设为(low+high)/2(=3)。

https://cdn.china-scratch.com/timg/190729/1326334a0-30.jpg

3. key 大于列表 data 的第 mid 项(=13),因此将 low 设为 mid+1(=4),low(=4)不大于  high,因此移动到下一步。

https://cdn.china-scratch.com/timg/190729/1326333K7-31.jpg

4. 将变量 mid 设为(low+high)/2(=4)(设为向下取整)。

https://cdn.china-scratch.com/timg/190729/1326331N0-32.jpg

5. key 与列表 data 的第 mid 项(=15)相同,因此输出“搜索成功”,完成操作。

https://cdn.china-scratch.com/timg/190729/1326334F1-33.jpg

编写程序

1. 建立列表 name 和 age,删除其全部项,并将 7 名学生的姓名(按部首笔画递增排序)和相应年龄分别添加到列表 name  和 age。

https://cdn.china-scratch.com/timg/190729/1326344S5-34.jpg

2. 建立变量 key,设为要搜索的数据。建立变量 low,设为 1;建立变量 high,设为列表 name 的项目数。

https://cdn.china-scratch.com/timg/190729/13263425Q-35.jpg

3. 添加

https://cdn.china-scratch.com/timg/190729/1326346335-36.jpg

https://cdn.china-scratch.com/timg/190729/1326342041-37.jpg

4. 如果 key 与列表 name 的第 mid 项相同,则说出相应学生的姓名和年龄,程序停止。

https://cdn.china-scratch.com/timg/190729/1326345632-38.jpg

6. 如果 key 与列表 name 的第 mid 项不同,则变更 low 或者 high 的值,继续重复执行。那么绿框 2  处应该填写什么内容?

https://cdn.china-scratch.com/timg/190729/132634G43-39.jpg

7. 如果直到low>high时依然没有找到 key,则说出“没有”。程序创建完成。

https://cdn.china-scratch.com/timg/190729/1326353a3-40.jpg

8.此程序运行结果如下。

声明:本文章由网友投稿作为教育分享用途,如有侵权原作者可通过邮件及时和我们联系删除

网友点评

共有5条评论来说两句吧...