首页 / 算法 / 算法竞赛专题解析（16）：附A-测试数据的构造与对拍

算法竞赛专题解析（16）：附A-测试数据的构造与对拍

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法竞赛专题解析（16）：附A-测试数据的构造与对拍，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7356字，纯文字阅读大概需要11分钟。

内容图文

本系列文章将于2021年整理出版，书名《算法竞赛专题解析》。

前驱教材是：《算法竞赛入门到进阶》(京东当当 ) 清华大学出版社。

如有建议，请联系：（1）QQ 群，567554289；（2）作者QQ，15512356

??竞赛队员在OJ上做题时，提交到OJ的代码，OJ是如何判断是否正确的？OJ并不看代码，而是使用“黑盒测试”，用测试数据来验证。每一题，OJ都事先设定好很多组输入数据datain和输出数据dataout，参赛队员提交代码后，OJ执行代码，输入datain，产生输出，看是否和dataout完全一致。
??OJ所设定的测试数据，可能非常多而且复杂，队员不可能知道，更不能手工一个个进行验证，这时要自己构造测试数据，并且用两种代码进行对比测试。包括以下两个任务：
??（1）构造数据。包括输入和输出数据。如果输入情况复杂，不能方便手工构造，而要编一个小程序，随机生成。输出数据，则要通过下面的低效率代码来生成。
??（2）两种代码。用两种算法写代码进行对比：低效率代码、高效率代码。被称为“对拍”。
??低效率代码。一般用暴力法实现，代码简单、逻辑正确，它因为效率低无法通过OJ的时间限制，它的用途是做为基准（benchmark）代码，产生正确的输出数据。
??高效率代码，准备提交到OJ。把它产生的输出数据，与低效率代码产生的输出数据进行对比，如果一致，就认为是正确的，可以提交了；如果不一致，可以找到那些不一致的数据，用来修改程序。测试数据非常重要，往往能帮助编程者找到代码的错误所在。

A.0 随机数基础

??构造输入数据，需要用到随机数。
??传统的c++98只能产生一个较小的随机数；如果编译器支持c++11，那么可以产生一个很大的随机数，用起来简单得多。
1、c++98随机数
??与随机数相关的函数和变量有：
??srand(seed)：产生以seed为种子的随机数列。对一个seed种子，产生的随机数列是固定的，所以是“伪随机”的。要产生“真”随机数列，就需要一个“随机”的seed，一般用当前时间做seed。
??time(0)：返回当前时间，即从1970.1.1日零时到现在的秒数。
??rand()：返回[0, RAND_MAX]内的一个随机正整数。
??RAND_MAX：一般有RAND_MAX = 32767。

2、c++11随机数
??用c++11的3个函数，能简单地获得大随机数。
??mt19937：随机数产生器[1]，返回一个unsigned int的32位无符号随机数。
??mt19937_64：返回一个64位无符号随机整数。
??uniform_int_distribution[2]：在指定区间内生成一个随机整数。

??下面是演示代码。

        #include <bits/stdc++.h>
using namespace std;
int main(){   
    mt19937 u32Rnd(time(0));              //32位
    cout << "32: " << u32Rnd() << endl;   //打印一个无符号32位随机整数
    cout << "32: " << u32Rnd() << endl;   //再打印一个
                                          //如果用printf打印，注意输出的格式
    mt19937_64 u64Rnd(time(0));           //64位
    cout << "64: " << u64Rnd() << endl;   //打印一个无符号64位随机整数

    uniform_int_distribution<> distrib(-100, 100);    //设置随机数范围
    cout << "[32]: " << distrib(u32Rnd) << endl;      //打印[-100,100]内的一个随机数
    cout << "[64]: " << distrib(u64Rnd) << endl;      

    return 0;
}

??输出的例子：

        32: 1575274362
32: 3712921037
64: 8709987447837980106
[32]: 67
[64]: -20

A.1 构造负数和实数

??c++98环境，需要[-n, n]内的随机数时，先产生一个[0, 2n]的正随机数，然后再减去n。
??c++11环境，直接用uniform_int_distribution设置范围。
??需要实数时，先产生一个大的随机正整数，然后除以10的幂。

A.2 构造极大范围内的随机数

