從規(guī)則的實(shí)體化看計(jì)算思維

陳凱

有一種數(shù)列叫做三角形數(shù)列，數(shù)列由三角形數(shù)組成，它們是1、3、6、10、15、21、28……關(guān)于三角形數(shù)之名的來(lái)歷，看圖1便可知曉。很顯然，第n項(xiàng)三角形數(shù)即是前n項(xiàng)自然數(shù)之和。對(duì)于大部分人來(lái)說(shuō)，通過(guò)在頭腦中想象一個(gè)三角形點(diǎn)陣的構(gòu)建過(guò)程來(lái)計(jì)算前n項(xiàng)自然數(shù)之和，還是比較容易的。那么，如何讓某個(gè)自動(dòng)裝置也能夠計(jì)算出第n項(xiàng)三角形數(shù)，或者說(shuō)計(jì)算出前n項(xiàng)自然數(shù)的數(shù)列和？上一期本欄目的《從數(shù)據(jù)的空間結(jié)構(gòu)看計(jì)算思維——以數(shù)列求和為例》這篇文章中提到，為了培養(yǎng)計(jì)算思維，需要讓學(xué)生體驗(yàn)到，在自動(dòng)計(jì)算的任務(wù)實(shí)現(xiàn)的過(guò)程中，既要考慮人的需求，同時(shí)也要從機(jī)器運(yùn)作的可能性、可行性和效率方面來(lái)考慮構(gòu)建一個(gè)自動(dòng)計(jì)算模型的問(wèn)題。為了達(dá)成此目標(biāo)，方法可能有多種，本文設(shè)計(jì)方案將體驗(yàn)過(guò)程展開(kāi)為兩步：第一步是針對(duì)計(jì)算任務(wù)的目標(biāo)創(chuàng)設(shè)出一種自動(dòng)變換規(guī)則，然后將變換過(guò)程實(shí)體化;第二步是將變換規(guī)則本身也實(shí)體化。

● 第一步：創(chuàng)設(shè)自動(dòng)變換規(guī)則，并將變換過(guò)程實(shí)體化

如果要設(shè)計(jì)一個(gè)生成三角形數(shù)的裝置，那么它的基本結(jié)構(gòu)如圖2所示。

應(yīng)該如何設(shè)定變換規(guī)則？傳統(tǒng)的數(shù)學(xué)方法很簡(jiǎn)單，如從1、2、3開(kāi)始累加，直到判斷加到n時(shí)停止;又如為求得n項(xiàng)三角形數(shù)，則先遞歸求n-1項(xiàng)三角形數(shù);再如直接應(yīng)用n（n+1）/2的通項(xiàng)公式。但對(duì)于一個(gè)簡(jiǎn)單的自動(dòng)變換裝置來(lái)說(shuō)，這些方法中的數(shù)字符號(hào)本身的變換和處理是非常困難的，為了更容易將變換過(guò)程實(shí)體化，可以暫時(shí)先避免使用數(shù)字符號(hào)，而用某種實(shí)體的數(shù)量來(lái)代表某個(gè)數(shù)。

例如，在畫圖軟件里玩圖形變換，即便是簡(jiǎn)單的畫圖軟件，也可以是培養(yǎng)計(jì)算思維的好工具，張勤堅(jiān)老師在《教學(xué)設(shè)計(jì)：畫圖里的計(jì)算思維》一文中提到，通過(guò)復(fù)制、翻轉(zhuǎn)和拼接，就可以實(shí)施有思維含量的實(shí)踐操作，筆者深以為然。如何設(shè)定畫圖規(guī)則用以實(shí)現(xiàn)三角形數(shù)的計(jì)算呢？能簡(jiǎn)單想到的方法如：第一行畫n個(gè)點(diǎn)，第二行畫n-1個(gè)點(diǎn)，第三行畫n-2個(gè)點(diǎn)……每新加一層就少畫一個(gè)點(diǎn)，等到不再有點(diǎn)可畫時(shí)，則數(shù)一下所有點(diǎn)的數(shù)量。這樣，就將第n項(xiàng)三角形數(shù)的生成過(guò)程同構(gòu)為圖形變換的過(guò)程。這里給出一個(gè)有趣的謎題，如何在畫圖軟件中，在不觀看屏幕的情況下，只用鍵盤操作來(lái)實(shí)現(xiàn)n，n-1，n-2……個(gè)點(diǎn)累加的效果，也就是說(shuō)，通過(guò)某種機(jī)械化重復(fù)鍵盤操作動(dòng)作的方式，實(shí)現(xiàn)如下頁(yè)圖3所示的圖形變換。

