奎恩－麦克拉斯基化简法 (Q-M 法）化简逻辑代数式

《数字电子技术基础（第6版）》（阎石）



极度暴力的模拟实现，不保熟的代码QAQ：

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
vector<int>vec[11],temp;
int a[100],head[11],tail[11],flag[1050];
int box[1050][100],ans[100][100];
int num[1050][11],now,last,q;
int ed[100],minn=0x3f3f3f,b[100],vis[100];void dfs(int x,int sum)
{if(sum>minn) return;if(x>cnt){for(int i=1;i<=cnt;i++){if(vis[i]){for(int j=1;j<=ans[i][0];j++)ed[ans[i][j]]=1;}}int ok=1;for(int i=1;i<=m;i++){if(!ed[a[i]]){ok=0;break;}}if(ok){memset(b,0,sizeof(b));q=0;minn=min(minn,sum);for(int i=1;i<=cnt;i++){if(vis[i]){b[++q]=i;}}}memset(ed,0,sizeof(ed));return;}vis[x]=1;dfs(x+1,sum+1);vis[x]=0;dfs(x+1,sum);return;
}int check(int x,int y)
{int cnt=0,pos=-1;for(int t=0;t<n;t++){if(num[x][t]==-1&&num[y][t]==-1) continue;if(num[x][t]==-1||num[y][t]==-1) return -1;if(num[x][t]^num[y][t]){if(!cnt) pos=t,cnt++;else return -1;}}return pos;
}
int main()
{cout<<"请输入变量数目："<<endl;cin>>n;cout<<"请输入最小项数目："<<endl;cin>>m;cout<<"请依次输入最小项序号："<<endl;for(int i=1;i<=m;i++)scanf("%d",&a[i]);now=m,last=1;//计算每个最小项中1的个数for(int i=1;i<=m;i++){int t=a[i],cnt=0;int j=0;while(t){cnt+=(t%2);num[i][j++]=t%2;t>>=1;}vec[cnt].push_back(i);box[i][++box[i][0]]=a[i];}/*for(int i=0;i<=n;i++){tail[i]=vec[i].size();cout<<"vec["<<i<<"]:";for(int j=0;j<vec[i].size();j++)cout<<a[vec[i][j]]<<' ';cout<<endl;}*/int T=10;//合并最小项while(T--){for(int i=0;i<=n;i++){for(int j=head[i];j<tail[i];j++){for(int k=head[i+1];k<tail[i+1];k++){int pos=check(vec[i][j],vec[i+1][k]);{flag[vec[i][j]]=1,flag[vec[i+1][k]]=1;++now;a[now]=a[vec[i][j]];for(int t=0;t<=n;t++)num[now][t]=num[vec[i][j]][t];num[now][pos]=-1;for(int t=1;t<=box[vec[i][j]][0];t++)box[now][++box[now][0]]=box[vec[i][j]][t];for(int t=1;t<=box[vec[i+1][k]][0];t++)box[now][++box[now][0]]=box[vec[i+1][k]][t];vec[i].push_back(now);}}}head[i]=tail[i],tail[i]=vec[i].size();}}for(int i=1;i<=now;i++){if(!flag[i]){cout<<'P'<<++cnt<<":"<<endl;cout<<" 字母组合：";for(int j=n-1;j>=0;j--){if(num[i][j]==-1) cout<<"-";else cout<<num[i][j];}cout<<endl<<" 包含的最小项:"; for(int j=1;j<=box[i][0];j++)cout<<box[i][j]<<' ',ans[cnt][j]=box[i][j];ans[cnt][0]=box[i][0];cout<<endl;}}dfs(1,0);//求最小覆盖cout<<"最小项个数:"<<minn<<endl;cout<<"最小项组成：" ; for(int i=1;i<=q;i++)cout<<"P"<<b[i]<<' ';return 0;
}
//5
//11
//0 2 3 8 10 14 15 22 24 27 31