亲宝软件园·资讯

展开

c++ 对数器 c++ 对数器实现示例

机巧的胖子 人气:0
想了解c++ 对数器实现示例的相关内容吗,机巧的胖子在本文为您仔细讲解c++ 对数器的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:c++,对数器,下面大家一起来学习吧。

对数器的作用

对数器用于在自己的本地平台验证算法正确性,用于算法调试,无需online judge。

好处:

对数器的实现代码

首先需要有一个你想要测试的方法,本文利用归并排序算法举例。归并算法代码如下:

//有一个你想要测试的算法,这里以归并排序为例
class Solution {
public:
    static int reversePairs(vector<int>& nums) {
        auto L = 0;
        auto R = nums.size() - 1;
        auto res = 0;
        mergesort(nums, L, R);
        return res;
    }

    //归并排序,从大到小排列(逆序)
    static void mergesort(vector<int>& nums, int L, int R)
    {
        //递归终止条件
        if (L >= R)
        {
            return;
        }
        //序列中心位置计算
        auto mid = (L + ((R - L) >> 1));
        //auto mid = (R + L) / 2;
        //左右序列分别排序
        mergesort(nums, L, mid);
        mergesort(nums, mid + 1, R);

        //归并两个排好序的序列
        merge(nums, L, mid, R);
    }

    static void merge(vector<int>& nums, int L, int mid, int R)
    {
        //临时向量存储归并的结果
        vector<int> tmp(R - L + 1);
        auto pos = 0;
        auto Lp = L;
        auto Rp = mid + 1;
        while ((Lp <= mid) && (Rp <= R))
        {
            tmp[pos++] = (nums[Lp] < nums[Rp]) ? nums[Lp++] : nums[Rp++];
        }
        while (Lp <= mid)
        {
            tmp[pos++] = nums[Lp++];
        }
        while (Rp <= R)
        {
            tmp[pos++] = nums[Rp++];
        }

    	//将排序好部分拷贝至nums数组
        copy(nums, tmp, L, R);
        //nums = tmp;
    }

	//部分数组拷贝函数
    static void copy(vector<int>& nums, vector<int>& tmp, int L, int R)
    {
        auto pos = 0;
        for (auto i = L; i <= R; i++)
        {
            nums[i] = tmp[pos++];
        }
    }
};

准备一个随机数组(样本)生成器,该示例选择size为10,value为30,代码如下:

//函数名:generateRandomVector
//函数功能描述:随机数组(样本)生成器
//函数参数: size    生成数组最大尺寸
//         value   数组每个元素的最大值
//返回值:  vector<int> 生成的数组
//for test
vector<int> generateRandomVector(int size, int value)
{
    //time 函数返回从 1970 年 1 月 1 日午夜开始到现在逝去的秒数,因此每次运行程序时,它都将提供不同的种子值。
    srand((int)time(NULL));//为随机数生成器产生随机种子
    //分配随机大小的数组,产生随机数的范围公式number = (rand()%(maxValue - minValue +1)) + minValue;
    vector<int> result(rand() % (size + 1));
    for (auto i = 0; i < result.size(); i++)
    {
        result[i] = rand() % (value + 1);
    }

    return result;

}

大样本测试,同时还需要准备一个绝对正确的方法,这里用algorithm头文件中的sort函数进行排序,同时测试次数应该尽量大,从而覆盖尽可能所有的实例,如果没有自己算法和绝对正确的算法的结果的比对方法,还需要自己编写结果的比对方法,判断结果是否正确(这里vector重载了比较运算符,直接使用即可),代码如下:

//大样本测试
//函数名:main
//函数功能描述:大样本测试
//函数参数: size    生成数组最大尺寸
//         value   数组每个元素的最大值
//返回值:  vector<int> 生成的数组
//for test
int main()
{
    auto test_time = 50000;//测试次数,设置比较大,排除特殊情况
    auto size = 10;//生成数组最大尺寸
    auto value = 30;//生成数组每个元素的最大值
    auto if_accept = true;//方法是否正确标志位
	for(auto i = 0; i < test_time; i++)
	{
        //拷贝初始化,生成新的数组向量
        vector<int> nums(generateRandomVector(size, value));
        //生成两个临时数组拷贝
        vector<int> nums1(nums);
        vector<int> nums2(nums);

		//绝对正确方法
        sort(nums1.begin(), nums1.end());
		//自己写的方法,想要测试的算法
        Solution::reversePairs(nums2);

		//判断两个向量是否相同,vector类已经重载了比较运算符,不用自己实现,不相同说明算法不正确
		if(nums1 != nums2)
		{
            if_accept = false;
			//输出结果不相等的原始向量
			for(auto c: nums)
			{
                cout << c << " ";
			}
			break;
		}
		
	}
	

	//输出结果
    cout << (if_accept ? "nice!\n" : "false!\n");
    
}

