《离散数学实验报告资料》由会员分享，可在线阅读，更多相关《离散数学实验报告资料（25页珍藏版）》请在金锄头文库上搜索。
1、实 验 报 告（2016 / 2017 学年 第 一 学期）课程名称离散数学实验名称利用真值表法求取主析取范式以及主合取范式的实现实 验 报 告实验名称利用真值表法求取主析取范式以及主合取范式的实现指导教师实验类型验证实验学时4实验时间一、 实验目的和要求内容：编程实现用真值表法求取任意数量变量的合式公式的主析取范式和主合取范式。要求：能够列出任意合式公式的真值表并给出相应主析取和主合取范式。二、实验环境(实验设备)X86架构计算机操作系统：Windows 7 32bitIDE: CodeBlokcs 16.02编程语言：C+编译器：GCC三、实验原理及内容内容：编程实现用真值表法求取任意数量
2、变量的合式公式的主析取范式和主合取范式。原理：先将中缀表达式转换成后缀表达式，再将后缀表达式中每一个字母变量一一赋值，用递归枚举的方法枚举所有赋值情况，并且用map映射将每一个字母变量与当前被枚举的值一一映射，对每一种赋值情况调用后缀表达式计算函数计算后缀表达式的值，打印真假情况。如果是真，记录到名为zhen的vector不定长数组中，如果是假，记录到名为jia的vector不定长数组中。最后根据zhen和jia的不定长数组来打印主析取范式和主合取范式。 此程序可以实现任意数量的字母变量的主析取范式求取和主合取范式求取，以及真值表打印。 实 验 报 告第一步：预处理 预处理，去除中缀表达式中条
3、件-中的,和双条件中的= 和 ，这样，所有的运算符只是一个字符，后期处理起来更加方便。 void ddd() string:iterator i=zhong.begin(); /string类迭代器，需在头文件加入#includeint flag=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); flag=1; break; 第二步：将中缀表达式转换后缀表达式 利用栈和优先级函数来将中缀表达式转换成
4、后缀表达式，此函数另一个功能是将中缀表达式中所有出现过的字母变量都保存包名为alpha的string类中（string类为STL中的string，需要在头文件加入#include），并且alpha中不出现重复字母，这样，通过alpha.size()函数就可以得到所有字母变量的个数，并且方便后面枚举赋值映射。全局变量：string zhong; /中缀表达式char hou1000; /后缀表达式string alpha; /存放所有字母变量优先级函数： int icp(char a) /栈外优先级if(a=#) return 0;if(a=() return 12;if(a=!) return
5、 10;if(a=&) return 8;if(a=|) return 6;if(a=-) return 4;if(a=) return 2;if(a=) return 1;int isp(char a) /栈内优先级if(a=#) return 0;if(a=() return 1;if(a=!) return 11;if(a=&) return 9;if(a=|) return 7;if(a=-) return 5;if(a=) return 3;if(a=) return 12; void change() /中缀表达式转换后缀表达式int j=0;stack s; /定义临时栈，需要在
6、头文件加入#include char ch,y;s.push(#);char t1,t2;stringstream ss(zhong); /字符串流，需要在头文件加入#include while(ssch,ch!=#)if(isalpha(ch) /判断是不是字母，如果是，加入到alpha字符串中houj+=ch; /并且加入到后缀表达式字符串中if(alpha.find(ch)=-1)alpha.push_back(ch);else if(ch=)for(y=s.top(),s.pop();y!=(;y=s.top(),s.pop()houj+=y;elsefor(y=s.top(),s.p
7、op();icp(ch)=isp(y);y=s.top(),s.pop()houj+=y;s.push(y);s.push(ch);while(!s.empty()y=s.top();s.pop();if(y!=#)houj+=y;houj=#; 第三步：递归枚举每一个字母变量的取值情况 用深度优先搜索（dfs）的思想进行递归枚举，如果当前递归深度已经达到字符串长度，就说明所有字母已经取值成功，字母的“值”用map进行映射（需要在头文件加入#include），所有字母都已经枚举后调用cal（）函数对当前取值情况的后缀表达式进行计算，因为map M对象是全局变量，所以cal（）函数可以查看到相应
8、字母的取值情况。 计算完成后，打印真值，如果当前计算结果是true，那么加入到zhen数组中，以待后面的主析取范式打印调用，如果是false，加入到jia数组，以待后面的主合取范式打印调用。 全局变量：map M; /映射，将字母变量与0或1一一对应struct noteint a100;vector zhen; /不定长数组，存放主析取范式对应字母变量的01情况，也就是表达式真值为Tvector jia; /不定长数组，存放主合取范式对应字母变量的01情况，也就是表达式真值是Fvoid dfs(int cur) /递归枚举每一种字符变量的取值情况if(cur=alpha.size()int
9、ans=cal();for(int i=0;ialpha.size();i+)if(Malphai)printf(Tt);elseprintf(Ft);if(ans=1) /真值为T 计入到zhen数组，以待后面主析取范式使用printf(Tn);note t;for(int i=0;ialpha.size();i+)t.ai=Malphai;zhen.push_back(t);else /真值为F 计入到jia数组，以待后面主合取范式使用printf(Fn);note t;for(int i=0;ialpha.size();i+)t.ai=Malphai;jia.push_back(t);return ;Malphacur=1; /深度优先搜索（dfs）进行递归枚举dfs(cur+1);Malphacur=0;dfs(cur+1); int cal() /对赋值后的后缀表达式进行计算，返回计算结果stack s;char ch;int j=0;int t1,t2;while(1)ch=houj;if(ch=#) break;if(ch=0) break;j+;if(ch=A&ch=a&ch=z)s.push(Mch);elseif(ch=!)t1=s.top();s.pop();s.push(!t1);else if(ch=&)t1=s.top();s.pop();
