交互式計(jì)算機(jī)算法學(xué)習(xí)平臺設(shè)計(jì)

夏征華，胡保坤，刁灣灣，黃玉錢

(杭州師范大學(xué)信息科學(xué)與技術(shù)學(xué)院，浙江 杭州 311121)

信息科技教育是素質(zhì)教育的重要組成部分.算法編程教育可優(yōu)化青少年邏輯思維模式，掌握計(jì)算機(jī)算法對運(yùn)用計(jì)算機(jī)解決工程問題具有重要意義.傳統(tǒng)板書和幻燈投影授課方式的計(jì)算機(jī)算法教學(xué)很難展示算法內(nèi)部過程，缺少教育理念和學(xué)習(xí)策略的指導(dǎo)，難以將復(fù)雜抽象的算法邏輯進(jìn)行形象具體化地表現(xiàn)，基本都以外顯學(xué)習(xí)的方式來傳遞知識[1]，教學(xué)效果不是很理想[2].

目前，國內(nèi)代表性的可視化算法學(xué)習(xí)平臺有LeetCode Animation，國外可視化算法學(xué)習(xí)平臺有VisuAlgo、Data Structure Visualizations以及Algorithm Visualizer.這些平臺雖各具特色，但仍然無法滿足實(shí)際課程的需要：1)缺乏交互性.VisuAlgo與Data Structure Visualizations平臺未提供與用戶交互的功能，只是單純對算法進(jìn)行演示，算法的動態(tài)演示與算法的代碼脫節(jié).2)編程方式復(fù)雜.Algorithm Visualizer平臺允許用戶編寫代碼創(chuàng)建算法進(jìn)行演示，但采用了復(fù)雜的文本編程方式.3)編程語言選擇有局限性.LeetCode Animation、VisuAlgo以及Data Structure Visualizations平臺雖然提供了較多的算法動畫模塊，但未提供選擇編程語言的功能.Algorithm Visualizer雖然提供了選擇編程語言的功能，但只支持JavaScript語言.因此開發(fā)具有編程語言多樣性、編程方式圖形化、算法教學(xué)可視化等特點(diǎn)的交互式計(jì)算機(jī)算法學(xué)習(xí)平臺非常有必要.

本研究以算法流程為重點(diǎn)，突出算法編程的趣味與創(chuàng)意，以提供提高分析解決問題和算法編程能力的學(xué)習(xí)環(huán)境為目標(biāo)，基于Google的可視化圖形編程工具 Blockly和ngx-blockly庫，研發(fā)交互式計(jì)算機(jī)算法學(xué)習(xí)平臺.平臺主要特點(diǎn)包括可視化編程、可視化動態(tài)演示算法步驟、交互式學(xué)習(xí)計(jì)算機(jī)算法理論知識等.教師可以使用此平臺將 Blockly 圖形化、搭積木式教學(xué)融入到計(jì)算機(jī)算法課程中，通過堆疊法將繁瑣的知識點(diǎn)圖形化，降低算法學(xué)習(xí)難度[3]，幫助學(xué)生盡快掌握計(jì)算機(jī)算法的相關(guān)知識.

1 學(xué)習(xí)平臺的設(shè)計(jì)

1.1 系統(tǒng)架構(gòu)

本學(xué)習(xí)平臺采用云架構(gòu)，不僅為用戶提供良好的交互體驗(yàn)，還因其良好的前后端工作分離模式而降低系統(tǒng)開發(fā)的難度，提高系統(tǒng)的可擴(kuò)展性，平臺的系統(tǒng)架構(gòu)如圖1所示.本學(xué)習(xí)平臺基于Blockly和ngx-blockly庫進(jìn)行了二次開發(fā)，在邏輯層面上完成了變量類型定義和模塊的生成功能.針對交互式學(xué)習(xí)[4]計(jì)算機(jī)算法的需要，平臺提供了如圖1所示的一系列重要功能，以促進(jìn)學(xué)生在學(xué)習(xí)過程中將理論知識與實(shí)踐結(jié)合.另外，通過阿里云與系統(tǒng)的交互，實(shí)現(xiàn)整個平臺的平穩(wěn)運(yùn)行.本平臺的主界面如圖2所示.

圖1 系統(tǒng)架構(gòu)Fig.1 System architecture

圖2 平臺主界面Fig.2 Main interface of the platform

1.2 平臺的主要功能

