QM算法代码如下，求大神指点，感激不尽！
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
//蕴含项构造类
class Implicant{
public:
int* er;
int lengh;
int n1;
int n2;
Implicant(int l,int n);
Implicant();
Implicant(const Implicant &tem);
~Implicant(){delete[]er;}
bool Can(Implicant&tem);
Implicant Merge(Implicant &tem);
bool Canc(int m);
Implicant& operator=(Implicant &tem);
bool operator ==(Implicant &tem);
};
//构造函数
Implicant::Implicant(int l,int n)
{
int i=0;
lengh=l;
er=new int[l];
n1=0;n2=0;
for(i=0;i<l;i++)
{
if(n%2==1)
{
er[l-1-i]=1;
n1++;
}
else
er[l-1-i]=0;
n/=2;
}
}
//默认构造函数
Implicant::Implicant()
{
er=NULL;
lengh=0;
n1=0;
n2=0;
}
//复制构造函数
Implicant::Implicant(const Implicant &temp)
{
lengh=temp.lengh;
er=new int[lengh];
for(int i=0;i<lengh;i++)
er[i]=temp.er[i];
n1=temp.n1;
n2=temp.n2;
}
//判断两个蕴含项是否能合并
bool Implicant::Can(Implicant &tem)
{
int s=0,i=0;
if(n1!=tem.n1+1&&n1!=tem.n1-1)
return false;
if(n2!=tem.n2)
return false;
for(i=0;i<lengh;i++)
{
if(er[i]==2&&tem.er[i]!=2)
return false;
if(er[i]!=2&&tem.er[i]==2)
return false;
if(er[i]!=2&&tem.er[i]!=2)
{
if(er[i]!=tem.er[i])
s++;
}
}
if(s==1)
return true;
else
return false;
}
//将两个蕴含项合并
Implicant Implicant::Merge(Implicant &tem)
{
int i=0;
Implicant after(tem);
for(i=0;i<lengh;i++)
{
if(er[i]!=tem.er[i])
{
after.er[i]=2;
after.n2++;
if(n1<tem.n1)
after.n1=n1;
else
after.n1=tem.n1;
}
}
return after;
}
//判断蕴含项能否覆盖最小项
bool Implicant::Canc(int m)
{
int i=0;
if(this==NULL)
return false;
int* mer=new int(lengh);
for(i=0;i<lengh;i++)
{
if(m%2==1)
mer[lengh-i-1]=1;
else
mer[lengh-i-1]=0;
m=m/2;
}
for(i=0;i<lengh;i++)
{
if(er[i]!=2&&er[i]!=mer[i])
return false;
}
return true;
}
//重载等号
Implicant&Implicant::operator=(Implicant& tem)
{
int i=0;
if(lengh!=tem.lengh)
{
lengh=tem.lengh;
delete []er;
er=new int[lengh];
}
for(i=0;i<lengh;i++)
er[i]=tem.er[i];
n1=tem.n1;
n2=tem.n2;
return *this;
}
//重载判断蕴含项是否相同
bool Implicant::operator==(Implicant& tem)
{
int i=0;
if(lengh!=tem.lengh)
return false;
if(n1!=tem.n1)
return false;
if(n2!=tem.n2)
return false;
for(i=0;i<lengh;i++)
{
if(er[i]!=tem.er[i])
return false;
}
return true;
}
//合并蕴含项返回合并后的个数
int merge(Implicant* &result,int n)
{
int s=0,m=0,i=0,j=0,k=0;
Implicant *tem=new Implicant[n*(n+1)/2];
bool* flag=new bool[n];
for(int i=0;i<n;i++)
flag[i]=false;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(result[i].Can(result[j]))
{
tem[k]=result[i].Merge(result[j]);
flag[i]=true;
flag[j]=true;
k++;
}
}
}
m=k;
for(i=0;i<m;i++)
{
if(tem[i].lengh!=0)
{
for(j=i+1;j<m;j++)
{
if(tem[i]==tem[j])
{
k--;
tem[j]=tem[k];
tem[k]=Implicant();
}
}
}
}//去除重复项
for(i=0;i<n;i++)
{
if(flag[i]==false)
{
tem[k]=result[i];
k++;
}
}//将未合并的蕴含项添加进来
delete []result;
delete []flag;
result=tem;
tem=NULL;
return k;
}
//排序比较函数
bool com(Implicant &tem2,Implicant &tem1)
{
int i=0;
for(i=0;i<tem1.lengh;i++)
{
if(tem1.er[i]!=2&&tem2.er[i]==2)
return false;
else
if(tem1.er[i]==2&&tem2.er[i]!=2)
return true;
else
if(tem1.er[i]==1&&tem2.er[i]==0)
return false;
else
if(tem1.er[i]==0&&tem2.er[i]==1)
return true;
else
continue;
}
return false;
}
//寻找最小覆盖
int Cover(Implicant*&result,Implicant*&ess,int nm,int nd,int*&min,int n)
{
int a=0,s=0,i=0,j=0,nn=0,m=0,r=0,k=0,h=0;
int*b;
bool* cover=new bool[nm];
for(i=0;i<nm;i++)
cover[i]=false;
nn=nm+nd;
for(i=0;i<n;i++)
nn=merge(result,nn);//合并蕴含项
b=new int[nn];
for(i=0;i<nm;i++)
{
s=0;m=0;
for(j=0;j<nn;j++)
{
if(result[j].Canc(min[i]))
{
s++;
m=j;
}
}
if(s==1)
{
ess[a]=result[m];
a++;
}
}//本质本原蕴含项
k=a;
for(i=0;i<k;i++)
{
if(ess[i].lengh!=0)
{
for(j=i+1;j<k;j++)
{
if(ess[i]==ess[j])
{
a--;
ess[j]=ess[a];
ess[a]=Implicant();
}
}
}
}//删除重复的本质本原蕴含项
Implicant*start=ess;
Implicant*end=ess+a;
sort(start,end,com);//对本质本原蕴含项排序
h=a;//本质本原蕴含项个数+1
for(i=0;i<a;i++)
{
for(j=0;j<nm;j++)
{
if(ess[i].Canc(min[j]))
cover[j]=true;//未被覆盖的项
}
}
for(i=0;i<nm;i++)
{
if(cover[i]==false)
r++;//未被覆盖的项个数
}
//找最小覆盖
while(r>0)
{
for(i=0;i<nn;i++)
b[i]=0;
for(i=0;i<nn;i++)
{
for(j=0;j<nm;j++)
{
if(cover[j]==false&&result[i].Canc(min[j]))
b[i]++;
}
}
s=0;m=0;
for(i=0;i<nn;i++)
{
if(s<b[i])
{
m=i;
s=b[i];
}
}
ess[a]=result[m];
a++;
for(i=0;i<nm;i++)
{
if(cover[i]==false&&result[m].Canc(min[i]))
{
cover[i]=true;
r--;
}
}
}
delete []b;
delete []cover;
k=a;
for(i=0;i<k;i++)
{
if(ess[i].lengh!=0)
{
for(j=i+1;j<k;j++)
{
if(ess[i]==ess[j])
{
a--;
ess[j]=ess[a];
ess[a]=Implicant();
}
}
}
}//删除重复项
start=ess+h;
end=ess+a;
sort(start,end,com);//排序
return a;
}
int main()
{
int nq=0,k=0,j=0,n=0,b=0;
cin>>nq;
vector<Implicant>*o=new vector<Implicant>[nq];
for(k=0;k<nq;k++)
{
int nm=0,nd=0,a=0,i=0,max=0,lengh=0,m=0;
Implicant*f;
Implicant*essential;
cin>>nm>>nd;
if(nm==0)
{
cout<<0;
break;
}
int *min,*don;
min=new int[nm];
don=new int[nd];
for(i=0;i<nm;i++)
{
cin>>a;
min[i]=a;
if(a>max)
max=a;
}
for(i=0;i<nd;i++)
{
cin>>a;
don[i]=a;
if(max<a)
max=a;
}
for(i=1;i<=10;i++)
{
if(max<pow(2.0,i))
{
lengh=i;
break;
}
}//求变量数
f=new Implicant[nm+nd];
for(i=0;i<nm;i++)
f[i]=Implicant(lengh,min[i]);
for(i=0;i<nd;i++)
f[i+nm]=Implicant(lengh,don[i]);
essential=new Implicant[nm];
m=Cover(f,essential,nm,nd,min,lengh);
for(i=0;i<m;i++)
o[k].push_back(essential[i]);//存储结果
delete []min;
delete []don;
delete []f;
delete []essential;
}
for(k=0;k<nq;k++)
{
for(j=0;j<(int)o[k].size();j++)
{
n=0;
for(b =0;b<o[k][0].lengh;b++)
{
if(o[k][j].er[b]==0)
cout<<(char)('A' + b)<<"'";
if(o[k][j].er[b]==1)
cout<<(char)('A'+b);
if(o[k][j].er[b]==2)
n++;
}
if(j!=(int)o[k].size()-1)
cout << "+";
if(n==o[k][j].lengh)
cout<<1;
}
cout<<endl;
}//输出结果
delete []o;
return 0;
}
样例为：
1
4 3
2 3 5 6
0 4 7
时正常
为
1
6 2
4 8 10 11 12 15
9 14
时
多次查找时直接崩溃停止工作
