数据对拍器

文章首发于：My Blog 欢迎大佬们前来逛逛

数据对拍

使用数据对拍的功能来检测代码有没有出错误。

步骤：针对某个题的做题过程

1. 首先写这道题的你认为的优化做法，因为一般的算法竞赛中肯定不可能是暴力的。
2. 然后写这道题的暴力做法。
3. 然后写数据对拍器，比较数据的差异

举例

2. 01背包问题

dp

对于背包问题我们可以有 dp动态规划的做法（这是最基本的），代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3+10;
int n,v;
int nums[N],val[N],dp[N];
int main()
{
	cin>>n>>v;
 	for (int i=1;i<=n;i++){
    	cin>>nums[i]>>val[i];
 	}
 	for (int i=1;i<=n;i++){
 		for (int j=v;j>=nums[i];j--){
 			dp[j]=max(dp[j],dp[j-nums[i]]+val[i]);	
		}
	}
 	cout<<dp[v];
 	return 0;
}

暴力

对于01背包的暴力方法，我们考虑二进制枚举的思想。

对于每一个 n，我们都把它转换为二进制的形式，其中 1表示选择这个物品，0表示不选择这个物品，则通过暴力枚举二进制的所有的01情况，来得到每一种情况的背包价值，然后得到ans

假设n=5 ，则我们需要枚举 00000 - 11111共32种情况，即 1<<5种，然后通过一层循环来获得二进制中所有的1，然后进行数据的累加。

注意我们的范围都是从 0开始的，因为二进制中全0表示都不选，全1表示全选，因此我们的for循环要写成这样的形式：

for (int i=0;i<(1<<n);i++)

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3+10;
int n,W;
int w[N],v[N];
int main(){
	cin>>n>>W;
	for (int i=0;i<n;i++){
		cin>>w[i]>>v[i];
	}
	int ans=0;
	for (int i=0;i<(1<<n);i++){
		int sumv=0,sumw=0;
		for (int j=0;j<n;j++){
			if (i>>j&1){
				sumv+=v[j];
				sumw+=w[j];
			}
		}
		if (sumw<=W){
			ans=max(ans,sumv);
		}
	}
	cout<<ans;
	return 0;
}

---

数据对拍

然后就到了我们的重头戏：数据对拍，首先把生面生成的两个exe放到同一文件夹下面

基本思路：

1. 通过随机产生数据，把数据存储到 input.txt中。
2. 对于上面的两个exe程序，从文件读取内容，然后分别把两个运行的结存储到两个xx_out,txt文件中。
3. 然后比较这两个xxx_out.txt文件内容是否是一致的。

---

如何进行文件的读写？

• 头文件：#include <fstream>表示对文件流操作；
• ofstream out(input.txt)输出重定向到文件中
• ifstream in(input.txt)输入重定向到文件中

system对文件的操作

• system("dp.exe < input.txt > dp_out.txt")，dp解法从文件读取数据，然后把dp.exe的输出重定向到dp_out.txt中；对于暴力也是同理。
• system("fc dp_out.txt baoli_out.txt")，比较两个文件是否存在差异。

如果没有差异，证明我们写的解法基本上是正确的。

#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;

void generate_data(){
	ofstream out("input.txt");
	out<<10<<' '<<rand()%200+50<<endl;//物品数量和背包容量 
	for (int i=1;i<=10;i++){
		int w=rand()%50+10,v=rand()%50+10;
		out<<w<<' '<<v<<endl;
	}
	out.close();
}
int main(){
	for (int i=1;i<=100;i++){
		cout<<"i = "<<i<<":";
		generate_data();
		system("dp.exe < input.txt > dp_out.txt");
		system("baoli.exe < input.txt > baoli_out.txt");
		system("fc dp_out.txt baoli_out.txt"); 	
	}
	return 0;
}

总结

通过手写两种解法（优化 and 暴力）并且通过数据对拍的功能来实现降低我们程序出错的可能性，数据对拍在蓝桥杯等竞赛中是一个不错的技巧。