Post
by Orgi » Wed Dec 05, 2007 1:35 pm
Can anybody tell me what's wrong with my program?
It keeps getting WA..
#include <iostream.h>
struct funcdep
{ int left;
int right;
int ind;
};
int n;
funcdep funcd[110];
funcdep proof[110];
int np;
bool checkredundancy(funcdep fd, funcdep hypo[], int nh)
{ int coverage = fd.left, i;
np = 0;
do {
for (i = 0; i < nh; i++)
if (((coverage & hypo.left) == hypo.left) &&
((coverage | hypo.right) != coverage)
)
{ coverage = coverage | hypo.right;
proof[np] = hypo;
np++;
break;
}
if (i == nh) break;
} while (1);
return (coverage & fd.right) == fd.right;
}
bool checkredundancy1(funcdep fd, funcdep hypo[], int nh)
{ int coverage = fd.left, i;
do {
for (i = 0; i < nh; i++)
if (((coverage & hypo.left) == hypo.left) &&
((coverage | hypo.right) != coverage)
)
{ coverage = coverage | hypo.right;
break;
}
if (i == nh) break;
} while (1);
return (coverage & fd.right) == fd.right;
}
void solve()
{ bool suc, suc1;
int i, j;
funcdep help;
suc = false;
for (i = 0; i < n; i++)
{ help = funcd[0];
funcd[0] = funcd;
funcd[i] = help;
suc1 = checkredundancy(funcd[0],funcd+1,n-1);
suc = suc || suc1;
help = funcd[0];
funcd[0] = funcd[i];
funcd[i] = help;
if (!suc1) continue;
do {
suc1 = false;
for (j = 0; j < np; j++)
{ help = proof[0];
proof[0] = proof[j];
proof[j] = help;
suc1 = checkredundancy1(funcd[i],proof+1,np-1);
help = proof[0];
proof[0] = proof[j];
proof[j] = help;
if (suc1) break;
}
if (suc1) { proof[j] = proof[np-1]; np--; }
} while (suc1);
cout << " FD " << (i+1) << " is redundant using FDs:";
for (j = 0; j < np; j++)
cout << " " << (proof[j].ind+1);
cout << endl;
}
if (!suc) cout << " No redundant FDs." << endl;
cout << endl;
}
int main()
{ int i, j, tst = 0;
do {
tst++;
cin >> n;
if (n == 0) break;
for (i = 0; i < n; i++)
{ char s[100];
cin >> s;
funcd[i].left = funcd[i].right = 0;
funcd[i].ind = i;
for (j = 0;;j++)
{ if (s[j] == '-') break;
if (s[j] >= 'A' && s[j] <= 'Z')
funcd[i].left = funcd[i].left | (1 << (s[j]-'A'));
}
j += 2;
for(;;j++)
{ if (s[j] >= 'A' && s[j] <= 'Z')
funcd[i].right = funcd[i].right | (1 << (s[j]-'A'));
else break;
}
}
cout << "Set number " << tst << endl;
solve();
} while (1);
cout.flush();
return 0;
}