提高在線評(píng)測(cè)代碼提交接受率的三步法

喬海燕，周曉聰，王若梅，萬(wàn) 海

（中山大學(xué)計(jì)算機(jī)學(xué)院，廣東廣州 510006）

0 引言

計(jì)算思維（Computational Thinking）［1］是計(jì)算機(jī)相關(guān)專業(yè)本科生應(yīng)具備的一種基本能力，程序設(shè)計(jì)是訓(xùn)練該能力的基本方法。編寫程序往往被認(rèn)為是具有一定挑戰(zhàn)性的活動(dòng)，即使對(duì)于計(jì)算機(jī)相關(guān)專業(yè)并具備程序設(shè)計(jì)基本知識(shí)的本科生，編寫正確的程序仍然具有一定難度。如何訓(xùn)練學(xué)生編寫高質(zhì)量的程序，一直是程序設(shè)計(jì)教學(xué)重點(diǎn)探討的問(wèn)題。

在程序設(shè)計(jì)教學(xué)中使用在線評(píng)測(cè)系統(tǒng)（Online Judge System）可以給學(xué)生提供大量練習(xí)機(jī)會(huì)，并吸引學(xué)生主動(dòng)進(jìn)行練習(xí)，從而提高學(xué)生的程序設(shè)計(jì)能力［2-3］。研究表明，學(xué)生提交通過(guò)的題目數(shù)量越多，其編程能力越強(qiáng)，課程成績(jī)也越好［4］。然而，在線評(píng)測(cè)系統(tǒng)在使用過(guò)程中也存在一些問(wèn)題，例如，學(xué)生拿到問(wèn)題后往往直接開始編寫代碼，如果不限制其提交次數(shù)，學(xué)生一般不會(huì)耐心將程序編寫正確，而是不加測(cè)試，甚至不在本地運(yùn)行就提交，將系統(tǒng)作為編譯器。有的學(xué)生每隔幾秒就重新提交一次，一個(gè)簡(jiǎn)單題目的提交次數(shù)可高達(dá)30 多次。如果系統(tǒng)限制提交次數(shù)，學(xué)生就會(huì)變得更謹(jǐn)慎，在一定程度上可以提高接受率。但一旦提交不成功，學(xué)生往往會(huì)在調(diào)試方面花費(fèi)大量時(shí)間。主要原因可能在于學(xué)生急于求成，沒有遵循程序設(shè)計(jì)的正確方法，省略了從問(wèn)題到代碼過(guò)程中的必要步驟，從而導(dǎo)致早期錯(cuò)誤遺留到代碼中，使得后期調(diào)試過(guò)程復(fù)雜化。

設(shè)計(jì)或制造一件高質(zhì)量的商品應(yīng)遵循一定的方法、步驟和規(guī)范，已成為人們的共識(shí)。程序這種智能產(chǎn)品雖然有其特殊之處，但如果有比較明確的可遵循且操作性較強(qiáng)的方法與步驟，也能提高計(jì)算機(jī)程序編寫質(zhì)量。

程序設(shè)計(jì)教學(xué)重點(diǎn)在于引導(dǎo)學(xué)生掌握程序設(shè)計(jì)思想和方法［5］。許多研究表明，描述思想方法、編寫偽代碼有利于培養(yǎng)人們利用計(jì)算機(jī)解決問(wèn)題的能力［6-7］。編寫程序應(yīng)該首先寫出算法，最后再編寫源代碼。但在線評(píng)測(cè)系統(tǒng)的便捷性也為學(xué)生提供了快速獲得分?jǐn)?shù)的“捷徑”，由此忽略了編寫程序必需的步驟。

如何培養(yǎng)學(xué)生養(yǎng)成良好的編程習(xí)慣，一步步完成程序設(shè)計(jì)過(guò)程中的必要步驟，從而進(jìn)一步提高提交程序的正確性或接受率，減少調(diào)試時(shí)間，已有的相關(guān)研究文獻(xiàn)并不多。為此，本文在“數(shù)據(jù)結(jié)構(gòu)與算法”課程教學(xué)中，嘗試將程序設(shè)計(jì)過(guò)程適度進(jìn)行細(xì)化與規(guī)范化，明確要求學(xué)生采取三步走的方法：先描述方法，再編寫偽代碼算法，最后用程序設(shè)計(jì)語(yǔ)言編寫代碼。通過(guò)對(duì)考試成績(jī)的分析，發(fā)現(xiàn)采取三步法確實(shí)可以有效提高學(xué)生的提交接受率，令學(xué)生養(yǎng)成更好的編程習(xí)慣。

