调试程序的常用方法

前言

在 OI 赛制的比赛中，高效、恰当地调试程序，是拿到稳定分数的必要条件。只有一次提交机会，意味着本地需要进行大量调试工作，以保证程序在各种各样的输入下都能正常运行。

一般来说，选手会手造特殊数据、对拍随机数据，对程序进行调试。

特殊数据构造

应在开始编码前，就考虑算法在各种极端情况下的表现。

常见的特殊情况有：

答案最大值
答案最小值
最大数据范围
最小数据范围

此外，根据问题的不同，还有不同的特殊情况。

序列问题

序列中，考虑单调递增、单调递减、常值序列。

若有区间询问，考虑询问长度特别小(例如全为单点)、长度特别大(例如全为整个区间)。

树上问题

序列的情况可以搬到树上，此外，还可以考虑：

链
菊花
完全二叉树
菊花上挂链
链上挂单点

图上问题

图上问题同样可以照搬树上问题的情况，还可以考虑：

环，例如全图为一个大环
全部点都不连通
强连通

在完成代码后，可以手造特殊数据，手算答案来补充小样例，若程序出错可以使用小样例进行调试。

而通过手造的样例后，可以用代码生成特殊的大样例来测试程序的复杂度的正确性。

随机数据对拍

随机数据对拍是一种强有力的调试手段。

在进行对拍前，需要准备：

数据生成器(generator)
暴力程序(std)，常常正确性显然而时间复杂度不够优秀。
期望程序(target)，常常正确性不显然而时间复杂度优秀。
对拍器(runner)，用于运行生成器、暴力、期望程序以及对比输出答案。

一般来说，OI 赛制的题目设有小数据范围的部分分，选手可以先打出部分分的代码，再思考正解。
这样一来，暴力代码可以用于对拍，而没有想出正解也能拿到暴力分。
在此过程中，请注意不要随意地对暴力代码进行修改，而是新开文件写正解，保证若最后失败，也能直接交上暴力程序拿分。

若暴力程序编写难度较大，对拍得不偿失，可以考虑放弃对拍。

数据生成器

在对拍中，生成有强度的随机数据是非常必要的。

生成随机数，常用的有 rand() 和 mt19937，后者是 c++11 中强度较高的随机数生成方法。
如果需要使用后者，需要使用 c++11 或以上版本，例如 Dev C++ 在编译命令中加入 -std=c++11 才能使用。

为了保证数据随机，需要设置随机数种子。
以下是一个生成随机序列的例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));//use time as random seed
const int maxn = 1e4 + 100;
int n,a[maxn];
inline int getint(int x)
{
	return (rnd() % x) + 1;//get an integer in [1,x]
}
int main()
{
	freopen("file.in","w",stdout);
	n = getint(10000);//generate n in [1,10000]
	for(int i = 1; i <= n; ++i) a[i] = getint(1000000);
	//output
	printf("%d\n", n);
	for(int i = 1; i <= n; ++i) printf("%d ", a[i]);
	putchar('\n');
	return 0;
}

暴力程序

暴力程序没有什么额外要求，按照 OI 赛制要求的 FILEIO 即可。

1
2
3


freopen("file.in","r",stdin);
freopen("std.out","w",stdout);
...

期望程序

期望程序输入可以与暴力共用，但输出必须不同。

1
2


freopen("file.in","r",stdin);
freopen("ans.out","w",stdout);

对拍器

对拍器是对拍的中枢，功能流程如下：

调用数据生成器生成数据
调用暴力程序得到答案
调用期望程序得到答案
对比两个程序输出的答案

对拍有两种常用的实现方式：批处理实现与 c++实现。

核心的对比答案都使用了系统自带的 fc 函数，因此两种实现差别不大。

批处理版本：

1
2
3
4
5
6
7
8
9


@echo off
    :loop
        datamaker
        std
        myprogram
        fc myprogram.out std.out
    if not errorlevel 1 goto loop
    pause
    go to loop

c++ 版本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


#include <iostream>
#include <windows.h>
using namespace std;
int main()
{
    int T = 200;
    while(T--)
    {
        system("generator.exe");
        system("std.exe");
        system("yourprogram.exe");
        if(system("fc std.out ans.out")) system("pause");
    }
    return 0;
}

将程序编译为 exe 后，放在同一目录下，运行对拍器即可开始对拍了。

一般来说，从小数据开始对拍，用来找出程序潜在的漏洞并加以改进。

生成范围小的随机数据，方便出错时手动调试。而在小数据通过后，生成大数据来检验正确性。

需要注意，生成的数据范围需要在暴力程序可接受范围内。

因此对拍能检验的数据范围是有限的，而仅仅能检验在部分范围内的正确性。

当范围更大时，需要注意的几点是：

数值是否会溢出
数组是否会越界
运行时间是否可接受

其中前两点可以用良好的编程习惯加以避免，而最后一点可以直接生成极限数据检验。

对拍的任务仅仅是检验算法的正确性，而一般情况下，中等数据下运行正确的算法，在极限数据下正确性不会受到太大影响。