雖然說(shuō)圖形變換操作是在畫圖軟件中進(jìn)行的，但換成實(shí)物來(lái)代替那些點(diǎn)，效果是類似的（如摞瓶子）。然而，這些規(guī)則還是需要依靠人來(lái)執(zhí)行的，大家不妨先行思考一下，如何設(shè)定規(guī)則，讓一個(gè)簡(jiǎn)單的裝置自動(dòng)實(shí)現(xiàn)圖形變換操作？

這里再舉一個(gè)用類似于用跳棋游戲的方法實(shí)現(xiàn)三角形數(shù)計(jì)算的例子，假設(shè)要計(jì)算的是第4項(xiàng)三角形數(shù)，則可以在初始時(shí)放置一排4個(gè)“*”號(hào)棋。從最左面的棋子開(kāi)始，“*”號(hào)棋可以用它右面的棋子當(dāng)跳板跳到整排棋子的末尾，如果它右面的棋子也是“*”號(hào)棋，則當(dāng)它跳躍到末尾時(shí)變?yōu)椤?”號(hào)棋，如果它右面是“#”號(hào)棋，則它跳躍到末尾時(shí)自動(dòng)消失。當(dāng)這一排棋子最左面是“#”號(hào)棋時(shí)，它的跳躍規(guī)則和“*”號(hào)棋類似，它可以用右面的棋子當(dāng)跳板跳到末尾，如果它右面的棋子也是“#”號(hào)棋，則當(dāng)它跳躍到末尾時(shí)變?yōu)椤?”號(hào)棋，如果它右面是“*”號(hào)棋，則它跳躍到末尾時(shí)自動(dòng)消失。棋子具體跳躍的過(guò)程演示如圖4所示，演示中用點(diǎn)來(lái)代表跳躍后空出的位置：

當(dāng)無(wú)法再找到可跳躍的棋子時(shí)，最后一個(gè)棋子處在第10個(gè)字符的位置，這就對(duì)應(yīng)了第4項(xiàng)的三角形數(shù)是10。

用這兩種形狀的跳棋，按預(yù)設(shè)規(guī)則跳躍和落子，就可以計(jì)算出第n項(xiàng)三角形數(shù)。不過(guò)，與剛才的分層畫點(diǎn)的方法同樣存的問(wèn)題是：棋子跳躍和落子的規(guī)則是由人的頭腦來(lái)監(jiān)督的，能否制作出一個(gè)裝置，讓這個(gè)跳棋裝置按規(guī)則自動(dòng)運(yùn)行起來(lái)？

● 第二步：將變換規(guī)則也實(shí)體化

為了制作出一個(gè)自動(dòng)實(shí)現(xiàn)變換的裝置，不僅要考慮變換對(duì)象和過(guò)程的實(shí)體化，還要考慮變換規(guī)則本身的實(shí)體化。

對(duì)于分層畫點(diǎn)的方案，存在這樣的問(wèn)題：怎樣自動(dòng)實(shí)現(xiàn)后一層畫的點(diǎn)比前一層畫的點(diǎn)恰好少一個(gè)？下面給出一種思路：設(shè)計(jì)出一種拼插板，每個(gè)拼插板均是數(shù)字1，規(guī)定必須將拼插板左右兩端同時(shí)插入拼插槽內(nèi)，可以想象最上面一排拼插板是懸掛在空中的，新一層的拼插板如果只有一端插入拼插槽，仍然會(huì)因?yàn)橹亓ψ饔玫袈洹０创艘?guī)則拼接就能解決剛才的問(wèn)題（如圖5）。例如，為了計(jì)算第3項(xiàng)三角形數(shù)，可以排列好三個(gè)拼插板，然后陸續(xù)將其他拼插板插入拼插槽內(nèi)，最后拼接過(guò)程會(huì)自動(dòng)停止（想象一下，雖然用于執(zhí)行自動(dòng)拼接任務(wù)的裝置始終在運(yùn)轉(zhuǎn)，但拼接的圖案卻不會(huì)再發(fā)生變化），用到的拼插板的數(shù)量就是第3項(xiàng)三角形數(shù)6。

