能得見(jiàn)計(jì)算的拼圖

陳凱

“計(jì)算”一詞在不同語(yǔ)境下有不同的含義，即便是將范圍嚴(yán)格限定于“用機(jī)器進(jìn)行自動(dòng)計(jì)算”這樣狹窄的場(chǎng)景之中，其含義也是豐富多彩、變化多樣的?？紤]這樣一個(gè)簡(jiǎn)單的需求，計(jì)算第一項(xiàng)為1，且第二項(xiàng)為1的斐波那契數(shù)列第n項(xiàng)的值，如用戶輸入的是數(shù)字6，而機(jī)器給出的是對(duì)應(yīng)的第6項(xiàng)斐波那契數(shù)列的值8，顯然，機(jī)器的確進(jìn)行了計(jì)算，可要是深究其“計(jì)算”的含義，卻有如下不同。例如，機(jī)器可能只是預(yù)存了整個(gè)斐波那契數(shù)列，對(duì)于輸入的n，它實(shí)施了一個(gè)查找數(shù)據(jù)的工作?？紤]人類在做8加7得15，或做8乘以7得56的計(jì)算的時(shí)候，人的頭腦事實(shí)上所做的也是這種查找數(shù)據(jù)的工作，毫無(wú)疑問(wèn)這是一種計(jì)算，然而對(duì)于這個(gè)計(jì)算機(jī)器的使用者來(lái)說(shuō)，它是如何查找和匹配數(shù)據(jù)的，其過(guò)程是一個(gè)黑盒，是不可見(jiàn)的。又如，機(jī)器可能是根據(jù)斐波那契數(shù)列的通項(xiàng)公式來(lái)進(jìn)行計(jì)算的，而通項(xiàng)公式的由來(lái)，是經(jīng)由觀察、歸納、假設(shè)、證明、演繹等一系列數(shù)學(xué)工作的結(jié)果，在具體使用通項(xiàng)公式時(shí)，數(shù)學(xué)計(jì)算本身仍然是一個(gè)黑盒，使用者還是不知道，機(jī)器是如何實(shí)現(xiàn)對(duì)5開(kāi)方等一系列具體計(jì)算步驟的。再如，機(jī)器可能是通過(guò)一個(gè)循環(huán)結(jié)構(gòu)的程序來(lái)實(shí)現(xiàn)計(jì)算的，它首先計(jì)算了第一項(xiàng)和第二項(xiàng)的和，并將計(jì)算結(jié)果賦予第三項(xiàng)，然后再計(jì)算第二項(xiàng)和第三項(xiàng)的和，再將計(jì)算結(jié)果賦予第四項(xiàng)，在這個(gè)過(guò)程中，除了具體的加法計(jì)算過(guò)程是黑盒，循環(huán)結(jié)構(gòu)的實(shí)現(xiàn)本身也是一種黑盒，顯然，對(duì)于程序的編寫者來(lái)說(shuō)，他不知道循環(huán)語(yǔ)句和結(jié)構(gòu)何以能發(fā)揮作用，他只是借助這些語(yǔ)句和算法結(jié)構(gòu)發(fā)揮了作用而已。在上述所有的例子中，對(duì)于使用計(jì)算機(jī)器的人而言，“計(jì)算”要么是全部不可見(jiàn)的，要么是局部不可見(jiàn)的。

