☆ 理解并在游戲中運(yùn)用三種常用的數(shù)據(jù)搜索算法：線性 ( sequential ) 搜索算法、二分法 ( binary ) 搜索算法、散列 ( hashing ) 搜索算法。

☆  培養(yǎng)計(jì)算機(jī)科學(xué)素養(yǎng)。

☆ 洗手液 （最好是免沖洗）

☆ 寫(xiě)有數(shù)字的卡片

☆ 健康好吃的糖果

☆ 游戲《大海戰(zhàn)》圖紙 & 簽字筆

☆ 白板&白板筆

120分鐘

☆ 線性算法就是逐一比對(duì)數(shù)據(jù)，是最簡(jiǎn)單、最低效、沒(méi)有什么“算法”的算法。

☆ 二分法算法用于已排序數(shù)據(jù)，每次取中間值查詢，不斷縮小范圍。

☆ 散列法算法是將數(shù)據(jù)按照一定的方法換算成便于查找的關(guān)鍵字，所有的關(guān)鍵字組成“關(guān)鍵字表”，然后按照關(guān)鍵字表分組數(shù)據(jù)。這樣在查找時(shí)可以快速定位到數(shù)據(jù)所在組，并在組內(nèi)進(jìn)一步查詢。

對(duì)于這個(gè)年紀(jì)的孩子來(lái)說(shuō)，本課程更多的是“計(jì)算機(jī)科學(xué)素養(yǎng)”的培養(yǎng)，而非“算法課程”；因此對(duì)孩子的要求僅是理解和游戲中的應(yīng)用。

因?yàn)檎n程運(yùn)用了一定的數(shù)學(xué)知識(shí)，有一定難度，為了避免枯燥，課程設(shè)計(jì)要注重強(qiáng)化趣味性。

因此，特意設(shè)置“暖身”環(huán)節(jié)，并在課程中全程用游戲貫穿教學(xué)內(nèi)容。

暖身環(huán)節(jié)讓孩子快速體驗(yàn)線性算法，并思考排序數(shù)據(jù)的搜索算法，帶著問(wèn)題進(jìn)入主體游戲。過(guò)程中加入糖果小獎(jiǎng)品，強(qiáng)化娛樂(lè)性。

主體游戲采用海戰(zhàn)游戲的形式，兩人一組；用三套棋盤(pán)分別執(zhí)行三種搜索算法，讓孩子在游戲中體驗(yàn)算法的使用環(huán)境和執(zhí)行效率。

課程后讓孩子向父母講述三種搜索算法的基本原理，強(qiáng)化理解。

☆ 兩位數(shù)的加減乘除運(yùn)算

☆ 英文字母表

“全都去把手洗的干干凈凈的！我們一會(huì)兒要吃好吃的！”

從第一句話開(kāi)始，我就在調(diào)動(dòng)他們的情緒。要是不讓他們?nèi)计饋?lái)，這兩個(gè)小時(shí)的“數(shù)學(xué)課”可不好上。

如果可以給孩子們準(zhǔn)備免沖洗手液更好，普通洗手液也可以，讓孩子們把手洗干凈，好抓糖吃。

接著讓孩子們手拉手圍成一個(gè)圓圈，用“手心手背” + “猜丁殼”確定一個(gè)站在圓心的孩子。

這個(gè)孩子會(huì)有機(jī)會(huì)獲得更多的糖果，所以選擇過(guò)程一定要嚴(yán)格、公平，不然一定會(huì)有孩子不滿意。

給外圈的孩子每人發(fā)一張寫(xiě)有數(shù)字的卡片，讓孩子捂好，只有自己能看到數(shù)字。

給圓心的孩子一個(gè)裝有糖果的盒子，糖果數(shù)量等于外圈孩子的數(shù)量。

然后我開(kāi)始宣布游戲規(guī)則：老師隨機(jī)給出一個(gè)卡片上的數(shù)字，圓心的孩子要用提問(wèn)的方式，找出持有這個(gè)數(shù)字的卡片的孩子。她每問(wèn)一個(gè)孩子，被問(wèn)的孩子就要亮出卡片，同時(shí)得到一塊糖果；直到最終找到數(shù)字，此時(shí)盒子里剩下的糖果就都?xì)w圓心的孩子所有。（所以理論上，圓心的孩子最多可以擁有 總數(shù)-1 個(gè)糖果，最少一個(gè)都沒(méi)有。）