运行上述代码,由于我们测试样本次数为50000次,而样本量本身比较小(size = 10, value = 30)可以得到结果,如下图所示,所以我们默认已经覆盖了所有情况,我们的算法是正确的。

在这里插入图片描述

将归并排序算法改为降序排列,重新运行可得:

在这里插入图片描述

由于每次设定的种子源是随机的,所以每次运行可以得到不同的序列。

在这里插入图片描述

完整代码

附完整代码:

// 对数器.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

//有一个你想要测试的算法,这里以归并排序为例
class Solution {
public:
    static int reversePairs(vector<int>& nums) {
        auto L = 0;
        auto R = nums.size() - 1;
        auto res = 0;
        mergesort(nums, L, R);
        return res;
    }

    //归并排序,从大到小排列(逆序)
    static void mergesort(vector<int>& nums, int L, int R)
    {
        //递归终止条件
        if (L >= R)
        {
            return;
        }
        //序列中心位置计算
        auto mid = (L + ((R - L) >> 1));
        //auto mid = (R + L) / 2;
        //左右序列分别排序
        mergesort(nums, L, mid);
        mergesort(nums, mid + 1, R);

        //归并两个排好序的序列
        merge(nums, L, mid, R);
    }

    static void merge(vector<int>& nums, int L, int mid, int R)
    {
        //临时向量存储归并的结果
        vector<int> tmp(R - L + 1);
        auto pos = 0;
        auto Lp = L;
        auto Rp = mid + 1;
        while ((Lp <= mid) && (Rp <= R))
        {
            tmp[pos++] = (nums[Lp] < nums[Rp]) ? nums[Lp++] : nums[Rp++];
        }
        while (Lp <= mid)
        {
            tmp[pos++] = nums[Lp++];
        }
        while (Rp <= R)
        {
            tmp[pos++] = nums[Rp++];
        }

    	//将排序好部分拷贝至nums数组
        copy(nums, tmp, L, R);
        //nums = tmp;
    }

	//部分数组拷贝函数
    static void copy(vector<int>& nums, vector<int>& tmp, int L, int R)
    {
        auto pos = 0;
        for (auto i = L; i <= R; i++)
        {
            nums[i] = tmp[pos++];
        }
    }
};


//准备一个随机数组(样本)生成器
//函数名:generateRandomVector
//函数功能描述:随机数组(样本)生成器
//函数参数: size    生成数组最大尺寸
//         value   数组每个元素的最大值
//返回值:  vector<int> 生成的数组
//for test
vector<int> generateRandomVector(int size, int value)
{
    //time 函数返回从 1970 年 1 月 1 日午夜开始到现在逝去的秒数,因此每次运行程序时,它都将提供不同的种子值。
    srand((int)time(NULL));//为随机数生成器产生随机种子
    //分配随机大小的数组,产生随机数的范围公式number = (rand()%(maxValue - minValue +1)) + minValue;
    vector<int> result(rand() % (size + 1));
    for (auto i = 0; i < result.size(); i++)
    {
        result[i] = rand() % (value + 1);
    }

    return result;

}

//大样本测试
//函数名:main
//函数功能描述:大样本测试
//函数参数: size    生成数组最大尺寸
//         value   数组每个元素的最大值
//返回值:  vector<int> 生成的数组
//for test
int main()
{
    auto test_time = 50000;//测试次数,设置比较大,排除特殊情况
    auto size = 10;//生成数组最大尺寸
    auto value = 30;//生成数组每个元素的最大值
    auto if_accept = true;//方法是否正确标志位
	for(auto i = 0; i < test_time; i++)
	{
        //拷贝初始化,生成新的数组向量
        vector<int> nums(generateRandomVector(size, value));
        //生成两个临时数组拷贝
        vector<int> nums1(nums);
        vector<int> nums2(nums);

		//绝对正确方法
        sort(nums1.begin(), nums1.end());
		//自己写的方法,想要测试的算法
        Solution::reversePairs(nums2);

		//判断两个向量是否相同,vector类已经重载了比较运算符,不用自己实现,不相同说明算法不正确
		if(nums1 != nums2)
		{
            if_accept = false;
			//输出结果不相等的原始向量
			for(auto c: nums)
			{
                cout << c << " ";
			}
			break;
		}
		
	}
	

	//输出结果
    cout << (if_accept ? "nice!\n" : "false!\n");
    
}

加载全部内容

相关教程
猜你喜欢
用户评论