基于編輯距離的自適應(yīng)反饋程序評(píng)測(cè)方法

薄鈞戈，喬亞男，齊 琪，黃 鑫，房琛琛

(西安交通大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西 西安 710049)

0 引 言

程序設(shè)計(jì)類課程是計(jì)算機(jī)類專業(yè)的專業(yè)基礎(chǔ)課，是數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)與分析等計(jì)算機(jī)核心課程的先修課[1]。程序設(shè)計(jì)類課程教學(xué)目標(biāo)是培養(yǎng)學(xué)生應(yīng)用計(jì)算機(jī)去求解實(shí)際問題的能力，為了達(dá)到此目標(biāo)，同學(xué)們需要反復(fù)的上機(jī)編程訓(xùn)練。由于傳統(tǒng)的程序設(shè)計(jì)類課程考核方式(紙面試卷)有很多缺點(diǎn)，比如教師需要花大量的時(shí)間和精力來批改作業(yè)、學(xué)生無法及時(shí)獲得學(xué)習(xí)效果反饋、缺乏在編程中的自我判斷能力等，導(dǎo)致學(xué)習(xí)興趣逐漸減退[2-3]，因此近幾年有不少高水平本科院校程序設(shè)計(jì)類課程將程序在線評(píng)測(cè)系統(tǒng)(Online Judge，OJ)引入到實(shí)踐教學(xué)環(huán)節(jié)中[4-5]，以提高學(xué)生編程熱情和壓力情況下解決編程問題的能力，以正確的計(jì)算思維去理解和構(gòu)建復(fù)雜的程序系統(tǒng)[6-7]。

對(duì)于編程題的自動(dòng)評(píng)閱，目前主要有兩種方法，一種是將學(xué)生程序代碼編譯為可執(zhí)行文件，然后輸入“預(yù)設(shè)測(cè)試用例輸入”，得出“學(xué)生代碼輸出”，再和“預(yù)設(shè)測(cè)試用例輸出”比對(duì)，給出相應(yīng)得分情況，該方法在基礎(chǔ)教學(xué)和算法競(jìng)賽中皆有長(zhǎng)時(shí)間廣泛而成熟的應(yīng)用[8]；另一種是結(jié)合程序代碼特征和復(fù)雜性度量，如學(xué)生代碼的行數(shù)、變量個(gè)數(shù)、復(fù)雜度以及語法樹等去評(píng)價(jià)學(xué)生程序代碼的質(zhì)量并給出得分[9-10]，并結(jié)合一些分類、聚類、可視化等數(shù)據(jù)挖掘的方法進(jìn)行圖表顯示[11-13]，這兩種方法都有明顯的缺點(diǎn)：當(dāng)學(xué)生代碼編譯錯(cuò)誤，或者測(cè)試用例評(píng)測(cè)不對(duì)，在沒有得全分的情況下，面對(duì)編譯、運(yùn)行等問題，學(xué)生還是很難改對(duì)代碼；尤其是在編譯通過而測(cè)試用例不通過的情況下，學(xué)生在修改代碼時(shí)有可能只是因?yàn)闇y(cè)試用例輸出的大小寫出錯(cuò)、缺失標(biāo)點(diǎn)符號(hào)、順序出錯(cuò)、有無空格等簡(jiǎn)單格式問題而花費(fèi)大量時(shí)間進(jìn)行調(diào)試(為了保證測(cè)試用例的安全，測(cè)試用例不能公開)。

