小朋友学算法：对拍程序

素颜马尾好姑娘i 2022-02-04 23:39 234阅读 0赞

# 一、介绍 #

在做题或者正式比赛过程中，有时候因为样例有坑所以直接过了样例，然后拿去评测结果发现全WA。那如何在这种情况下检查自己程序或算法的正确性呢？对拍是一个简便省事的方案。

所谓“对拍”，顾名思义，就是让两者相互比对。所谓“两者”，一是你要测试的程序，二是一个答案在该程序在一定范围（时间/空间）内结果必定正确的程序（一般是用暴力求解的程序）。

两个程序准备好编译好了以后，就可以开始准备测试用的输入样例了。但是输入样例要是人为准备起来的话肯定浪费时间还费脑，更别提在正式比赛的时候了。人脑靠不住，那就靠电脑。

为了让测试的样例更全面，我们可以用伪随机数的方法。我们需要用到这几个的头文件：

#include <ctime>
    #include <cstdlib>

首先利用srand()函数在随机数表中找一个点，作为取随机数的起始点。但是如何做到每次选不同的起始点来取数呢？时间是一直在变化的，所以用time(0)取系统时间放入srand()函数中去，每次取的起始点都不一样。如果用固定值的话，每次取得的随机数都会是一样的。  
　　接下来，就按照输入格式用rand() 函数将输入样例的每个变量赋随机值。考虑到输入数据的范围问题，若在0~n的范围内，rand()%n就可以使随机数范围控制在\[0, n)内了;若是在\[1, n)内，因为随机数下限为0，所以rand()%(n-1)+1就把随机数控制在了该范围内。以此类推，若在\[m, n)范围内，生成随机数的公式就为rand()%(n-m)+m。

最后将变量严格按输入格式输出就好了，后续步骤可以把输出的数据添加到 .in文件里。

有了相比对的程序，有了随机数生成器，现在就差一个“发动机”兼“处理机”了。

为了进行多次对拍以及处理对拍程序输出的异同，我们需要一个程序可以进行给定次数下的对拍，并且在有结果不同时停止。写这个程序时需要用到这个头文件：

#include <windows.h>

首先我们要人为规定进行对拍的次数,在这里咱们可以规定 cnt = 100,即进行100次对拍。然后在一层while(cnt–)的循环里进行对拍。在循环里层，我们需要把随机数生成器生成的数据通过代码写入 .in文件里，然后将 .in文件分别通过两个程序运行，最后比对两个程序 .out文件的内容，若相同，则继续下一次对拍，若不同，则停止对拍。注意要把所有.cpp文件放在同一个文件夹中，运行对拍程序即可。

# 二、程序举例 #

### 1 add.cpp ###

#include <stdio.h>
    
    int main()
    {
        int a,b;
        scanf("%d %d", &a, &b);
        printf("%d\n", a+b);
        
        return 0;
    }

### 2 add2.cpp对照程序 ###

#include <stdio.h>
    
    int main()
    {
        int a,b;
        scanf("%d %d",&a, &b);
        while(b--) 
    	{
    		a++;
    	}
    	
        printf("%d\n", a);
        
        return 0;
    }

注意，假如a + b = c，则b自减1和a自加1后，仍有a + b = c。所以这个程序可以用来检验上一个加法程序是否正确。

### 3 data.cpp生成随机数据 ###

#include <stdio.h>
    #include <ctime>
    #include <cstdlib>
    using namespace std;
    
    int main()
    {
        srand(time(0));
        
        int a,b;
        a=rand();
    	b=rand();
        
        printf("%d %d",a,b);
        
        return 0;
    }

### 4 对拍程序 ###

#include <stdio.h>
    #include <windows.h>
    using namespace std;
    
    int main()
    {
        int cnt = 100;
        
        while(cnt--)
    	{
    		system("g++ data.cpp -o data");		// compile to generate data.exe 
            system("data > a+b.in");			// run data.exe to generate data, and write the data to a+b.in
            system("g++ add.cpp -o add");
            system("add < a+b.in > add.out");  	// force.exe read data from a+b.in, then write the result to force.out
    		system("g++ add2.cpp -o add2");	
            system("add2 < a+b.in > add2.out");
            
            if(system("fc add.out add2.out")) 	// file compare
    		{
    			break;
    		}
        }
        
        system("pause");
        
        return 0;
    }

运行duipai.cpp后，所得结果为

![1.png][]

> 少儿编程、信息学竞赛咨询请加微信307591841或QQ群581357582  
> ![信息学竞赛公众号.jpg][.jpg]

[1.png]: /images/20220205/fac4df68465a4e038356094bd5c50d9c.png
[.jpg]: /images/20220205/3e0955a96afa4b47864274c38302bb99.png