本學(xué)習(xí)平臺的主要功能：1)可視化編程.在可視化編程教學(xué)中，教師通過拖動代碼塊，以一種搭積木的方式，從打地基開始，逐漸建成高樓大廈.學(xué)生可以充分理解每個代碼在程序中的作用.搭建成功的積木塊及其所屬的代碼塊如圖3、圖4所示.2)算法可視化.對算法進(jìn)行動畫演示，能把抽象的計(jì)算機(jī)算法知識具體化、形象化，促進(jìn)學(xué)生對計(jì)算機(jī)算法知識的吸收理解.3)代碼云編譯.在可視化編程的基礎(chǔ)上提供在線云編譯功能，在教學(xué)中不需要在拖動代碼塊搭建完畢一個程序后，再復(fù)制生成代碼至IDE上進(jìn)行編譯.集成化的設(shè)計(jì)能夠充分提高學(xué)習(xí)效率.4)編程語言多樣.本平臺實(shí)現(xiàn)將多種編程語言集成，學(xué)生可以選擇不同的語言模塊進(jìn)行算法學(xué)習(xí)，可以通過云編譯功能獲取運(yùn)行結(jié)果，實(shí)現(xiàn)對知識的理解.5)云端服務(wù).每個用戶使用注冊的賬號登錄平臺后，都可獲取上傳云端的權(quán)限，可以將搭建好的積木塊上傳至云端.當(dāng)用戶需要的時候，可以隨時隨地從云端下載自己備份的代碼塊，接續(xù)上一次未完成的項(xiàng)目.功能頁面如圖5所示.

圖5 云端服務(wù)Fig.5 Data cloud service

2 平臺的主要特色

2.1 可視化編程呈現(xiàn)

2.2 數(shù)據(jù)云服務(wù)

Blockly框架是基于Web瀏覽器開箱即用的，其積木塊控件及其代碼等數(shù)據(jù)都是保存在內(nèi)存中，關(guān)閉瀏覽器后，所有數(shù)據(jù)都會消失.為實(shí)現(xiàn)用戶斷點(diǎn)使用，本平臺開發(fā)云服務(wù)功能，包括云端的上傳與下載，具體如下：

積木塊在Blockly中以XML格式進(jìn)行渲染.本研究使用Blcokly提供的操作DOM元素的Blockly.Xml.workspaceToDom()和Blockly.Xml.domToText()兩個方法將界面上的積木塊轉(zhuǎn)為文本格式，在用戶獲得讀寫云服務(wù)權(quán)限的Token后，云服務(wù)器將其上傳至云端保存.當(dāng)用戶搭建完成一個功能模塊后，點(diǎn)擊保存按鈕時會有彈窗出現(xiàn)，輸入保存的文件名并確認(rèn)后，積木塊上傳至阿里云服務(wù)器.

當(dāng)用戶點(diǎn)擊云端下載按鈕后，進(jìn)入下載界面，頁面顯示保存的所有存檔.用戶可根據(jù)需要來選擇載入.在載入云端保存的內(nèi)容時，后端通過用戶選擇的某一存檔，獲取到存放此存檔的URL地址并進(jìn)行訪問.在此期間，通過axios請求的頭部攜帶用戶獲得的唯一Token獲得訪問權(quán)限.在訪問到云端地址并且讀取到云端文本內(nèi)容后，根據(jù)ngx-blockly庫的邏輯特性(積木塊以XML格式)構(gòu)建、存儲以及存放在云端內(nèi)容格式的特性(TXT文本格式).為使文本內(nèi)容轉(zhuǎn)化為XML格式，本研究調(diào)用Blockly.Xml.domToWorkSpace() 和Blockly.Xml.textToDom()兩個格式轉(zhuǎn)換方法實(shí)現(xiàn)對界面的渲染.

2.3 在線云編譯

本研究使用GitHub開源框架Remote Code Runner實(shí)現(xiàn)云編譯功能.Remote Code Runner是一個遠(yuǎn)程代碼執(zhí)行服務(wù)，可以讓用戶在網(wǎng)頁在線編寫C、Python等代碼.當(dāng)用戶點(diǎn)擊運(yùn)行按鈕后，把代碼發(fā)送到遠(yuǎn)程服務(wù)器執(zhí)行，再返回執(zhí)行結(jié)果，然后渲染界面.在線云編譯運(yùn)行結(jié)果如圖6、圖7所示，顯示了順序查找的運(yùn)行結(jié)果.

3 平臺的創(chuàng)新點(diǎn)及其實(shí)現(xiàn)

3.1 C語言模塊的實(shí)現(xiàn)