為了解決上述問題，該文提出一種基于編輯距離的自適應(yīng)反饋程序評(píng)測(cè)方法，通過檢測(cè)學(xué)生代碼的編譯信息和測(cè)試用例信息，應(yīng)用編輯距離，自適應(yīng)給出學(xué)生代碼出錯(cuò)原因并給出反饋指導(dǎo)，幫助學(xué)生快速找到代碼出錯(cuò)位置并有針對(duì)的進(jìn)行修改。該方法應(yīng)用到了本校面向大面積計(jì)算機(jī)基礎(chǔ)課程的作業(yè)系統(tǒng)中(該系統(tǒng)由教學(xué)團(tuán)隊(duì)自主研發(fā)，相關(guān)界面見圖1)，該系統(tǒng)基于ASP.NET MVC框架開發(fā)，主要有題庫管理、在線練習(xí)、實(shí)時(shí)評(píng)測(cè)、系統(tǒng)監(jiān)控、學(xué)習(xí)預(yù)警等功能。學(xué)生注冊(cè)后，根據(jù)題目在線提交多種編程語言(C，C++，C#等)源代碼，系統(tǒng)編譯源代碼后執(zhí)行，采用黑盒測(cè)試的方式，通過和預(yù)設(shè)測(cè)試用例的比對(duì)來檢驗(yàn)源代碼編譯和運(yùn)行的正確性。

圖1 計(jì)算機(jī)基礎(chǔ)課程作業(yè)系統(tǒng)截圖

實(shí)踐證明，通過結(jié)合自適應(yīng)反饋程序評(píng)測(cè)方法的OJ系統(tǒng)，可以有效促進(jìn)程序設(shè)計(jì)類課程的教學(xué)質(zhì)量[14]。

1 研究方法和過程

該文提出的基于編輯距離的自適應(yīng)反饋程序評(píng)測(cè)方法，整體的步驟如圖2所示[8]。

圖2 自適應(yīng)反饋程序評(píng)測(cè)方法步驟

第一步，教師端布置編程題目信息，如題目描述、參考答案、開始完成和截止時(shí)間、預(yù)設(shè)測(cè)試用例等，其中測(cè)試用例根據(jù)題目考察點(diǎn)，可設(shè)置多個(gè)測(cè)試用例；

第二步，學(xué)生根據(jù)題目要求通過在線編輯器完成題目編寫并上傳至代碼評(píng)測(cè)服務(wù)器，其中在線編輯器有代碼高亮顯示、折疊、縮進(jìn)等模擬真實(shí)開發(fā)環(huán)境功能；

第三步，在評(píng)測(cè)學(xué)生程序代碼之前，需檢測(cè)過濾學(xué)生程序，對(duì)學(xué)生程序中出現(xiàn)不安全代碼進(jìn)行過濾，所述不安全代碼包括fdisk-硬盤分區(qū)、format-格式化、shutdown-關(guān)機(jī)等命令，防止惡意代碼；

第四步，編譯學(xué)生程序，代碼中如果由于語法錯(cuò)誤導(dǎo)致編譯失敗，獲取編譯錯(cuò)誤信息，如圖3所示，通過對(duì)編譯器返回的編譯錯(cuò)誤信息進(jìn)行篩選整理，分別獲得下面信息：

圖3 獲取編譯錯(cuò)誤信息

(1)編譯錯(cuò)誤代碼，通過編譯錯(cuò)誤代碼，彈出相應(yīng)錯(cuò)誤代碼幫助文檔，如MSDN文檔，或者打開相應(yīng)錯(cuò)誤代碼幫助網(wǎng)頁；

(2)編譯錯(cuò)誤行號(hào)，通過編譯錯(cuò)誤行號(hào)，學(xué)生可以快速定位找到程序錯(cuò)誤位置；

(3)編譯錯(cuò)誤詳細(xì)說明，通過編譯錯(cuò)誤詳細(xì)說明，可以幫助學(xué)生理解編譯錯(cuò)誤原因，有針對(duì)地修改錯(cuò)誤代碼。

第五步，如果學(xué)生程序編譯通過，而運(yùn)行不通過，則表示學(xué)生程序通過“預(yù)設(shè)測(cè)試用例的輸入”生成的輸出結(jié)果和“預(yù)設(shè)測(cè)試用例輸出”兩段文本不相等。因此，如果需要提供給學(xué)生一個(gè)比較準(zhǔn)確的錯(cuò)誤反饋信息，則需比對(duì)分析學(xué)生程序的輸出和“預(yù)設(shè)測(cè)試用例輸出”的異同，然而，學(xué)生編寫練習(xí)的程序和一般軟件產(chǎn)品不同，比如結(jié)構(gòu)簡(jiǎn)單，大多數(shù)有固定的算法模塊，如果編譯通過而運(yùn)行不通過，大概率總有這樣的情況：學(xué)生代碼通過“預(yù)設(shè)測(cè)試用例的輸入”生成的輸出總是朝著“預(yù)設(shè)測(cè)試用例輸出”靠近。因此對(duì)于學(xué)生代碼編譯通過而運(yùn)行不通過的錯(cuò)誤原因可能是常見簡(jiǎn)單錯(cuò)誤，所述常見簡(jiǎn)單錯(cuò)誤包括：學(xué)生代碼輸出結(jié)果大小寫出錯(cuò)、中英文標(biāo)點(diǎn)符號(hào)錯(cuò)誤、缺失或存在多余的空格、順序出錯(cuò)、錯(cuò)位問題、數(shù)值間存在倍數(shù)擴(kuò)大或縮小等。

該文將重點(diǎn)討論第五步 “程序編譯通過而運(yùn)行不通過” 這種情況，將在下一小節(jié)詳細(xì)介紹。

2 基于編輯距離的自適應(yīng)反饋程序評(píng)測(cè)方法

2.1 判斷測(cè)試用例考察類型

基于編輯距離的自適應(yīng)反饋程序評(píng)測(cè)方法首先判斷測(cè)試用例考察類型，可以結(jié)合“預(yù)設(shè)測(cè)試用例輸出”，得出測(cè)試用例考察類型，根據(jù)程序設(shè)計(jì)類課程歷史中同學(xué)們常見問題總結(jié)考察類型為四種，分別為：“單一字符串型”、“多個(gè)字符串型”、“單一純數(shù)值型”、“多個(gè)純數(shù)值型”。測(cè)試用例考察類型確定方法如圖4所示。

圖4 測(cè)試用例考察類型判斷方式

當(dāng)預(yù)設(shè)測(cè)試用例輸出文本內(nèi)容有字符或符號(hào)時(shí)，且字符串間沒有空格隔開，判斷測(cè)試用例類型為“單一字符串型”；

當(dāng)預(yù)設(shè)測(cè)試用例輸出文本內(nèi)容有字符或符號(hào)時(shí)，且字符串間以空格隔開，判斷測(cè)試用例類型為“多個(gè)字符串型”；

當(dāng)預(yù)設(shè)測(cè)試用例輸出文本內(nèi)容只有純數(shù)值(包括小數(shù))時(shí)，判斷測(cè)試用例類型為“單一純數(shù)值型”；

當(dāng)預(yù)設(shè)測(cè)試用例輸出文本內(nèi)容只有純數(shù)值或小數(shù)點(diǎn)或空格，并數(shù)值間以空格隔開時(shí)，判斷測(cè)試用例類型為“多個(gè)純數(shù)值型”。

2.2 計(jì)算編輯距離

對(duì)于四種不同的測(cè)試用例考察類型，需要計(jì)算學(xué)生代碼的輸出結(jié)果和“預(yù)設(shè)測(cè)試用例輸出”的編輯距離(Minimum Edit Distance，MED)。

編輯距離是由俄羅斯科學(xué)家Vladimir Levenshtein在1965年提出的，因此編輯距離也稱為 Levenshtein Distance。在信息論、語言學(xué)和計(jì)算機(jī)科學(xué)領(lǐng)域，編輯距離是用來度量?jī)蓚€(gè)序列相似程度的指標(biāo)。簡(jiǎn)單的說編輯距離就是指在兩個(gè)單詞之間，由其中一個(gè)單詞A轉(zhuǎn)換為另一個(gè)單詞B所需要的最少單字符編輯操作次數(shù)[15]。

