0x72 随机数据生成与对拍

本节介绍随机数据的生成方法与对拍测试方法。读者将学习使用 $\mathrm{C}++$ 随机数产生器，根据题目要求构造各种规模的输入数据，用于对自己编写的程序进行检测。同时，读者也将学习编写简单的脚本，自动化、批量化运行“数据生成程序”和两份不同的“问题求解程序”，并对两份程序的输出结果进行比对——我们把这种过程称为“对拍”。

随机数据生成与对拍可用于以下场景：

在无法获得实时评测反馈的比赛中，思考并实现了一个“高分解法”，但实在不会证明自己的结论，或者不能确保自己编写的程序是否完全正确。

这种情况下，建议读者酌情分配一些时间，额外编写一份随机数据生成程序、一份用朴素算法求解的程序（通常朴素解法时间复杂度高，但实现简单，不易出错）。然后把“高分解法”与“朴素解法”进行对拍，看二者的输出结果是否始终保持一致。

在平时解题时，自己编写的程序无法在 Online Judge 上取得 Accepted 结果，调试很久仍未发现错误，并且不能下载到题目的测试数据，或者虽然能下载到测试数据，但发生错误的数据规模过大，不容易进行调试。

这时，可以编写一个随机数据生成程序，再编写一个使用朴素算法的程序（或者直接在网络上搜索其他人的AC程序），与自己的“错误解法”对拍。我们可以适当调整随机数据的规模，控制在易于人工演算和调试的范围内。虽然数据越小，出错概率越低，

但是“对拍”脚本能够批量化执行，在成千上万次检测中，一般总能找到一个造成错误的小规模数据。

有一个不错的构思，自己出了一道题目。

此时当然需要生成一些测试数据，并且需要用“对拍”来检测自己编写的“标准程序”的正确性。不过，除了随机数据外，通常还需要增加一些特殊构造的数据，保证测试数据的全面性。

$\spadesuit$ 随机数据生成

头文件 cstdlib (stdlib.h) 包含 rand 和 srand 两个函数, 以及 RAND_MAX 常量。

RAND_MAX 是一个不小于 32767 的整数常量，它的值与操作系统环境、编译器环境有关。一般来说，在 Windows 系统中为 32767，在类 Unix 系统中为 2147483647。

rand() 函数返回一个 $0 \sim \mathrm{RAND}_{\mathrm{MAX}}$ 之间的随机整数 int。

srand(seed) 函数接受 unsigned int 类型的参数 seed，以 seed 为“随机种子”。rand 函数基于线性同余递推式生成随机数，“随机种子”相当于计算线性同余时的一个初始参数，感兴趣的读者可以查阅相关资料。若不执行 srand 函数，则种子默认为 1。

当种子确定后，接下来产生的随机数列就是固定的，所以这种随机方法也被称为“伪随机”。因此，一般在随机数据生成程序 main 函数的开头，用当前系统时间作为随机种子。

头文件 ctime (time.h) 包含 time 函数，调用 time(0) 可以返回从 1970 年 1 月 1 日 0 时 0 分 0 秒（Unix 纪元）到现在的秒数。执行 srand((unsigned)time(0)) 即可初始化随机种子。

下面的程序可作为随机数据生成器的模板，函数 random(n) 返回 $0 \sim n - 1$ 之间的随机整数，并综合考虑了操作系统和编译器环境的差异，对 int 范围内的 $n$ 均能正常工作。