JavaScript、Python等編程語言都不具有數(shù)據(jù)類型[5].編程語言的類型系統(tǒng)具有錯誤檢查、程序驗(yàn)證、文檔化、提高程序效率等作用，對于初學(xué)者非常重要.同時，本平臺加入了C語言模塊.

本研究以ngx-blockly庫的源碼為基礎(chǔ)，借鑒Protzenko[6]和Pasternak等[7]提出的Blcokly生成其他語言的思路，使用Typescript建立起對C語言模塊中每個積木塊以及其所對應(yīng)的代碼塊定義的服務(wù).以類型系統(tǒng)的實(shí)現(xiàn)為例，本研究使用ngx-blockly庫提供的block.jsonInit({‘對象元素’})方法，在系統(tǒng)平臺對象元素中，增加type為field_dropdown的下拉列表，以實(shí)現(xiàn)對數(shù)據(jù)類型的表示：

{"type":"field_dropdown","name":"dropdown",

"options": [["integer","int"],["float","float"],...]},

第六，鼓勵國有資本入股非國有企業(yè)。在公共服務(wù)、高新技術(shù)、生態(tài)環(huán)境保護(hù)和戰(zhàn)略性產(chǎn)業(yè)等重點(diǎn)領(lǐng)域，以市場選擇為前提，鼓勵具有資本運(yùn)作經(jīng)驗(yàn)的國有企業(yè)、國有資本投資公司對發(fā)展?jié)摿Υ?、成長性強(qiáng)的非國有企業(yè)進(jìn)行股權(quán)投資。鼓勵國有企業(yè)按照產(chǎn)業(yè)鏈、價值鏈要求，通過投資入股、聯(lián)合投資、重組等多種方式，與業(yè)務(wù)相同或關(guān)聯(lián)度高的非國有企業(yè)進(jìn)行股權(quán)融合、戰(zhàn)略合作、資源整合。

此外，還需產(chǎn)生模塊對應(yīng)的代碼塊，其功能的實(shí)現(xiàn)依賴block.getFieldValue(’dropdown’)方法：

let type=block.getFieldValue(’dropdown’);

return code=type;

經(jīng)過上述開發(fā)，本學(xué)習(xí)平臺實(shí)現(xiàn)了C語言模塊.

3.2 算法執(zhí)行過程動畫演示

在學(xué)習(xí)算法過程中觀看算法的動畫演示，交互式學(xué)習(xí)算法的原理能提高學(xué)習(xí)效果.本學(xué)習(xí)平臺提供選擇算法、排序算法、圖算法、二叉樹算法等常用算法的動畫演示功能，此功能包含算法步驟動畫演示以及算法運(yùn)行時各步結(jié)果的動態(tài)顯示.算法步驟動畫演示示例如圖8、圖9所示.以C語言模塊的冒泡排序動畫演示為例，可視化演示算法的操作流程為：用戶拖動封裝好的積木塊至工作區(qū)后，點(diǎn)擊運(yùn)行按鈕.后臺把積木塊所對應(yīng)的代碼塊以及當(dāng)前所使用的語言以API請求的方式，發(fā)送到云編譯服務(wù)器.服務(wù)器在判斷語言類型后，進(jìn)行代碼執(zhí)行，然后把執(zhí)行結(jié)果返回.后臺在接收到結(jié)果后，進(jìn)行遍歷渲染動畫.每條方柱的藍(lán)色填充高度代表當(dāng)前數(shù)值的大小.排序過程中，每次循環(huán)的結(jié)果都會渲染一次動畫，方柱的位置和高度也會與每次變化的結(jié)果一樣，以一種動態(tài)的、可視化的方式演示算法的執(zhí)行步驟.

圖8 冒泡排序算法動畫示例 Fig.8 Example of bubble sorting algorithm animation

圖9 深度優(yōu)先搜索動畫演示Fig.9 Animation demonstration of depth first search

實(shí)現(xiàn)算法動畫演示的難點(diǎn)在于如何把C語言代碼云編譯后的結(jié)果轉(zhuǎn)換為Typescript代碼，并使其可以在頁面進(jìn)行渲染.對此，本研究使用了如下的解決方案:

