对拍程序 x
一、介绍
在做题或者正式比赛过程中总会把水题做水做乱,但因为样例有坑所以直接过了样例,然后拿去评测结果发现全WA。那如何在这种情况下检查自己程序或算法的正确性呢?对拍是一个简便省事的方案。
所谓“对拍”,顾名思义,就是让两者相互比对。所谓“两者”,一是你要测试的程序,二是一个答案在该程序在一定范围(时间/空间)内结果必定正确的程序(一般是用暴力求解的程序)。
两个程序准备好编译好了以后,就可以开始准备测试用的输入样例了。但是输入样例要是人为准备起来的话肯定浪费时间还费脑,更别提在正式比赛的时候了。人脑靠不住,那就靠电脑。
为了让测试的样例更全面,我们可以用伪随机数的方法。我们需要用到这几个高贵妖艳的头文件:
#include <cstdio>
#include <ctime>
#include <cstdlib>
在高中数学的统计知识中学过的随机抽样,可以用随机数表法选取一些随机的数值。在生成随机数时也是用这个原理。首先利用srand()函数在随机数表中找一个点,作为取随机数的起始点。但是如何做到每次选不同的起始点来取数呢?时间是一直在变化的,所以用time(0)取系统时间放入srand()函数中去,每次取的起始点都不一样。如果用固定值的话,每次取得的随机数都会是一样的。
接下来,就按照输入格式用rand() 函数将输入样例的每个变量赋随机值。考虑到输入数据的范围问题,若在0~n的范围内,rand()%n就可以使随机数范围控制在0~n内了;若是在1~n内,因为随机数下限为0,所以rand()%(n-1)+1就把随机数控制在了该范围内。以此类推,若在m~n(m<=n)范围内,生成随机数的公式就为rand()%(n-m)+m。
最后将变量严格按输入格式输出就好了,后续步骤可以把输出的数据添加到 .in文件里。
有了相比对的程序,有了随机数生成器,现在就差一个“发动机”兼“处理机”了。
为了进行多次对拍以及处理对拍程序输出的异同,我们需要一个程序可以进行给定次数下的对拍,并且在有结果不同时停止。写这个程序时需要用到这个奇淫的头文件:
#include <windows.h>
首先我们要人为规定进行对拍的次数,在这里我就先规定 t = 100,即进行100次对拍。然后在一层while(t--)的循环里进行对拍。在循环里层,我们需要把随机数生成器生成的数据通过奇技淫巧加入 .in文件里,然后将 .in文件分别通过奇技淫巧交给两个程序运行,最后比对两个程序 .out文件的内容,若相同,则继续下一次对拍,若不同,则停止对拍。注意要把所有.exe文件放在同一个文件夹中,运行对拍程序即可。
二、程序举例
a+b prob.
force.cpp
#include <cstdio> int main()
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",a+b);
return ;
}
force2.cpp
#include <cstdio> int main()
{
int a,b;
scanf("%d%d",&a,&b);
while(b--) a++;
printf("%d\n",a);
return ;
}
data.cpp
#include <cstdio>
#include <ctime>
#include <cstdlib> using namespace std; int main()
{
srand(time());
int a,b;
a=rand(); b=rand();
printf("%d %d",a,b);
return ;
}
duipai.cpp
#include <cstdio>
#include <windows.h> using namespace std; int main()
{
int t=;
while(t--)
{
system("data>a+b.in");
system("force<a+b.in>force.out");
system("force2<a+b.in>force2.out");
if(system("fc force.out force2.out")) break;
}
system("pause");
return ;
}
高精度加法 prob.
gjd_ac.cpp
#include<cstdio>
#include<cstring> char num1[],num2[];
int sum[],a[],b[]; int main()
{
int i=,j=,len1=,len2=,temp=;
bool flag=false,flag2=false; gets(num1);
len1=strlen(num1);
for(i=,j=len1-; i<len1,j>=; i++,j--)
a[j]=num1[i]-''; gets(num2);
len2=strlen(num2);
for(i=,j=len2-; i<len2,j>=; i++,j--)
b[j]=num2[i]-''; if(len2>len1) len1=len2;
for(i=; i<=len1; i++)
{
sum[i]=a[i]+b[i]+temp;
temp=;
if(sum[i]>=)
{
temp++;
sum[i]=sum[i]%;
}
}
for(i=len1; i>=; i--)
{
if(sum[i]==&&flag2==false) flag=false;
else
{
flag=true;
flag2=true;
}
if(flag==true)printf("%d",sum[i]);
}
if(flag==false)printf("");
return ;
}
gjd_wa.cpp
#include <iostream>
#include <cstring> using namespace std; char a[],b[];
int aa[],bb[],sum[]; int main(void)
{
cin>>a;
int i,lena=strlen(a);
for(i=; i<lena; i++)
aa[lena--i]=a[i]-''; cin>>b;
int lenb=strlen(b);
for(i=; i<lenb; i++)
bb[lenb-i-]=b[i]-''; if(lena>lenb) lenb=lena;
int temp=;
for(i=; i<lenb; i++)
{
sum[i]=aa[i]+bb[i]+temp;
temp=sum[i]/;
sum[i]%=;
}
while(temp>)
{
sum[lenb]+=temp%;
temp/=;
}
if(sum[lenb]!=)lenb+=;
bool flag=false;
for(i=lenb-; i>=; i--)
{
if(sum[i]==&&flag==false)continue;
if(sum[i]!=)flag=true;
cout<<sum[i];
}
if(flag==false)cout<<'';
return ;
}
dat.cpp
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <iostream> using namespace std; int main()
{
srand(time());
int lena=rand()%;
int lenb=rand()%;
for(int i=; i<lena; i++) printf("%d",rand()%);
printf("\n");
for(int i=; i<lenb; i++) printf("%d",rand()%);
return ;
}
duip.cpp
#include <cstdio>
#include <windows.h> using namespace std; int main()
{
int t=;
while(t--)
{
system("dat>gjd.in");
system("gjd_ac<gjd.in>gjd_ac.out");
system("gjd_wa<gjd.in>gjd_wa.out");
if(system("fc gjd_ac.out gjd_wa.out")) break;
}
system("pause");
return ;
}
转自:大佬
End.
最新文章
- request.getParameter()、request.getInputStream()和request.getReader()
- response项目的各个写法
- 黑马程序员+ADO.Net基础(下)
- Daikon Forge GUI 制作UI面板
- C++中虚函数的作用浅析
- Java构建工具:如何用Maven,Gradle和Ant+Ivy进行依赖管理
- 仿淘宝颜色属性选择展示代码(jQuery)
- [ES6] 17. Set
- C#操作Office- Cannot find the interop type that matches the embedded interop type &#39;Microsoft.Office.Interop.Excel.Application&#39;
- Hive入门学习--HIve简介
- Linux内核入门到放弃-时间管理-《深入Linux内核架构》笔记
- 同一个dll 不同路径下注册 一个失败 一个成功
- Django框架----权限组件(具体代码实现)
- js 时间戳转特定格式的日期
- jquery滚动条平滑滑动
- Orleans实战目录
- UWP 轨道视图Orbit View
- .NET:事务、并发、并发问题、事务隔离级别、锁等相关资料整理
- IO 之 InputStream 和 Reader
- 以打字形式展示placeholder的插件