在自然語言中的拼寫檢查時(shí)，根據(jù)一個(gè)拼錯(cuò)的字符串和其他正確的字符串的編輯距離，可以判斷哪一個(gè)或哪幾個(gè)是比較可能的字符串。對(duì)于兩段字符串A和B，其中字符串A的長(zhǎng)度為m，字符串B的長(zhǎng)度為n，其計(jì)算方法如下：

d[0][0]=0

d[i][0]=0, 1≤i≤m

d[0][j]=0, 1≤j≤n

d[i][j]=

其中，d表示一個(gè)[m+1][n+1]大小的二維數(shù)組(d的數(shù)組比字符串長(zhǎng)度長(zhǎng)1個(gè)，是因?yàn)樾枰粋€(gè)[1][1]大小的數(shù)組記錄其編輯距離為0)，d[i][j]表示完成從A(0,i)到B(0,j)的編輯次數(shù)。wdel(ai)表示把A[i]刪除的一次操作，wins(bj)表示把B[j]插到A[i]的一次操作，wsub(ai,bj)表示把A[i]用B[j]替換的一次操作。

相應(yīng)的符號(hào)如圖5所示。

圖5 文中相應(yīng)的符號(hào)及表示內(nèi)容

2.3 “單一字符串型”用例結(jié)果錯(cuò)誤