1 三步法介紹

數(shù)據(jù)結(jié)構(gòu)與算法是在中山大學(xué)計(jì)算機(jī)學(xué)院（下文稱“學(xué)院”）大二第一學(xué)期為計(jì)算機(jī)類專業(yè)開設(shè)的一門專業(yè)基礎(chǔ)課。學(xué)生在第一學(xué)年已完成了程序設(shè)計(jì)、離散數(shù)學(xué)等課程的學(xué)習(xí)，掌握了一門面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言以及離散數(shù)學(xué)等先行課相關(guān)知識(shí)，具備了編寫更復(fù)雜程序的基礎(chǔ)，但大部分學(xué)生的程序設(shè)計(jì)能力仍然不足，而且多數(shù)學(xué)生不能用偽代碼描述算法。

數(shù)據(jù)結(jié)構(gòu)與算法也屬于高級(jí)程序設(shè)計(jì)課程，為了訓(xùn)練學(xué)生利用計(jì)算機(jī)解決問(wèn)題的能力，增強(qiáng)學(xué)生的動(dòng)手能力，包括建立數(shù)學(xué)模型、設(shè)計(jì)算法，以及用程序設(shè)計(jì)語(yǔ)言編寫程序，該課程專門設(shè)置了實(shí)驗(yàn)課，并且多年來(lái)在課程教學(xué)和考試中使用在線評(píng)測(cè)系統(tǒng)Sicily［8］和Vmatrix［9］對(duì)學(xué)生提交的代碼進(jìn)行測(cè)試，以減少程序中的錯(cuò)誤，提高程序質(zhì)量。實(shí)踐結(jié)果證明，在線評(píng)測(cè)系統(tǒng)對(duì)于提高學(xué)生的編程能力可起到重要作用。

該課程目前使用的在線評(píng)測(cè)系統(tǒng)Vmatrix 是學(xué)院專門為程序設(shè)計(jì)教學(xué)開發(fā)的，系統(tǒng)可設(shè)置提交次數(shù)上限，以及學(xué)生提交代碼通過(guò)每個(gè)測(cè)試集的得分。如果不限制提交次數(shù)，學(xué)生往往不會(huì)耐心將程序編寫正確后再提交。為此，系統(tǒng)在平時(shí)作業(yè)和練習(xí)中給每個(gè)題目都設(shè)置了提交次數(shù)上限，結(jié)果顯示，學(xué)生提交作業(yè)時(shí)變得更謹(jǐn)慎，一次提交通過(guò)率也有所提高。然而，一旦提交的程序未通過(guò)系統(tǒng)測(cè)試，答案出現(xiàn)錯(cuò)誤，學(xué)生往往需要花費(fèi)很多時(shí)間調(diào)試程序。

為了進(jìn)一步提高學(xué)生提交給在線評(píng)測(cè)系統(tǒng)的程序接受率，降低出錯(cuò)率，本文在教學(xué)、作業(yè)與考試中都進(jìn)一步規(guī)范程序設(shè)計(jì)過(guò)程，明確要求學(xué)生采取三步走的方法：①在數(shù)學(xué)抽象層，用自然語(yǔ)言描述解決問(wèn)題的方法；②在數(shù)據(jù)結(jié)構(gòu)層，用偽代碼將上一步的方法轉(zhuǎn)換為算法；③最后用程序設(shè)計(jì)語(yǔ)言將算法轉(zhuǎn)換為源代碼。

對(duì)于一個(gè)程序設(shè)計(jì)問(wèn)題，明確要求學(xué)生先用自然語(yǔ)言寫出解決問(wèn)題的思路與方法，然后將方法進(jìn)一步細(xì)化，寫出偽代碼算法，在確保偽代碼算法完整性，并作為作業(yè)的一部分提交后，最后將偽代碼算法轉(zhuǎn)換為代碼。該方法將原來(lái)從問(wèn)題到代碼一步走的方法劃分成三步，每一步任務(wù)都是比較具體、明確的，每一步都是保證下一步能夠順利進(jìn)行的必要條件，而且在此三步之間，從上一步結(jié)果轉(zhuǎn)換到下一步結(jié)果相對(duì)容易，這種細(xì)化的過(guò)程可以減少傳統(tǒng)方法容易出現(xiàn)的諸多錯(cuò)誤。

