“對拍”方法在程序驗證中的應用

謝玉韜 徐劍 李慶英

摘要：在編程實踐中，如何驗證所寫程序是否正確有很多方法，“對拍”是常用的一種。介紹了“對拍”的基本概念、應用場景，以兩個數(shù)求和為例詳細說明了“對拍”的過程，在此基礎上使用Java語言開發(fā)了圖形用戶界面的判題工具，該工具利用對拍原理，基于給定多組樣例數(shù)據(jù)，對用戶提交的程序的正確性進行驗證并給出反例，操作界面友好，操作方便，提高了程序驗證的效率。

關鍵詞：程序驗證;對拍;Java語言;圖形化工具

中圖分類號：TP311? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）18-0045-03

開放科學（資源服務）標識碼（OSID）：

1 引言

對拍是驗證人們寫出的程序是否正確的常用方法，特別是在編程競賽中，如果一個題目暴力算法容易寫，高效算法拿不準時，常采用“對拍”檢驗高效算法的正確性，避免不必要的丟分[1-2]。本文介紹了對拍的概念、應用場景、具體實現(xiàn)過程[3-4]，在此基礎上基于Java語言[5]開發(fā)了圖形用戶界面的判題工具，操作界面友好，操作方便，提高了程序驗證的效率。

2 “對拍”的基本概念

“對拍”，就是針對相同的輸入數(shù)據(jù)，對兩份程序的輸出結果進行比對。其中一份是確定正確的程序（樸素算法實現(xiàn)或網(wǎng)絡上搜索的Accepted的程序），另一份是自己寫的正確性待驗證的程序，通過“對拍”可以較容易地得出自己程序是否正確的結論，如果不正確，“對拍”發(fā)現(xiàn)的反例也有助于程序的修正。在后面“對拍過程”一節(jié)會詳細介紹對拍的實現(xiàn)步驟。

3 “對拍”的應用場景

3.1 通過“對拍”進行程序檢錯

平時在Online Judge上提交程序時，自己的程序無法通過，但又無法獲得測試數(shù)據(jù)，可以編寫隨機數(shù)據(jù)生成程序，生成大量輸入數(shù)據(jù)，再找一份正確的程序和自己的程序“對拍”，從而找到反例，找出程序錯誤。

3.2 通過“對拍”進行算法驗證

參加編程比賽時，當編寫出效率更高、算法更優(yōu)的程序，但無法確定程序算法正確性時，可以再寫一份用樸素算法實現(xiàn)的程序（通常時間復雜度高，思路簡單，不易出錯），將兩者對拍，以此判斷“高效算法”正確與否。

3.3 通過“對拍”出題

自己出題時，測試數(shù)據(jù)的生成、“標程”的正確性驗證都需要運用“對拍”的方法。

4 “對拍”的過程

“對拍”可分為代碼準備、編寫并執(zhí)行對拍腳本或對拍程序等步驟，下面以Window環(huán)境為例，結合例題介紹“對拍”的過程。

4.1 代碼準備

“對拍”是將大量測試數(shù)據(jù)分別交給兩份程序運行，比對兩份程序運行結果，并將結果輸出的過程。因此在“對拍”之前，通常需要編寫隨機數(shù)據(jù)生成、樸素算法程序和無法確定對錯的高分解法程序。下面以求兩個1～100的整數(shù)的和的C++源碼為例：

1）編寫隨機數(shù)據(jù)生成程序（gen.cpp）

#include

#include

#include

using namespace std;

//產(chǎn)生[0，n）的隨機整數(shù)

int rand1（int n） {

return （long long）rand（）*rand（）%n;

}

//產(chǎn)生[x，y]的隨機整數(shù)

int rand2（int x，int y） {

return rand1（y-x+1） + x;

}

int main（） {

srand（（unsigned）time（0））;

cout<

return 0;

}

2）編寫確定正確的程序（std.cpp）

#include

using namespace std;

int main（） {

int a， b;

cin >> a >> b;

cout << a + b << endl;

return 0;

}

3）編寫自己的程序（my.cpp）

#include

using namespace std;

int main（） {

int a， b;

cin >> a >>b;

if （a > 80 && b > 80） {

cout << a - b << endl;

} else {

cout << a + b << endl;

}

return 0;

}

在my.cpp中，當兩個加數(shù)a和b都大于80時，輸出了它們的差，結果顯然是錯誤的，下面通過對拍找出該錯誤。

4.2 “對拍”過程及實現(xiàn)

在“對拍”之前，依次編譯上述三個程序，得到三個可執(zhí)行文件： gen.exe、std.exe和my.exe。然后編寫腳本或C++程序，循環(huán)執(zhí)行如下過程，達到“對拍”的目的：

Step1：運行gen.exe產(chǎn)生輸入數(shù)據(jù)in.txt。

Step2：以in.txt作為輸入運行std.exe產(chǎn)生輸出數(shù)據(jù)stdout.txt。

Step3：以in.txt作為輸入運行my.exe產(chǎn)生輸出數(shù)據(jù)myout.txt。

Step4：比對stdout.txt和myout.txt內容是否一致。

下面用批處理腳本和C++程序兩種方式實現(xiàn)上述步驟。

1）批處理腳本（duipai.bat）實現(xiàn)對拍

：loop

@echo off

gen.exe > in.txt

my.exe < in.txt? > myout.txt

std.exe < in.txt? > stdout.txt

fc myout.txt stdout.txt

if not errorlevel 1? ?goto loop

pause

上述腳本中，fc命令用于比較文件內容是否相同，相同時輸出“找不到差異”，不同時會列出不同的內容便于比對。

雙擊腳本運行，當找到例外，即兩份程序輸出結果不同時，循環(huán)結束，得到圖1所示結果：