對(duì)于測(cè)試用例考察類型為“單一字符串型”，首先判斷學(xué)生代碼輸出結(jié)果和預(yù)設(shè)測(cè)試用例輸出長(zhǎng)度是否相等。

(1)學(xué)生代碼輸出結(jié)果字符串和預(yù)設(shè)測(cè)試用例輸出字符串長(zhǎng)度相等時(shí)，依次做如下處理：

將學(xué)生代碼輸出結(jié)果字符串大、小寫轉(zhuǎn)換(大寫字符轉(zhuǎn)為小寫字符、小寫字符轉(zhuǎn)為大寫字符、全部轉(zhuǎn)為大寫字符、全部轉(zhuǎn)為小寫字符)后和預(yù)設(shè)測(cè)試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“字符大小寫問題”導(dǎo)致運(yùn)行不通過；

將學(xué)生代碼輸出結(jié)果字符串標(biāo)點(diǎn)符號(hào)中英文轉(zhuǎn)換后和預(yù)設(shè)測(cè)試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“標(biāo)點(diǎn)符號(hào)中英文問題”導(dǎo)致運(yùn)行不通過；

調(diào)整修改學(xué)生代碼輸出結(jié)果字符串的順序后和預(yù)設(shè)測(cè)試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“順序錯(cuò)誤”導(dǎo)致運(yùn)行不通過；

將學(xué)生代碼輸出結(jié)果字符串旋轉(zhuǎn)(從首字符到最后一個(gè)字符進(jìn)行多次旋轉(zhuǎn))后和預(yù)設(shè)測(cè)試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“存在輸出錯(cuò)位問題”導(dǎo)致運(yùn)行不通過；

計(jì)算學(xué)生代碼輸出結(jié)果字符串和預(yù)設(shè)測(cè)試用例輸出字符串的編輯距離edit_Dis，以及編輯距離計(jì)算中刪除字符次數(shù)Ndel，編輯距離計(jì)算中添加字符次數(shù)Nins，且計(jì)算編輯距離占預(yù)設(shè)測(cè)試用例輸出比例R=edit_Dis/Lt，其中Lt為預(yù)設(shè)測(cè)試用例輸出字符串的長(zhǎng)度，如果R<0.5，則中英文反饋指導(dǎo)學(xué)生由于“輸出與測(cè)試用例輸出長(zhǎng)度相等，但是一半的字符無法匹配”導(dǎo)致運(yùn)行不通過；如果編輯距離edit_Dis和預(yù)設(shè)測(cè)試用例輸出字符串長(zhǎng)度相等，則中英文反饋指導(dǎo)學(xué)生由于“輸出與測(cè)試用例輸出長(zhǎng)度相等，但是所有字符均無法匹配”導(dǎo)致運(yùn)行不通過。

(2)學(xué)生代碼輸出結(jié)果字符串和預(yù)設(shè)測(cè)試用例輸出字符串長(zhǎng)度不相等時(shí)，依次做如下處理：

刪除學(xué)生代碼輸出結(jié)果字符串中所有標(biāo)點(diǎn)符號(hào)(主要是空格、回車等)后和預(yù)設(shè)測(cè)試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“輸出了多余的標(biāo)點(diǎn)符號(hào)”導(dǎo)致運(yùn)行不通過；

刪除預(yù)設(shè)測(cè)試用例輸出字符串中所有標(biāo)點(diǎn)符號(hào)(主要是空格、回車等)后和學(xué)生代碼輸出結(jié)果字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“缺少某些標(biāo)點(diǎn)符號(hào)”導(dǎo)致運(yùn)行不通過；

