离散数学实验报告

离散数学实验报告.WORD专业.实验报告（2016/2017学年第一学期）课程名称离散数学实验名称利用真值表法求取主析取式以及主合取式的实现离散数学实验报告全文共25页，当前为第1页。离散数学实验报告全文共25页，当前为第1页。离散数学实验报告全文共25页，当前为第2页。实验报告离散数学实验报告全文共25页，当前为第2页。实验名称利用真值表法求取主析取式以及主合取式的实现指导教师实验类型验证实验学时4实验时间实验目的和要求容：编程实现用真值表法求取任意数量变量的合式公式的主析取式和主合取式。要求：能够列出任意合式公式的真值表并给出相应主析取和主合取式。二、实验环境(实验设备)X86架构计算机操作系统：Windows732bitIDE:CodeBlokcs16.02编程语言：C++编译器：GCC三、实验原理及容容：编程实现用真值表法求取任意数量变量的合式公式的主析取式和主合取式。原理：先将中缀表达式转换成后缀表达式，再将后缀表达式中每一个字母变量一一赋值，用递归枚举的方法枚举所有赋值情况，并且用map映射将每一个字母变量与当前被枚举的值一一映射，对每一种赋值情况调用后缀表达式计算函数计算后缀表达式的值，打印真假情况。如果是真，记录到名为zhen的vector不定长数组中，如果是假，记录到名为jia的vector不定长数组中。最后根据zhen和jia的不定长数组来打印主析取式和主合取式。此程序可以实现任意数量的字母变量的主析取式求取和主合取式求取，以及真值表打印。离散数学实验报告全文共25页，当前为第3页。离散数学实验报告全文共25页，当前为第3页。离散数学实验报告全文共25页，当前为第4页。实验报告离散数学实验报告全文共25页，当前为第4页。第一步：预处理预处理，去除中缀表达式中条件->中的>,和双条件<=>中的=和>，这样，所有的运算符只是一个字符，后期处理起来更加方便。voidddd(){ string::iteratori=zhong.begin();//string类迭代器，需在头文件加入#include<string> intflag=1; while(flag){flag=0;for(i=zhong.begin();i!=zhong.end();++i){if(*i=='>'){zhong.erase(i);flag=1;break;}if(*i=='='){离散数学实验报告全文共25页，当前为第5页。zhong.erase(i);离散数学实验报告全文共25页，当前为第5页。flag=1;break;}} }}第二步：将中缀表达式转换后缀表达式利用栈和优先级函数来将中缀表达式转换成后缀表达式，此函数另一个功能是将中缀表达式中所有出现过的字母变量都保存包名为alpha的string类中（string类为STL中的string，需要在头文件加入#include<string>），并且alpha中不出现重复字母，这样，通过alpha.size()函数就可以得到所有字母变量的个数，并且方便后面枚举赋值映射。全局变量：stringzhong;//中缀表达式charhou[1000];//后缀表达式stringalpha;//存放所有字母变量优先级函数：离散数学实验报告全文共25页，当前为第6页。inticp(chara)//栈外优先级离散数学实验报告全文共25页，当前为第6页。{ if(a=='#')return0; if(a=='(')return12; if(a=='!')return10; if(a=='&')return8; if(a=='|')return6; if(a=='-')return4; if(a=='<')return2; if(a==')')return1;}intisp(chara)//栈优先级{ if(a=='#')return0; if(a=='(')return1; if(a=='!')return11; if(a=='&')return9; if(a=='|')return7; if(a=='-')return5; if(a=='<')return3; if(a==')')return12;离散数学实验报告全文共25页，当前为第7页。}离散数学实验报告全文共25页，当前为第7页。voidchange()//中缀表达式转换后缀表达式{ intj=0; stack<char>s;//定义临时栈，需要在头文件加入#include<stack> charch,y; s.push('#'); chart1,t2; stringstreamss(zhong);//字符串流，需要在头文件加入#include<sstream> while(ss>>ch,ch!='#') { if(isalpha(ch))//判断是不是字母，如果是，加入到alpha字符串中 { hou[j++]=ch;//并且加入到后缀表达式字符串中 if(alpha.find(ch)==-1) { alpha.push_back(ch); }离散数学实验报告全文共25页，当前为第8页。 }离散数学实验报告全文共25页，当前为第8页。 elseif(ch==')') { for(y=s.top(),s.pop();y!='(';y=s.top(),s.pop()) { hou[j++]=y; } } else { for(y=s.top(),s.pop();icp(ch)<=isp(y);y=s.top(),s.pop()) { hou[j++]=y; } s.push(y); s.push(ch); } } while(!s.empty()) { y=s.top(); s.pop();离散数学实验报告全文共25页，当前为第9页。 if(y!='#')离散数学实验报告全文共25页，当前为第9页。 { hou[j++]=y; } } hou[j]='#';}第三步：递归枚举每一个字母变量的取值情况用深度优先搜索（dfs）的思想进行递归枚举，如果当前递归深度已经达到字符串长度，就说明所有字母已经取值成功，字母的“值”用map进行映射（需要在头文件加入#include<map>），所有字母都已经枚举后调用cal（）函数对当前取值情况的后缀表达式进行计算，因为map<string,int>M对象是全局变量，所以cal（）函数可以查看到相应字母的取值情况。计算完成后，打印真值，如果当前计算结果是true，那么加入到zhen数组中，以待后面的主析取式打印调用，如果是false，加入到jia数组，以待后面的主合取式打印调用。全局变量：map<char,int>M;//映射，将字母变量与0或1一一对应structnote{ inta[100];离散数学实验报告全文共25页，当前为第10页。};离散数学实验报告全文共25页，当前为第10页。vector<note>zhen;//不定长数组，存放主析取式对应字母变量的01情况，也就是表达式真值为Tvector<note>jia;//不定长数组，存放主合取式对应字母变量的01情况，也就是表达式真值是Fvoiddfs(intcur)//递归枚举每一种字符变量的取值情况{ if(cur==alpha.size()) { intans=cal(); for(inti=0;i<alpha.size();i++) { if(M[alpha[i]]) { printf("T\t"); } else { printf("F\t"); } }离散数学实验报告全文共25页，当前为第11页。 if(ans==1)//真值为T计入到zhen数组，以待后面主析取式使用离散数学实验报告全文共25页，当前为第11页。 { printf("T\n"); notet; for(inti=0;i<alpha.size();i++) { t.a[i]=M[alpha[i]]; } zhen.push_back(t); } else//真值为F计入到jia数组，以待后面主合取式使用 { printf("F\n"); notet; for(inti=0;i<alpha.size();i++) { t.a[i]=M[alpha[i]]; } jia.push_back(t); } return; }离散数学实验报告全文共25页，当前为第12页。 M[alpha[cur]]=1;//深度优先搜索（dfs）进行递归枚举离散数学实验报告全文共25页，当前为第12页。 dfs(cur+1); M[alpha[cur]]=0; dfs(cur+1);}intcal()//对赋值后的后缀表达式进行计算，返回计算结果{ stack<int>s; charch; intj=0; intt1,t2; while(1) { ch=hou[j]; if(ch=='#')break; if(ch==0)break; j++; if((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')) { s.push(M[ch]);离散数学实验报告全文共25页，当前为第13页。 }离散数学实验报告全文共25页，当前为第13页。 else { if(ch=='!') { t1=s.top(); s.pop(); s.push(!t1); } elseif(ch=='&') { t1=s.top(); s.pop(); t2=s.top(); s.pop(); if(t1==1&&t2==1) { s.push(1); } else { s.push(0);离散数学实验报告全文共25页，当前为第14页。 }离散数学实验报告全文共25页，当前为第14页。 } elseif(ch=='|') { t1=s.top(); s.pop(); t2=s.top(); s.pop(); if(t1==0&&t2==0) { s.push(0); } else { s.push(1); } } elseif(ch=='-') { t1=s.top(); s.pop(); t2=s.top();离散数学实验报告全文共25页，当前为第15页。 s.pop();离散数学实验报告全文共25页，当前为第15页。 if(t1==0&&t2==1) { s.push(0); } else { s.push(1); } } elseif(ch=='<') { t1=s.top(); s.pop(); t2=s.top(); s.pop(); if((t1==1&&t2==1)||(t1==0&&t2==0)) { s.push(1); } else {离散数学实验报告全文共25页，当前为第16页。 s.push(0);离散数学实验报告全文共25页，当前为第16页。 } } } } intans=s.top(); returnans;}最后一步：打印主析取式和主合取式最后一步，也是最简单的一步，打印主析取式和主合取式，由于前面在递归枚举dfs的过程中已经把真值表顺带打印了，所以就只剩下主析取式和主合取式了，在dfs过程中，所有取值为真的情况已经加入zhen的vector数组中了，所有取值为假的以及加入到了jia的vector数组中了，虽然存放的是01序列，但是alpha中字母顺序自始至终不变，所以根据下标可以形成一一对应关系。main函数intmain(){ while(true) {离散数学实验报告全文共25页，当前为第17页。 inti;离散数学实验报告全文共25页，当前为第17页。 M.clear(); alpha.clear(); zhen.clear(); jia.clear(); printf("或运算为|,与运算为&,单条件为->,双条件我<=>,非运算为!\n"); printf("请输入表达式,回车结束\n"); cin>>zhong; zhong.append("#"); ddd(); change(); for(i=0;i<alpha.size();i++) { printf("%c\t",alpha[i]); } printf("表达式真值\n"); dfs(0); printf("主析取式为\n"); intlena=zhen.size(); for(i=0;i<lena;i++) {离散数学实验报告全文共25页，当前为第18页。 if(i!=0)printf("∨");离散数学实验报告全文共25页，当前为第18页。 int*p=zhen[i].a; printf("("); for(intj=0;j<alpha.size();j++) { if(j!=0)printf("∧"); if(p[j]==1) { printf("%c",alpha[j]); } else { printf("￢%c",alpha[j]); } } printf(")"); } printf("\n"); printf("主合取式为\n"); for(i=0;i<jia.size();i++) { if(i!=0)printf("∧");离散数学实验报告全文共25页，当前为第19页。 int*p=jia[i].a;离散数学实验报告全文共25页，当前为第19页。 printf("("); for(intj=0;j<alpha.size();j++) { if(j!=0)printf("∨"); if(p[j]==0) { printf("%c",alpha[j]); } else { printf("￢%c",alpha[j]); } } printf(")"); } printf("\n\n"); } return0;}离散数学实验报告全文共25页，当前为第20页。离散数学实验报告全文共25页，当前为第20页。程序测试与分析：由于使用了STL中vector数组和string类，所以可以实现计算含有任意数量的字母变量的表达式。本程序中或运算为|,与运算为&,单条件为->,双条件我<=>,非运算为!测试一：输入P&Q运行截图：结果：正确测试二：离散数学实验报告全文共25页，当前为第21页。输入书上第37页下方例题(P&Q)|(!P&R)离散数学实验报告全文共25页，当前为第21页。结果：正确测试三：课本39页（4）d）(P->(Q&R))&(!P->(!Q&!R))离散数学实验报告全文共25页，当前为第22页。离散数学实验报告全文共25页，当前为第22页。测试四输入A&B&C&D&E正确离散数学实验报告全文共25页，当前为第23页。离散数学实验报告全文共25页，当前为第23页。测试五输入课本39页（2）b）P->((Q&R)->S)正确测试六：输入：课本39页（4）a）(!P|!Q)->(P<=>!Q)离散数学实验报告全文共25页，当前为第24页。正确离散数学实验报告全文共25页，当前为第24页。实验报告四、实验小结（包括问题和解决方法、心得体会