分治-芯片测试问题

唔仄lo咚锵

发布于 2020-10-26 11:07:29

6990

发布于 2020-10-26 11:07:29

芯片测试问题

本文应某人要求被迫经营

问题描述：有n（2≤n≤20）块芯片，有好有坏，已知好芯片比坏芯片多。每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。给出所有芯片的测试结果，问哪些芯片是好芯片。 输入格式：输入数据第一行为一个整数n，表示芯片个数。第二行到第n+1行为n*n的一张表，每行n个数据。表中的每个数据为0或1，在这n行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本身进行测试）。 输出格式：按从小到大的顺序输出所有好芯片的编号 样例输入： 3 1 0 1 0 1 0 1 0 1 样例输出： 1 3 其他要求：构造大样本数据，测试运行结果和运行时间，也可在OJ平台上测试。分析你设计算法的时间复杂度。

生成数据

"蓝桥杯"练习系统有原题，~~然而贫穷限制了我。~~

根据题意生成随机测试数据

void getrand(int num) { //num为样本大小
	int rightcnt = num / 2 + 1; //保证一半以上好芯片
	int wrongcnt = num - rightcnt;
	srand((unsigned int)time(0)); //随机种子
	int r = rand() % wrongcnt;
	rightcnt += r; //随机好坏数量
	wrongcnt -= r;
	int ans[maxn] = { 0 };  //记录芯片好坏
	while (rightcnt--) {  //随机好芯片编号
		int idx = rand() % num + 1;
		if (ans[idx]) {
			rightcnt++;
			continue;
		}
		ans[idx] = 1;
	}
	for (int i = 1; i <= num; i++)
		if (ans[i])
			printf("%d ", i);
	FILE* fp = fopen("in.txt", "w+");
	if (!fp) {
		printf("无法打开文件\n");
		exit(0);
	}
	fprintf(fp, "%d\n", num);
	for (int i = 1; i <= num; i++) {
		if (ans[i])  //i是好的，输出ans
			for (int j = 1; j <= num; j++)
				fprintf(fp, "%d ", ans[j]);
		else  //i是坏的，随机
			for (int j = 1; j <= num; j++) 
				fprintf(fp, "%d ", rand() % 2);
		fprintf(fp, "\n");
	}
	fclose(fp);
}

暴力

void method1() { //O(n^2)
	int cnt[maxn] = { 0 };
	DWORD start_time = GetTickCount();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (m[i][j] && i != j)
				cnt[j]++;
	int half = n >> 1;
	FILE* f = fopen("out1.txt", "w+");
	if (!f) {
		printf("无法打开文件\n");
		exit(0);
	}
	for (int i = 1; i <= n; i++)
		if (cnt[i] >= half)
			fprintf(f,"%d ", i);
	DWORD end_time = GetTickCount();
	fprintf(f, "\n用时%dms", end_time - start_time);
	fclose(f);
}

分治

void method2() { //O(n)
	list<int>l;  //删除操作多,用list
	list<int>::iterator it, ij;
	for (int i = 1; i <= n; i++)l.push_back(i);
	DWORD start_time = GetTickCount();
	while (l.size() > 3) {
		for (it = l.begin(); it != l.end(); ) {
			ij = it;
			it++;
			if (it == l.end()) { //奇数轮空
				int cnt = 0;
				for (it = l.begin(); it != l.end(); it++) 
					if (m[*it][*ij])
						cnt++;
				if (cnt < l.size() / 2) //超过一半坏，弃之
					l.erase(ij);
				break;
			}
			else { //偶数
				if (m[*it][*ij] && m[*ij][*it]) //两好则保留一个
					it=l.erase(it);
				else {  //否则全弃
					it = l.erase(it);
					it = l.erase(ij);
				}
			}
		}
	}
	int right;
	if (l.size() == 3) {
		it = l.begin();
		ij = it++;
		if (m[*it][*ij] && m[*ij][*it])right = *it;
		else right = *(++it);
	}
	else right = l.front();
	FILE* f = fopen("out2.txt", "w+");
	if (!f) {
		printf("无法打开文件\n");
		exit(0);
	}
	for (int i = 1; i <= n; i++)
		if (m[right][i])
			fprintf(f, "%d ", i);
	DWORD end_time = GetTickCount();
	fprintf(f, "\n用时%dms", end_time - start_time);
	fclose(f);
}

