对拍是什么
对拍,是一个比较实用的工具。它能够非常方便地对于两个程序的输出文件进行比较,可以帮助我们实现一些自动化的比较输出结果的问题。
众所周知,每一道编程题目,都会有某种正解能拿到满分;当我们想不出正解时,我们往往可以打暴力代码来获取部分分数。
但是,当我们觉得有思路写正解,但又担心自己正解写的不对,而恰好,我们又有一个能够暴力骗分的代码。这个时候就可以用到对拍。 暴力骗分代码必须保证正确性,最多只是超时,不能出现答案错误的情况。
这样,我们可以造多组数据,让暴力骗分的程序跑一遍,再让我们自己写的正解跑一遍,二者进行多次对比。如果多组数据都显示二者的输出结果一样,那么这个正解大概率没问题。相反地,如果两组数据不同,我们就找到了一组错误数据,方便调试,找到正解哪里出了问题。
这便是对拍。其作用也在上文提出。
对拍的实现
准备基本代码
首先,我们要有2份代码,一份是这一道题“你写的正解”代码,另一份是同一道题“你打的暴力”代码。
为了方便,我们先用 A+B problem 来演示对拍。
自己的代码: std.cpp
#include <cstdio>
using namespace std;
int main()
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", a + b);
return 0;
}
暴力代码:baoli.cpp
#include <cstdio>
using namespace std;
int main()
{
int a, b;
scanf("%d%d", &a, &b);
int ans = 0;
int i;
for (i = 1; i <= a; i++)
ans++;
for (i = 1; i <= b; i++)
ans++;
printf("%d\n", ans);
return 0;
}
两份代码有了,我们把它放在同一个文件夹里。这样算是做好了对拍的准备。
制作数据生成器
我们制作的数据要求格式和上面两份代码的输入格式一样。
根据上面,我们可以知道输入的数据为2个数,中间有空格分隔。那么,我们的数据生成器就要输出2个数,中间也要用空格分隔。
#include <cstdio>
#include <cstdlib>
#include <ctime>
int main()
{
srand(time(0));
//这是一个生成随机数随机种子,需要用到 ctime 库
printf("%d %d\n", rand(), rand());
//这样就生成了2个随机数
return 0;
}
运行一下,确实生成了2个随机数。
注:如果不加那个随机种子,生成的随机数每次都是一样的数。
Extra:数据范围
如果我们对于数据范围有要求,那怎么办呢?
要让随机数限定在一个范围,可以采用 “模除加加法” 的方式。
对于任意数,0≤rand()%(a+1)≤a 。
于是 0+k≤rand()%(a+1)+k≤a+k 。
举几个简单的例子:
- 当 a=rand()%2 时,a 的范围:0≤a≤1 。
- 当 a=rand()%2+1 时,a 的范围:1≤a≤2 。
- 要想让 1≤a≤30000 ,则 a=rand()%30000+1 。
但是,这里有个小问题。Windows 系统下 rand() 生成的随机数的范围在0~32767之间。如果我们想要得到比32767更大的随机数怎么办呢?除了换 Unix 系统外,我还有一个小办法,很实用。
比如让 1≤a≤1,000,000
ll random(ll mod)
{
ll n1, n2, n3, n4, ans;
n1 = rand();
n2 = rand();
n3 = rand();
n4 = rand();
ans = n1 * n2 % mod;
ans = ans * n3 % mod;
ans = ans * n4 % mod;
return ans;
}
int main()
{
srand((unsigned)time(0));
ll n;
while (1)
{
n = random(1000000);
cout << n << endl;
}
return 0;
}
看一下输出结果
这种 “暴力” 的方法是不是感到很神奇呢?
对拍代码
标准输入输出代码
标准输入输出指的是:两份基本代码和数据生成代码里不含文件输入输出操作,如 freopen 等。
在这里,我们需要用到一些文件的读写符号。(需用到 库)
system(“A.exe > A.txt”) 指的是运行 A.exe,把结果输出(>)到 A.txt 中。
system(“B.exe < A.txt > C.txt”) 指的是运行 B.exe,从 A.txt 中读入(<)数据,把结果输出(>)到 C.txt 中。
system(“fc A.txt B.txt”) 指的是比较 A.txt 和 B.txt ,如果两个文件里的数据相同返回0,不同返回1。
那么,我们就可以执行这一操作来实现对拍。
- 先让数据生成器输出数据。 system(“data.exe > in.txt”)
- 然后用这个数据跑一遍暴力代码,输出结果。 system(“baoli.exe < in.txt > baoli.txt”)
- 再用这个数据跑一遍你写的正解代码,输出结果。 system(“std.exe < in.txt > std.txt”)
- 把两个结果相比较,判断是不是一样的。 system(“fc std.txt baoli.txt”)
文件输入输出
标准输入输出指的是:两份基本代码和数据生成代码里含有文件输入输出操作,如 freopen 等。
因为基本代码中有文件输入输出,所以我们在对拍代码中不必使用 ‘ < ‘ 、’ > ‘ 等符号对文件进行操作。只需运行一下两个程序,程序会自己输出文件。
这种文件输入输出的模式适合各种大型线下比赛使用。优点在于对拍的时候不用删除 freopen 。
1. 数据生成代码例子:
#include <bits/stdc++.h>
int main()
{
srand(time(0));
freopen("in.in", "w", stdout); //生成 使两份基本代码 将要读入的数据
int a = rand(), b = rand();
printf("%d %d\n", a, b);
}
2. 暴力代码例子:
#include <bits/stdc++.h>
int main()
{
freopen("in.in", "r", stdin); //读入数据生成器造出来的数据
freopen("baoli.txt", "w", stdout); //输出答案
int a, b, ans = 0;
scanf("%d %d", &a, &b);
for (int i = 1; i <= a; ++i)
ans++;
for (int i = 1; i <= b; ++i)
ans++;
printf("%d\n", ans);
}
3. 正解代码例子:
#include <bits/stdc++.h>
int main()
{
freopen("in.in", "r", stdin);
freopen("std.txt", "w", stdout);
scanf("%d %d", &a, &b);
printf("%d\n", a + b);
}
4. 对拍代码
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
while (1) //一直循环,直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
break; //不一样就跳出循环
}
return 0;
}
运行对拍程序
目前,我们有了4份代码。为了实现对拍,我们要把这些代码放在同一个文件夹的同一层里。
并且打开每一份代码,让每一份代码都生成一个同名的 .exe 程序。如下:
然后,打开 duipai.exe ,我们可以看到程序正在对两个输出文件进行比较
找不到差异,说明这两份代码输出的两个文件是一样的。
那么我们可以一直拍着,如果长时间都是找不到差异,那么你写的正解就可能是对的了。
如果找到差异,它会分别返回两个文件的数据,这样我们就有了一组错误数据,方便我们 debug 。
这是存在差异的情况。
程序的优化
节约对拍次数
在对拍时,你有没有发现在 cmd 的黑色框框里面,“找不到差异” 这几行输出的很快,看起来对拍的频率好像很高的样子。实际上,这样浪费了很多次对拍,数据生成需要一定的时间,而文件的读取输出等都需要一定时间。但是两个输出文件的对比却在不停地运行着,数据生成器生成的文件在一定的时间内是相同的,这样就浪费了许多次对拍。
为此,我们可以使每次对拍完毕后休眠1秒,给四个程序留给一定的缓冲时间,使得每次对拍时,数据生成器生成的数据都不同。
那么,我们可以使用 <windows.h> 库里的 Sleep(t) ,t 为时间,单位是毫秒。它可以使程序休眠 t 毫秒。我们可以在每次对拍之后加上 Sleep(1000) ,这样每次对拍之后休眠1秒,就不会出现浪费对拍的情况了。详见下面代码部分。
美化对拍程序
众所周知,每一道编写程序题都有时间限制。那么我们可以用一个计时函数”clock()”,来计算我们写的正解用的时间,判断它是否超时(当然,本地测出的时间和评测机测的时间一般不同),并把所用时间在对拍程序上体现出来。
我们还可以给把一个通过的数据当作一个测试点,还可以给他赋予编号,这些都能在对拍程序直观地体现出来,像下面这样:
#include <iostream>
#include <cstdio>
#include <windows.h>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
int ok = 0;
int n = 50;
for (int i = 1; i <= n; ++i)
{
system("make.exe > make.txt");
system("std.exe < make.txt > std.txt");
double begin = clock();
system("baoli.exe < make.txt > baoli.txt");
double end = clock();
double t = (end - begin);
if (system("fc std.txt baoli.txt"))
{
printf("测试点#%d Wrong Answer\n", i);
}
else if (t > 1000) //1秒
{
printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
}
else
{
printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
ok++; //AC数量+1
}
}
printf("\n");
double res = 100.0 * ok / n;
printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
Sleep(1000); //休眠1秒,为了节约对拍次数。
}
上面造了50个测试点,我们还可以计算程序 AC 多少个点来评个总分。这样可以让我们大致地了解一下编出的程序的正确性。
这样子,对拍的作用就发挥到了极致。
原文链接
C++ 对拍详解 -QT开发中文网C++ 对拍详解
版权声明:本文为博主作者:Qt开发老杰原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/QtCompany/article/details/129883002