當(dāng)然，無(wú)論是為了教學(xué)，還是為了某個(gè)實(shí)際的用途，將計(jì)算機(jī)器所有的計(jì)算過(guò)程都展現(xiàn)出來(lái)，是不現(xiàn)實(shí)的，也是不必要的。例如，在用循環(huán)結(jié)構(gòu)的程序計(jì)算某個(gè)斐波那契數(shù)列項(xiàng)的時(shí)候，人們的頭腦尚能跟蹤高級(jí)語(yǔ)言環(huán)境中，每個(gè)變量或數(shù)組變量中值的變化，但若要在寄存器的級(jí)別上，跟蹤用以實(shí)現(xiàn)循環(huán)和賦值操作的每個(gè)電信號(hào)的變化，就是相當(dāng)困難的事了，更何況，求得斐波那契數(shù)列項(xiàng)的值只是一個(gè)很簡(jiǎn)單的程序。若要使得解決某個(gè)具體任務(wù)的整個(gè)計(jì)算過(guò)程清晰可見(jiàn)，不可避免要做到以下步驟：首先，需要知道編譯程序是如何將這個(gè)高級(jí)語(yǔ)言程序代碼轉(zhuǎn)化成二進(jìn)制機(jī)器語(yǔ)言的;接著，跟蹤這個(gè)二進(jìn)制機(jī)器語(yǔ)言的執(zhí)行過(guò)程，繼續(xù)往下深入，跟蹤普林斯頓結(jié)構(gòu)或其他結(jié)構(gòu)的計(jì)算機(jī)器中的各個(gè)部件是如何協(xié)調(diào)工作，執(zhí)行這些可實(shí)現(xiàn)循環(huán)功能的機(jī)器代碼的;然后在更底層，了解數(shù)字電路是如何實(shí)現(xiàn)邏輯運(yùn)算和數(shù)學(xué)運(yùn)算的……如果能將整個(gè)藍(lán)圖展現(xiàn)出來(lái)，計(jì)算便是可見(jiàn)的，但顯然，即便是將很簡(jiǎn)單的高級(jí)語(yǔ)言程序按上述過(guò)程全部展開(kāi)，其規(guī)模也龐大到讓人的頭腦無(wú)法進(jìn)行跟蹤，所以就結(jié)果而言，計(jì)算過(guò)程仍然是部分不可見(jiàn)的。

在工業(yè)設(shè)計(jì)上，人們采用的是模塊化和層層封裝的方式，來(lái)構(gòu)造具有特定功能的計(jì)算機(jī)器。但在教學(xué)上，人們面對(duì)的是盒子里套盒子層層疊疊一時(shí)無(wú)法窮盡到底層的窘境。然而，為了理解某個(gè)問(wèn)題，人的頭腦并不需要真的像機(jī)器那樣，去跟蹤所有的電信號(hào)或機(jī)械狀態(tài)的變化。因?yàn)閺闹庇^上說(shuō)，當(dāng)人們發(fā)現(xiàn)一個(gè)小型的系統(tǒng)是以某種模式進(jìn)行計(jì)算的之后，就能直觀推斷，一個(gè)以類似結(jié)構(gòu)搭建的更大型的系統(tǒng)，也應(yīng)該能以同樣的模式進(jìn)行更大規(guī)模的計(jì)算。舉例說(shuō)，計(jì)算28加7，人的思維過(guò)程是從記憶里找出8加7所對(duì)應(yīng)的15，然后低位寫5，高位進(jìn)1，很容易判斷，對(duì)于更大的數(shù)字，如280+70，采用的方法也是類似的，這其實(shí)就是一種模式的識(shí)別和匹配。人的頭腦能夠直觀地認(rèn)識(shí)到，一個(gè)較小數(shù)字的可行的計(jì)算模式，是可以套用到更大數(shù)字上的（這里暫不討論用小規(guī)模的計(jì)算系統(tǒng)實(shí)現(xiàn)普適計(jì)算的問(wèn)題，因?yàn)槟巧婕坝靡环N計(jì)算模型去模擬另一種計(jì)算模型的問(wèn)題）。要想讓學(xué)生理解計(jì)算之所以可行，就需要通過(guò)一個(gè)小型的計(jì)算系統(tǒng)的運(yùn)作過(guò)程，建立起關(guān)于“計(jì)算”的直觀概念。