例如，對(duì)于一個(gè)有向無(wú)環(huán)圖G，輸出結(jié)點(diǎn)的拓?fù)渑判騿?wèn)題，自然語(yǔ)言描述的方法如下：

重復(fù)下列步驟，直至所有結(jié)點(diǎn)均已輸出：

（1）選擇一個(gè)入度為0 的結(jié)點(diǎn)v。

（2）輸出結(jié)點(diǎn)v。

（3）將結(jié)點(diǎn)v 的每個(gè)外鄰接結(jié)點(diǎn)入度減1。

將以上方法轉(zhuǎn)換成算法，需要確定圖的存儲(chǔ)結(jié)構(gòu)。為便于進(jìn)行步驟（1），需要每個(gè)結(jié)點(diǎn)的入度，為此，可用一個(gè)數(shù)組表達(dá)所有結(jié)點(diǎn)的入度。為簡(jiǎn)單起見，將步驟（2）理解為簡(jiǎn)單地打印結(jié)點(diǎn)，則步驟（3）可用圖的鄰接表方便地實(shí)現(xiàn)。因此，使用數(shù)組indegree［］表示結(jié)點(diǎn)度數(shù)，用鄰接表表示有向圖。進(jìn)一步，為了簡(jiǎn)化步驟（1），引入一個(gè)隊(duì)列Q，將入度為0 的結(jié)點(diǎn)先置于隊(duì)列中，由此得到以下的偽代碼算法1。

算法1 拓?fù)渑判蚋袷?/p>

在算法1 中，隊(duì)列及其操作是由標(biāo)準(zhǔn)庫(kù)提供的，因此第一個(gè)for 循環(huán)很容易實(shí)現(xiàn)，第二個(gè)for 循環(huán)在鄰接表上也很容易實(shí)現(xiàn)，學(xué)生不難將算法轉(zhuǎn)換成源代碼。采用三步法編寫程序，看似多花了時(shí)間寫方法和算法，但只有在前兩步得到正確的結(jié)果后，才能避免將方法和算法中的錯(cuò)誤遺留到源代碼中，避免后續(xù)需要花費(fèi)更多時(shí)間調(diào)試源代碼。如果算法是正確、清晰的，則將其轉(zhuǎn)換成代碼出現(xiàn)錯(cuò)誤的幾率可以大幅降低。

2 三步法教學(xué)過(guò)程

在數(shù)據(jù)結(jié)構(gòu)與算法課程中，本文選擇3 個(gè)班進(jìn)行對(duì)比，其中A 班采取三步法，而B、C 班采用傳統(tǒng)教學(xué)方法。3個(gè)班在教學(xué)過(guò)程中同時(shí)使用了Vmatrix 在線評(píng)測(cè)系統(tǒng)，A班還使用了BlackBoard［10］系統(tǒng)提交方法和偽代碼。

采取三步法的A 班，在課程教學(xué)環(huán)節(jié)，教師給出三步法的案例，并在作業(yè)環(huán)節(jié)要求學(xué)生首先提交解決問(wèn)題的方法和算法。學(xué)生將作業(yè)提交到中山大學(xué)數(shù)字化學(xué)習(xí)平臺(tái)BlackBoard，并通過(guò)學(xué)生之間互評(píng)打分，進(jìn)一步提高了學(xué)生書寫與評(píng)判偽代碼的能力。

書寫偽代碼是編寫程序的基礎(chǔ)，也是培養(yǎng)算法思維的重要一環(huán)。如果一個(gè)學(xué)生不能用算法形式表示解決問(wèn)題的方法，也無(wú)法寫出高質(zhì)量的代碼。為此，本文在教學(xué)每個(gè)環(huán)節(jié)中都強(qiáng)調(diào)了偽代碼的重要性，讓學(xué)生感受到遵循科學(xué)步驟做好一件事的重要性，并形成一種習(xí)慣。

完成偽代碼后，A 班學(xué)生將其轉(zhuǎn)換成源代碼，然后提交到在線評(píng)測(cè)系統(tǒng)。系統(tǒng)通常設(shè)置提交上限最多為6 次，發(fā)現(xiàn)限制提交次數(shù)后，學(xué)生每題的平均提交次數(shù)少于系統(tǒng)無(wú)限制時(shí)的對(duì)應(yīng)平均提交次數(shù)，而且第一次提交的通過(guò)率也有所上升。