??c++11可以直接产生大随机数。下面是c++98环境的用法。

  1. 生成[0, 1000000]内的随机数
    ??rand() 只能生成大小在[0, RAND_MAX]内的随机数，RAND_MAX = 32767。
    ??如何用rand()生成大随机数？有2个方法：
    ??（1） rand()*rand()
    ??这方法很简单，但是缺点是生成的几乎全是合数，很少有素数。
    ??（2）用组合的方法，把3个随机数组合起来，得到一个24位的随机数。
        unsigned long ulrand(){      //生成一个大随机数
    return (
             (((unsigned long)rand()<<24)& 0xFF000000ul)
            |(((unsigned long)rand()<<12)& 0x00FFF000ul)
            |(((unsigned long)rand())    & 0x00000FFFul));
}
  1. 生成 [MIN, MAX]之间的一个随机数
        const int MAX = 1000000;    //自己定义MAX和MIN 
const int MIN = 0;
int big_rand;               //大随机数
big_rand = ulrand() % (MAX - MIN + 1) + MIN;

A.3 去掉重复的随机数

??上面生成的随机数，很多是重复的。如何去掉100万个数中的重复数字？而且要求去重后不改变剩下数据的顺序。
??因为数太多，所以不可能用暴力法一个个对比。用unique()函数去重则会改变顺序。
??简单又快的方法是用hash去重：

        int myhash[MAX];     //hash表
int mynum[MAX];      //记录去重后的随机数

??下面处理随机数big_rand，把重复的去掉。

        if(myhash[big_rand] == 0) {   //第big_rand位置还没有
     myhash[big_rand]=1;      //随机数big_rand ，登记在myhash[]的第big_rand个位置
     mynum[num]= big_rand;    //记录随机数
     num++;                   //记录随机数的数量
}

A.4 例题

??用下面的例题演示如何构造大量的不重复的测试数据。

hdu 1425 sort
给你n个整数，请按从大到小的顺序输出其中前m大的数。
输入：每组测试数据有两行，第一行有两个数n, m(0 < n, m < 1000000)，第二行包含n个各不相同，且都处于区间[-500000, 500000]的整数。
输出：对每组测试数据按从大到小的顺序输出前m大的数。

（1）c++98环境
??Hdu 1425的测试数据构造代码：

        #include <bits/stdc++.h>
using namespace std;
const int MAX  = 1000000;    //100万个数
const int MIN  = 0;
int myhash[MAX]={0};         //用hash查重
int mynum[MAX];              //记录去重后的随机数

unsigned long ulrand(){      //生成一个大随机数
    return (
      (((unsigned long)rand()<<24)& 0xFF000000ul)
     |(((unsigned long)rand()<<12)& 0x00FFF000ul)
     |(((unsigned long)rand())    & 0x00000FFFul));
}
int main(){
    int big_rand;            //大随机数
  //printf("system: RAND_MAX= %d\n", RAND_MAX);  //查看系统随机数的最大值，一般是32767
    srand(time(0));          //用当前时间做随机数种子
//本题需要不同的随机数，用hash的方法来去重
     int num = 0;            //去重后随机数的数量
     for(int i=0; i< MAX; i++){      //hash
        big_rand = ulrand() % (MAX-MIN + 1) + MIN;  //[MIN,MAX]之间的一个随机数
        if(myhash[big_rand] == 0){   //用hash查重
           myhash[big_rand]=1;       //数字big_rand，登记在big_rand这个位置
           mynum[num]= big_rand;     //记录随机数
           num++;                    //最后产生 num-1 个随机数
        }
     }
     big_rand = ulrand() % (MAX-MIN + 1) + MIN;
     printf("%d %d\n",num, big_rand %(num +1));  //case的第一行

     int k= 500000; //题目要求[-500000,500000]内的数字
     for(int i=0; i<= num-1; i++){
        if(i< num-1)      printf("%d ", mynum[i]-k);   //有正有负
        if(i == num-1)    printf("%d\n", mynum[i]-k);  //最后一个，末尾没有空格
     }
	return 0;
}

（2）c++11环境

        #include <bits/stdc++.h>
using namespace std;
const int MAX  = 1000000;    //100万个数
const int MIN  = 0;
int myhash[MAX]={0};         //用hash查重
int mynum[MAX];              //记录去重后的随机数

