提高在線評測代碼提交接受率的三步法

喬海燕，周曉聰，王若梅，萬 海

（中山大學計算機學院，廣東廣州 510006）

0 引言

計算思維（Computational Thinking）［1］是計算機相關專業本科生應具備的一種基本能力，程序設計是訓練該能力的基本方法。編寫程序往往被認為是具有一定挑戰性的活動，即使對于計算機相關專業并具備程序設計基本知識的本科生，編寫正確的程序仍然具有一定難度。如何訓練學生編寫高質量的程序，一直是程序設計教學重點探討的問題。

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

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

程序設計教學重點在于引導學生掌握程序設計思想和方法［5］。許多研究表明，描述思想方法、編寫偽代碼有利于培養人們利用計算機解決問題的能力［6-7］。編寫程序應該首先寫出算法，最后再編寫源代碼。但在線評測系統的便捷性也為學生提供了快速獲得分數的“捷徑”，由此忽略了編寫程序必需的步驟。

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

1 三步法介紹

數據結構與算法是在中山大學計算機學院（下文稱“學院”）大二第一學期為計算機類專業開設的一門專業基礎課。學生在第一學年已完成了程序設計、離散數學等課程的學習，掌握了一門面向對象的程序設計語言以及離散數學等先行課相關知識，具備了編寫更復雜程序的基礎，但大部分學生的程序設計能力仍然不足，而且多數學生不能用偽代碼描述算法。

數據結構與算法也屬于高級程序設計課程，為了訓練學生利用計算機解決問題的能力，增強學生的動手能力，包括建立數學模型、設計算法，以及用程序設計語言編寫程序，該課程專門設置了實驗課，并且多年來在課程教學和考試中使用在線評測系統Sicily［8］和Vmatrix［9］對學生提交的代碼進行測試，以減少程序中的錯誤，提高程序質量。實踐結果證明，在線評測系統對于提高學生的編程能力可起到重要作用。

該課程目前使用的在線評測系統Vmatrix 是學院專門為程序設計教學開發的，系統可設置提交次數上限，以及學生提交代碼通過每個測試集的得分。如果不限制提交次數，學生往往不會耐心將程序編寫正確后再提交。為此，系統在平時作業和練習中給每個題目都設置了提交次數上限，結果顯示，學生提交作業時變得更謹慎，一次提交通過率也有所提高。然而，一旦提交的程序未通過系統測試，答案出現錯誤，學生往往需要花費很多時間調試程序。

為了進一步提高學生提交給在線評測系統的程序接受率，降低出錯率，本文在教學、作業與考試中都進一步規范程序設計過程，明確要求學生采取三步走的方法：①在數學抽象層，用自然語言描述解決問題的方法；②在數據結構層，用偽代碼將上一步的方法轉換為算法；③最后用程序設計語言將算法轉換為源代碼。

對于一個程序設計問題，明確要求學生先用自然語言寫出解決問題的思路與方法，然后將方法進一步細化，寫出偽代碼算法，在確保偽代碼算法完整性，并作為作業的一部分提交后，最后將偽代碼算法轉換為代碼。該方法將原來從問題到代碼一步走的方法劃分成三步，每一步任務都是比較具體、明確的，每一步都是保證下一步能夠順利進行的必要條件，而且在此三步之間，從上一步結果轉換到下一步結果相對容易，這種細化的過程可以減少傳統方法容易出現的諸多錯誤。

例如，對于一個有向無環圖G，輸出結點的拓撲排序問題，自然語言描述的方法如下：

重復下列步驟，直至所有結點均已輸出：

（1）選擇一個入度為0 的結點v。

（2）輸出結點v。

（3）將結點v 的每個外鄰接結點入度減1。

將以上方法轉換成算法，需要確定圖的存儲結構。為便于進行步驟（1），需要每個結點的入度，為此，可用一個數組表達所有結點的入度。為簡單起見，將步驟（2）理解為簡單地打印結點，則步驟（3）可用圖的鄰接表方便地實現。因此，使用數組indegree［］表示結點度數，用鄰接表表示有向圖。進一步，為了簡化步驟（1），引入一個隊列Q，將入度為0 的結點先置于隊列中，由此得到以下的偽代碼算法1。

算法1 拓撲排序格式

在算法1 中，隊列及其操作是由標準庫提供的，因此第一個for 循環很容易實現，第二個for 循環在鄰接表上也很容易實現，學生不難將算法轉換成源代碼。采用三步法編寫程序，看似多花了時間寫方法和算法，但只有在前兩步得到正確的結果后，才能避免將方法和算法中的錯誤遺留到源代碼中，避免后續需要花費更多時間調試源代碼。如果算法是正確、清晰的，則將其轉換成代碼出現錯誤的幾率可以大幅降低。

2 三步法教學過程

在數據結構與算法課程中，本文選擇3 個班進行對比，其中A 班采取三步法，而B、C 班采用傳統教學方法。3個班在教學過程中同時使用了Vmatrix 在線評測系統，A班還使用了BlackBoard［10］系統提交方法和偽代碼。

采取三步法的A 班，在課程教學環節，教師給出三步法的案例，并在作業環節要求學生首先提交解決問題的方法和算法。學生將作業提交到中山大學數字化學習平臺BlackBoard，并通過學生之間互評打分，進一步提高了學生書寫與評判偽代碼的能力。

書寫偽代碼是編寫程序的基礎，也是培養算法思維的重要一環。如果一個學生不能用算法形式表示解決問題的方法，也無法寫出高質量的代碼。為此，本文在教學每個環節中都強調了偽代碼的重要性，讓學生感受到遵循科學步驟做好一件事的重要性，并形成一種習慣。

完成偽代碼后，A 班學生將其轉換成源代碼，然后提交到在線評測系統。系統通常設置提交上限最多為6 次，發現限制提交次數后，學生每題的平均提交次數少于系統無限制時的對應平均提交次數，而且第一次提交的通過率也有所上升。

在期中考試的4 個程序設計問題中，也要求學生先寫出解決問題的方法和算法，然后編寫代碼提交給在線評測系統，限制每題最多提交6 次。結果顯示，學生平均成績為27.2，相當于百分制平均成績68 分。學生每題平均提交次數為2.0 次，每次提交平均得分8.3 分（滿分10 分）。

3 機考成績分析

在2019 學年數據結構與算法實驗期末考試中，使用在線評測系統進行機試。考試設置了10 個程序設計題目，每題滿分10 分，每題限制提交不超過10 次，考試時長3h，各班平均成績和及格率如表1 所示。通過對考試成績的分析，發現采取三步法的A 班有更高平均成績、及格率和優秀率，A 班平均成績比B 班高7 分，比C 班高出10分。A 班的每題平均提交次數也較其它班級低。

表1 各班平均成績和及格率（2019 學年）

在各班隨機選擇66 名學生，計算各學生的總得分與總提交次數之比。圖1 顯示各班66 名學生每次提交的得分（將每個學生總成績與其提交總次數之比按從大到小排列）。統計顯示，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%。因此，三步法可以有效提高學生的提交接受率。

同時，計算各班每個學生總提交次數與成績之比（放大10 倍），相當于每題的提交次數。圖2 顯示，A 班大部分學生每題提交次數少于其它班的提交次數。

本文在2018 學年的數據結構與算法課程中也選擇一個班試行了三步法，并對期末機考成績進行統計，如表2所示。結果顯示，使用三步法的A 班平均成績和及格率明顯高于其它班級。

圖1 各班一次提交得分

圖2 各班平均每題提交次數

表2 各班成績和及格率（2018 學年）

4 結語

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