算法训练 My Bad
问题描述
一个逻辑电路将其输入通过不同的门映射到输出，在电路中没有回路。输入和输出是一个逻辑值的有序集合，逻辑值被表示为1和0。我们所考虑的电路由与门（and gate，只有在两个输入都是1的时候，输出才为1）、或门（or gate，只要两个输入中有一个是1，输出就是1）、异或门（exclusive or（xor）gate，在两个输入中仅有一个是1，输出才是1）和非门（not gate，单值输入，输出是输入的补）组成。下图给出两个电路。
不幸的是，在实际中，门有时会出故障。虽然故障会以多种不同的方式发生，但本题将门会出现的故障限于如下三种形式之一：
1）总是与正确的输出相反；
2）总是产生0；
3）总是产生1；
在本题给出的电路中，最多只有一个门出故障。
请编写一个程序，对一个电路进行分析，对多组输入和输出进行实验，看电路运行是正确的还是不正确的。如果至少有一组输入产生了错误的输出，程序要确定唯一的出故障的门，以及这个门出故障的方式。但这也可能是无法判断的。
输入格式
输入由多组测试数据组成，每组测试用例描述了一个电路及其输入和输出。每个测试数据按序给出下述部分。
1. 一行给出3个正整数：在电路中输入的数量（N ≤ 8），门的数量（G ≤ 19）和输出的数量（U ≤ 19）。
2. 每行一个门，第一行描述g1门，如果有若干个门，则下一行描述g2门，以此类推。每行给出门类型（a = and，n = not，o = or，x = exclusive or）和对这个门的所有输入的标识符，对这个门的输入来自电路输入（i1, i2, …）或来自另一个门的输出（g1, g2, …）。
3. 一行给出与U个输出u1, u2, ….所关联的门的编号。例如，如果有三个输出，u1来自g5，u2来自g1，u3来自g4，那么这一行为：5 1 4。
4. 一行给出一个整数，表示对电路的进行实验的次数（B）。
5. 最后给出B行，每行(N+U)个值（1和0），给出实验的输入值和相应的输出值。不存在有两个相同输入的情况。
输入中的标识符或数字以空格分开，输入以包含3个0的一行结束。
输出格式
对于输入数据中的每个电路，输出测试数据的编号（从1开始），然后输出一个冒号和一个空格，再输出电路分析，内容为如下之一（用#代替相应的门的编号）：
No faults detected
Gate # is failing; output inverted
Gate # is failing; output stuck at 0
Gate # is failing; output stuck at 1
Unable to totally classify the failure
在图1和图2 中给出的电路图是第一个和最后一个测试数据。
样例输入
2 2 1
o i1 i2
n g1
2
2
1 0 0
0 0 1
2 1 1
a i1 i2
1
1
1 0 1
2 1 1
a i1 i2
1
2
1 0 1
1 1 1
1 1 1
n i1
1
2
1 1
0 0
3 4 4
n g4
a i1 i2
o i2 i3
x i3 i1
2 3 4 1
4
0 1 0 0 1 0 1
0 1 1 0 1 1 0
1 1 1 0 1 0 1
0 0 0 0 0 0 1
0 0 0
样例输出
Case 1: No faults detected
Case 2: Unable to totally classify the failure
Case 3: Gate 1 is failing; output stuck at 1
Case 4: Gate 1 is failing; output inverted
Case 5: Gate 2 is failing; output stuck at 0
数据规模和约定
N<=8;G,U<=19
代码(存在一些问题，待修改)
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
using namespace std;
int len = 0;//记录当前存储的语句位置
int N, G, U;//输入的数量（N ≤ 8），门的数量（G ≤ 19）和输出的数量（U ≤ 19）
string s[100];//存储输出的语句
enum input
{
i1 = 1,
i2,
i3,
i4,
i5,
i6,
i7,
i8,
g1 = 11,
g2,
g3,
g4,
g5,
g6,
g7,
g8,
g9,
g10,
g11,
g12,
g13,
g14,
g15,
g16,
g17,
g18,
g19,
g20
}myinput;
input getEnum(string s)
{
if (s == "i1")
{
return i1;
}
else if (s == "i2")
{
return i2;
}
else if (s == "i3")
{
return i3;
}
else if (s == "i4")
{
return i4;
}
else if (s == "i5")
{
return i5;
}
else if (s == "i6")
{
return i6;
}
else if (s == "i7")
{
return i7;
}
else if (s == "i8")
{
return i8;
}
else if (s == "g1")
{
return g1;
}
else if (s == "g2")
{
return g2;
}
else if (s == "g3")
{
return g3;
}
else if (s == "g4")
{
return g4;
}
else if (s == "g5")
{
return g5;
}
else if (s == "g6")
{
return g6;
}
else if (s == "g7")
{
return g7;
}
else if (s == "g8")
{
return g8;
}
else if (s == "g9")
{
return g9;
}
else if (s == "g10")
{
return g10;
}
else if (s == "g11")
{
return g11;
}
else if (s == "g12")
{
return g12;
}
else if (s == "g13")
{
return g13;
}
else if (s == "g14")
{
return g14;
}
else if (s == "g15")
{
return g15;
}
else if (s == "g16")
{
return g16;
}
else if (s == "g17")
{
return g17;
}
else if (s == "g18")
{
return g18;
}
else if (s == "g19")
{
return g19;
}
else if (s == "g20")
{
return g20;
}
}
void brokendoor(int N, int G, int U)
{
int type[20][20];//记录门的类型
int datadoor[30][30];//记录门输出的数据
for (int i = 1; i <= G; i++)
{
int temp;
char c;
cin >> c;
type[i][0] = temp = c;//输入类型
int j = 0;
do
{
j++;
string s;
cin >> s;
temp = getEnum(s);
type[i][j] = temp;
} while (cin.get() != '\n');
}
int outdoor[20];//记录输出的结果与相关的门
int tests;//记录试验次数
int test_class[20][20];//记录实际实验的数据
for (int i = 1; i <= U; i++)
{
cin >> outdoor[i];
}
cin >> tests;
for (int i = 1; i <= tests; i++)
{
for (int j = 1; j <= N + U; j++)
{
cin >> test_class[i][j];
}
}
//初始化datadoor[];
for (int i = 1; i <= tests; i++)
{
for (int j = 1; j <= G; j++)
datadoor[i][j] = -1;
}
//验证过程
int iscontinuezero = -1;//是否连续为某错误值
int isreverse = -1;//是否是结果相反
int brokenU = -1;//错误输出号
for (int i = 1; i <= tests; i++)
{
int doorend = G;//要计算的门数量
while (doorend > 0)
{
//在while循环中寻找合适的门先计算，再计算基于其它门的结果的门输出
for (int j = 1; j <= G; j++)
{
if (datadoor[i][j] != -1)continue;
if (type[j][0] == 'o')//'o'门输出结果
{
int a, b;
if (type[j][1] < 10)
a = test_class[i][type[j][1]];
else
{
if (datadoor[i][type[j][1] - 10] != -1)
{
a = datadoor[i][type[j][1] - 10];
}
else continue;
}
if (type[j][2] < 10)
b = test_class[i][type[j][2]];
else
{
if (datadoor[i][type[j][2] - 10] != -1)
{
b = datadoor[i][type[j][2] - 10];
}
else continue;
}
datadoor[i][j] = a || b;
doorend--;
}
else if (type[j][0] == 'a')//'a'门输出结果
{
int a, b;
if (type[j][1] < 10)
a = test_class[i][type[j][1]];
else
{
if (datadoor[i][type[j][1] - 10] != -1)
{
a = datadoor[i][type[j][1] - 10];
}
else continue;
}
if (type[j][2] < 10)
b = test_class[i][type[j][2]];
else
{
if (datadoor[i][type[j][2] - 10] != -1)
{
b = datadoor[i][type[j][2] - 10];
}
else continue;
}
datadoor[i][j] = a && b;
doorend--;
}
else if (type[j][0] == 'n')//'n'门输出结果
{
int a;
if (type[j][1] < 10)
a = test_class[i][type[j][1]];
else
{
if (datadoor[i][type[j][1] - 10] != -1)
{
a = datadoor[i][type[j][1] - 10];
}
else continue;
}
datadoor[i][j] = !a;
doorend--;
}
else if (type[j][0] == 'x')//'x'门输出结果
{
int a, b;
if (type[j][1] < 10)
a = test_class[i][type[j][1]];
else
{
if (datadoor[i][type[j][1] - 10] != -1)
{
a = datadoor[i][type[j][1] - 10];
}
else continue;
}
if (type[j][2] < 10)
b = test_class[i][type[j][2]];
else
{
if (datadoor[i][type[j][2] - 10] != -1)
{
b = datadoor[i][type[j][2] - 10];
}
else continue;
}
if ((a == 1 && b == 0) || (a == 0 && b == 1))
datadoor[i][j] = 1;
else
datadoor[i][j] = 0;
doorend--;
}
}
}
if (brokenU == -1)
{
for (int k = 1; k <= U; k++)
{
int a, b;
if ((a = datadoor[i][outdoor[k]]) != (b = test_class[i][k + N]))
{
iscontinuezero = b;
if (a == !b)isreverse = 1;
brokenU = k;
break;
}
}
}
}
//将错误的一例依次与每例对比
if (brokenU != -1)
{
for (int i = 1; i <= tests; i++)
{
if (i == brokenU)continue;
else
{
int a = datadoor[i][outdoor[brokenU]];
int b = test_class[i][brokenU + N];
{
if ((b == 0 && iscontinuezero != 0) || (b == 1 && iscontinuezero != 1))
{
iscontinuezero = 3;
}
if (a == b)
{
isreverse = 0;
}
}
}
}
}
//错误门号
int brokendoornumber = outdoor[brokenU];//与错误输出相关联的门
stringstream st1;
st1 << len + 1;
string strlen = st1.str();
stringstream st2;
st2 << brokendoornumber;
string strbroken = st2.str();
//错误类别
if (isreverse == 1 && (iscontinuezero == 1 || iscontinuezero == 0))
{
s[len] = "Case " + strlen + ": " + "Unable to totally classify the failure";
}
else if (isreverse == -1 && iscontinuezero == -1)
{
s[len] = "Case " + strlen + ": " + "No faults detected";
}
else if (isreverse == 1 && (iscontinuezero != 1 && iscontinuezero != 0))
{
s[len] = "Case " + strlen + ": " + "Gate " + strbroken + " is failing; output inverted";
}
else if (isreverse != 1 && iscontinuezero == 1)
{
s[len] = "Case " + strlen + ": " + "Gate " + strbroken + " is failing; output stuck at 1";
}
else if (isreverse != 1 && iscontinuezero == 0)
{
s[len] = "Case " + strlen + ": " + "Gate " + strbroken + " is failing; output stuck at 0";
}
len++;
}
int main()
{
cin >> N >> G >> U;
do
{
brokendoor(N, G, U);
cin >> N >> G >> U;
} while (N != 0 && G != 0 && U != 0);
for (int i = 0; i < len; i++)
{
cout << s[i] << endl;
}
return 0;
}
测试图片