這樣，就在一定程度上將頭腦中的拼圖規(guī)則實(shí)體化了，可以讓學(xué)習(xí)者認(rèn)識(shí)到，非實(shí)體化的規(guī)則是依賴于語(yǔ)言的，是靠人腦的規(guī)定而使得圖形產(chǎn)生變化，就好像下棋的雙方都必須遵守該種棋的規(guī)則那樣。而實(shí)體化的規(guī)則依賴于某種具體的結(jié)構(gòu)，圖形的變換方式是在結(jié)構(gòu)上被限定的。關(guān)于實(shí)體化，計(jì)算機(jī)科學(xué)中考慮的重點(diǎn)與通用技術(shù)學(xué)科中考慮的重點(diǎn)不同，在通用技術(shù)學(xué)科中，是考慮如何將設(shè)計(jì)圖樣轉(zhuǎn)換為實(shí)體，在計(jì)算機(jī)科學(xué)中，是考慮如何用實(shí)體的變換來(lái)同構(gòu)狀態(tài)的變換過(guò)程。但這個(gè)方法的實(shí)體化還很不徹底，“必須將拼插板左右兩端同時(shí)插入拼插槽內(nèi)”這一步還是需要人來(lái)實(shí)施。對(duì)比上面的拼插板，一個(gè)更傳統(tǒng)的實(shí)體化的規(guī)則轉(zhuǎn)換系統(tǒng)可能是這樣實(shí)現(xiàn)的：首先，用一個(gè)樹狀結(jié)構(gòu)來(lái)對(duì)應(yīng)先前的拼圖，樹的節(jié)點(diǎn)處是可以存儲(chǔ)狀態(tài)的，在第一行，按希望計(jì)算的項(xiàng)數(shù)連續(xù)畫點(diǎn)，在后續(xù)行中，只有當(dāng)左前方并且右前方的節(jié)點(diǎn)的狀態(tài)是點(diǎn)時(shí)，前節(jié)點(diǎn)的狀態(tài)才是點(diǎn)，否則就是空，如上頁(yè)圖6所示。這個(gè)變換規(guī)則比先前的“每新加一層就少畫一個(gè)點(diǎn)”更明確，它解釋了“少畫一個(gè)點(diǎn)”在結(jié)構(gòu)上到底是如何做到的。

接下來(lái)的任務(wù)，是將“只有當(dāng)左前方并且右前方是點(diǎn)時(shí)，則當(dāng)前格子里才是點(diǎn)”這一規(guī)則進(jìn)一步還原為更實(shí)體的形式，那就是邏輯門之間的連接結(jié)構(gòu)，圖7所示是一個(gè)可用于計(jì)算第n項(xiàng)三角形數(shù)的數(shù)字邏輯原理圖，它仿佛是橫過(guò)來(lái)擺放的樹，其基本原理是依靠用與門獲得鄰近兩個(gè)存儲(chǔ)單元的數(shù)據(jù)并實(shí)現(xiàn)邏輯運(yùn)算的工作，這個(gè)可以互動(dòng)的原理圖是在DigitalJS在線軟件中借助Verilog語(yǔ)言制作的，圖示展現(xiàn)的是計(jì)算第3項(xiàng)三角形數(shù)為6的情況。這個(gè)裝置實(shí)現(xiàn)了規(guī)則的“相對(duì)”實(shí)體化。為什么說(shuō)“相對(duì)”呢？所謂的實(shí)體常常是相對(duì)于某個(gè)更實(shí)體的襯底而顯現(xiàn)出來(lái)的，而這個(gè)更實(shí)體的襯底，本身很可能也只是相對(duì)于其他襯底而相對(duì)顯現(xiàn)為實(shí)體，通常來(lái)說(shuō)，只有最底層的電路和機(jī)械裝置才能算是絕對(duì)的物質(zhì)實(shí)體。關(guān)于實(shí)體和襯底的關(guān)系，大家可以參考侯世達(dá)的《哥德?tīng)柊釥柊秃眨杭愯抵蟪伞芬粫抻谄@里不再展開(kāi)。如果要將數(shù)字邏輯結(jié)構(gòu)的層次進(jìn)一步還原為更實(shí)體的裝置，就要將邏輯門展開(kāi)為場(chǎng)效應(yīng)管或晶體管電路了。