計(jì)算學(xué)生代碼輸出結(jié)果字符串和預(yù)設(shè)測(cè)試用例輸出字符串的編輯距離edit_Dis，以及編輯距離計(jì)算中刪除字符次數(shù)Ndel，如果編輯距離edit_Dis和刪除字符次數(shù)Ndel相等，則中英文反饋指導(dǎo)學(xué)生由于“多輸出了某些字符，與預(yù)設(shè)測(cè)試用例輸出無法匹配”導(dǎo)致運(yùn)行不通過；

計(jì)算學(xué)生代碼輸出結(jié)果字符串和預(yù)設(shè)測(cè)試用例輸出字符串的編輯距離edit_Dis，以及編輯距離計(jì)算中添加字符次數(shù)Nins，如果編輯距離edit_Dis和添加字符次數(shù)Nins相等，則中英文反饋指導(dǎo)學(xué)生由于“少輸出了某些字符，與預(yù)設(shè)測(cè)試用例輸出無法匹配”導(dǎo)致運(yùn)行不通過；

計(jì)算學(xué)生代碼輸出結(jié)果字符串和預(yù)設(shè)測(cè)試用例輸出字符串的編輯距離edit_Dis，以及計(jì)算編輯距離占預(yù)設(shè)測(cè)試用例輸出比例R=edit_Dis/Lt，其中Lt為預(yù)設(shè)測(cè)試用例輸出字符串的長(zhǎng)度，如果R<0.5，則中英文反饋指導(dǎo)學(xué)生由于“輸出與測(cè)試用例輸出長(zhǎng)度不相等，且一半的字符無法匹配”導(dǎo)致運(yùn)行不通過；否則顯示“輸出與測(cè)試用例輸出長(zhǎng)度不相等，且超過一半的字符無法匹配”導(dǎo)致運(yùn)行不通過。

2.4 “多個(gè)字符串型”用例結(jié)果錯(cuò)誤

對(duì)于測(cè)試用例考察類型為“多個(gè)字符串型”，需先判斷學(xué)生代碼輸出結(jié)果字符串個(gè)數(shù)Ns(以空格隔開)和預(yù)設(shè)測(cè)試用例輸出字符串個(gè)數(shù)Na(以空格隔開)是否相等。

(1)學(xué)生代碼輸出結(jié)果字符串個(gè)數(shù)和預(yù)設(shè)測(cè)試用例輸出字符串個(gè)數(shù)相等時(shí)，依次做如下處理：

判斷刪除學(xué)生代碼輸出結(jié)果字符串空格、回車后和預(yù)設(shè)測(cè)試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“輸出內(nèi)容與測(cè)試用例要求大體一致，有多余的空格、回車”導(dǎo)致運(yùn)行不通過；

判斷刪除預(yù)設(shè)測(cè)試用例輸出字符串空格、回車后和學(xué)生代碼輸出結(jié)果字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“輸出內(nèi)容與測(cè)試用例要求大體一致，缺失題目要求的空格或回車(可在輸出頭、尾檢查)”導(dǎo)致運(yùn)行不通過；

將學(xué)生代碼輸出結(jié)果字符串大、小寫轉(zhuǎn)換(大寫字符轉(zhuǎn)為小寫字符、小寫字符轉(zhuǎn)為大寫字符、全部轉(zhuǎn)為大寫字符、全部轉(zhuǎn)為小寫字符)后和預(yù)設(shè)測(cè)試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“字符大小寫問題”導(dǎo)致運(yùn)行不通過；

將學(xué)生代碼輸出結(jié)果字符串標(biāo)點(diǎn)符號(hào)中英文轉(zhuǎn)換后和預(yù)設(shè)測(cè)試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“標(biāo)點(diǎn)符號(hào)中英文問題”導(dǎo)致運(yùn)行不通過；

調(diào)整修改學(xué)生代碼輸出結(jié)果字符串的順序后和預(yù)設(shè)測(cè)試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“順序錯(cuò)誤”導(dǎo)致運(yùn)行不通過；

將學(xué)生代碼輸出結(jié)果字符串旋轉(zhuǎn)(從第一個(gè)字符串到最后以個(gè)字符串進(jìn)行多次旋轉(zhuǎn))后和預(yù)設(shè)測(cè)試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“存在輸出錯(cuò)位問題”導(dǎo)致運(yùn)行不通過。

(2)學(xué)生代碼輸出結(jié)果字符串個(gè)數(shù)和預(yù)設(shè)測(cè)試用例輸出字符串個(gè)數(shù)不相等時(shí)，依次做如下處理：

