“对拍”方法在程序验证中的应用

谢玉韬 徐剑 李庆英

摘要：在编程实践中，如何验证所写程序是否正确有很多方法，“对拍”是常用的一种。介绍了“对拍”的基本概念、应用场景，以两个数求和为例详细说明了“对拍”的过程，在此基础上使用Java语言开发了图形用户界面的判题工具，该工具利用对拍原理，基于给定多组样例数据，对用户提交的程序的正确性进行验证并给出反例，操作界面友好，操作方便，提高了程序验证的效率。

关键词：程序验证;对拍;Java语言;图形化工具

中图分类号：TP311      文献标识码：A

文章编号：1009-3044（2022）18-0045-03

开放科学（资源服务）标识码（OSID）：

1 引言

对拍是验证人们写出的程序是否正确的常用方法，特别是在编程竞赛中，如果一个题目暴力算法容易写，高效算法拿不准时，常采用“对拍”检验高效算法的正确性，避免不必要的丢分[1-2]。本文介绍了对拍的概念、应用场景、具体实现过程[3-4]，在此基础上基于Java语言[5]开发了图形用户界面的判题工具，操作界面友好，操作方便，提高了程序验证的效率。

2 “对拍”的基本概念

“对拍”，就是针对相同的输入数据，对两份程序的输出结果进行比对。其中一份是确定正确的程序（朴素算法实现或网络上搜索的Accepted的程序），另一份是自己写的正确性待验证的程序，通过“对拍”可以较容易地得出自己程序是否正确的结论，如果不正确，“对拍”发现的反例也有助于程序的修正。在后面“对拍过程”一节会详细介绍对拍的实现步骤。

3 “对拍”的应用场景

3.1 通过“对拍”进行程序检错

平时在Online Judge上提交程序时，自己的程序无法通过，但又无法获得测试数据，可以编写随机数据生成程序，生成大量输入数据，再找一份正确的程序和自己的程序“对拍”，从而找到反例，找出程序错误。

3.2 通过“对拍”进行算法验证

参加编程比赛时，当编写出效率更高、算法更优的程序，但无法确定程序算法正确性时，可以再写一份用朴素算法实现的程序（通常时间复杂度高，思路简单，不易出错），将两者对拍，以此判断“高效算法”正确与否。

3.3 通过“对拍”出题

自己出题时，测试数据的生成、“标程”的正确性验证都需要运用“对拍”的方法。

4 “对拍”的过程

“对拍”可分为代码准备、编写并执行对拍脚本或对拍程序等步骤，下面以Window环境为例，结合例题介绍“对拍”的过程。

4.1 代码准备

“对拍”是将大量测试数据分别交给两份程序运行，比对两份程序运行结果，并将结果输出的过程。因此在“对拍”之前，通常需要编写随机数据生成、朴素算法程序和无法确定对错的高分解法程序。下面以求两个1～100的整数的和的C++源码为例：

1）编写随机数据生成程序（gen.cpp）

#include

#include

#include

using namespace std;

//产生[0，n）的随机整数

int rand1（int n） {

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

}

//产生[x，y]的随机整数

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中，当两个加数a和b都大于80时，输出了它们的差，结果显然是错误的，下面通过对拍找出该错误。

4.2 “对拍”过程及实现

在“对拍”之前，依次编译上述三个程序，得到三个可执行文件： gen.exe、std.exe和my.exe。然后编写脚本或C++程序，循环执行如下过程，达到“对拍”的目的：

Step1：運行gen.exe产生输入数据in.txt。

Step2：以in.txt作为输入运行std.exe产生输出数据stdout.txt。

Step3：以in.txt作为输入运行my.exe产生输出数据myout.txt。

Step4：比对stdout.txt和myout.txt内容是否一致。

下面用批处理脚本和C++程序两种方式实现上述步骤。

1）批处理脚本（duipai.bat）实现对拍

：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命令用于比较文件内容是否相同，相同时输出“找不到差异”，不同时会列出不同的内容便于比对。

双击脚本运行，当找到例外，即两份程序输出结果不同时，循环结束，得到图1所示结果：

此时in.txt的内容为：95 87，此时正确输出值为182，自测程序输出值为8，原因是两个数都大于80时，程序处理逻辑有误。

2）C++程序实现对拍

编写脚本需要熟悉其语法规则，而且不同操作系统脚本差别较大，为避免再学习新的语言规则或造成混淆，可以使用C++程序实现同样的功能。头文件cstdlib中提供了System函数，可用来执行系统命令。源码如下：

#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 给定测试数据的程序验证工具实现

前面介绍了对拍原理及实现过程，程序的测试数据是随机生成的，下面考虑另一种情形：n组程序测试数据已经给出，如何判断程序是否正确？这种情形常用于以下场合：比赛后官方发布了测试数据但不提供在线判题入口;做书上题目时，通过作者提供的样例判断程序是否正确等。

将前面代码中输入数据和标准输出数据生成过程省略，不难得到实现思路，下面给出字符界面和图形界面两种实现。

5.1 字符界面实现（C++）

在n组测试数据给出的情况下，需要提供n的值、程序文件名称、样例文件主名、样例输出和待测试输出文件扩展名等，源码如下：

#include

#include

#include

#include

using namespace std;

int main（） {

string programName，fileName，ansName，solName;

int n;

cout<<"输入测试数据组数：";

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;

}

假设测试数据有10组，输入文件为add1.in，add2.in...，add10.in，輸出文件为add1.out，add2.out...，add10.out，则在上面代码中，n的值为10;程序文件是指待测试程序编译后的exe文件，如自己写的求和程序编译后为my.exe;输入样例文件主名为add，正确程序输出文件扩展名为.out，待测试输出文件扩展名自己设定，如.my，将它们放到同一个目录下。

5.2 图形界面实现（Java）

在上一节字符界面程序中，程序使用较为烦琐，表现在如下方面：源程序需要手工编译、输入数据较多、出现错误需要去测试文件中核对等。基于上述原因，使用Java语言设计了图形用户界面的验证工具，用户输入样例文件信息并直接在界面中输入源程序，提交后就可以直观地看到对拍结果，提高了验证效率，程序界面如图2所示：

程序实现思路与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）; // 执行编译指令

pr1.waitFor（）;

2）读取样例文件内容函数

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 结束语

本文介绍了对拍工具在程序验证中的应用，首先介绍对拍的概念、应用场景、具体实现过程，在此基础上基于Java语言开发了给定测试数据的图形用户界面的判题工具，为给定样例数据判定程序正确性提供了方便。将该工具设计为线上使用是下一步考虑的工作。

参考文献：

[1] 李煜东.算法竞赛进阶指南[M].郑州：河南电子音像出版社，2018.

[2] 王亚峰.信息学竞赛解题过程研究[J].中小学电教（下），2011（2）：152.

[3] 贾小军.C语言程序设计[M].北京：人民邮电出版社，2014.

[4] 李柯景.浅析C语言中的随机数问题[J].长春大学学报，2008，18（6）：64-68.

[5] 张继军.Java程序设计[M].北京：中国水利水电出版社，2019.

【通联编辑：谢媛媛】