分治-芯片测试问题

怼烎@ 2022-12-14 06:37 158阅读 0赞

### 文章目录 ###

*  芯片测试问题
 *   *  生成数据
     *  暴力
     *  分治
     *  源码

# 芯片测试问题 #

--------------------

本文应某人要求被迫经营

> **问题描述**：  
> 有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平台上测试。分析你设计算法的时间复杂度。

## 生成数据 ##

--------------------

["蓝桥杯"练习系统][Link 1]有原题，然而贫穷限制了我。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center]

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

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);
    }

## 暴力 ##

--------------------

用其他n-1片芯片对A芯片测试，至少有一半报“好”，则A是好芯片。时间复杂度是 O ( n 2 ) O(n^2) O(n2)。

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);
    }

## 分治 ##

--------------------

将芯片两两一组进行测试，若结果都是好芯片则任意保留一个，其他情况(一好一坏、两坏)则都舍弃这两个芯片。当数量是奇数时，对没有分组的那个芯片单独暴力处理，好则保留，坏则舍弃。

出口是数量<=3，因为好芯片比坏芯片多，所以数量是3的时候再拿出两个测，若结果一好一坏，则剩余那个是好芯片；否则两个芯片都是好的。数量1或2时都是好芯片。找到一片好芯片后便能知道所有芯片的好坏。  
时间复杂度 W ( n ) = W ( n 2 ) + O ( n ) = O ( n ) W(n)=W(\\frac\{n\}2)+O(n)=O(n) W(n)=W(2n)\+O(n)=O(n)。

那么为什么剩下的就一定好芯片多于坏芯片呢？会不会坏芯片更多？  
两两分组共三种情况

1.  两好（设 i i i组）
2.  一好一坏（设 j j j组）
3.  两坏（设 k k k组）

因为题目保证输入好芯片多余坏芯片，初始时有 2 i + j > 2 k + j 2i+j>2k+j 2i\+j>2k\+j，即 i > k i>k i>k。又因为当互测结果都是好芯片时（两好或两坏）时保留一个，其余舍弃，所以一轮淘汰后，好芯片剩余至少 i i i个，坏芯片剩余至多 k k k个，而 i > k i>k i>k，即满足好芯片仍多余坏芯片。

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][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;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center 1]

> **原创不易，请勿转载**（本不富裕的访问量雪上加霜 ）  
> 博主首页：[https://wzlodq.blog.csdn.net][https_wzlodq.blog.csdn.net]  
> 微信公众号：吾仄lo咚锵  
> *如果文章对你有帮助，记得一键三连❤*

[Link 1]: http://lx.lanqiao.cn/problemset.page?code=BASIC-
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/765cb83fc69143ad97fd4a6d38102464.png
[https_wzlodq.blog.csdn.net]: https://wzlodq.blog.csdn.net
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/4a400fe9aa924e68a7b64e5d36846823.png