真值表的C 算法实现.doc

08 届课程 设计 论文 题题 目目命命题题公公式式的的真真值值表表算算 法法 专专业业班班级级信信息息与与计计算算科科学学 1 班班 学学 号号0809030116 学学生生姓姓名名上上官官业业云云 指指导导教教师师李李圆圆媛媛 指指导导教教师师职职称称讲讲师师 学学院院名名称称理理学学院院 完完成成日日期期 2010 年年 09 月月 27 日日 武汉工程大学本科课程设计 论文 目目 录录 目 录 I 摘 要 III 前 言 IV 第 1 章 课题背景 1 1 1 背景 1 1 2 性质 1 1 3 意义 1 1 4 实验数据与结果 1 1 5 文献综述 2 第 2 章 问题的分析与算法的实现 3 2 1 问题的分析 3 2 2 算法的实现 3 第 3 章 总 结 13 致 谢 14 参考文献 15 附 录 16 武汉工程大学本科课程设计 论文 I 摘摘 要要 为了解决命题公式的真值表算法问题 本文采用 面向对象编程 输入命题 变元 并以字符串形式读入命题公式 应用运算符重载来进行相关运算 并在 C 使用的编译工具为 VS2010 下 给出了问题的具体解决方案 关键词关键词 命题公式 真值表 类 运算符重载 递归 字符串 武汉工程大学本科课程设计 论文 II 前前 言言 本文解决了计算任意含个命题变元的命题公式的真值表的C 算 Nnn 法 全文共 3 章 第 1 章介绍了 问题背景 问题以及性质问题的意义 在本章中 还给出了具 体的实验数据和我们查阅并借用的一些参考文献的主要内容 第 2 章主要介绍了在对问题的分析 后设计的算法 并编写程序 求出其具 体调度方案 第 3 章是本次课程设计的总结 全文的最后是致谢 参考文献和程序的源代码 上官业云 武汉工程大学理学院 武汉工程大学本科课程设计 论文 0 第第 1 1 章章 课课题题背背景景 1 1 1 1 背景背景 设为含有命题变元的命题公式 给一组确定的取值 F n PPP 21 n PPP 21 称为公式关于的一组真值指派 含有个命题变元的公式有组F n PPP 21 n n 2 不同的真值指派 对于每一组真值指派 公式都有一个确定的真值 一般用 0 表示假 1 表示真 公式与其命题变元之间的真值关系可以用真值 表的方法方便的表示出来 1 1 2 2 性质性质 含有个命题变元的公式有组不同的真值指派 对于每一组真值指派 n n 2 公式都有一个确定的真值 一般用 0 表示假 1 表示真 1 1 3 3 意义意义 使用计算机来完成各种复杂的真值表计算 尤其是当命题变元增多时 对应 的取值成指数增长 计算量也指数增长 紧靠人很难完成 应用计算机强大的计 算能力 可以又好又快的完成任意命题公式的真值表的计算 1 1 4 4 实验数据实验数据与结果与结果 实验时 本文主要是用编写的程序计算参考资料 1 上的相关命题公式来验 证相关算法的正确性 稳定性 由程序计算得出的命题公式的真值表 2 SQQPF 武汉工程大学本科课程设计 论文 1 1 上 236 页给出的答案 PQSQP Q SQ SQQP 0001100 0011111 0100010 0110010 1000100 1010110 1101011 1111011 二者除命题变元取值顺序不一样外 最后的真值结果完全吻合 表明算法的 正确性 稳定性 1 1 5 5 文献综述文献综述 文献 0 介绍了命题变元与命题公式真值表的相关知识 文献 Error Reference source not found 介绍了 C 程序设计基础知识 文献 Error Reference source not found 提供了 C 面向对象的 程序设计 武汉工程大学本科课程设计 论文 2 相关知识 武汉工程大学本科课程设计 论文 3 第第 2 2 章章 问问题题的的分分析析与与算算法法的的实实现现 2 2 1 1 问题的分析问题的分析 对于含有个命题变元的公式有组不同的真值指派 对于每一组真值指n n 2 派 公式都有一个确定的真值 这里 0 表示假 1 表示真 为了枚举 出所有的情形 须用重 for 循环 为了使程序具有通用性 的取值是不确nn 定的 这时 使用递归的算法就较方便 给命题变元赋值的问题解决后 还得解决计算问题 在这里 本文采用 面向对象的方法 通过运算符的重 载来完成相关计算 定义了类 Proposition 它包括两个变量 命题变元名和命题变元的真值 和相关成员 函数 需重载的运算符 再设计计算真值的函数 考虑到命题公式中可能会出现括号 改变了运算 的优先级 本文同样采用递归的算法 当遇到括号时 把括号里面的部分作为一 个命题公式来计算 再把结果作为一个命题变元放到整个命题公式进行计算 而 当遇到相关的运算符时 重载运算符进行计算 最后返回真值 最后 主函数只需完成输入并存储命题变元与命题公式 调用赋值函数就 行了 由以上方法可以进行真值的运算 但程序冗余太长 再对其进行优化处理 用另一函数来代替大量重复的代码 使程序更简洁 2 2 2 2 算算法法的的实实现现 定义命题变元类 Proposition class Proposition int data char data1 data 命题的真值 0 1 data1 命题名 public 武汉工程大学本科课程设计 论文 4 Proposition data 2 data1 A friend Proposition operator Proposition 定义否定运算符 friend Proposition operator 定义合取运算符 定义析取运算符 friend Proposition operator Proposition 定义蕴含运算符 friend Proposition operator Proposition 定义等值运算符 0 p input1 1 else p input1 0 return p Proposition operator Proposition else p input1 1 武汉工程大学本科课程设计 论文 5 return p Proposition operator Proposition else p input1 0 return p 其中函数 void input1 int x 用于输入命题变元的真值 函数void input2 char x 用于输入命题名 int get 与 int get1 分别用于获取命题 真值和命题名 运算符重载部分由 1 中的知识得出 给命题变元赋值 void fuzhi string A int N int M Proposition a for int j 0 j1 fuzhi A N 1 M else for int i 0 i M i cout a i get cout bds A M int L int i 0 L strlen 计算表达式长度 while i L if A i 括号的处理 int k 1 for int j i 2 j L j if k 0 if A j k if A j k if k 0 int l j i 1 char p new char l 1 string B for int m 0 m l m 武汉工程大学本科课程设计 论文 7 p m A i 1 m p l 0 B p delete p Temp input1 bds B N if i 0 ANS input1 Temp get i j 1 break else if A i 否定的计算 Temp input1 jisuan A i L N ANS Temp i continue else if A i Temp input1 jisuan A i L N ANS ANS Temp i continue 武汉工程大学本科课程设计 论文 8 else if A i ANS ANS i continue else if A i Temp input1 jisuan A i L N ANS ANS Temp input1 jisuan A i L N ANS ANS Temp i continue else for int j 0 j 存储的是 5 个重载的运算符名 用于识别运算符 jisuan A i L N if A i 1 int k 1 for int j i 2 j L j if k 0 if A j k if A j 武汉工程大学本科课程设计 论文 10 k if k 0 int l j i 1 char p new char l 1 string B for int m 0 m l 1 m p m A i 2 m p l 1 0 B p delete p Temp input1 bds B N i i j break else int j 0 while j L if A i 1 char a j get1 i Temp a j 武汉工程大学本科课程设计 论文 11 break j return Temp get 为了使主函数看起来更简洁 把以上内容都放入头文件zzb h 中 主函 数部分同时还完成命题变元及命题公式的输入与储存 最后调用函数void fuzhi string A int N int M Proposition a 完成全部计算 其内容如下 Proposition a 30 char x 1 int i 0 N cout 请输入涉及的命题变元 输入 0 按回车结束 x if i 19 cout 命题变元个数超过 30 无法处理 endl break if x 0 a i input2 x i N i 武汉工程大学本科课程设计 论文 12 int M M N string A cout 等值 A cout A 的真值表为 endl for int j 0 j M j cout char a j get1 cout 真值 endl fuzhi A N M system pause return 0 从实验结果还可以看出 本程序的通用性强 能够识别全部五种运算及括号 这样在理论上是可以计算任意复杂的命题公式的真值表 当然 由于计算机硬件 及 C 的递归深度的限制 命题公式的复杂度超过一定限制也会无法计算 对于 一般性的复杂命题公式的真值计算 本程序完全可以胜任 完整的源代码在附录中 武汉工程大学本科课程设计 论文 13 第第 3 3 章章 总总 结结 在大学过去的两年里 我学习了 C 程序设计基础 C 面向对象 程序设计 和 算法与数据结构 老实说 对这些课学的有些吃力 因为自 己动手时总是困难重重 很多时候是处于理论的学习而没有上机的实践操作 在有限的上机操作时 经常是看懂老师提供的代码就算了 平时遇到问题 总是 到网上找代码 几乎没有自己原创的程序 也没认真下功夫去写过代码 但是 这次课程设计从选题开始 就给自己定了一个较高的要求 选的题是自己觉得可 供选择的题中最难得一个 同时也力求100 独立自主完成 在做这次课程设 计的过程中 有遇到问题而一时又无法解决时的无奈 也有写代码调程序到深夜 的艰辛 更有解决某个问题和最后成功的喜悦 一般来讲 构想一个算法并不困难 难的是把设计的算法变成有效的代码 在代码的调试中 经常出现编译通过了 但运行时报错 而这类问题又很难查到 这就需要花时间和精力 没有足够的耐心是不行的 当遇到这类问题时 我常常 不知所措 每每想要放弃时 都会想到我的程序员梦想 想到数模竞赛时的那股 干劲和精神 这样又有了动力 重新开始调试 虽然有时一连几个小时都毫无进 展 但我坚持下来了 最后写的程序基本上达到了预定目标 功能上完全达到了 只是没有容错能力 稳定性还不够强 同时 经过这次的课程时机 我有了许多收获 意志得到了锻炼 获得了很 多编程的经验 每每调试错误 我都会有新的发现 新的收获 能更好的利用现 有的资源为我服务 如现在我能更好的利用MSDN2010 的资源 当遇到错误时 通过它 往往能够找到我想要的 无所谓会做或不会做 编程非登天般难 唯有做与不做 武汉工程大学本科课程设计 论文 14 致致 谢谢 不应该放弃 直到失去的那一刻 我们见过多少 无私提供帮助甚至放弃休息来服务学生的老师 默默奉献一生的父母 还有热情鼓励和给予帮助的同学 能忘记他们的期盼和自己的梦想吗 不能 为了不辜负他们的希望 更为了自己的明天生活 我坚持下来了 因为我有这样的义务 使命 哪怕时间紧 基础薄 但是 谁说我不能独立完成程序创作 不是吗 经过半个月的奋斗 达到预期没标 不管最终评分的高低 在做课程设计的半个月里 我又一次刻画了人生的烙印 仅以此篇课程设计感谢 提供过帮助的老师 同学 养育我二十年的父母 武汉工程大学本科课程设计 论文 15 参参考考文文献献 1 洪帆 离散数学 第 3 版 武汉 华中科技大学出版社 2008 2 吴文虎 程序设计基础 第 2 版 M 北京 清华大学出版社 2004 3 谭浩强 C 面向对象程序设计 M 北京 清华大学出版社 2008 武汉工程大学本科课程设计 论文 16 附附 录录 命题公式的真值表算 法完整源代码 VS2010 调试通过 真值表 CPP 真值表 cpp 定义控制台应用程序的入口点 include stdafx h include zzb h int main Proposition a 30 char x 1 int i 0 N cout 请输入涉及的命题变元 输入 0 按回车结束 x if i 19 cout 命题变元个数超过 30 无法处理 endl break if x 0 a i input2 x i N i int M M N 武汉工程大学本科课程设计 论文 17 string A cout 等值 A cout A 的真值表为 endl for int j 0 j M j cout char a j get1 cout 真值 endl fuzhi A N M system pause return 0 zzb h ifndef ZZB H define ZZB H include include include using namespace std class Proposition int data char data1 data 命题的真值 0 1 data1 命题名 public Proposition data 2 data1 A friend Proposition operator Proposition 定义否定运算符 friend Proposition operator 武汉工程大学本科课程设计 论文 18 定义合取运算符 定义析取运算符 friend Proposition operator Proposition 定义蕴含运算符 friend Proposition operator Proposition 定义等值运算符 0 p input1 1 else p input1 0 return p Proposition operator Proposition else p input1 1 return p Proposition operator Proposition 武汉工程大学本科课程设计 论文 19 else p input1 0 return p void fuzhi string A int N int M Proposition a int bds string A int N Proposition a int jisuan string A int void fuzhi string A int N int M Proposition a 命题赋值并计算真值 for int j 0 j1 fuzhi A N 1 M else for int i 0 i M i cout a i get cout bds A M int L int i 0 L strlen 计算表达式长度 while i L if A i 括号的处理 int k 1 for int j i 2 j L j if k 0 if A j k if A j k if k 0 int l j i 1 char p new char l 1 string B for int m 0 m l m p m A i 1 m p l 0 B p 武汉工程大学本科课程设计 论文 21 delete p Temp input1 bds B N if i 0