看完分層畫點(diǎn)的例子，再來(lái)看跳棋的例子，顯然，跳棋規(guī)則的實(shí)體化看上去更加困難，因?yàn)槠遄硬粌H要跳過(guò)若干個(gè)未知數(shù)量的其他棋子，還要根據(jù)當(dāng)作跳板的棋子的狀態(tài)來(lái)決定自己跳躍后落子時(shí)的狀態(tài)。這看上去很難仿照分層畫點(diǎn)的例子直接用邏輯原理圖來(lái)完成。所以需要引入一個(gè)相對(duì)實(shí)體化的中間裝置，來(lái)實(shí)現(xiàn)棋子的跳動(dòng)。這里給出一種方案：設(shè)定某個(gè)檢測(cè)、匹配和替換裝置，它可以將檢測(cè)到的以某種模式鄰近的兩種棋子替換成另外一些棋子。實(shí)現(xiàn)整個(gè)自動(dòng)化跳棋裝置的規(guī)則設(shè)定相當(dāng)復(fù)雜，限于篇幅這里只給出局部的規(guī)則示例，圖8中所列的規(guī)則，就可以實(shí)現(xiàn)部分跳躍動(dòng)作。

為了實(shí)現(xiàn)自動(dòng)跳棋裝置，需要引入一些輔助的棋子，分別用“a”“b”“c”“d”“.”“_”等符號(hào)代表?！癮*-->.b”的意思是，把“a*”棋子替換成“.b”棋子。單獨(dú)看這個(gè)替換規(guī)則，是難以發(fā)現(xiàn)其中的意義的，但這些規(guī)則組合起來(lái)使用，就能產(chǎn)生出類似程序變量賦值和分支語(yǔ)句判斷的效果（必須試一下才能體會(huì)到）。

接下來(lái)，還要思考這個(gè)裝置可能是怎樣制造出來(lái)的：假設(shè)有i1和i2兩個(gè)檢測(cè)器，當(dāng)i1檢測(cè)器檢測(cè)到“a”，并且i2檢測(cè)器檢測(cè)到“b”時(shí)，則把檢測(cè)到的棋子替換成“.b”，在所有匹配和替換操作完成后，檢測(cè)器右移到新的位置重復(fù)剛才的操作。可以發(fā)現(xiàn)，這里用到了與的邏輯運(yùn)算。

假設(shè)初始時(shí)，棋子按“a****_”的方式擺放，那么只要反復(fù)地按以上匹配替換序列操作，棋子的狀態(tài)就會(huì)成為“.....###_.”。

可見(jiàn)，這個(gè)自動(dòng)裝置完成了兩項(xiàng)任務(wù)，一是“*”號(hào)跳棋在跳過(guò)“*”號(hào)跳棋后變成了“#”號(hào)跳棋，二是“*”號(hào)跳棋在跳過(guò)“#”號(hào)跳棋后消失。按類似的思路，將替換規(guī)則加以擴(kuò)展，就可以實(shí)現(xiàn)完整的自動(dòng)跳棋了。為了測(cè)試方便，可使用帶宏功能的文字編輯器，如WPS、Notepad++等來(lái)進(jìn)行實(shí)驗(yàn)。當(dāng)然，這個(gè)自動(dòng)匹配替換規(guī)則的裝置并非最底層的實(shí)體裝置，可以使用存儲(chǔ)器和邏輯門使其進(jìn)一步實(shí)體化。在借助跳棋游戲來(lái)實(shí)現(xiàn)計(jì)算三角形數(shù)或自然數(shù)數(shù)列和的過(guò)程中，展現(xiàn)出一個(gè)相互依賴的層次系統(tǒng)，如圖9所示。

從計(jì)算思維培養(yǎng)的目標(biāo)看，是希望學(xué)習(xí)者能夠認(rèn)識(shí)到變換規(guī)則實(shí)體化過(guò)程中層次的存在，并從中領(lǐng)會(huì)到當(dāng)前實(shí)現(xiàn)某種計(jì)算的變換規(guī)則系統(tǒng)，是如何依賴更底層的某個(gè)系統(tǒng)的變換規(guī)則來(lái)實(shí)現(xiàn)的。最后需要說(shuō)明的是，雖然借助變換規(guī)則的實(shí)體化，可以實(shí)現(xiàn)并體驗(yàn)?zāi)硞€(gè)特定的計(jì)算任務(wù)進(jìn)行的過(guò)程，但如果目標(biāo)不是為了實(shí)現(xiàn)某特定的計(jì)算任務(wù)，而是要?jiǎng)?chuàng)造出一個(gè)具有通用計(jì)算能力的裝置，必然需要設(shè)計(jì)一個(gè)特殊的實(shí)體化的裝置，這個(gè)裝置擁有能將各種實(shí)現(xiàn)特定計(jì)算任務(wù)的實(shí)體化裝置同構(gòu)為一個(gè)虛擬裝置的能力，顯然，對(duì)這個(gè)問(wèn)題的理解還依賴更高階、更綜合的思維。