1)使用數(shù)據(jù)的單向綁定來解決C代碼云編譯結(jié)果轉(zhuǎn)換為Typescript代碼的難點(diǎn).以排序算法為例，每個排序算法模塊都設(shè)計(jì)有兩個對應(yīng)的代碼塊，這兩個代碼塊進(jìn)行單向數(shù)據(jù)綁定.一個代碼塊面向用戶顯示，另一個則增加一個遍歷循環(huán)方法，以此來輸出算法在運(yùn)行過程中每一次排序產(chǎn)生的結(jié)果，此代碼不對外顯示.C代碼是無法直接與Typescript交互，因此在Angular中創(chuàng)建一個服務(wù)文件，以依賴注入的方式給平臺提供服務(wù).在此文件中，渲染步驟動畫的代碼時刻監(jiān)聽面向用戶代碼塊的狀態(tài)，并隨其進(jìn)行改變，反之則不可.積木塊產(chǎn)生的代碼塊使用Axios向云編譯器發(fā)出請求后，得到了C代碼編譯后的結(jié)果，此結(jié)果是Typescript代碼，這就間接地實(shí)現(xiàn)了其直接交互.

3.3 流程圖生成對應(yīng)積木塊

流程圖是將所需要解決問題的順序、步驟用特定的圖形、符號進(jìn)行表達(dá)[8].使用流程圖可以輔助學(xué)生學(xué)習(xí)算法程序設(shè)計(jì)，將復(fù)雜的問題、過程直觀化，幫助學(xué)生加深對算法程序設(shè)計(jì)的理解，提高課堂學(xué)習(xí)效率[9].因此，本研究設(shè)計(jì)了根據(jù)算法邏輯搭建流程圖來生成對應(yīng)積木塊的功能，從流程圖到積木塊再到對應(yīng)編程語言代碼的實(shí)時生成，將算法邏輯清晰化，幫助學(xué)生更好地學(xué)習(xí)算法知識.

在本學(xué)習(xí)平臺中，積木塊在系統(tǒng)內(nèi)部的表現(xiàn)形式是XML格式，流程圖生成對應(yīng)積木塊的關(guān)鍵在于對流程圖中的每一個節(jié)點(diǎn)都要設(shè)計(jì)一個對象變量，對象里面綁定其對應(yīng)的積木塊的XML內(nèi)容.要對流程圖節(jié)點(diǎn)內(nèi)容進(jìn)行配置，需要使用高度可自定義的交互性圖形庫.為此，本平臺引入了GoJS庫.圖10所示為使用流程圖生成對應(yīng)積木塊來搭建一個簡單數(shù)學(xué)運(yùn)算模塊的界面.

圖10 流程圖生成對應(yīng)積木塊Fig.10 Flow chart generating corresponding building blocks

實(shí)現(xiàn)此功能模塊，一方面，要修改GoJS的 public paletteNodeData:Array數(shù)組，增加一個Blockly()方法以使每個流程圖綁定對應(yīng)的積木塊XML數(shù)據(jù):

paletteNodeData[{category:"Comment",key:"1", Blockly:(value,id)=>{return`

},...]

另一方面，需要實(shí)現(xiàn)在積木塊界面實(shí)時監(jiān)聽流程圖的變化以生成對應(yīng)積木塊.因此，本研究借助Angular的訂閱者模式，對流程圖生成數(shù)據(jù)進(jìn)行監(jiān)聽.每當(dāng)一個流程圖模塊搭建，訂閱者就會把其對應(yīng)的對象數(shù)據(jù)中預(yù)先設(shè)置好的Blockly()方法中的XML數(shù)據(jù)使用渲染DOM元素的Blockly.Xml.domToWorkspace()以及Blockly.Xml.textToDom()兩個API將格式為字符串類型的XML數(shù)據(jù)轉(zhuǎn)換為合法的XML并渲染到界面.當(dāng)需要的流程圖搭建完畢后，對應(yīng)的積木塊也隨之出現(xiàn)在工作區(qū)域，此時，后臺邏輯會對搭建的積木塊進(jìn)行相應(yīng)的處理，產(chǎn)生其對應(yīng)的代碼塊，實(shí)現(xiàn)了從流程圖到積木塊再到代碼塊的連續(xù)功能服務(wù).

4 結(jié)語

本研究基于ngx-blockly庫，貫徹運(yùn)用交互式教學(xué)的思想，開發(fā)了交互式計(jì)算機(jī)算法學(xué)習(xí)平臺.本平臺提供的C語言模塊的實(shí)現(xiàn)、算法執(zhí)行過程動畫演示、流程圖生成對應(yīng)積木塊等功能展示了計(jì)算機(jī)算法的執(zhí)行過程，可降低計(jì)算機(jī)算法學(xué)習(xí)的難度.