“对拍”方法在程序验证中的应用
作者: 谢玉韬 徐剑 李庆英
摘要:在编程实践中,如何验证所写程序是否正确有很多方法,“对拍”是常用的一种。介绍了“对拍”的基本概念、应用场景,以两个数求和为例详细说明了“对拍”的过程,在此基础上使用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());