（~~插播反爬信息~~ ）博主CSDN地址：https://wzlodq.blog.csdn.net

源码

#include<bits/stdc++.h>
#include<Windows.h>
using namespace std;
const int maxn = 10004;
int n, m[maxn][maxn];
void getrand(int num) {
	int rightcnt = num / 2 + 1; //保证一半以上好芯片
	int wrongcnt = num - rightcnt;
	srand((unsigned int)time(0)); //随机种子
	int r = rand() % wrongcnt;
	rightcnt += r; //随机好坏数量
	wrongcnt -= r;
	int ans[maxn] = { 0 };
	while (rightcnt--) {
		int idx = rand() % num + 1;
		if (ans[idx]) {
			rightcnt++;
			continue;
		}
		ans[idx] = 1;
	}
	for (int i = 1; i <= num; i++)
		if (ans[i])
			printf("%d ", i);
	FILE* fp = fopen("in.txt", "w+");
	if (!fp) {
		printf("无法打开文件\n");
		exit(0);
	}
	fprintf(fp, "%d\n", num);
	for (int i = 1; i <= num; i++) {
		if (ans[i])  //i是好的，输出ans
			for (int j = 1; j <= num; j++)
				fprintf(fp, "%d ", ans[j]);
		else  //i是坏的，随机
			for (int j = 1; j <= num; j++) 
				fprintf(fp, "%d ", rand() % 2);
		fprintf(fp, "\n");
	}
	fclose(fp);
}
void method1() { //O(n^2)
	int cnt[maxn] = { 0 };
	DWORD start_time = GetTickCount();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (m[i][j] && i != j)
				cnt[j]++;
	int half = n >> 1;
	FILE* f = fopen("out1.txt", "w+");
	if (!f) {
		printf("无法打开文件\n");
		exit(0);
	}
	for (int i = 1; i <= n; i++)
		if (cnt[i] >= half)
			fprintf(f,"%d ", i);
	DWORD end_time = GetTickCount();
	fprintf(f, "\n用时%dms", end_time - start_time);
	fclose(f);
}
void method2() { //O(n)
	list<int>l;
	list<int>::iterator it, ij;
	for (int i = 1; i <= n; i++)l.push_back(i);
	DWORD start_time = GetTickCount();
	while (l.size() > 3) {
		for (it = l.begin(); it != l.end(); ) {
			ij = it;
			it++;
			if (it == l.end()) { //奇数轮空
				int cnt = 0;
				for (it = l.begin(); it != l.end(); it++) 
					if (m[*it][*ij])
						cnt++;
				if (cnt < l.size() / 2) //超过一半坏，弃之
					l.erase(ij);
				break;
			}
			else { //偶数
				if (m[*it][*ij] && m[*ij][*it]) //两好则保留一个
					it=l.erase(it);
				else {  //否则全弃
					it = l.erase(it);
					it = l.erase(ij);
				}
			}
		}
	}
	int right;
	if (l.size() == 3) {
		it = l.begin();
		ij = it++;
		if (m[*it][*ij] && m[*ij][*it])right = *it;
		else right = *(++it);
	}
	else right = l.front();
	FILE* f = fopen("out2.txt", "w+");
	if (!f) {
		printf("无法打开文件\n");
		exit(0);
	}
	for (int i = 1; i <= n; i++)
		if (m[right][i])
			fprintf(f, "%d ", i);
	DWORD end_time = GetTickCount();
	fprintf(f, "\n用时%dms", end_time - start_time);
	fclose(f);
}
int main() {
	getrand(1000);
	FILE* fp = fopen("in.txt", "r");
	if (!fp) {
		printf("无法打开文件\n");
		exit(0);
	}
	fscanf(fp, "%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			fscanf(fp, "%d", &m[i][j]);
	fclose(fp);
	method1();
	method2();
	return 0;
}