int main(){
    int big_rand;            //大随机数
//本题需要不同的随机数，用hash的方法来去重
     int num = 0;            //去重后随机数的数量
     mt19937 u32Rnd(time(0)); 
     uniform_int_distribution<> distrib(MIN, MAX);

     for(int i=0; i< MAX; i++){      //hash
        big_rand = distrib(u32Rnd);    //[MIN,MAX]之间的一个随机数
        if(myhash[big_rand] == 0){   //用hash查重
           myhash[big_rand]=1;       //数字big_rand，登记在big_rand这个位置
           mynum[num]= big_rand;     //记录随机数
           num++;                    //最后产生 num-1 个随机数
        }
     }
     big_rand = distrib(u32Rnd);
     printf("%d %d\n",num, big_rand %(num +1));  //case的第一行

     int k= 500000; //题目要求[-500000,500000]内的数字
     for(int i=0; i<= num-1; i++){
        if(i< num-1)      printf("%d ", mynum[i]-k);   //有正有负
        if(i == num-1)    printf("%d\n", mynum[i]-k);  //最后一个，末尾没有空格
     }
	return 0;
}

（3）运行
??上面的两个代码在一次运行后，从生成的100万个随机数中，得到约63万个不重复的数。
??设代码的文件名是hdu1425，执行代码，输出到文件data.in：

        D:\>hdu4585 >data.in

A.5 对拍

??把程序提交到OJ之前，要先检验程序的正确性。前面已经获得了输入测试数据，那么输出数据如何产生?此时需要尽快写一个代码，它的逻辑和代码很简单，但是保证结果是正确的。
1、对拍的多个代码
??下面以Hdu 1425为例，给出3个实现：暴力的冒泡代码、sort排序、hash算法。
??（1）冒泡排序
??冒泡算法很容易写，但是它的时间复杂度是O(\(n^2\))，如果排序100万个数，时间长达数小时，不能作为benchmark。
??不过，由于冒泡排序的代码非常简单，在赛场能快速编码，那么可以用小规模的输入测试数据，例如对10万个数排序，运行时间就能接受了。
??（2）sort排序
??下面代码也能通过OJ测试，不过这里把它看成benchmark，用来验证后面hash算法的正确性。

        #include<bits/stdc++.h>
using namespace std;
int a[1000001];    		               //记录数字
#define swap(a, b) {int temp = a; a = b; b = temp;} //交换
int n, m;
int main(){
    while(~scanf("%d%d", &n, &m)){
        for(int i=1; i<=n; i++)  scanf("%d", &a[i]);//scanf比cin快
        sort(a + 1, a + n + 1);
        for(int i = n; i >= n-m+1; i--){   //打印前m大的数，反序打印
            if(i == n-m+1)  printf("%d\n", a[i]);
            else            printf("%d ",  a[i]);
        }
    }
    return 0;
}

??设代码的文件名是sort，执行代码，读取输入data.in，输出到文件sort.out

        D:\>sort <data.in >sort.out

（3）hash算法

        #include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000001;
int a[MAXN];
int main(){
    int n,m;
    while(~scanf("%d%d", &n, &m)){
        memset(a, 0, sizeof(a));
        for(int i=0; i<n; i++){
            int t;
            scanf("%d", &t); //此题数据多，如果用很慢的cin输入，肯定TLE
            a[500000+t]=1;    //数字t，登记在500000+t这个位置
        }
        for(int i=MAXN; m>0; i--)
            if(a[i]){
                if(m>1)  printf("%d ", i-500000);
                else      printf("%d\n", i-500000);
                m--;
            }
    }
    return 0;
}

??设代码的文件名是hash，执行代码，读取输入data.in，输出到文件hash.out

        D:\>hash <data.in >hash.out

2、比较2个代码的输出是否一样
??Windows：fc命令

        D:\>fc sort.out hash.out /n

??Linux：diff命令

        [root]#diff -c hash.out sort.out

A.6 统计执行时间

??代码运行的时间是多少，能通过OJ的时间限制吗？一般情况下，通过分析算法的复杂度就足够估算运行时间了。如果确实想知道运行时间，可以用下面的代码计时（windows环境）。不过，个人电脑和OJ的服务器速度并不同，而且还有输入输出的时间，所以下面的代码只能作为参考。

        #include<bits/stdc++.h>
using namespace std;
int main(){ 
   	clock_t start, end;
  	start = clock();                                  //开始时间
    system("d:\\hash <d:\\data.in >d:\\data.out");    //运行hash代码，注意目录
   	end = clock();                                    //结束时间
  	cout << (double)(end - start) / CLOCKS_PER_SEC << endl;      //输出时间
}

  1. https://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine ??

  2. https://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution ??

原文：https://www.cnblogs.com/luoyj/p/13209093.html

内容总结

以上是互联网集市为您收集整理的算法竞赛专题解析（16）：附A-测试数据的构造与对拍全部内容，希望文章能够帮你解决算法竞赛专题解析（16）：附A-测试数据的构造与对拍所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1248108.html

来源：【匿名】