include<stdio>   
#include<ctime>   
int random(int n){ return(long long)rand() \* rand(）%n;   
}   
int main(){ strand((unsigned)time(o)); //…具体内容…   
1

若要产生随机实数，则可以先产生一个较大的随机整数，再用它除以10的次幂。若要同时产生负数，则可以先产生一个 $0\sim 2n$ 之间的随机整数，再减去 $n$ ，就得到了 $-n\sim n$ 之间的随机整数。

【实例】随机生成整数序列

在本节的模板基础上，随机生成 $n \leq 10^{5}$ 个绝对值在 $10^{9}$ 之内的整数。

int n = random(100000) + 1;  
int m = 1000000000;  
for (int i = 1; i <= n; i++) {  
    a[i] = random(2 * m + 1) - m;  
}

【实例】随机生成区间列

在本节的模板基础上，随机生成 $m$ 个 $[1, n]$ 的子区间，这些区间可作为数据结构题目的操作序列。

for (int i = 1; i <= m; i++) { int l = random(n) + 1; int r = random(n) + 1; if (l > r) swap(l, r); printf("%d %d\n", l, r); }

【实例】随机生成树

在本节的模板基础上，随机生成一棵 $n$ 个点的树，用 $n$ 个点 $n - 1$ 条边的无向图的形式输出，每条边附带一个 $10^{9}$ 以内的正整数权值。

for (int i = 2; i <= n; i++) { //从  $2\sim n$  之间的每个点i向1~i-1之间的点随机连一条边 int fa = random(i - 1) + 1; int val = random(100000000) + 1; printf("%d %d %d\n",fa,i,val); }

【实例】随机生成图

在本节的模板基础上，随机生成一张 $n$ 个点 $m$ 条边的无向图，图中不存在重边、

自环，且必须连通，保证 $5 \leq n \leq m \leq n * (n - 1) / 4 \leq 10^{6}$ 。①

pair<int, int> e[1000005]; // 保存数据  
map< pair<int, int>, bool  $>$  h; // 防止重边  
// 先生成一棵树，保证连通  
for (int i = 1; i < n; i++) {  
    int fa = random(i) + 1;  
    e[i] = make_pair(fa, i + 1);  
    h[e[i]] = h[make_pair(i + 1, fa)] = 1;  
}  
// 再生成剩余的 m-n+1 条边  
for (int i = n; i <= m; i++) {  
    int x, y;  
    do {  
        x = random(n) + 1, y = random(n) + 1;  
    } while (x == y || h[make_pair(x, y)]);  
    e[i] = make_pair(x, y);  
    h[e[i]] = h[make_pair(y, x)] = 1;  
}  
// 随机打乱，输出  
random_shuffle(e + 1, e + m + 1);  
for (int i = 1; i <= m; i++)  
    printf("%d%d\n", e[i].first, e[i].second);

在树、图结构中，有三类特殊数据常用于对程序进行极端状况下的效率测试：

1.链形数据——有很长的直径。

就是把 $N$ 个节点用 $N - 1$ 条边连成一条长度为 $N - 1$ 的“链”。这种数据会造成很大的递归深度，也是点分治等算法需要特别注意的数据。

菊花形数据——有度数很大的节点。

以1号节点为中心， $2\sim N$ 号节点都用一条边与1号节点相连，最终1号节点的度数为 $N - 1$ 。这种数据画出来形似一朵“菊花”，缩点等图论算法若处理不当，复杂度容易在这种数据上退化。

蒲公英形数据。

即链形和菊花形数据的综合。令树的一部分构成链，一部分构成菊花，再把两部分

连接。

在以上三种数据的基础上，再添加少量随机的边，即可得到一张既包含局部特殊结构、又不失一般性和多样性的图。请读者自己尝试生成相关的数据。

$\spadesuit$ 对拍

假设我们已经编写好了三个程序：

自己编写的“正解”，即准备提交评测的程序，名为 sol.cpp①。

该程序从文件 data.in 中读取输入数据，并输出答案到文件 data.out 中。

自己编写的“朴素解法”程序，名为 bf.cpp。

该程序从文件 data.in 中读取输入数据，并输出答案到文件 data.ans 中。

自己编写的随机数据生成程序，名为 random.cpp。

该程序输出随机数据到文件 data.in 中。

依次编译这三个程序，得到三个可执行文件，例如在 Windows 系统下得到 sol.exe, bf.exe 和 random.exe。

现在，我们需要编写一个脚本，循环执行以下过程：

运行随机数据生成器 random。
运行“正解”程序 sol。
运行“朴素解法”程序bf。
比对文件 data.out 和 data.ans 的内容是否一致。

Windows 和类 Unix 系统分别有 bat 批处理脚本和 bash 脚本。不过，为了避免介绍一门新的脚本语言，这里就用读者都熟悉的 C++ 语言来编写“对拍”程序。

头文件 cstdlib (stdlib.h) 中提供了一个函数 system，它接受一个字符串参数，并把该字符串作为系统命令执行。例如代码 system("C:\random.exe") 执行 C 盘根目录下的 random.exe 文件。

Windows 系统命令 fc 或类 Unix 系统命令 diff 可以执行文件比对的工作，它们接受两个文件路径，比较二者是否一致。若一致，返回 0，否则返回非零值。

Windows系统对拍程序

include<cstdlib> #include<cstdio> #include<ctime>

int main(){for(int  $\mathrm{T} = 1$  .T<=10000;T++){//自行设定适当的路径system("C:\\random.exe");//当前程序已经运行的CPU时间，Windows下单位ms，Unix下单位sdoublest=clock();system("C:\\sol.exe");doubleed=clock();system("C:\\bf.exe");if(system("fc C:\\data.out C:\\data.ans")){puts("Wrong Answer");//程序立即退出，此时data.in即为发生错误的数据return0;1else{printf("Accepted，测试点%d，用时%.0lfms\n",T,ed-st);11

编译运行该 $\mathrm{C}++$ 程序即可开始“对拍”过程。

类Unix系统对拍程序

在Windows系统对拍程序的基础上，更改system中的路径格式，并把fc命令改为diff命令，用时单位改为“秒”。

到此为止，全书计划讲解的内容就告一段落了。希望读者能够理论联系实践，在充分理解所学知识的同时，认真完成习题，注重思维模型的构建与代码能力的提升，善用数据生成与对拍技巧，独立克服解题困难，并发掘适合自身的比赛策略，最终在算法竞赛带来的挑战中收获乐趣和成就。

0x72_随机数据生成与对拍