对数器的简单使用

1.前言

学习左神的数据结构的过程中，推荐使用对数器检验自己的算法是否正确

2.内容

简介对数器

1.对数器的作用：在一个题目未OJ的时候，可以通过对数器检验自己算法是否正确。
（比如，自己写了两种方法，一种是暴力但正确（也可能错误），另一种是复杂度较小，但不知道是否正确的B，此时可以通过对数器检测两种方法得出的结果是否一致，来判断对错）
（如果两种都有可能错，可以在中间结果不同 时 进行打印，通过比较，更好地修改两种方法）
2.对数器的实现
进行数据量尽可能大的测试，比如测试次数>=100000,如果两种方法的结果都一致，那么很有可能就是对的

以排序算法的检测为实例

这里选择插入排序，检测自己写的插入排序是否存在问题

#include<iostream>
using namespace std;                //整个对数器玩儿玩儿，嘿嘿
#include <ctime>        
#include <cstdlib>
#include <algorithm>    
//思路 ：  利用系统的排序方法 和 自己写的方法 比较每次排序后的结果 
//如果在数据量较大的时候也可以 两个都对，那么 说明写的没毛病

void main()
{
	void test();           //测试
	test();
}

void test()
{
	int GenerateArrayAndCompare();     //生成一个随机数组并进行比较
	srand((unsigned int)time(NULL));    //设置随机种子
	int testtime = 10000;                 //测试次数
	int i;
	for (i = 0; i < testtime; i++)
	{
		if (!GenerateArrayAndCompare())     //返回为0，说明排序不对
			break;
	}
	if (i == testtime)         //通过了所有测试
		cout << "success!" << endl;
}

void InsertionSort(int* a, int n)       //插入排序
{
	for (int i = 1; i < n; i++)
	{
		for (int j = i; j > 0 && a[j] < a[j - 1]; j--)     //j从i向前看
		{
			a[j] = a[j] ^ a[j - 1];
			a[j - 1] = a[j] ^ a[j - 1];
			a[j] = a[j] ^ a[j - 1];
		}
	}
}
int Compare(int *a, int *b, int n)
{
	sort(b, b + n);     //用系统提供的快速排序将b排序好
	InsertionSort(a, n);    //用自己写的插入排序排好a

	for (int i = 0; i < n; i++)     //比较排序后的两个数组
	{
		if (a[i] != b[i])           //有不同的则先把所有的数字先打印，再返回0
		{
			cout << "fail!" << endl;
			for (int j = 0; j < n; j++)
			{
				cout << a[j] << " ";
			}
			cout << endl;
			for (int j = 0; j < n; j++)
			{
				cout << b[j] << " ";
			}
			return 0;
		}
	}
	return 1;                 //都相同返回1
}

int GenerateArrayAndCompare()
{
	int MaxValue = 100;               //数值范围为0~100
	int MaxArea = 5000;              //数组最大大小在5000以内
	int n = rand() % MaxArea + 1;     //数组大小1~5000
	int* a = new int[n];             //动态内存分配
	int* b = new int[n];
	int i;
	for (i = 0; i < n; i++)
	{
		a[i] = rand() % MaxValue + 1;            //每个元素1~100
	}
	for (int j = 0; j < n; j++)           //将a的每个元素赋给b
		b[j] = a[j];                 
	int flag = Compare(a, b, n);
	delete[]a;
	delete[]b;
	if (flag)
		return 1;
	else
		return 0;
}

这里设置测试次数为10000次，基本已经可以确定是正确的了

3.总结

现在只觉得很巧妙
希望在之后的学习中能更加灵活运用~~

4.更新日志

2022.4.20 整理
欢迎评论留言、指正~~