圓心的孩子會(huì)想方設(shè)法尋找蛛絲馬跡，察言觀色；圓圈里的孩子也會(huì)嘰嘰喳喳籌謀劃策，但還是會(huì)毫無(wú)頭緒，最后只能一個(gè)個(gè)的蒙（其實(shí)就是在實(shí)施線性搜索算法）。

找出數(shù)字后，一起做一個(gè)小小的總結(jié)。我們用了什么辦法找到老師給的數(shù)字的？一個(gè)個(gè)問(wèn)的。有更好的方法嗎？好像沒(méi)有。

好，下面我們開(kāi)始升級(jí)游戲。老師給圓心的孩子也發(fā)一張數(shù)字卡，讓她站回圓圈；所有的孩子按照卡片數(shù)字順序排列，重新站隊(duì)，圍成一個(gè)新的圓圈。

大家可以一邊吃糖，一邊在老師的帶領(lǐng)下共同思考：在重新排序的情況下，我們想最快找到一個(gè)數(shù)字，該怎么辦呢？

孩子們會(huì)有各種奇思妙想的方案，不過(guò)都有問(wèn)題。這個(gè)時(shí)候老師不能揭曉答案，要讓他們暢所欲言，再用提問(wèn)的方式，幫助他們發(fā)現(xiàn)問(wèn)題，進(jìn)一步思考。帶著思考，我們結(jié)束熱身活動(dòng)，準(zhǔn)備開(kāi)始正式游戲——大海戰(zhàn)！

開(kāi)始前，我必須先把今天的主題引出來(lái)，要讓孩子明白我們?cè)诟墒裁础?/p>

“有誰(shuí)用過(guò)互聯(lián)網(wǎng)搜索？”

齊刷刷的舉手。

“老師我拿我爸手機(jī)用過(guò)百度！”

“老師我用谷歌不用百度！”

“老師我用過(guò)美團(tuán)外賣(mài)！”

果然是移動(dòng)互聯(lián)網(wǎng)原住民啊，我像他們這么大的時(shí)候連計(jì)算器都沒(méi)見(jiàn)過(guò)。

但是有長(zhǎng)處也就有短處。沒(méi)有經(jīng)歷過(guò)數(shù)字時(shí)代的發(fā)展，他們就會(huì)缺少一些計(jì)算機(jī)科學(xué)的基本常識(shí)。

我曾遇到過(guò)孩子甚至以為，電腦里就真的有一個(gè)個(gè)圖標(biāo)，一個(gè)個(gè)窗口。

這也是我們?cè)O(shè)計(jì)這節(jié)課的最主要目的：給孩子一些計(jì)算機(jī)科學(xué)的“基本素養(yǎng)”。

“那么大家想過(guò)沒(méi)有，互聯(lián)網(wǎng)上那~~么多的信息，搜索引擎是怎樣那么快的找到他們呢？”

小朋友們馬上張大了嘴巴，一腦袋問(wèn)號(hào)……是哎，好像從來(lái)沒(méi)想過(guò)這個(gè)問(wèn)題?。∈窃趺凑业降哪?？

我轉(zhuǎn)身在白板上寫(xiě)下兩個(gè)字：算法。

從這里開(kāi)始，正式把算法的概念教授給孩子。

當(dāng)我們?cè)诖罅康臄?shù)據(jù)中搜索的時(shí)候，我們要用到一些巧妙的的計(jì)算方法，來(lái)加速搜索的過(guò)程，這就是“搜索算法”。

“大家先想想剛才的小朋友是怎么找到數(shù)字的？”

“她蒙的！”

“她一個(gè)一個(gè)問(wèn)的！”

“那么一個(gè)一個(gè)問(wèn)是不是一種算法呢？”

