返回

调试程序的常用方法

调试程序的常用方法

前言

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

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

特殊数据构造

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

常见的特殊情况有:

  1. 答案最大值
  2. 答案最小值
  3. 最大数据范围
  4. 最小数据范围

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

序列问题

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

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

树上问题

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

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

图上问题

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

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

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

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

随机数据对拍

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

在进行对拍前,需要准备:

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

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

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

数据生成器

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

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

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

#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 即可。

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

期望程序

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

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

对拍器

对拍器是对拍的中枢,功能流程如下:

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

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

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

批处理版本:

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

c++ 版本:

#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 后,放在同一目录下,运行对拍器即可开始对拍了。

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

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

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

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

当范围更大时,需要注意的几点是:

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

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

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

Licensed under CC BY-NC-SA 4.0