此時in.txt的內容為：95 87，此時正確輸出值為182，自測程序輸出值為8，原因是兩個數(shù)都大于80時，程序處理邏輯有誤。

2）C++程序實現(xiàn)對拍

編寫腳本需要熟悉其語法規(guī)則，而且不同操作系統(tǒng)腳本差別較大，為避免再學習新的語言規(guī)則或造成混淆，可以使用C++程序實現(xiàn)同樣的功能。頭文件cstdlib中提供了System函數(shù)，可用來執(zhí)行系統(tǒng)命令。源碼如下：

#include

#include

using namespace std;

int main（） {

while（true） {

system（"gen.exe>in.txt"）;

system（"std.exestdout.txt"）;

system（"my.exemyout.txt"）;

if（system（"fc stdout.txt myout.txt"））{

cout<<"wrong";

break;

}

}

return 0;

}

5 給定測試數(shù)據(jù)的程序驗證工具實現(xiàn)

前面介紹了對拍原理及實現(xiàn)過程，程序的測試數(shù)據(jù)是隨機生成的，下面考慮另一種情形：n組程序測試數(shù)據(jù)已經(jīng)給出，如何判斷程序是否正確？這種情形常用于以下場合：比賽后官方發(fā)布了測試數(shù)據(jù)但不提供在線判題入口;做書上題目時，通過作者提供的樣例判斷程序是否正確等。

將前面代碼中輸入數(shù)據(jù)和標準輸出數(shù)據(jù)生成過程省略，不難得到實現(xiàn)思路，下面給出字符界面和圖形界面兩種實現(xiàn)。

5.1 字符界面實現(xiàn)（C++）

在n組測試數(shù)據(jù)給出的情況下，需要提供n的值、程序文件名稱、樣例文件主名、樣例輸出和待測試輸出文件擴展名等，源碼如下：

#include

#include

#include

#include

using namespace std;

int main（） {

string programName，fileName，ansName，solName;

int n;

cout<<"輸入測試數(shù)據(jù)組數(shù)：";

cin>>n;

cout<<"輸入程序文件名稱：";

cin>>programName;

cout<<"輸入樣例文件主名：";

cin>>fileName;

cout<<"正確程序的輸出文件擴展名：";

cin>>ansName;

cout<<"待測試程序的輸出文件擴展名：";

cin>>solName;

for（int i=1; i<=n; i++） {

ostringstream oss1，oss2;

oss1<"<

system（oss1.str（）.c_str（））;

oss2<<"fc "<

system（oss2.str（）.c_str（））;

}

return 0;

}

假設測試數(shù)據(jù)有10組，輸入文件為add1.in，add2.in...，add10.in，輸出文件為add1.out，add2.out...，add10.out，則在上面代碼中，n的值為10;程序文件是指待測試程序編譯后的exe文件，如自己寫的求和程序編譯后為my.exe;輸入樣例文件主名為add，正確程序輸出文件擴展名為.out，待測試輸出文件擴展名自己設定，如.my，將它們放到同一個目錄下。

5.2 圖形界面實現(xiàn)（Java）

在上一節(jié)字符界面程序中，程序使用較為煩瑣，表現(xiàn)在如下方面：源程序需要手工編譯、輸入數(shù)據(jù)較多、出現(xiàn)錯誤需要去測試文件中核對等。基于上述原因，使用Java語言設計了圖形用戶界面的驗證工具，用戶輸入樣例文件信息并直接在界面中輸入源程序，提交后就可以直觀地看到對拍結果，提高了驗證效率，程序界面如圖2所示：

程序實現(xiàn)思路與C++類似，核心步驟及源碼如下：

1）編譯源程序

FileWriter fw=new FileWriter（"d：/duipai/1.cpp"）;

fw.write（jta1.getText（））;

fw.close（）;

String cmd = "g++ d：/duipai/1.cpp -o d：/duipai/1.exe";

Process pr1=Runtime.getRuntime（）.exec（cmd）; // 執(zhí)行編譯指令

pr1.waitFor（）;

2）讀取樣例文件內容函數(shù)

public String rf（String fileName） throws Exception {

File f=new File（"d：/duipai/"+fileName）;

FileReader fr=new FileReader（f）;

char[] cs=new char[5000];

int a=fr.read（cs）;

String css=new String（cs，0，a）;

fr.close（）;

return css;

}

3）文件比對

for（int i=1;i<=n;i++） {

String s11=rf（"a"+i+".out"）.trim（）;

String s22=rf（"a"+i+".my"）.trim（）;

if（s11.equals（s22）） {

jta2.append（i+"：Accepted"+"＼n"）;

}

else {

jta2.append（i+"：Error.輸入："+rf（"a"+i+".in"）+";樣例輸出："+s11+";你的輸出："+s22+"＼n"）;

}

}

}

6 結束語

本文介紹了對拍工具在程序驗證中的應用，首先介紹對拍的概念、應用場景、具體實現(xiàn)過程，在此基礎上基于Java語言開發(fā)了給定測試數(shù)據(jù)的圖形用戶界面的判題工具，為給定樣例數(shù)據(jù)判定程序正確性提供了方便。將該工具設計為線上使用是下一步考慮的工作。

參考文獻：

[1] 李煜東.算法競賽進階指南[M].鄭州：河南電子音像出版社，2018.

[2] 王亞峰.信息學競賽解題過程研究[J].中小學電教（下），2011（2）：152.

[3] 賈小軍.C語言程序設計[M].北京：人民郵電出版社，2014.

[4] 李柯景.淺析C語言中的隨機數(shù)問題[J].長春大學學報，2008，18（6）：64-68.

[5] 張繼軍.Java程序設計[M].北京：中國水利水電出版社，2019.

【通聯(lián)編輯：謝媛媛】