c++ 對數(shù)器實現(xiàn)示例
更新時間：2021年08月13日 16:11:31 作者：機巧的胖子
對數(shù)器用于在自己的本地平臺驗證算法正確性，本文詳細(xì)的介紹了c++ 對數(shù)器實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
對數(shù)器的作用
對數(shù)器用于在自己的本地平臺驗證算法正確性，用于算法調(diào)試，無需online judge。
好處：
- 沒找到線上測試的online judge，則可以使用對數(shù)器。
- 大數(shù)據(jù)樣本出錯時，快速找到出錯地方。
- 貪心策略使用，直接驗證是否正確
對數(shù)器的實現(xiàn)代碼
首先需要有一個你想要測試的方法，本文利用歸并排序算法舉例。歸并算法代碼如下：
//有一個你想要測試的算法，這里以歸并排序為例
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)
{
//臨時向量存儲歸并的結(jié)果
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數(shù)組
copy(nums, tmp, L, R);
//nums = tmp;
}
//部分?jǐn)?shù)組拷貝函數(shù)
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++];
}
}
};
準(zhǔn)備一個隨機數(shù)組（樣本）生成器，該示例選擇size為10，value為30，代碼如下：
//函數(shù)名：generateRandomVector
//函數(shù)功能描述：隨機數(shù)組（樣本）生成器
//函數(shù)參數(shù)： size 生成數(shù)組最大尺寸
// value 數(shù)組每個元素的最大值
//返回值： vector<int> 生成的數(shù)組
//for test
vector<int> generateRandomVector(int size, int value)
{
//time 函數(shù)返回從 1970 年 1 月 1 日午夜開始到現(xiàn)在逝去的秒數(shù)，因此每次運行程序時，它都將提供不同的種子值。
srand((int)time(NULL));//為隨機數(shù)生成器產(chǎn)生隨機種子
//分配隨機大小的數(shù)組，產(chǎn)生隨機數(shù)的范圍公式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;
}
大樣本測試，同時還需要準(zhǔn)備一個絕對正確的方法，這里用algorithm頭文件中的sort函數(shù)進行排序，同時測試次數(shù)應(yīng)該盡量大，從而覆蓋盡可能所有的實例，如果沒有自己算法和絕對正確的算法的結(jié)果的比對方法，還需要自己編寫結(jié)果的比對方法，判斷結(jié)果是否正確（這里vector重載了比較運算符，直接使用即可），代碼如下：
//大樣本測試
//函數(shù)名：main
//函數(shù)功能描述：大樣本測試
//函數(shù)參數(shù)： size 生成數(shù)組最大尺寸
// value 數(shù)組每個元素的最大值
//返回值： vector<int> 生成的數(shù)組
//for test
int main()
{
auto test_time = 50000;//測試次數(shù)，設(shè)置比較大，排除特殊情況
auto size = 10;//生成數(shù)組最大尺寸
auto value = 30;//生成數(shù)組每個元素的最大值
auto if_accept = true;//方法是否正確標(biāo)志位
for(auto i = 0; i < test_time; i++)
{
//拷貝初始化，生成新的數(shù)組向量
vector<int> nums(generateRandomVector(size, value));
//生成兩個臨時數(shù)組拷貝
vector<int> nums1(nums);
vector<int> nums2(nums);
//絕對正確方法
sort(nums1.begin(), nums1.end());
//自己寫的方法，想要測試的算法
Solution::reversePairs(nums2);
//判斷兩個向量是否相同，vector類已經(jīng)重載了比較運算符，不用自己實現(xiàn)，不相同說明算法不正確
if(nums1 != nums2)
{
if_accept = false;
//輸出結(jié)果不相等的原始向量
for(auto c: nums)
{
cout << c << " ";
}
break;
}
}
//輸出結(jié)果
cout << (if_accept ? "nice!\n" : "false!\n");
}
運行上述代碼，由于我們測試樣本次數(shù)為50000次，而樣本量本身比較?。╯ize = 10, value = 30）可以得到結(jié)果，如下圖所示，所以我們默認(rèn)已經(jīng)覆蓋了所有情況，我們的算法是正確的。
將歸并排序算法改為降序排列，重新運行可得：
由于每次設(shè)定的種子源是隨機的，所以每次運行可以得到不同的序列。
完整代碼
附完整代碼：
// 對數(shù)器.cpp : 此文件包含 "main" 函數(shù)。程序執(zhí)行將在此處開始并結(jié)束。
//
#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)
{
//臨時向量存儲歸并的結(jié)果
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數(shù)組
copy(nums, tmp, L, R);
//nums = tmp;
}
//部分?jǐn)?shù)組拷貝函數(shù)
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++];
}
}
};
//準(zhǔn)備一個隨機數(shù)組（樣本）生成器
//函數(shù)名：generateRandomVector
//函數(shù)功能描述：隨機數(shù)組（樣本）生成器
//函數(shù)參數(shù)： size 生成數(shù)組最大尺寸
// value 數(shù)組每個元素的最大值
//返回值： vector<int> 生成的數(shù)組
//for test
vector<int> generateRandomVector(int size, int value)
{
//time 函數(shù)返回從 1970 年 1 月 1 日午夜開始到現(xiàn)在逝去的秒數(shù)，因此每次運行程序時，它都將提供不同的種子值。
srand((int)time(NULL));//為隨機數(shù)生成器產(chǎn)生隨機種子
//分配隨機大小的數(shù)組，產(chǎn)生隨機數(shù)的范圍公式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;
}
//大樣本測試
//函數(shù)名：main
//函數(shù)功能描述：大樣本測試
//函數(shù)參數(shù)： size 生成數(shù)組最大尺寸
// value 數(shù)組每個元素的最大值
//返回值： vector<int> 生成的數(shù)組
//for test
int main()
{
auto test_time = 50000;//測試次數(shù)，設(shè)置比較大，排除特殊情況
auto size = 10;//生成數(shù)組最大尺寸
auto value = 30;//生成數(shù)組每個元素的最大值
auto if_accept = true;//方法是否正確標(biāo)志位
for(auto i = 0; i < test_time; i++)
{
//拷貝初始化，生成新的數(shù)組向量
vector<int> nums(generateRandomVector(size, value));
//生成兩個臨時數(shù)組拷貝
vector<int> nums1(nums);
vector<int> nums2(nums);
//絕對正確方法
sort(nums1.begin(), nums1.end());
//自己寫的方法，想要測試的算法
Solution::reversePairs(nums2);
//判斷兩個向量是否相同，vector類已經(jīng)重載了比較運算符，不用自己實現(xiàn)，不相同說明算法不正確
if(nums1 != nums2)
{
if_accept = false;
//輸出結(jié)果不相等的原始向量
for(auto c: nums)
{
cout << c << " ";
}
break;
}
}
//輸出結(jié)果
cout << (if_accept ? "nice!\n" : "false!\n");
}
到此這篇關(guān)于c++ 對數(shù)器實現(xiàn)示例的文章就介紹到這了,更多相關(guān)c++ 對數(shù)器內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語言之素數(shù)(質(zhì)數(shù))的判斷以及輸出
這篇文章主要介紹了C語言之素數(shù)(質(zhì)數(shù))的判斷以及輸出方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-03-03
本人很菜，今天看《C++編程思想》中的一道課后題中說到這樣一個問題。修改兩層嵌套的for循環(huán)的標(biāo)識符，觀察結(jié)果變化2013-05-05
這篇文章主要為大家詳細(xì)介紹了c++ signal實現(xiàn)發(fā)送信號的相關(guān)知識,文中的示例代碼講解詳細(xì),具有一定的學(xué)習(xí)價值,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-01-01
C++ read函數(shù)讀入int整形數(shù)據(jù)
這篇文章主要介紹了C++ read函數(shù)讀入int整形數(shù)據(jù)的相關(guān)資料,需要的朋友可以參考下2016-07-07
C語言編程數(shù)據(jù)結(jié)構(gòu)線性表之順序表和鏈表原理分析
本篇文章是C語言編程篇主要為大家介紹了C語言編程中的數(shù)據(jù)結(jié)構(gòu)線性表，文中附含豐富的圖文示例代碼為大家詳解了線性表中的順序表和鏈表，有需要的朋友可以借鑒參考下2021-09-09
這篇文章主要介紹了C++鏈表倒序?qū)崿F(xiàn)方法,是一個很經(jīng)典的C++鏈表操作實例,需要的朋友可以參考下2014-08-08
這篇文章主要為大家詳細(xì)介紹了C語言課程設(shè)計之抽獎系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12
這篇文章主要為大家詳細(xì)介紹了C++遍歷文件夾獲取文件列表的相關(guān)資料，感興趣的小伙伴們可以參考一下2016-05-05
這篇文章主要為大家詳細(xì)介紹了C++設(shè)計模式之外觀模式(Facade)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-03-03
這篇文章主要介紹了C語言多線程服務(wù)器的實現(xiàn)實例,文章用實例講解的很清楚，有對這方面不太懂的同學(xué)可以參考下2021-02-02