學(xué)生代碼輸出結(jié)果字符串個(gè)數(shù)Ns大于預(yù)設(shè)測(cè)試用例輸出字符串個(gè)數(shù)Na時(shí)，判斷學(xué)生代碼輸出結(jié)果字符串中前Na個(gè)字符串是否和預(yù)設(shè)測(cè)試用例輸出字符串相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“前Na個(gè)字符串和預(yù)設(shè)測(cè)試用例輸出匹配，但多輸出了某些字符串”導(dǎo)致運(yùn)行不通過；

學(xué)生代碼輸出結(jié)果字符串個(gè)數(shù)Ns小于預(yù)設(shè)測(cè)試用例輸出字符串個(gè)數(shù)Na時(shí)，判斷學(xué)生代碼輸出結(jié)果字符串中前Ns個(gè)字符串是否和預(yù)設(shè)測(cè)試用例輸出字符串相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“前Ns個(gè)字符串和預(yù)設(shè)測(cè)試用例輸出匹配，但少輸出了某些字符串”導(dǎo)致運(yùn)行不通過；

將學(xué)生代碼輸出結(jié)果調(diào)整順序后，判斷學(xué)生代碼輸出結(jié)果字符串中前min{Ns,Na}個(gè)字符串是否和預(yù)設(shè)測(cè)試用例輸出字符串相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“輸出字符串個(gè)數(shù)有誤，且存在輸出順序問題”導(dǎo)致運(yùn)行不通過；

將學(xué)生代碼輸出結(jié)果按照字符串間隔旋轉(zhuǎn)后和預(yù)設(shè)測(cè)試用例輸出字符串比較是否部分相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“輸出字符串個(gè)數(shù)有誤，且存在輸出錯(cuò)位問題”導(dǎo)致運(yùn)行不通過；

去除掉學(xué)生代碼輸出結(jié)果字符串和預(yù)設(shè)測(cè)試用例輸出中的所有空格，并計(jì)算學(xué)生代碼輸出結(jié)果字符串和預(yù)設(shè)測(cè)試用例輸出字符串的編輯距離edit_Dis，以及計(jì)算編輯距離占預(yù)設(shè)測(cè)試用例輸出比例R=edit_Dis/Lt，其中Lt為去除掉空格后的預(yù)設(shè)測(cè)試用例輸出字符串的長(zhǎng)度，如果R<0.5，則中英文反饋指導(dǎo)學(xué)生由于“輸出字符串個(gè)數(shù)與測(cè)試用例輸出字符串個(gè)數(shù)不相等，且一半的字符無法匹配”導(dǎo)致運(yùn)行不通過；否則顯示“輸出字符串個(gè)數(shù)與測(cè)試用例輸出字符串個(gè)數(shù)不相等，且超過一半的字符無法匹配”導(dǎo)致運(yùn)行不通過。

2.5 “單一純數(shù)值型”用例結(jié)果錯(cuò)誤

對(duì)于測(cè)試用例考察類型為“單一純數(shù)值型”，依次做如下處理：

將學(xué)生代碼輸出結(jié)果字符串和和預(yù)設(shè)測(cè)試用例輸出字符串轉(zhuǎn)為數(shù)值型，按照10的倍數(shù)放大或縮小學(xué)生代碼輸出結(jié)果，再與預(yù)設(shè)測(cè)試用例輸出比較，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“輸出字符串與預(yù)設(shè)測(cè)試用例輸出無法匹配，但是存在10的倍數(shù)關(guān)系”導(dǎo)致運(yùn)行不通過；

判斷學(xué)生代碼輸出結(jié)果字符串和和預(yù)設(shè)測(cè)試用例輸出字符串長(zhǎng)度是否相等，如果不相等，計(jì)算學(xué)生代碼輸出結(jié)果字符串和和預(yù)設(shè)測(cè)試用例輸出字符串的編輯距離edit_Dis，再比較前min{Ls-edit_Dis, Lt-edit_Dis}(Ls為學(xué)生代碼輸出結(jié)果字符串長(zhǎng)度，Lt為預(yù)設(shè)測(cè)試用例輸出字符串長(zhǎng)度)個(gè)學(xué)生代碼輸出結(jié)果字符串是否和預(yù)設(shè)測(cè)試用例輸出字符串相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“輸出字符串與預(yù)設(shè)測(cè)試用例輸出無法匹配，但是有效位保留出錯(cuò)”導(dǎo)致運(yùn)行不通過。

