本文应某人要求被迫经营
问题描述: 有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;
}
原创不易,请勿转载(
本不富裕的访问量雪上加霜)