因此，當(dāng)前的任務(wù)，就是找到一個(gè)可以進(jìn)行計(jì)算的小型系統(tǒng)。這個(gè)系統(tǒng)需要滿足以下特征：一、能演示自動(dòng)化的工作流程，或者稍加改造就能演示自動(dòng)化的工作流程;二、運(yùn)行過(guò)程能體現(xiàn)出計(jì)算思維的特征，如抽象化、形式化、模塊化等思想;三、運(yùn)作過(guò)程是完全可見(jiàn)的;四、能完成某個(gè)具體任務(wù)，并且，從直觀上看，它具有經(jīng)由改造后完成其他任務(wù)的潛力;五、考慮到教學(xué)資源、課時(shí)等因素，對(duì)其的講解和操作不需要依賴太多其他專業(yè)方面的知識(shí)。為了滿足以上五點(diǎn)要求，可供選擇的小型的計(jì)算系統(tǒng)范圍被大大縮小。雖然說(shuō)一個(gè)小型的電子電路系統(tǒng)基本上也能契合上述大部分要求，但以信息技術(shù)學(xué)科“過(guò)程與控制”模塊中有限的電子電路內(nèi)容看，是難以用來(lái)展現(xiàn)稍微復(fù)雜一些的具有計(jì)算思維特征的運(yùn)作過(guò)程（如迭代、遞歸等）的。圖靈機(jī)雖然極為符合以上一到四點(diǎn)的要求，但若要讓學(xué)生們對(duì)其工作過(guò)程真正理解，需要耗費(fèi)較多時(shí)間進(jìn)行講解和操作訓(xùn)練。

這就促使筆者設(shè)計(jì)出一種拼圖游戲來(lái)充當(dāng)這樣一個(gè)小型的計(jì)算系統(tǒng)。游戲有很多種變化形式，下面是一個(gè)可計(jì)算斐波那契數(shù)列項(xiàng)的拼圖游戲，拼圖是一些不同長(zhǎng)度的條狀紙片，紙片上分出格子并按自然數(shù)順序標(biāo)上數(shù)字。每個(gè)拼圖就好像太空站一樣，在最大數(shù)字的格子的下方兩個(gè)格子上各留出了兩個(gè)對(duì)接接口，用于拼接那些最大數(shù)字和格子號(hào)碼相同的拼圖。拼圖的最大數(shù)字是n，則接口的位置在n-1和n-2處。例如，對(duì)有6個(gè)格子的拼圖，接口位置在5號(hào)格子和4號(hào)格子的位置，5號(hào)格子可以拼5個(gè)格子的拼圖，4號(hào)格子可以拼4個(gè)格子的拼圖。如果按這樣的模式匹配，則計(jì)算過(guò)程一直能進(jìn)行下去，直到所有的“空間艙”都無(wú)法滿足繼續(xù)拼接的要求，也就是說(shuō)，不再能找到可匹配的模式，計(jì)算過(guò)程自然而然就停止了。顯然，拼接工作終止于最大數(shù)字是2或者1的拼圖。圖1顯示了拼圖的第一步，圖2顯示了完成后的整個(gè)拼圖。

當(dāng)每次使用到最大數(shù)字是2或是1的拼圖時(shí)，可以用作標(biāo)記的方法計(jì)數(shù)一次，可以看到，如果最初使用的拼圖的最大數(shù)字是6，則整個(gè)拼圖完成后，計(jì)數(shù)值是8。這其實(shí)就是計(jì)算了第6項(xiàng)的斐波那契數(shù)列的值為8。整個(gè)過(guò)程對(duì)應(yīng)用遞歸的方法來(lái)計(jì)算斐波那契數(shù)列的過(guò)程：為了計(jì)算第n項(xiàng)的斐波那契數(shù)列的值，則需要先計(jì)算第n-1項(xiàng)和第n-2項(xiàng)的斐波那契數(shù)列的值，此過(guò)程一直持續(xù)下去直到遇見(jiàn)第二項(xiàng)和第一項(xiàng)的斐波那契數(shù)列的值為1?？梢钥闯觯磮D游戲能體現(xiàn)出解決具體問(wèn)題中計(jì)算思維的特征，整個(gè)運(yùn)作過(guò)程是完全可見(jiàn)的，拼接過(guò)程中并不涉及其他專業(yè)知識(shí)。雖然說(shuō)拼圖過(guò)程并不是全自動(dòng)化進(jìn)行的，但一旦規(guī)則設(shè)定好，即便是手工操作，其結(jié)果也是必然的。這里可以鼓勵(lì)學(xué)生對(duì)拼圖進(jìn)行改進(jìn)，如留出特定寬度的拼接凹凸接口，這樣，即便不對(duì)照數(shù)字的大小，也能將拼接過(guò)程進(jìn)行下去。