2.6 “多個(gè)純數(shù)值型”用例結(jié)果錯(cuò)誤

對(duì)于測(cè)試用例考察類型為“多個(gè)純數(shù)值型”，需先判斷學(xué)生代碼輸出結(jié)果數(shù)值個(gè)數(shù)Ns(以空格隔開)和預(yù)設(shè)測(cè)試用例輸出數(shù)值個(gè)數(shù)Na(以空格隔開)是否相等。

(1)學(xué)生代碼輸出結(jié)果數(shù)值個(gè)數(shù)和預(yù)設(shè)測(cè)試用例輸出數(shù)值個(gè)數(shù)相等時(shí)，依次做如下處理：

判斷刪除學(xué)生代碼輸出結(jié)果字符串空格、回車后和預(yù)設(shè)測(cè)試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“輸出內(nèi)容與測(cè)試用例要求大體一致，有多余的空格、回車”導(dǎo)致運(yùn)行不通過；

判斷刪除預(yù)設(shè)測(cè)試用例輸出字符串空格、回車后和學(xué)生代碼輸出結(jié)果字符串比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“輸出內(nèi)容與測(cè)試用例要求大體一致，缺失題目要求的空格或回車(可在輸出頭、尾檢查)”導(dǎo)致運(yùn)行不通過；

調(diào)整修改學(xué)生代碼輸出結(jié)果數(shù)值的順序后和預(yù)設(shè)測(cè)試用例輸出數(shù)值比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“多個(gè)數(shù)值間存在輸出順序錯(cuò)誤”導(dǎo)致運(yùn)行不通過；

將學(xué)生代碼輸出結(jié)果多個(gè)數(shù)值進(jìn)行旋轉(zhuǎn)(從第一個(gè)數(shù)值到最后一個(gè)數(shù)值進(jìn)行多次旋轉(zhuǎn))后和預(yù)設(shè)測(cè)試用例輸出數(shù)值比較是否相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“多個(gè)數(shù)值間存在輸出錯(cuò)位問題”導(dǎo)致運(yùn)行不通過。

(2)學(xué)生代碼輸出結(jié)果數(shù)值個(gè)數(shù)和預(yù)設(shè)測(cè)試用例輸出數(shù)值個(gè)數(shù)不相等時(shí)，依次做如下處理：

學(xué)生代碼輸出結(jié)果數(shù)值個(gè)數(shù)Ns大于預(yù)設(shè)測(cè)試用例輸出中數(shù)值個(gè)數(shù)Na時(shí)，判斷學(xué)生代碼輸出結(jié)果數(shù)值中前Na個(gè)數(shù)值是否和預(yù)設(shè)測(cè)試用例輸出相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“前Na個(gè)數(shù)值和預(yù)設(shè)測(cè)試用例輸出匹配，但多輸出了某些數(shù)值”導(dǎo)致運(yùn)行不通過；

學(xué)生代碼輸出結(jié)果數(shù)值個(gè)數(shù)Ns小于預(yù)設(shè)測(cè)試用例輸出中數(shù)值個(gè)數(shù)Na時(shí)，判斷學(xué)生代碼輸出結(jié)果數(shù)值中前Ns個(gè)數(shù)值是否和預(yù)設(shè)測(cè)試用例輸出相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“前Ns個(gè)數(shù)值和預(yù)設(shè)測(cè)試用例輸出匹配，但多輸出了某些數(shù)值”導(dǎo)致運(yùn)行不通過；

將學(xué)生代碼輸出結(jié)果調(diào)整順序后，判斷學(xué)生代碼輸出結(jié)果中前min{Ns,Na}個(gè)數(shù)值是否和預(yù)設(shè)測(cè)試用例輸出相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“輸出數(shù)值個(gè)數(shù)有誤，且存在輸出順序問題”導(dǎo)致運(yùn)行不通過；

