离散数学实验指导书2010.doc

《离散数学》实验指导 一 实验课的任务、性质与目的 本实验课程是信息专业学生的一门专业基础课程，通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。 二 实验目标 1. 掌握离散数学中涉及的相关概念。 2. 培养学生的逻辑思维能力和算法设计的思想。 3. 熟练掌握C/C++语言程序设计的基本方法和各种调试手段。 4. 熟练掌握包括数组、链表以及邻接表或邻接矩阵等数据结构的建立和运用。 5. 通过实验掌握递归程序设计的基本方法。 6. 掌握图的存储和遍历方法。 三 实验要求 实验前，复习《离散数学》课程中的有关内容。 上机前编好程序，上机时调试。 编程要独立完成，程序应加适当的注释。 完成实验报告。 四 实验报告要求 “离散数学”实验报告 专业 班级 学号 姓名 日期  封面：如右图 文字用小4号或4号；程序和注释用5号 以班为单位交. 实验报告文件名：080x姓名学号（实验xA/B/C） 实验报告上交时间：做完实验后一到两周内，在课间拷贝到教室机器的指定目录中。 实验一 一 实验内容（二选一） 1. 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、条件和双条件的真值。（A） 2. 求任意一个命题公式的真值表（B，并根据真值表求主范式（C）） 注意：题目类型分为A，B，C三类，其中A为基本题，完成A类题目可达到设计的基本要求，其他均为加分题，并按字母顺序分数增加越高。 二 实验目的 熟悉掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。 三 实验环境 C或C＋＋语言编程环境实现。 四 实验说明 1. 逻辑联接词的运算 本实验要求大家利用C/C＋＋语言，实现二元合取、析取、条件和双条件表达式的计算。充分利用联接词和逻辑运算符之间的相似性实现程序功能。 2. 求任意一个命题公式的真值表 本实验要求大家利用C/C＋＋语言，实现任意输入公式的真值表计算。一般???们将公式中的命题变元放在真值表的左边，将公式的结果放在真值表的右边。命题变元可用数值变量表示，合适公式的表示及求真值表转化为逻辑运算结果；可用一维数表示合式公式中所出现的n个命题变元，同时它也是一个二进制加法器的模拟器，每当在这个模拟器中产生一个二进制数时，就相当于给各个命题变元产生了一组真值指派。算法逻辑如下： （1）将二进制加法模拟器赋初值0 （2）计算模拟器中所对应的一组真值指派下合式公式的真值。 （3）输出真值表中对应于模拟器所给出的一组真值指派及这组真值指派所对应的一行真值。 （4）产生下一个二进制数值，若该数值等于2n-1，则结束，否则转（2）。 注意，在进行表达式求值的时候，可先将带括号的中缀表达式利用栈结构转换为不带括号的后缀表达式（逆波兰式），然后进行计算。具体方法请参考数据结构中有关“栈”的知识。 五 实验要求 在实验报告中要写下列内容： 1. 实验目的； 2. 实验内容； 3. 实验环境； 4. 实验原理和实现过程（算法描述）； 5. 实验数据及结果分析； 6. 源程序清单； 7. 其他收获和体会。 注意： 程序需具有基本的容错控制，在输入错误时有处理手段； 程序界面友好，需要输入的地方有输入说明，说明输入的内容和格式要求等； 实验原理和实现过程应该详细分析问题，给出解决思路，描述算法思想，不能用源程序代替算法； 测试数据应全面，包括非法输入的处理结果等都应包含在内 实验二 一 实验内容（三选一） 1. 求有限集上给定关系的自反、对称和传递闭包。（有两种求解方法，只做一种为A，两种都做为B） 2. 求有限集上等价关系的数目。（有两种求解方法，只做一种为A，两种都做为B） 3. 求解商集，输入集合和等价关系，求相应的商集。（C） 注意：题目类型分为A，B，C三类，其中A为基本题，完成A类题目可达到设计的基本要求，其他均为加分题，并按字母顺序分数增加越高。 二 实验目的 掌握关系的概念与性质，基本的关系运算，关系的各种闭包的求法。理解等价类的概念，掌握等价类的求解方法。 三 实验环境 C或C＋＋语言编程环境实现。 四 实验说明 1. 求有限集上等价关系的数目。 集合上的等价关系与该集合的划分之间存在一一对应关系。一个等价关系对应一个划分，一个划分也对应一个等价关系。我们把n个元素的集合划分成k块的方法数叫第二类Stirling数，表示为S(n,k)。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此S(4,1) = 1；若所有人分成