拼圖游戲的一個(gè)很重要的優(yōu)勢(shì)是，拼接規(guī)則是可以方便地進(jìn)行擴(kuò)充和改造的。不妨思考這樣的問(wèn)題，如果設(shè)計(jì)一臺(tái)計(jì)算機(jī)器，那么它將如何自動(dòng)完成圖形的拼接，并由此實(shí)現(xiàn)斐波那契數(shù)列項(xiàng)的計(jì)算？關(guān)于自動(dòng)機(jī)器實(shí)現(xiàn)拼接過(guò)程中可能遇到的麻煩，以及如何使得自動(dòng)拼接成為可能，可以開(kāi)展一次頭腦風(fēng)暴活動(dòng)。關(guān)于機(jī)器實(shí)現(xiàn)自動(dòng)拼接中的困難，這里試舉一項(xiàng)：計(jì)算機(jī)中比較容易實(shí)現(xiàn)的數(shù)據(jù)存儲(chǔ)方式，是一系列前后相鄰的存儲(chǔ)單元，于是就產(chǎn)生出問(wèn)題，即二維空間上的拼圖，如何轉(zhuǎn)化為一維的數(shù)據(jù)存儲(chǔ)方式。

顯然，在一維的數(shù)據(jù)存儲(chǔ)空間中，拼接過(guò)程要通過(guò)符號(hào)模擬來(lái)達(dá)成。具體方案很多，如用“#”代表拼圖，“*”代表等待拼接，“^”代表拼接完成，一種可能的操作規(guī)則和操作過(guò)程如下表所示。

下表表示了6個(gè)格子的拼圖拼接上5個(gè)格子和4個(gè)格子的拼圖的過(guò)程，每次拼接完成后，“*”變?yōu)椤癪”符號(hào)，表示處理完成。整個(gè)拼接過(guò)程中，總是按遇見(jiàn)n個(gè)格子則在最后拼接n-1個(gè)格子和n-2個(gè)格子的規(guī)則進(jìn)行，如果遇見(jiàn)的是2個(gè)格子和1個(gè)格子的拼圖，則只是簡(jiǎn)單拼接上和自己相同數(shù)量的格子的拼圖（為了簡(jiǎn)化問(wèn)題，這個(gè)匹配過(guò)程沒(méi)有考慮停機(jī)問(wèn)題，可以引入新的符號(hào)來(lái)實(shí)現(xiàn)停機(jī)的匹配規(guī)則），整個(gè)變化過(guò)程用字符串描述如圖3所示。

第9步之后，拼圖中“*”的數(shù)量不會(huì)再發(fā)生變化，而“*”的個(gè)數(shù)則對(duì)應(yīng)著相應(yīng)第6項(xiàng)斐波那契數(shù)列的值。并且，還能有辦法看出不同拼圖之間的關(guān)系：第1塊拼圖拼接的是第2和第3塊，第2塊拼接的是第4和第5塊，第3塊拼接的是第6和第7塊，以此類推。當(dāng)然，這樣的表示方法很不直觀，如果以樹的形狀將拼圖之間的關(guān)系呈現(xiàn)出來(lái)，則要清晰得多，圖4是第4步拼接操作完成時(shí)所顯示出的拼圖之間的關(guān)系。于是這里又引出了新的問(wèn)題，如何能更合理地借助一維的存儲(chǔ)空間，使得機(jī)器能方便地識(shí)別出拼圖之間的關(guān)系，同時(shí)，也能讓人更容易將存儲(chǔ)空間里的數(shù)據(jù)轉(zhuǎn)換成人更能理解的圖示？這就很自然地從如何實(shí)現(xiàn)自動(dòng)計(jì)算的問(wèn)題，指向了數(shù)據(jù)結(jié)構(gòu)的研究。

至此我們可以看出，借助拼圖游戲，不僅使得計(jì)算的過(guò)程變成可見(jiàn)的，而且也使得自動(dòng)計(jì)算中，解決問(wèn)題的思維方式成為可見(jiàn)的。關(guān)于如何使計(jì)算過(guò)程可見(jiàn)，進(jìn)而如何使計(jì)算思維可見(jiàn)，方法必然有很多種，本文權(quán)當(dāng)拋轉(zhuǎn)引玉，希望能激發(fā)出大家的思考欲望。