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