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

六月丶

发布于 2022-12-26 17:45:47

20400

代码可运行

文章被收录于专栏：六月-游戏开发六月-游戏开发

运行总次数：0

代码可运行

对数器的概念

在做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");
}

运行结果

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020 年 04 月，如有侵权请联系 cloudcommunity@tencent.com 删除

腾讯云测试服务

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

腾讯云测试服务

登录后参与评论

0 条评论

热度