电商网站开发prd,文案代写平台,如何用凡科做网站,做公司员工福利的网站都有哪些0x72 随机数据生成与对拍
本节介绍随机数据的生成方式与对拍测试方式。将学习使用C随机数产生器#xff0c;根据题目要求构造各种规模的输入数据#xff0c;用于对自己编写的程序进行检测。同时#xff0c;也将学习编写简单的脚本#xff0c;自动化、批量化运行“数据生成…0x72 随机数据生成与对拍
本节介绍随机数据的生成方式与对拍测试方式。将学习使用C随机数产生器根据题目要求构造各种规模的输入数据用于对自己编写的程序进行检测。同时也将学习编写简单的脚本自动化、批量化运行“数据生成程序”和两份不同的“问题求解程序”并对两份程序的输出结果进行对比——我们把这种过程称为“对拍”。
随机数据生成与对拍可用于一下场景
1.在无法获得实时测评反馈的比赛中思考并实现了一个“高分解法”但实在不会证明自己的结论或者不能确保自己编写的程序是否完全正确。
这种情况下建议斟酌分配一些时间额外编写一份随机数据生成程序、一份用朴素算法求解的程序通常朴素解法时间复杂度高但容易实现不易出错。然后把“高分解法”与“朴素解法”进行对拍看二者的输出结果是否始终保持一致。
2.在平时解题时自己编写的程序无法在Online Judge取得Accepted结果调试很久之后仍未发现错误并且不能下载到题目的测试数据或者虽然能下载到测试数据但发生错误的数据规模过大不容易进行调试。
这时可以编写一个随机数据生成程序再编写一个使用朴素算法的程序或者直接在网络上搜索其他人的AC程序与自己的“错误解法”对拍。我们可以适当调整随机数据的规模控制在易于人工演算和调试的范围内。虽然数据越小出错概率越低但是“对拍”脚本能够批量化执行在成千上万次检测中一般总能找到一个造成错误的小规模数据。
3.有一个不错的构思自己出了一道题目。
此时当然需要生成一些测试数据并且需要用“对拍”来检测自己编写的“标准程序”的正确性。不过除了随机数据外通常还需要增加一些特殊构造的数据保证数据的全面性。
1.随机数据生成
头文件cstdlib(stdlib.h)包含了rand和srand两个函数以及RAND_MAX常量。
RAND_MAX是一个不小于32767的整数常量它的值与操作系统、编译环境有关。一般来说在Windows系统中为32767在类Unix系统中为2147483647。
rand()函数返回一个0~RAND_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 ∼ n − 1 0\sim n-1 0∼n−1之间的随机整数并综合考虑了操作系统和编译器环境的差异对int范围内的 n n n均能正常工作。
#include cstdlib.h
#include ctime
int random(int n)
{return (long long)rand()*rand()%n;
}
int main()
{srand((unsigned)time(0));//...具体内容...
}若要产生随机实数则可以先产生一个较大的随机整数在用它除以10的次幂。若要同时产生负数则可以先产生一个 0 ∼ 2 n 0\sim 2n 0∼2n之间的随机整数再减去 n n n就得到了 − n ∼ n -n\sim n −n∼n之间的随机整数。 随机生成一张 n n n个点 m m m条边的无向图图中不存在重边、自环且必须连通保证 5 ≤ n ≤ m ≤ n ∗ ( n − 1 ) / 4 ≤ 1 0 6 5\leq n\leq m\leq n*(n-1)/4\leq 10^6 5≤n≤m≤n∗(n−1)/4≤106。 pairint,int e[1000005];
mappairint,int,bool h; //防止重边
//先生成一棵树保证连通
for(int i1;in;i)
{int farandom(i)1;e[i]make_pair(fa,i1);h[e[i]]h[make_pair(i1,fa)]1;
}
//再生成剩余的m-n1条边
for(int in;im;i)
{int x,y;do{xrandom(n)1,yrandom(n)1;}while(xy||k[make_pair(x,y)]);e[i]make_pair(x,y);h[e[i]]h[make_pair(y,x)]1;
}
//随机打乱输出
random_shuffle(e1,em1);
for(int i1;im;i)printf(%d %d\n,e[i].first,e[i].second);在树、图结构中有三类特殊数据常用于对程序进行极端情况下的效率测试
1.链形数据——有很长的直径。
就是把 N N N个节点用 N − 1 N-1 N−1条边连成一条长度为 N − 1 N-1 N−1的“链”。这种数据会造成很大的递归深度也是点分治等算法需要特别注意的数据。
2.菊花形数据——有度数很大的节点。
以1号节点为中心 2 ∼ N 2\sim N 2∼N号节点都用一条边与1号节点相连最终1号节点的度数为 N − 1 N-1 N−1。这种数据画出来形似一朵“菊花”缩点等图论算法若处理不当复杂度容易在这种数据上退化。
3.蒲公英形数据。
即链形和菊花形数据的综合。令树的一部分构成链一部分构成菊花再把两部分连接。
在以上三种数据的基础上再添加少量的随机的边即可得到一张包含局部特殊结构、又不失一般性和多样性的图。
2.对拍
假设我们已经编好了三个程序
1.自己编写的“正解”即准备提交测评的程序名为sol.cpp。
该程序从文件data.in中读入输入数据并输出答案到data.out中。
2.自己编写的“朴素解法”程序名为bf.cpp。
该程序从文件data.in中读入输入数据并输出答案到data.ans中。
3.自己编写的随机数据生成程序名为random.cpp。
该程序输出随机数据到文件data.in中。
依次编写这三个程序得到三个可执行文件例如在Windows系统下得到sol.exebf.exe和random.exe。
现在我们需要编写一个脚本循环执行以下过程
1.运行随机数据生成器random。
2.运行“正解”程序sol。
3.运行“朴素解法”程序bf。
4.对比文件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系统对拍程序
#includecstdlib
#includecstdio
#includectime
int main()
{for(int T1;T10000;T){//自行设定适当的路径system(C:\\random.exe);//当前程序已经运行的CPU时间Windows下单位msUnix下单位sdouble stclock();system(C:\\sol.exe);double edclock();system(C:\\bf.exe);if(system(fc C:\\data.out C:\\data.ans)){puts(Wrong Answer);//程序立即退出此时data.in即为发生错误的数据return 0;}else{printf(Accept,测试点 #%d,此时 %.0lfms\n,T,ed-st);}}
}编译运行该C程序即可开始“对拍”过程。
类Unix系统对拍程序
在Windows系统对拍程序的基础上更改system中的路径格式并把fc命令改为diff命令用时单位改为“秒”。
