另辟蹊徑：在創(chuàng)編程序中培育計(jì)算思維

李友興

摘要：程序設(shè)計(jì)題庫(kù)平臺(tái)里的題目從何而來(lái)？它是如何被創(chuàng)造出來(lái)的？出題者是以怎樣的方式構(gòu)建問(wèn)題來(lái)考察解題者的算法能力？這一系列的思考讓作者審視目前程序設(shè)計(jì)教學(xué)方法，將創(chuàng)新引入到程序設(shè)計(jì)教學(xué)的領(lǐng)域中，探索程序設(shè)計(jì)教學(xué)的另一條路徑——?jiǎng)?chuàng)編程序題。對(duì)于創(chuàng)編程序題的教學(xué)探索，本文提出了規(guī)范框架、確定算法、辨識(shí)情境、試用反饋等方法。創(chuàng)編程序題不僅可以發(fā)展學(xué)生的計(jì)算思維力，而且還可以激發(fā)學(xué)生的創(chuàng)造潛能，提升學(xué)生的技術(shù)學(xué)習(xí)成就感。

關(guān)鍵詞：程序設(shè)計(jì);計(jì)算思維;教學(xué)策略;創(chuàng)新實(shí)踐

中圖分類號(hào)：G434? 文獻(xiàn)標(biāo)識(shí)碼：A? 論文編號(hào)：1674-2117（2019）10-0034-04

在程序設(shè)計(jì)教學(xué)中，通常以程序題的求解為載體，來(lái)培養(yǎng)學(xué)生的算法構(gòu)建能力，發(fā)展學(xué)生的計(jì)算思維。而教師通常會(huì)在程序題的OI平臺(tái)中“上下翻騰”，通過(guò)“以身探題”來(lái)了解題目中所蘊(yùn)含的算法，為學(xué)生構(gòu)建拾階而上的算法構(gòu)建能力培育的程序題序列。隨著教師和學(xué)生對(duì)題目求解的不斷深入，師生都會(huì)自然地萌發(fā)一種想法：這些程序題從何而來(lái)？出題者有怎樣的算法理解力？他（她）以怎樣的方式構(gòu)建問(wèn)題來(lái)考察解題者的算法能力？這一系列的思考，讓筆者審視目前程序設(shè)計(jì)的教學(xué)方法是不是該走出傳統(tǒng)的靠刷題的唯一路徑，向出題者致敬，從解題到創(chuàng)題，尋找一條新的程序設(shè)計(jì)教學(xué)路徑。

創(chuàng)編程序題是學(xué)生基于一個(gè)或若干個(gè)算法，借助特定的生活情境，通過(guò)改編或創(chuàng)造，編制程序題源的一種行為。在創(chuàng)編程序題的過(guò)程中，學(xué)生基于算法，從一道最簡(jiǎn)單的“裸題”出發(fā)，通過(guò)逐步構(gòu)造、轉(zhuǎn)化、深化、增加、整合等過(guò)程，完成對(duì)問(wèn)題的構(gòu)思，體驗(yàn)程序創(chuàng)編的快樂(lè)，同時(shí)發(fā)展與提升計(jì)算思維。

規(guī)范框架——從了解到理解

程序題有一些基本的格式和規(guī)范，其表述的文本是與解題者的一種對(duì)話。以NOIP試題為參照，其組成要素有題目名稱、問(wèn)題描述、輸入文件、輸出文件、樣例數(shù)據(jù)和數(shù)據(jù)規(guī)模，每種要素都有各自的價(jià)值，用于向解題者提供明確的信息。

以學(xué)生創(chuàng)編的“課間游戲”程序題為例，“課間游戲（kjyx.cpp/c/pas）”是程序題的“題目名稱”，它是對(duì)具體問(wèn)題情境的一種提煉與濃縮，同時(shí)明確了源程序的文件主名與擴(kuò)展名?！皢?wèn)題描述”是提供已知條件，拋出一個(gè)具體索求的問(wèn)題，本程序題的“問(wèn)題描述”提出的是“在地圖中棋子經(jīng)歷多次前進(jìn)與后退行動(dòng)后的最終狀態(tài)”。“輸入文件”是根據(jù)題目中的描述，提供一種一定規(guī)格的數(shù)據(jù)，第一行有三個(gè)數(shù)字，分別表示棋子移動(dòng)的次數(shù)為N次，最多前進(jìn)格數(shù)為M格，后退格數(shù)為K格。第二行數(shù)據(jù)表示每次移動(dòng)的格數(shù)，數(shù)據(jù)之間有空格分隔。輸入文件對(duì)應(yīng)的是“kjyx.in”。“輸出文件”是求解后輸出的結(jié)果，文件名對(duì)應(yīng)的是 “kjyx.out”。“樣例數(shù)據(jù)”分別對(duì)應(yīng)輸入輸出格式具體的數(shù)據(jù)說(shuō)明?！皵?shù)據(jù)規(guī)?！笔浅綐永臄?shù)據(jù)規(guī)模說(shuō)明，在構(gòu)造程序時(shí)要考慮極大、極小、特殊等一些數(shù)據(jù)，使得數(shù)據(jù)規(guī)模能夠區(qū)分解題者的算法能力水平。

