复习:我们学到哪里了 5 分钟
- 三个一起走的列表:每个列表的第 4 行合起来是一张牌。
(item # of [Bat] in [names v])给出一个行号,或者 0。- “目前最好的”和“一路加起来的总数”,都只要沿着列表走一趟。
快问快答
(item # of [Bat] in [names v]) 是怎么知道 Bat 在第 4 行的?
看答案
它是一行一行看出来的。第 1 行、第 2 行、第 3 行、第 4 行,每一行都比一比,直到对上为止。今天你要用积木把这个过程写出来。这会是你做的第一个有名字的东西,电脑科学家也用这个名字。
今天的主题 3 分钟
- 线性查找:从最上面开始,比一比,往下走,找到了就停
- 说出它在哪里,并处理好它不在的情况
- 数一数看了几次:最好的情况,最坏的情况
- 现成的积木帮你做了什么,又把什么藏起来了
学习目标
上完这节课,你能够:
- 用 Scratch 积木写出一个线性查找。
- 一找到答案,就让循环停下来。
- 说出一次查找比较了几次,以及为什么。
学一学:一行一行地找 28 分钟
1 · 你会怎么找?
把牌组正面朝上摆在桌上,请一个人找出 Frog。看看他怎么做。他会从一头开始,一张一张往下看,直到看见它。
这就是线性查找。它有名字,是因为这是找东西最直接的办法,而且几乎所有别的办法都拿它来比。
- 从第 1 行开始。
- 这一行是我要的吗?
- 如果是,记下行号,然后停。
- 如果不是,往下走一行。
- 如果走过了最后一行,那它就不在里面。
2 · 用积木写出来
这个循环有两种停法:找到了,或者找完了。所以它是一个 repeat until <>,里面放一个 <<> or <>>,和第 3-8 课的问答游戏一模一样:
set [n v] to (0)
set [found at v] to (0)
repeat until <<(n) > ((length of [names v]) - (1))> or <(found at) > (0)>>
change [n v] by (1)
if <(item (n) of [names v]) = (looking for)> then
set [found at v] to (n)
end
end
found at 从 0 开始,如果什么都对不上,它就一直是 0。这就是上节课的“0 表示哪里都没有”。怎么用: 点绿旗,看它一张一张地检查,还大声说出来,直到找到 Frog。
3 · 数一数花了多少功夫
加一块积木 change [looked at v] by (1),查找就会告诉你它找得有多辛苦:
| 要找的 | 看了几次 | 为什么 |
|---|---|---|
| Dragon(第 1 行) | 1 | 马上就找到了:最好的情况。 |
| Crab(第 6 行) | 6 | 在牌组的最后。 |
| Unicorn(不在里面) | 6 | 你要读完每一行,才能说“这里没有”。 |
怎么用: 点绿旗,看三次查找,每次都说出它看了几次。
基础任务:找任意一张牌 24 分钟
打开你上节课做的牌组。
第 1 步:几个框
- 建好
n、found at和looked at。 - 把后面两个显示在舞台上。
第 2 步:问要找什么
- 加上
ask [Type a card name] and wait。 - 紧接着把三个变量都设成 0。
第 3 步:循环
- 搭好
repeat until <>,里面放两部分的停止条件。 - 里面:给
n加 1,给looked at加 1,然后是 if。 - 加上
switch costume to (item (n) of [pics v]),这样你能看到它在找。 - 加一个短短的
wait (0.35) seconds,让大家看得清楚。
第 4 步:说出结果
- 循环结束后,如果
found at大于 0,就显示这张牌和它的力量。 - 不然就说它不在牌组里,再说你读了几行。
第 5 步:两头都试一试
- 找第一张牌。看的次数应该是 1。
- 找最后一张牌。看的次数应该是 6。
- 找一个乱打的名字。看的次数应该是 6,found at 是 0。
ask [Type a card name] and wait
set [n v] to (0)
set [found at v] to (0)
set [looked at v] to (0)
repeat until <<(n) > ((length of [names v]) - (1))> or <(found at) > (0)>>
change [n v] by (1)
change [looked at v] by (1)
switch costume to (item (n) of [pics v])
wait (0.35) seconds
if <(item (n) of [names v]) = (answer)> then
set [found at v] to (n)
end
end
if <(found at) > (0)> then
say (join [Row ] (join (found at) (join [, power ] (item (found at) of [powers v])))) for (3) seconds
else
say (join [No such card. I looked at all ] (join (looked at) [ of them.])) for (3) seconds
end
怎么用: 点绿旗,再点一下舞台。打 Bat 就能找到一张,打 Unicorn 就能看它读完整个牌组。
它总是说“不在牌组里”。
if 比较的是 (item (n) of [pics v]),或者是别的错的列表。它必须拿 names 列表和答案比。
它找到了牌,却还一直走到最后。
停止条件里少了 found at 那一半,或者比错了东西。found at 大于 0 时,循环必须停下来。
它漏掉了牌组里的最后一张。
差了一个。停止条件要用 ((length of [names v]) - (1)),因为 n 是在循环里面加 1 的,不是在检查之前。
第二次查找说出的是第一次查找的行号。
循环前面少了 set [found at v] to (0)。
捷径,还有它藏起来的东西
Scratch 有两块积木能帮你查找。拿它们和你做的比一比。
<[names v] contains [Shark]?>:是或不是。(item # of [Shark] in [names v]):一个行号,或者 0。- 说出每一块能做、另一块做不到的事,还有两块都做不到的事。
怎么用: 点绿旗,看两块积木回答一张在牌组里的牌,再回答一张不在的。
Teacher note
The honest answer is: use the block. The reason to write the loop is that item # of is a linear search with the lid on, and a pupil who has never lifted the lid thinks searching is free. That is the sentence worth saying.
按力量来找
用数字来找牌,而不是用名字。
- “哪张牌的力量是 8?”答案是 Dinosaur。
- 循环还是一样,只是里面的问题变了。
- 没有一张牌有的力量,也要好好地说出来。
怎么用: 点绿旗,看两次查找:力量 8,有;然后力量 6,没有。
Teacher note
Ask them how much of the script they had to change. It should be one block — the comparison. That is the moment an algorithm stops being “a script I wrote” and starts being a shape you can reuse.
有几个对得上?
有时候,第一个并不是你要的。那就把它们全部数一数。
- 让你的牌组里有三张力量一样的牌。
- 数一数有几张是这个力量。
- 循环在找到第一个时不停。
怎么用: 点绿旗,看它说出每一行对得上的,最后说出一共有几个。
Teacher reveal — the loop goes back to a plain repeat
set [how many v] to (0)
repeat (length of [powers v])
change [n v] by (1)
if <(item (n) of [powers v]) = (want)> then
change [how many v] by (1)
end
end
No found at, no early stop — counting needs every row, so the loop that was carefully stopping early now deliberately does not. Worth naming: “search” and “count” look alike and end differently.
早点放弃
如果牌组已经排好顺序,大的在前面,你常常不用走到最后就能停下来,因为下面的都比你刚读到的小。
- 用手把力量排成 9、8、7、5、4、3。
- 找一个牌组里没有的力量,比如 6。
- 一旦你所在的这一行比你要的小,就马上停。
怎么用: 点绿旗,比一比最后的两个数字:它读了几行,一共有几行。
Teacher reveal — the idea behind the idea
repeat until <<<(n) > ((length of [powers v]) - (1))> or <(found at) > (0)>> or <(item ((n) + (1)) of [powers v]) < (want)>>
That condition is getting unreadable, and saying so is part of the lesson — a give up variable set inside the loop is tidier than a three-part test. This is also the door to binary search: if the list is in order, you can do far better than reading from the top. Do not build it; just name it.
总结 5 分钟
- 线性查找:从第 1 行开始,比一比,往下走,找到了就停。
- 行号是 0,意思是“不在列表里”。
- 最好的情况是看一次。最坏的情况是每一行都看。要证明一样东西不在,永远是最坏的情况。
(item # of () in [names v])就是盖上盖子的这个查找。- 如果列表排好了顺序,早点停不费事;如果没排好,就很费事。
- 算法
- 一组能解决一类问题的步骤,不只是解决一个问题。
- 线性查找
- 从列表的一头开始往下找,直到找到为止。
- 比较
- 检查一行一次。查找花了多少功夫,就是数比较了几次。
- 最坏的情况
- 一个算法最多可能要做的功夫。
交作业
保存你的牌组。下节课你要把它排好顺序,看最强的牌一次换一下,慢慢走到最上面。