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

☆  培養(yǎng)計算機科學素養(yǎng)。

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

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

☆ 健康好吃的糖果

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

☆ 白板&白板筆

120分鐘

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

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

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

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

因為課程運用了一定的數(shù)學知識，有一定難度，為了避免枯燥，課程設(shè)計要注重強化趣味性。

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

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

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

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

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

☆ 英文字母表

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

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

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

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

這個孩子會有機會獲得更多的糖果，所以選擇過程一定要嚴格、公平，不然一定會有孩子不滿意。

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

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

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

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

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

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

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

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

開始前，我必須先把今天的主題引出來，要讓孩子明白我們在干什么。

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

齊刷刷的舉手。

“老師我拿我爸手機用過百度！”

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

“老師我用過美團外賣！”

果然是移動互聯(lián)網(wǎng)原住民啊，我像他們這么大的時候連計算器都沒見過。

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

我曾遇到過孩子甚至以為，電腦里就真的有一個個圖標，一個個窗口。

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

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

小朋友們馬上張大了嘴巴，一腦袋問號……是哎，好像從來沒想過這個問題啊！是怎么找到的呢？

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

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

當我們在大量的數(shù)據(jù)中搜索的時候，我們要用到一些巧妙的的計算方法，來加速搜索的過程，這就是“搜索算法”。

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

“她蒙的！”

“她一個一個問的！”

“那么一個一個問是不是一種算法呢？”

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

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

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

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

有了剛才的熱身活動，孩子們馬上明白，這些無序的數(shù)字，沒有什么好想的，一個一個猜，看誰運氣好。

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

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

可能的最大分數(shù)和最小分數(shù)分別是多少？26 和 1。

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

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

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

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

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

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

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

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

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

如果沒有學過，幾乎不會有孩子能想到要取中間值不斷逼近。

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

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

二分法的神奇之處在于，即使數(shù)據(jù)量翻了一倍，我們也只要多加一次查詢。當數(shù)據(jù)量不斷翻倍的時候，二分法的魔力就凸顯的更明顯。這里，還可以給孩子講一講“陰險的老爺爺讓不懂數(shù)學的國王往國際象棋盤里放米?！钡墓适?，孩子們會驚訝于指數(shù)增長的神奇力量，反過來想一想，就明白了二分法的強大威力。

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

游戲再次升級！

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

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

其實孩子觀察不出來，還是宣布好了。?? 

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

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

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

開始玩吧！

這次進行的非?？?，很快都得出了結(jié)果。

大家用了幾次擊中了敵艦？最少一次，最多四次。為什么是四次？因為一列里最多只有4艘船。

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

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

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

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

下課！

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

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

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

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

目前Project X第一期已經(jīng)開課，未來可能會有其他課程，請您關(guān)注TULLL的公眾號。

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

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

在此特別鳴謝！