对数器的概念
在做oj竞赛时，有时候写出了解法却并不确定自己的解法是否可以ac，即使有些竞赛可以重复提交，但不知道测试数据往往也不知道错在哪里。这时候就可以手写一个对数器来测试一下自己的代码了。
对数器的逻辑是，先写一个纯暴力解法，正确率高，再写一个优化解法，就是想测试的解法，再根据题目各数据范围用随机数做为输入，同时运行两个解法，看结果是否相同，如果不同就打印输入输出，如果大量随机样本测试后两方法结果都相同，则说明测试方法正确。
实现对数器
以一道oj题为例
1.编写测试解法
待测试解法
float xn,xm; //到达边缘前，每段走的n和m
int yun,yum; //剩余距离
int ixn,ixm;
bool lowd(float n,float m,float d){
return n*n+m*m <= d*d;
}
int func1(int n,int m,int d){
n--;m--;
int t = 0;
int r = 0,c = 0; //小明的坐标
xn = d/sqrt(n*n+m*m)*n;
xm = d/sqrt(n*n+m*m)*m;
//xn xm取整
//此时ixn^2+ixm^2必然小于等于d^2
while(!(r==n&&c==m)){
t++;
yun = n-r;
yum = m-c;
//靠边走
if(r==n)c = c+(int)d>m?m:c+(int)d;
else if(c==m)r = r+(int)d>n?n:r+(int)d;
else if((yun*yun+yum*yum)<=d*d)break;
else{
xn = d/sqrt(yun*yun+yum*yum)*yun;
xm = d/sqrt(yun*yun+yum*yum)*yum;
ixn = (int)(xn+1);
ixm = (int)(xm+1);
while((ixn*ixn+ixm*ixm)>d*d){
if(ixm>ixn)ixm-=1;
else ixn-=1;
}
r+=ixn;
c+=ixm;
}
}
return t;
}2.编写暴力解法
用于对比的暴力解法
struct P{
int x,y,t;
P(){
}
P(int tn,int tm,int tt){
x = tn;y = tm;t = tt;
}
};
int seen[1001][1001]; //走过的点
int func2(int n,int m,int d){
for(int i = 0;i < 1001;i++)
for(int j = 0;j < 1001;j++)
seen[i][j] = 0;
if(n==1&&m==1)return 0;
queue<P> que;
P p,newP;
que.push({1,1,0});
while(que.empty()==false){
p = que.front();
que.pop();
newP.t = p.t+1;
for(int xa = (int)-d;xa <= d;xa++)
for(int ya = (int)-d;ya <= d;ya++){
newP.x = p.x+xa;
newP.y = p.y+ya;
//越界或走过
if(newP.x<1||newP.y<1||newP.x>n||newP.y>m||seen[newP.x][newP.y])continue;
//cout << newP.x << " " << newP.y << endl;
if(lowd(newP.x-p.x,newP.y-p.y,d)){
if(newP.x == n&&newP.y == m){
return newP.t;
}
seen[newP.x][newP.y] = 1;
que.push(newP);
}
}
}
return -1;
}3.实现随机输入及循环测试
随机输入
#include<ctime>
#include<stdlib>
int main(){
int n,m;
float d;
srand((int)time(0));
for(int i = 0;i < 1000;i++){
n = rand()%1000+1;
m = rand()%1000+1;
d = rand()%100*1.0/10;
if(d<1)d=3;
int t1 = func1(n,m,d);
int t2 = func2(n,m,d);
if(t1!=t2){
printf("%-5d%-5d%-10.1ffunc1: %-5dfunc2: %-5d\terror!!\n",n,m,d,t1,t2);
return 0;
}
else printf("\tok\n");
}
cout << "no error" << endl;
return 0;
}4.运行查看结果
可以看到该输入下，测试方法输出为129，暴力方法为122，所以测试方法有误，这时就需要修改或换一个解法了。
或者还可以改一下测试循环次数和变量数据范围，看一下10个测试在该输入范围下大概能过几个。
for(int i = 0;i < 10;i++){
n = rand()%1000+1;
m = rand()%1000+1;
d = rand()%100*1.0/10;
if(d<1)d=3;
printf("%-5d%-5d%-10.1f",n,m,d);
int t1 = func1(n,m);
printf("func1: %-5d",t1);
int t2 = func2();
printf("func2: %-5d",t2);
if(t1!=t2){
printf("\terror!!\n");
}
else printf("\tok\n");
}运行结果
