“对拍”方法在程序验证中的应用
作者： 谢玉韬 徐剑 李庆英
摘要：在编程实践中，如何验证所写程序是否正确有很多方法，“对拍”是常用的一种。介绍了“对拍”的基本概念、应用场景，以两个数求和为例详细说明了“对拍”的过程，在此基础上使用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 <iostream>
#include <ctime>
#include <cstdlib>
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<<rand2（1，100）<<" "<<rand2（1，100）<<endl;
return 0;
}
2）编写确定正确的程序（std.cpp）
#include <iostream>
using namespace std;
int main（） {
int a， b;
cin >> a >> b;
cout << a + b << endl;
return 0;
}
3）编写自己的程序（my.cpp）
#include <iostream>
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 <iostream>
#include <cstdlib>
using namespace std;
int main（） {
while（true） {
system（"gen.exe>in.txt"）;
system（"std.exe<in.txt>stdout.txt"）;
system（"my.exe<in.txt>myout.txt"）;
if（system（"fc stdout.txt myout.txt"））{
cout<<"wrong";
break;
}
}
return 0;
}
5 给定测试数据的程序验证工具实现
前面介绍了对拍原理及实现过程，程序的测试数据是随机生成的，下面考虑另一种情形：n组程序测试数据已经给出，如何判断程序是否正确？这种情形常用于以下场合：比赛后官方发布了测试数据但不提供在线判题入口;做书上题目时，通过作者提供的样例判断程序是否正确等。
将前面代码中输入数据和标准输出数据生成过程省略，不难得到实现思路，下面给出字符界面和图形界面两种实现。
5.1 字符界面实现（C++）
在n组测试数据给出的情况下，需要提供n的值、程序文件名称、样例文件主名、样例输出和待测试输出文件扩展名等，源码如下：
#include <iostream>
#include <string>
#include <sstream>
#include <cstdlib>
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<<programName<<"<"<<fileName<<i<<".in>"<<fileName<<i<<solName;
system（oss1.str（）.c_str（））;
oss2<<"fc "<<fileName<<i<<solName<<" "<<fileName<<i<<ansName;
system（oss2.str（）.c_str（））;