在程序題創(chuàng)編輔導(dǎo)中，教師不要急著讓學(xué)生死記硬背其組成要素，而要與學(xué)生討論與交流，使其理解這幾大基本要素。通過(guò)暫時(shí)性隱藏某些元素與內(nèi)容，讓學(xué)生感受到這幾個(gè)元素的不可或缺性，如缺失了數(shù)據(jù)規(guī)模，就無(wú)法考慮時(shí)間復(fù)雜度與空間復(fù)雜度，缺失了樣例說(shuō)明，就難以確定輸入與輸出的數(shù)據(jù)具體含義，進(jìn)而也就難以理解題目。

確定算法——從簡(jiǎn)單到復(fù)雜

一般情況下，學(xué)生創(chuàng)編程序題初始階段構(gòu)造的題目是比較樸素的，能被“一眼看穿”，其算法暴露在題目的描述中，即所謂的“裸題”。此時(shí)，教師要順勢(shì)引導(dǎo)，讓學(xué)生通過(guò)轉(zhuǎn)化、增加、整合等方法，實(shí)現(xiàn)題目的難度升級(jí)。其目的在于，構(gòu)造的程序題不僅能考驗(yàn)解題者對(duì)問(wèn)題的理解力和抽象能力，還能考查解題者靈活應(yīng)用算法的能力。

以基于小數(shù)的計(jì)數(shù)算法創(chuàng)編為例，程序社團(tuán)小江同學(xué)打算創(chuàng)編計(jì)數(shù)算法的程序題，她一開(kāi)始確定的思路如上頁(yè)圖1所示——一組N個(gè)整數(shù)，要求若干個(gè)整數(shù)個(gè)數(shù)并按照整數(shù)的大小進(jìn)行排序，這樣的問(wèn)題設(shè)計(jì)對(duì)于學(xué)過(guò)計(jì)數(shù)的解題者來(lái)說(shuō)不需要任何思考。于是，筆者引導(dǎo)學(xué)生在原題的基礎(chǔ)上增加“關(guān)卡”，將計(jì)數(shù)算法作一定的隱藏。通過(guò)啟發(fā)，她開(kāi)始想“怎樣的數(shù)據(jù)是不能直接用來(lái)計(jì)數(shù)的，但是通過(guò)轉(zhuǎn)化仍可計(jì)數(shù)”？最后，她想出輸入的數(shù)據(jù)是小數(shù)，每個(gè)小數(shù)的位數(shù)又是不同的，那就要尋找到最大的小數(shù)位數(shù)n，再把所有的小數(shù)乘以10^n，將所有原來(lái)的小數(shù)數(shù)據(jù)轉(zhuǎn)換為整數(shù)形式。這樣，就可以應(yīng)用計(jì)數(shù)排序，只需要將排序后再還原為小數(shù)，就完成了問(wèn)題的求解。

當(dāng)學(xué)生將修改后的創(chuàng)編題提交時(shí)，筆者發(fā)現(xiàn)其最大數(shù)據(jù)規(guī)模為2<=N<=10^8，雖說(shuō)計(jì)數(shù)排序的數(shù)據(jù)規(guī)模理論上是可以開(kāi)到N（按照一秒的有限時(shí)間），但還要考慮數(shù)組存儲(chǔ)空間大?。▍⒄?28MB的內(nèi)存空間），最終將數(shù)據(jù)規(guī)模定在N<=10^7。同時(shí)，筆者進(jìn)一步引導(dǎo)學(xué)生考慮分層，讓普通的計(jì)數(shù)排序算法也能獲得一些分值，這樣就構(gòu)造出30%的數(shù)據(jù)規(guī)模為1<=N<=1000，ai是一位小數(shù)。最終版的程序題既有區(qū)分度，又有靈活性。

編織情境——從良構(gòu)到劣構(gòu)

學(xué)生在確定了算法的考量，明確了算法，也確定了數(shù)據(jù)規(guī)模之后所構(gòu)造出來(lái)的題目雖然有深度有區(qū)分度，但“嚼之無(wú)味”“讀之無(wú)趣”。這種沒(méi)有生活情境的題目缺少了現(xiàn)實(shí)意義的支撐，學(xué)生在分析問(wèn)題過(guò)程中感受不到其意義與價(jià)值，在一定程度上會(huì)降低解題者的探索興趣。此時(shí)，教師就需要引導(dǎo)學(xué)生聯(lián)系現(xiàn)實(shí)，走向真實(shí)世界，創(chuàng)設(shè)有“時(shí)代感”“生活味”的情境，將程序設(shè)計(jì)的問(wèn)題求解回歸現(xiàn)實(shí)的意義，如上頁(yè)圖2所示。