是的，這是一種算法，一種最簡(jiǎn)單的算法，我們叫它線性算法，或者順序算法。當(dāng)數(shù)據(jù)量不大，排列無(wú)序，數(shù)據(jù)本身很簡(jiǎn)單的時(shí)候，這也不失為一個(gè)有效的方法。比如剛才玩的熱身活動(dòng)，搜索簡(jiǎn)單的數(shù)字而已，一個(gè)個(gè)問(wèn)其實(shí)是最快的。

“下面我們就來(lái)一起玩一個(gè)很緊張刺激的游戲，《大海戰(zhàn)》！看看我們能不能用算法來(lái)取勝！”

下發(fā)第一套海戰(zhàn)圖和簽字筆。孩子分成兩人一組，一人持圖1A，另一人持圖1B。

老師宣布游戲規(guī)則：游戲目標(biāo)是用最少的炮彈擊中敵方的軍艦；游戲開(kāi)始時(shí)，每人選擇一艘自己的軍艦，告訴對(duì)方軍艦上的數(shù)字（不是英文字母！）；兩人輪流猜測(cè)軍艦所在的位置（英文字母），每猜測(cè)一次，計(jì)導(dǎo)彈發(fā)射一次；用最少數(shù)量的導(dǎo)彈擊中對(duì)方軍艦（猜到軍艦的位置）者獲勝。

有了剛才的熱身活動(dòng)，孩子們馬上明白，這些無(wú)序的數(shù)字，沒(méi)有什么好想的，一個(gè)一個(gè)猜，看誰(shuí)運(yùn)氣好。

真有一炮命中的，興高采烈。也有二十幾次才猜到的，好在場(chǎng)面很熱烈很歡樂(lè)，小朋友也不會(huì)很沮喪。??

進(jìn)行的差不多了，帶著孩子簡(jiǎn)單小總結(jié)一下：

可能的最大分?jǐn)?shù)和最小分?jǐn)?shù)分別是多少？26 和 1。

這些數(shù)字排列有規(guī)律嗎？沒(méi)有，無(wú)序的。

大家用了什么方法？線性算法。

還有什么好方法嗎？孩子們說(shuō)了一些。嗯！Good Try！但是基本還是在蒙。

接下來(lái)，海戰(zhàn)升級(jí)！給大家發(fā)放第二套海戰(zhàn)圖：2A 與 2B。

還是老師帶著孩子先觀察：看看這次的數(shù)字有什么不同？

孩子們看出來(lái)了：數(shù)字越來(lái)越大！

是的！這次海戰(zhàn)，戰(zhàn)艦數(shù)字是按順序排列的！

“還記得剛才我們也遇到了這種情況嗎？當(dāng)時(shí)大家都想了什么方法？現(xiàn)在就可以試試！”

規(guī)則與第一輪基本一致，只是在每次猜測(cè)時(shí)，需要告訴對(duì)方“大了”或“小了”。

如果沒(méi)有學(xué)過(guò)，幾乎不會(huì)有孩子能想到要取中間值不斷逼近。

但是他們也會(huì)有很多很好的嘗試，比如有的孩子會(huì)想：“我要取一個(gè)比較靠近最大值的位置，如果小了，那我就能排除掉很多可能性！但是萬(wàn)一大了怎么辦呢？那我就取一個(gè)靠近最小值的值！可是……”他就陷入死循環(huán)了。其實(shí)他離真理只有一步之遙了。

看火候差不多了，老師可以喊停了。聽(tīng)孩子們說(shuō)一說(shuō)自己的想法，經(jīng)過(guò)引導(dǎo)后，可以在黑板上寫(xiě)下第二個(gè)算法的名字了：二分法。

二分法的神奇之處在于，即使數(shù)據(jù)量翻了一倍，我們也只要多加一次查詢。當(dāng)數(shù)據(jù)量不斷翻倍的時(shí)候，二分法的魔力就凸顯的更明顯。這里，還可以給孩子講一講“陰險(xiǎn)的老爺爺讓不懂?dāng)?shù)學(xué)的國(guó)王往國(guó)際象棋盤(pán)里放米粒”的故事，孩子們會(huì)驚訝于指數(shù)增長(zhǎng)的神奇力量，反過(guò)來(lái)想一想，就明白了二分法的強(qiáng)大威力。

