六月丶

用对数器测试算法是否正确
对数器的概念在做oj竞赛时,有时候写出了解法却并不确定自己的解法是否可以ac,即使有些竞赛可以重复提交,但不知道测...
扫描右侧二维码阅读全文
23
2020/04

用对数器测试算法是否正确

对数器的概念

在做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.运行查看结果
sp_2020-04-23_17-56-46.png
可以看到该输入下,测试方法输出为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");
}

运行结果
sp_2020-04-23_18-07-01.jpg

本文作者:六月丶

本文链接:/index.php/archives/612/

版权声明:如无特别声明,本文即为六月'blog原创,仅代表个人观点,如要转载请务必注明文章出处。
最后修改:2020 年 04 月 23 日 06 : 13 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论