离散数学期末大作业.docx

离散数学课程期末大作业1、 通过本大作业设计实现如下目的1. 加深对离散数学理论知识的理解2. 增强学习兴趣3. 提高学生的动手能力和自学能力2、 实验内容1. 逻辑篇某班班委选举，已知王小红，李强，丁金生三人被选进班委会，甲乙丙三位同学预言： 甲：王小红班长，李强生活委乙：丁金生班长，王小红生活委丙：李强班长，王小红学习委名单公布后，每个人恰好猜对一半，问班委是如何分派的？要求编程完成如下功能：设：王小红是班长，：丁金生是班长，：李强是班长：王小红是生活委，：李强是生活委，：王小红是学习委员请用真值表法求解满足题目要求的一组解。提示：即证明在求解过程中，考虑每人只能担任一个职务，一个职务也只能由一个人来担任，因此，有且仅有一个为T，有且仅有一个为T，q3， 不能同时为T，可以利用这点，去除其中的永假项。难度：较难2. 集合篇对于给定集合A上的一个2元关系R，要求编程完成如下功能。其中涉及的所有关系在程序内直接赋值，例如：A=a,b,c，A上有关系R=,，则其对应的关系矩阵为：MR=000101101，因此该关系可以采用一个二维数组 R33存储。关系中的元素个数不定，由用户确定。可选题目：（括号中为建议使用函数名）(1) 判断该关系是否满足自反（isReflexive），如不是求出自反闭包（reflexiveClosure）判断是否满足对称（isSymmetric），如不满足求出对称闭包（symmetricClosure）判断是否满足反对称（isAntiSymmetric） 难度：简单(2) 求出该关系的传递闭包（transitiveClosure，Warshall,使用两种方法求解，分别由两个不同的函数实现），判断该关系是否满足传递性（isTransitive） 难度：中等(3) 判断是否等价关系（isEquivalence），如是求出相应的划分（partition）难度： 中等(4) 判断是否相容关系（isCompatible），如是求出完全覆盖（fullCover）难度：较难(5) 判断是否偏序关系（isPartialOrder），如是，求出所在集合A的极大元(maximal)，极小元(minimal)，最大元(greatest)，最小元(least)，给定A的任一子集B，求出子集B的上确界(supremum)，下确界(infimum)，（如果存在的话），判断该关系是否全序关系(isTotallyOrdered)。难度：较难3. 函数篇测试数据的存储方式与关系篇一致。可选题目：(6) 判断一个关系是否是函数（isFunc）。如果是函数，则判断函数是否是入射（isInjection）、满射(isSurjection)和一一映射(isBijection)。难度：简单4. 图论篇测试数据的存储方式与关系篇类似。如图G，包含5个点，可以采用二维矩阵G55 存储其邻接矩阵。可选题目：(7) 判断一个有向图中所有顶点的度数(Degree)、出度(inDegree)和入度(outDegree) 难度：简单(8) 判断一个图中任意两个顶点间指定长度的通路数(nRoad) 难度：中等(9) 判断一个图是否是欧拉图(isEuler)，若是，输出欧拉回路(EulerCircuit) 难度：较难(10) 判断一个平面图的着色数（nColor）难度：中等(11) 判断一个图是否是树(isTree)，若不是树，求解其最小生成树（Kruskal）难度：较难3、 编程具体要求1. 上述11题，可以选择任一题完成。如果有余力，可以完成多题，所有的报告写在一个报告内2. 编程注意程序的可读性3. 可采用任何编程语言实现4. 建议在编写时，考虑采用面向对象的思想实现5. 建议在设计时考虑人机友好性，采用友好美观的界面4、 大作业报告具体要求1， 写明作业要求2， 给出各功能的实现算法（用VISIO绘制流程图）3， 实现过程中遇到的困难（如算法设计的错误，程序编程错误等等，说明如何解决，可采用列表形式一一罗列，配上调试时的错误截图）。此项非常重要，是考察你是否独立完成的重要依据！4， 给出心得体会，自由发挥。5， 以上为大作业报告的必须部分，其他部分可自由掌握。6， 文档撰写采用word软件。撰写时请注意排版格式。5、 提交方法1. 每个同学都要上交1份报告（报告封面见最后一页模板，程序源代码不要放入报告中），报告必须按照上文”第四条：大作业报告具体要求”撰写。2. 要求在第16周周五前提交。3. 最后提交内容包括 （1）程序源代码(包含完整工程) （2）报告 （3）编译生成的可执行文件 将上述内容均放入一个文件夹，文件夹以 学号_姓名 命名，交给课代表，由课代表统一刻录到光盘中。并请课代表发送一个备份（压缩文件）到信箱28231894。6、 课堂演示本课程最后一次课（14周周五）将安排同学上台演示，愿意给大家展示你的成果的同学，请在13周前在我这里报名，以便安排。展示成果主要以幻灯片与程序演示结合的方式。主要给大家介绍你的设计思路，展示你的最终成果。7、 评分标准1. 总评分=期末大作业（70%）+平时成绩（30%）2. 期末大作业的评分考察范围包括 （1）报告（50%） （3）源代码（50%） 。请重视报告的写作质量。3. 程序评分标准：1) 90-100：程序正确，设计合理（使用函数实现各个子功能）2) 80-89：程序正确，设计合理3) 70-79：程序基本功能实现（存在一些小问题）4) 60-69：程序部分功能未实现，但关键功能已经实现5) 60以下：程序未完成或存在抄袭现象，态度不端正（无故缺席2次及以上，发现玩游戏等）4. 文档评分标准：1) 90-100：文档完整，条理清晰，格式规范，图文并茂，态度端正2) 80-89：文档存在小问题，图文并茂，态度端正3) 70-79：文档完整，态度端正4) 60-69：文档基本完整，态度端正5) 60以下：存在抄袭现象，态度不端正（无故缺席2次及以上，发现玩游戏等）5. 请勿抄袭，不管是代码还是报告，抄袭一律0分6. 难度分：较难：+10分 中等：+5分 简