在期中考試的4 個(gè)程序設(shè)計(jì)問(wèn)題中，也要求學(xué)生先寫出解決問(wèn)題的方法和算法，然后編寫代碼提交給在線評(píng)測(cè)系統(tǒng)，限制每題最多提交6 次。結(jié)果顯示，學(xué)生平均成績(jī)?yōu)?7.2，相當(dāng)于百分制平均成績(jī)68 分。學(xué)生每題平均提交次數(shù)為2.0 次，每次提交平均得分8.3 分（滿分10 分）。

3 機(jī)考成績(jī)分析

在2019 學(xué)年數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)期末考試中，使用在線評(píng)測(cè)系統(tǒng)進(jìn)行機(jī)試?？荚囋O(shè)置了10 個(gè)程序設(shè)計(jì)題目，每題滿分10 分，每題限制提交不超過(guò)10 次，考試時(shí)長(zhǎng)3h，各班平均成績(jī)和及格率如表1 所示。通過(guò)對(duì)考試成績(jī)的分析，發(fā)現(xiàn)采取三步法的A 班有更高平均成績(jī)、及格率和優(yōu)秀率，A 班平均成績(jī)比B 班高7 分，比C 班高出10分。A 班的每題平均提交次數(shù)也較其它班級(jí)低。

表1 各班平均成績(jī)和及格率（2019 學(xué)年）

在各班隨機(jī)選擇66 名學(xué)生，計(jì)算各學(xué)生的總得分與總提交次數(shù)之比。圖1 顯示各班66 名學(xué)生每次提交的得分（將每個(gè)學(xué)生總成績(jī)與其提交總次數(shù)之比按從大到小排列）。統(tǒng)計(jì)顯示，A 班平均每次提交得3.7 分，B 班和C 班平均每次提交得2.5 分和2.2 分。如果把平均每次提交得分稱為提交接受率，則A 班接受率為37.4%，B 班、C 班接受率分別為24.8% 和22.2%，采取三步法的A 班接受率分別比B 班與C 班高出12.6% 和15.2%。因此，三步法可以有效提高學(xué)生的提交接受率。

同時(shí)，計(jì)算各班每個(gè)學(xué)生總提交次數(shù)與成績(jī)之比（放大10 倍），相當(dāng)于每題的提交次數(shù)。圖2 顯示，A 班大部分學(xué)生每題提交次數(shù)少于其它班的提交次數(shù)。

本文在2018 學(xué)年的數(shù)據(jù)結(jié)構(gòu)與算法課程中也選擇一個(gè)班試行了三步法，并對(duì)期末機(jī)考成績(jī)進(jìn)行統(tǒng)計(jì)，如表2所示。結(jié)果顯示，使用三步法的A 班平均成績(jī)和及格率明顯高于其它班級(jí)。

圖1 各班一次提交得分

圖2 各班平均每題提交次數(shù)

表2 各班成績(jī)和及格率（2018 學(xué)年）

4 結(jié)語(yǔ)

對(duì)在線評(píng)測(cè)考試成績(jī)的分析顯示，在使用在線評(píng)測(cè)系統(tǒng)的程序教學(xué)中，遵循三步法的班級(jí)獲得了更高的平均成績(jī)、及格率、優(yōu)秀率以及提交接受率，而且可使學(xué)生養(yǎng)成良好的編程習(xí)慣。本文目前使用了兩個(gè)不同系統(tǒng)，偽代碼提交到elearning，程序代碼提交到Vmatrix，但從第二步到第三步的銜接并沒有很好的系統(tǒng)支持。今后可仿照國(guó)防科技大學(xué)開發(fā)的Educoder 實(shí)訓(xùn)平臺(tái)［11］中的過(guò)關(guān)模式，將提交偽代碼合并到Vmatrix 上，學(xué)生只有提交偽代碼后才可以進(jìn)行下一步程序設(shè)計(jì)。另外，在期末考試中，3 個(gè)班的考試環(huán)境和考核要求是一致的，并未單獨(dú)要求A 班學(xué)生編寫與提交偽代碼。因此，在考試期間要求先編寫并提交偽代碼，再編寫代碼對(duì)考試成績(jī)與提交成功率的影響也有待進(jìn)一步研究。目前，三步法在程序設(shè)計(jì)教學(xué)中取得了初步成效，今后需要作進(jìn)一步研究與推廣，以增強(qiáng)該方法的可操作性。