#include<iostream.h>
#define N 7
#define Q 128
struct INF{
int x; //十进制数
int ex[N];//二进制表示
int baohan[2*N];//存储的数为合成他的项的进十制数
int zyhb[Q]; ////质蕴涵表的每一行
int bhnum;//存储他包含项的个数
int Enum;//该节点中1的个数
int pdbh;////判断该节点是否被其它节点包含,若包含为1,否则为0
};
void stoe(int a[],int num,int x)//十进制转换成二进制
{
int i;
for(i=0;i<num;i++)
{
a[num-1-i]=x%2;
x=x/2;
}
}
int suanEnum(int a[],int wei)/////////计算得出每一项中1的个数
{
int num=0,i;
for(i=0;i<wei;i++)
if(a[i]==1)
num++;
return num;
}
int hebing(int a[],int b[],int z[],int wei)/////合并两项放到z[]中,如果成功返回1,否则返回0
{
int i;
int btc;/////记录不同的那个位子
int btn=0;////记录不同项的个数
for(i=0;i<wei;i++)
if(a[i]!=b[i])
{
btn++;
if((a[i]==1&&b[i]==0)||(a[i]==0&&b[i]==1))
btc=i;
}
if(btn==1)
{for(i=0;i<wei;i++)
z[i]=a[i];
z[btc]=-1;
return 1;
}
else return 0;
}
int pzj(int a[],int anum,int b[],int bnum)///如果a是b的子集返回1,b是a的子集返回2,否则返回0 anum与bnum不等
{
int i,j;
int pd=0;////判断是否找到了相同项,找到为1,否则为0
if(anum>bnum)
{
for(i=0;i<bnum;i++)
{
pd=0;
for(j=0;j<anum;j++)
if(b[i]==a[j])
{ pd=1;break;}
if(pd==0)
break;
}
if(pd==0)
return 0;
else return 2;
}
else
{
for(i=0;i<anum;i++)
{
pd=0;
for(j=0;j<bnum;j++)
if(a[i]==b[j])
{ pd=1;break;}
if(pd==0)
break;
}
if(pd==0)
return 0;
else return 1;
}
}
int comp(int a[],int b[],int wei)///////判断a与b是否相等,相等返回1,否则返回0
{
int num=0;
int i;
for(i=0;i<wei;i++)
{if(a[i]==b[i])
num++;
else break;
}
if(num==wei)
return 1;
else return 0;
}
void fuzhi(int a[],int b[],int sta,int wei)/////把b中wei位复制到a中从下标为sta后面
{
int i;
for(i=0;i<wei;i++)
a[sta+i]=b[i];
}
void deletes(INF zu[],int j,int &snum,int zsnum,int wei)///////////////////把下标为j的项删掉
{
fuzhi(zu[j].ex,zu[snum-1].ex,0,wei);///////////////////////////
fuzhi(zu[j].baohan,zu[snum-1].baohan,0,zu[snum-1].bhnum);///////////
fuzhi(zu[j].zyhb,zu[snum-1].zyhb,0,zsnum);
zu[j].Enum=zu[snum-1].Enum;//////////////////////////////////// 把相同的项去掉一项
zu[j].bhnum=zu[snum-1].bhnum;/////////////////////////////////
snum--;
}////////////////////////////////////////////////
void deletel(INF zu[],int j,int snum,int &zsnum)
{
int i;
for(i=0;i<snum;i++)
zu[i].zyhb[j]=zu[i].zyhb[zsnum-1];
zsnum--;
}
void putout(INF zu[],int snum,int wei)
{
int i,j;
char * ip;
ip=new char[wei];
for(i=0;i<wei;i++)
ip[i]=(char)(65+i);
struct OUT{
char* f;
char* z;
int num;
};
OUT *out;
out=new OUT[snum];
for(i=0;i<snum;i++)
{ out[i].num=0;
out[i].f=new char[wei+1];
out[i].z=new char[wei+1];
}
for(i=0;i<snum;i++)
{for(j=0;j<wei;j++)
{
if(zu[i].ex[j]==1)
{ out[i].f[out[i].num]=' ';out[i].z[out[i].num]=ip[j];out[i].num++;}
if(zu[i].ex[j]==0)
{ out[i].f[out[i].num]='_';out[i].z[out[i].num]=ip[j];out[i].num++;}
}
out[i].f[out[i].num]='\0';out[i].z[out[i].num]='\0';
}
cout<<" ";
for(i=0;i<snum;i++)
cout<<out[i].f<<' ';
cout<<endl;
cout<<"F=";
for(i=0;i<snum;i++)
{
cout<<out[i].z;
if(i!=snum-1)
cout<<'+';
}
cout<<endl;
}
int max(int a,int b)
{
if(a>b)
return a;
else return b;
}
void hjzyh(INF zu[],int &snum,int &zsnum,int wei)//化解质蕴涵表
{
int ksd=-1;//若下标小的zu中的ex中1多则值为1,否则为0
int i,j,k;
int pdxh=1;
while(pdxh)
{ pdxh=0;
for(i=0;i<snum;i++)
for(j=i+1;j<snum;j++)
{
for(k=0;k<zsnum;k++)
{
if(zu[i].zyhb[k]!=zu[j].zyhb[k])
{
if(zu[i].zyhb[k]==1&&ksd!=0)
ksd=1;
else if(zu[j].zyhb[k]==1&&ksd!=1)
ksd=0;
else {ksd=-1;break;}
}
}
if(k==zsnum&&ksd==-1)
{deletes(zu,j,snum,zsnum,wei);pdxh=1;}
if(k==zsnum&&ksd==1)
{deletes(zu,j,snum,zsnum,wei);pdxh=1;ksd=-1;}
if(k==zsnum&&ksd==0)
{deletes(zu,i,snum,zsnum,wei);pdxh=1;ksd=-1;}
}
for(i=0;i<zsnum;i++)
for(j=i+1;j<zsnum;j++)
{
for(k=0;k<snum;k++)
{
if(zu[k].zyhb[i]!=zu[k].zyhb[j])
{
if(zu[k].zyhb[i]==1&&ksd!=0)
ksd=1;
else if(zu[k].zyhb[j]==1&&ksd!=1)
ksd=0;
else {ksd=-1;break;}
}
}
if(k==snum&&ksd==-1)
{deletel(zu,i,snum,zsnum);pdxh=1;}
if(k==snum&&ksd==1)
{deletel(zu,i,snum,zsnum);pdxh=1;ksd=-1;}
if(k==snum&&ksd==0)
{deletel(zu,j,snum,zsnum);pdxh=1;ksd=-1;}
}
}
}
void main()
{
INF zu[Q],zu1[Q];
int pdxh=1;/////判断合并运算是否结束
int wei,i=0,j,k,snum=0,zsnum,snum1=0;//////snum1为合并后的项数
int sz[Q];
int xunh=1;
while(xunh==1)
{
cout<<"输入位数:";
cin>>wei;
cout<<"输入所有使输出为1对应的十进制数字(以小于0的数结束):"<<endl;
cin>>zu[i].x;
while(zu[i].x>=0)
{
sz[i]=zu[i].x;
zu[i].bhnum=1;//////////////////
zu[i].baohan[0]=zu[i].x;////////
///////////////////////////////对各项
stoe(zu[i].ex,wei,zu[i].x);/////////////// 附初值
zu[i].Enum=suanEnum(zu[i].ex,wei);///////////
zu[i].pdbh=0;zu1[i].pdbh=0;
snum++;
i++;
cin>>zu[i].x;
}
for(i=0;i<Q;i++)
zu1[i].bhnum=0;
zsnum=snum;
while(pdxh)
{ pdxh=0;
for(i=0;i<snum;i++)
for(j=i+1;j<snum;j++)///
{/////
if(zu[i].Enum-zu[j].Enum==1||zu[i].Enum-zu[j].Enum==-1)//// 把能合并的项合并
{/////////////////////////////////////////////////////// 暂时放到zu1[]中
if(hebing(zu[i].ex,zu[j].ex,zu1[snum1].ex,wei)==1)// 并对能合并的项注被包含标记
{ fuzhi(zu1[snum1].baohan,zu[i].baohan,zu1[snum1].bhnum,zu[i].bhnum);
zu1[snum1].bhnum+=zu[i].bhnum;
fuzhi(zu1[snum1].baohan,zu[j].baohan,zu1[snum1].bhnum,zu[j].bhnum);
zu1[snum1].bhnum+=zu[j].bhnum;
zu1[snum1].Enum=max(zu[i].Enum,zu[j].Enum)-1;
snum1++;
zu[i].pdbh=1;zu[j].pdbh=1;
pdxh=1;
}
}
}////////////////////////////////////////////////////////
for(i=0;i<snum;i++)//////////////////////////////////////////////////
{
if(zu[i].pdbh==0)/////////////////////// 把没有被包含的
{fuzhi(zu1[snum1].ex,zu[i].ex,0,wei);/// 项复制到zu1[]中
zu1[snum1].bhnum=zu[i].bhnum;/////////
zu1[snum1].Enum=zu[i].Enum;/////////////
zu1[snum1].x=zu[i].x;//////////////////
fuzhi(zu1[snum1].baohan,zu[i].baohan,0,zu[i].bhnum);////////////
snum1++;/////////////////////////////////////////
}////////////////////////////////////////////////
}/////
for(i=0;i<snum1;i++)////////////////////////////////////////////////
{
fuzhi(zu[i].ex,zu1[i].ex,0,wei);///////////////////////////
fuzhi(zu[i].baohan,zu1[i].baohan,0,zu1[i].bhnum);///////////
zu[i].Enum=zu1[i].Enum;//////////////////////////////////// 又把zu1复制到zu中
zu[i].bhnum=zu1[i].bhnum;//////////
zu[i].pdbh=0;//////////
snum=snum1;////////
}/////////////////////////////////////////////////////////////////////////
for(i=0;i<Q;i++)
zu1[i].bhnum=0;
snum1=0;
for(i=0;i<snum;i++) /////////////////////
{for(j=i+1;j<snum;j++) ////////////////// 相同的项删掉一项
if(comp(zu[i].ex,zu[j].ex,wei)==1)//////////////////
{deletes(zu,j,snum,zsnum,wei);j--;}
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
for(i=0;i<snum;i++)
{
for(k=0;k<zsnum;k++)
{
for(j=0;j<zu[i].bhnum;j++)///////////////////////////////// 把质蕴涵表
{
if(zu[i].baohan[j]==sz[k])///////////////////