( ! ) Notice: Undefined index: mobile in /var/www/html/head.php on line 16
Call Stack
#TimeMemoryFunctionLocation
10.0001230624{main}( ).../view.php:0
20.0001231368include( '/var/www/html/head.php' ).../view.php:2
30.0010250728isMobile( ).../head.php:30
数学思维训练网 - 小学计算思维课程(15)-线性搜索

小学计算思维课程(15)-线性搜索

小学计算思维课程(15)-线性搜索

本书共26课,如果您有好的建议,请联系作者:浙江省新昌县城西小学 唐明 147885198@qq.com

第十五课:线性搜索

让计算机完成特定任务的方法称为算法,算法通常由一系列指令组成,这些指令就称为计算机程序。不同的算法有不同的效率,本课所学的线性搜索算法是所有搜索算法中效率最低的一种,虽然计算机的运行速度非常快,但由于要搜索的数据浩如烟海,计算机处理起来也需要漫长的时间才能完成。想一想坐在计算机前苦苦等待一个半天也打不开的网页,那是多行的无趣!所以发明更快更有效率的算法非常重要。以下是一些需要提高效率的例子:

1.在互联网上查找含有你的名字的网页。

2.寻找快速员投递包裹的最短路径。

3.设计一个课程表,合理安排全校所有班级的课程。

计算机最重要的功能之一就是在浩瀚的数据中找到我们需要的信息。这节课我们来学习如何逐一查找全部数据,直到找到你想要的。我们将需要搜索的文字称为搜索关键字(search key)。

下面我们通过“秘密战舰”游戏来学习如何进行“线性搜索”。首先你需要一个搭档,你们每个人都有一艘秘密战舰,另一个需要在所有的战舰中找到对方的秘密战舰。

准备:你和搭档每人拿25张卡片,每张卡片上有一个随机的4位数,每人从手上的卡片中挑选一张作为自己的“秘密战舰”,并告诉搭档你的战舰号码。最后洗牌,以乱序摊开。

活动:每人依次从对方那里任选一张卡片翻开,第一个找到对方战舰的人就是胜利者。

问题:

1.记录找到战舰的次数,其中最多需要几次才能找到?

2.如果一共有25张卡片,你认为最多要几次一定能找到?最少要几次可以找到?

3.最一次就能猜到的可能性有多大呢?

4.如果秘密战舰不在这些卡片中,要猜多少次才能发现?

5.你认为,一般要猜多少次可以猜中秘密战舰?

6.如果有100张卡片,你认为一般需要猜几次才能猜中?

计算机的运算速度非常快,如果从数据的开头开始找,直到数据的结束,这样的搜索方法称为“线性搜索”。从上面的游戏中,我们可以发现,这种搜索方法是非常慢的。

假如一家超市有10000种不同的商品,当收银员扫描一件商品时需要在10000种不同的商品中找到这件商品,如果它们的计算机一秒可以比较1000件商品,那么查找全部商品需要10秒。这时客人一定等的很不耐烦,抛下商品去别家超市购物了。下一课我们就来学习一种更快速的算法来进行搜索。