謝玉韜 徐劍 李慶英

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

關(guān)鍵詞：程序驗(yàn)證;對(duì)拍;Java語言;圖形化工具

中圖分類號(hào)：TP311? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）18-0045-03

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

1 引言

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

2 “對(duì)拍”的基本概念

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

3 “對(duì)拍”的應(yīng)用場景

3.1 通過“對(duì)拍”進(jìn)行程序檢錯(cuò)

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

3.2 通過“對(duì)拍”進(jìn)行算法驗(yàn)證

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

3.3 通過“對(duì)拍”出題

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

4 “對(duì)拍”的過程

“對(duì)拍”可分為代碼準(zhǔn)備、編寫并執(zhí)行對(duì)拍腳本或?qū)ε某绦虻炔襟E，下面以Window環(huán)境為例，結(jié)合例題介紹“對(duì)拍”的過程。

4.1 代碼準(zhǔn)備

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

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

#include

#include

#include

using namespace std;

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

int rand1（int n） {

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

}

//產(chǎn)生[x，y]的隨機(jī)整數(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中，當(dāng)兩個(gè)加數(shù)a和b都大于80時(shí)，輸出了它們的差，結(jié)果顯然是錯(cuò)誤的，下面通過對(duì)拍找出該錯(cuò)誤。

4.2 “對(duì)拍”過程及實(shí)現(xiàn)

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

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

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

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

Step4：比對(duì)stdout.txt和myout.txt內(nèi)容是否一致。

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

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

：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命令用于比較文件內(nèi)容是否相同，相同時(shí)輸出“找不到差異”，不同時(shí)會(huì)列出不同的內(nèi)容便于比對(duì)。

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

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

2）C++程序?qū)崿F(xiàn)對(duì)拍

編寫腳本需要熟悉其語法規(guī)則，而且不同操作系統(tǒng)腳本差別較大，為避免再學(xué)習(xí)新的語言規(guī)則或造成混淆，可以使用C++程序?qū)崿F(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ù)的程序驗(yàn)證工具實(shí)現(xiàn)

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

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

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

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

#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<<"正確程序的輸出文件擴(kuò)展名：";

cin>>ansName;

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

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

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

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

程序?qū)崿F(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）讀取樣例文件內(nèi)容函數(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）文件比對(duì)

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 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

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