將學(xué)生代碼輸出結(jié)果按照數(shù)值間隔旋轉(zhuǎn)后和預(yù)設(shè)測(cè)試用例輸出比較是否部分相等，如果相等，則中英文反饋指導(dǎo)學(xué)生由于“輸出數(shù)值個(gè)數(shù)有誤，且存在輸出錯(cuò)位問題”導(dǎo)致運(yùn)行不通過。

3 自適應(yīng)反饋程序評(píng)測(cè)方法的實(shí)施與成效分析

將基于編輯距離的自適應(yīng)反饋程序評(píng)測(cè)方法引入到本校面向大面積計(jì)算機(jī)基礎(chǔ)課程的作業(yè)系統(tǒng)中，學(xué)生使用該系統(tǒng)的相關(guān)截圖如圖6和圖7所示。通過連續(xù)3年的應(yīng)用，發(fā)現(xiàn)學(xué)生在線提交作業(yè)后，由于自適應(yīng)的指導(dǎo)反饋，可以有效提高學(xué)生編程的積極性。通過該系統(tǒng)學(xué)生不再局限于時(shí)間和地點(diǎn)的約束，并且系統(tǒng)有學(xué)習(xí)狀況分析功能，能夠看到同班級(jí)學(xué)生的完成情況，營造競(jìng)爭(zhēng)和激勵(lì)的良好學(xué)習(xí)氛圍，也有利于同學(xué)們的自主學(xué)習(xí)。同時(shí)，教師從傳統(tǒng)的向?qū)W生傳授知識(shí)轉(zhuǎn)變?yōu)閰f(xié)助學(xué)生解決任務(wù)，有利于教師提前發(fā)現(xiàn)充滿熱情的學(xué)生，對(duì)其進(jìn)行有針對(duì)性的培養(yǎng)。

圖6 編譯不通過反饋提示界面

基于編輯距離的自適應(yīng)反饋程序評(píng)測(cè)方法除了在本校大面計(jì)算機(jī)基礎(chǔ)課程的教學(xué)有應(yīng)用外，還用于競(jìng)賽的培訓(xùn)，實(shí)現(xiàn)有效銜接。課程組老師指導(dǎo)的學(xué)生多次獲得ACM國際大學(xué)生程序設(shè)計(jì)競(jìng)賽、“藍(lán)橋杯”全國軟件和信息技術(shù)專業(yè)人才大賽以及團(tuán)體程序設(shè)計(jì)天梯賽獎(jiǎng)項(xiàng)。在2019-2021年，本校連續(xù)三屆均有團(tuán)隊(duì)獲得全國總決賽團(tuán)隊(duì)一等獎(jiǎng)。

圖7 編譯通過運(yùn)行不通過反饋提示界面

4 結(jié)束語

近年來，團(tuán)隊(duì)老師在計(jì)算機(jī)基礎(chǔ)課程體系、能力培養(yǎng)模式、教學(xué)資源、人才培養(yǎng)等方面取得了重要成果，應(yīng)用效果顯著。對(duì)于其他兄弟院校、專業(yè)開設(shè)程序設(shè)計(jì)課程和實(shí)踐能力培養(yǎng)具有較好的借鑒和示范作用。

實(shí)踐證明，結(jié)合自適應(yīng)反饋程序評(píng)測(cè)方法的在線評(píng)測(cè)系統(tǒng)，可以有效激發(fā)學(xué)生的學(xué)習(xí)熱情，通過在實(shí)踐中學(xué)習(xí)掌握正確的計(jì)算機(jī)思維和行動(dòng)方法，促進(jìn)程序設(shè)計(jì)類課程的教學(xué)質(zhì)量。同時(shí)，系統(tǒng)引入了線上學(xué)習(xí)新的教學(xué)評(píng)價(jià)體系和學(xué)習(xí)成績(jī)考核機(jī)制，取得了良好的教學(xué)效果。另一方面，在實(shí)際的應(yīng)用過程中，也存在一些不足和不完善的地方，例如系統(tǒng)沒有考慮到學(xué)生的自律性和主動(dòng)性存在差異，以及如何擴(kuò)展學(xué)習(xí)深度和難度，為更優(yōu)秀的學(xué)生提供深層次的教學(xué)擴(kuò)展等，這些不足還需要在后續(xù)研究和應(yīng)用中進(jìn)一步改進(jìn)和探索。