再回到我們的游戲，如果用二分法，最多幾次就能打到敵艦？孩子們一算，5次！好，趁熱打鐵，再做幾個(gè)小練習(xí)：老師心里想一個(gè)100以內(nèi)的數(shù)，讓大家用二分法來(lái)搜索；再來(lái)個(gè)1000以內(nèi)的數(shù)，再練一次。到此，孩子應(yīng)該可以熟練使用二分法了。

游戲再次升級(jí)！

第三次大海戰(zhàn)馬上開(kāi)始！給孩子們發(fā)第三套海戰(zhàn)圖：3A 和 3B。

和孩子一起觀察，這次的數(shù)字又有什么不同？

其實(shí)孩子觀察不出來(lái)，還是宣布好了。?? 

每艘船上幾個(gè)數(shù)字之和的尾數(shù)與船所在的列數(shù)是相同的！

其他的游戲規(guī)則還是和之前一樣。

“哇！那這次太簡(jiǎn)單啦！”孩子們能這么說(shuō)，說(shuō)明他們的思路非常清楚。

開(kāi)始玩吧！

這次進(jìn)行的非常快，很快都得出了結(jié)果。

大家用了幾次擊中了敵艦？最少一次，最多四次。為什么是四次？因?yàn)橐涣欣镒疃嘀挥?艘船。

像我們這樣，把搜索的數(shù)據(jù)按照一定方法算出一個(gè)關(guān)鍵字，很快定位到一個(gè)很小的范圍，再在小范圍內(nèi)去查找的方法，叫做——我轉(zhuǎn)身寫(xiě)下第三個(gè)算法的名字——散列法。

其實(shí)散列法我們大家可能都用到過(guò)！有小朋友翻看過(guò)微信里的聯(lián)系人嗎？我們按住聯(lián)系人右側(cè)的小字母，就可以快速定位到姓氏拼音首字母的位置，再在這個(gè)首字母里去尋找，就非?？炝恕＿@其實(shí)就是一種散列法的運(yùn)用。

那么線性算法、二分法和散列法，哪一種最快呢？在實(shí)際使用中，散列法一般是最快的一種方法。但是如果分組方法不夠好，在同一列里有太多的數(shù)據(jù)，散列法就很低效了。所以我們面對(duì)不同的數(shù)據(jù)，需要具體分析，使用合適的搜索方法！

好了，感覺(jué)孩子們燒腦燒的差不多了。最后布置一個(gè)作業(yè)：回家把這三種搜索方法給爸爸媽媽們說(shuō)明白了。只要能說(shuō)明白，我們的教學(xué)目標(biāo)就達(dá)成了。

下課！

本課程是清華大學(xué)終身學(xué)習(xí)實(shí)驗(yàn)室《不插電的編程課》系列課程中的一節(jié)。

此系列課程面向剛剛步入小學(xué)的一年級(jí)學(xué)生，旨在用最簡(jiǎn)單的工具（擺脫電腦等復(fù)雜、昂貴的教具的限制），游戲化的學(xué)習(xí)方法，教孩子學(xué)習(xí)計(jì)算機(jī)科學(xué)知識(shí)。

Project X是TULLL是一門(mén)實(shí)驗(yàn)性質(zhì)的課程，面向6到7歲（小學(xué)一、二年級(jí)）的小朋友。Project X 的教學(xué)目標(biāo)是盡可能的開(kāi)發(fā)孩子的創(chuàng)造力。

Project X可以被理解為“編程實(shí)驗(yàn)班”，但我們使用的主要學(xué)習(xí)工具遠(yuǎn)遠(yuǎn)不限于是編程。電腦編程僅僅是提升創(chuàng)造力的落腳點(diǎn)和工具之一。

目前Project X第一期已經(jīng)開(kāi)課，未來(lái)可能會(huì)有其他課程，請(qǐng)您關(guān)注TULLL的公眾號(hào)。

本課設(shè)計(jì)過(guò)程中，得到了 TULLL研究主管、清華大學(xué)心理學(xué)系助理教授伍珍老師的大力幫助。

她在建立兒童自信心、成長(zhǎng)型思維，培養(yǎng)兒童創(chuàng)造力方面，給出了諸多建議。

在此特別鳴謝！