c++ 對數器實現示例

Posted on 2021-08-13 by WalkonNet

對數器的作用

對數器用於在自己的本地平臺驗證算法正確性，用於算法調試，無需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++ 對數器內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

c++ 對數器實現示例

目錄

對數器的作用

對數器的實現代碼

完整代碼

推薦閱讀：

發佈留言取消回覆

近期文章

目錄

對數器的作用

對數器的實現代碼

完整代碼

推薦閱讀：

發佈留言 取消回覆

近期文章

標籤

發佈留言取消回覆