當(dāng)前的新課程理念提倡的是一種在復(fù)雜問(wèn)題情境中的求解，在程序創(chuàng)編中教師除了可以編織生活情境以外，還可以將良構(gòu)的問(wèn)題描述改編成劣構(gòu)的問(wèn)題情境。通常的做法是，在良構(gòu)的問(wèn)題描述上再加上一些冗余的信息，讓學(xué)生在生活情境、冗余的信息中去提煉信息，確定問(wèn)題，構(gòu)建算法。這樣，不僅有利于發(fā)展解題者的算法構(gòu)建力，而且也有利于提升創(chuàng)編者的計(jì)算思維，如圖3所示。

試用反饋——從薄弱到增強(qiáng)

程序題的創(chuàng)編是一個(gè)不斷地迭代與優(yōu)化的過(guò)程，就如同用程序設(shè)計(jì)一樣，它的改進(jìn)需要從創(chuàng)編的反方向去思考——解題者的反饋。其反饋主要有三種信息：興趣度、題目難度和數(shù)據(jù)漏洞。第一種是“趣味度”，表明了題目是否足夠引起解題者的興趣;第二種是“題目難度”，其指標(biāo)在于區(qū)分一個(gè)群體的程序算法的能力水平;第三種是“數(shù)據(jù)漏洞”，指的是數(shù)據(jù)構(gòu)造中的漏洞，具體表現(xiàn)為解題者不需要正確的算法也能“踩”到分值。根據(jù)反饋的不同，需要不斷地改進(jìn)。比如難度太簡(jiǎn)單，那就要對(duì)照前面的算法構(gòu)造進(jìn)行一定的轉(zhuǎn)化與隱藏，或者提高數(shù)據(jù)規(guī)模來(lái)增加難度。再如數(shù)據(jù)構(gòu)造上有漏洞，那就要對(duì)數(shù)據(jù)構(gòu)造方面進(jìn)行修正補(bǔ)全。

以上頁(yè)圖4“找數(shù)字朋友”為例，小黃同學(xué)第一次把題目提交給筆者時(shí)，數(shù)據(jù)規(guī)模為：“100%的數(shù)據(jù) 1<=n<=200，m<=200， 0<=ai<=100”。為了檢測(cè)該題的難易程度，筆者將此題發(fā)給社團(tuán)學(xué)員進(jìn)行現(xiàn)場(chǎng)測(cè)試，并由小黃同學(xué)親自監(jiān)考與cena評(píng)測(cè)。結(jié)果發(fā)現(xiàn)每位同學(xué)都得滿分，因?yàn)橹恍枰秒p重循環(huán)模擬掃一遍就可以求解出答案，難度不大。為了加大難度，小黃修改了數(shù)據(jù)規(guī)模為：“100%的數(shù)據(jù) 1<=n<=100000，0<=m<=2000，0<=ai<=1000”。通過(guò)再試做，發(fā)現(xiàn)10位同學(xué)有8位得滿分，那是因?yàn)椤皀數(shù)據(jù)規(guī)模到達(dá)10萬(wàn)”，采用雙重循環(huán)的解題者必然超時(shí)，而采用計(jì)數(shù)算法的解題者能夠?qū)r(shí)間復(fù)雜度降低到O（maxai），是為正解。為再次加大難度，小黃直接將數(shù)據(jù)規(guī)模調(diào)整為：“100%數(shù)據(jù) 1<=n<=

100000000<=m<=20000000，0<=ai<=10000000”，結(jié)果只有3位同學(xué)100%通過(guò)。由于ai到了10000000數(shù)據(jù)量，利用原先的計(jì)數(shù)算法加雙重循環(huán)已經(jīng)沒(méi)法實(shí)現(xiàn)，這就要解題者改為O（n）或者O（ai）的算法，利用read（x）;ans=ans+a[m-x];inc（a[x]）;外套一個(gè)循環(huán)語(yǔ)句掃一遍完成，只有靈活應(yīng)用計(jì)數(shù)算法，才能100%順利通過(guò)。

創(chuàng)編程序的關(guān)鍵在于學(xué)生對(duì)程序算法的深刻理解，在理解的基礎(chǔ)上才能聯(lián)系生活情境，做到算法與情境的深度融合。同時(shí)，創(chuàng)編程序題使學(xué)生在不斷地創(chuàng)編改良中進(jìn)一步地深刻理解算法，甚至對(duì)各類相類似的算法融會(huì)貫通。創(chuàng)編程序是一種以創(chuàng)促學(xué)的算法學(xué)習(xí)、算法研習(xí)方式，它使學(xué)生從一個(gè)學(xué)習(xí)者躍升為一個(gè)有著計(jì)算思維駕馭力和個(gè)性思考力的構(gòu)造者和創(chuàng)造者，這就極大地激發(fā)了學(xué)生的算法學(xué)習(xí)潛能，讓他們獲得技術(shù)學(xué)習(xí)的成就感。

參考文獻(xiàn)：

[1]中華人民共和國(guó)教育部.普通高中信息技術(shù)課程標(biāo)準(zhǔn)[M].北京：人民教育出版社，2018.

[2]費(fèi)海明.中小學(xué)生計(jì)算思維培育的路徑與策略[J].中小學(xué)信息技術(shù)教育，2017（10）.