离散数学实验报告

离散数学实验报告离散数学实验报告实验报告（2016/2017学年第一学期）课程名称离散数学实验名称利用真值表法求取主析取范式以及主合取范式的实现实验报告实验名称利用真值表法求取主析取范式指导教师以及主合取范式的实现实验类型验证实验学时4实验时间一、实验目的和要求内容：编程实现用真值表法求取任意数量变量的合式公式的主析取范式和主合取范式。要求：能够列出任意合式公式的真值表并给出相应主析取和主合取范式。二、实验环境(实验设备)X86架构计算机操作系统：Windows732bitIDE:CodeBlokcs16.02编程语言：C++编译...

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

                    本文档为【离散数学实验报告】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

离散数学实验报告

你可能还喜欢