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

作者: 谢玉韬 徐剑 李庆英

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

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

上一篇 点击页面呼出菜单 下一篇