c++ 对数器实现示例
更新时间:2021年8月14日 00:01 点击:1566
对数器的作用
对数器用于在自己的本地平台验证算法正确性,用于算法调试,无需online judge。
好处:
- 没找到线上测试的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"); }
到此这篇关于c++ 对数器实现示例的文章就介绍到这了,更多相关c++ 对数器内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
上一篇: C语言实现动态顺序表详解
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 在本篇内容里小编给大家分享了关于C++实现递归函数的教学步骤,需要的朋友跟着参考下。...2020-04-25