离散数学实践指导书.doc

离散数学实践实验指导书课程类型：必修课适应专业：计算机科学与技术总学时：20学时 实验学时：20（上机）实验次数：7先修课程：C（+）语言 一、前言离散数学课程实验的目的是培养学生使用所学过的计算机程序设计语言求解一些简单的离散数学问题，通过实验帮助实验者理解有关的重要概念，加深了解和更好地掌握离散数学课程教学大纲要求的内容。在离散数学实践的课程实验过程中，要求学生做到：1. 预习实验指导书有关部分，认真做好实验内容的准备，就实验可能出现的情况提前做出思考和分析；2. 认真书写实验报告。实验报告包括实验目的和要求，实验情况及其分析；写出程序设计说明，给出源程序框图和清单；3. 实验完成之后，应对算法与源程序进行评价，对运行结果进行分析，提交源程序及两组调试数据及其实验结果；4. 遵守机房纪律，爱护实验设备。二、实验目的1. 培养学生动手编程解决实际问题的能力；2. 训练学生分析问题和调试程序的能力；3. 锻炼学生分析科技实验结果的能力；4. 为后续的课程学习和工作奠定良好的基础。三、实验要求1. 问题分析：充分地分析和理解问题本身，弄清要求做什么，用什么算法。2. 程序设计1) 根据所采用的算法，设计数据结构，画出流程图并编程；2) 最后准备调试程序的数据及测试方案。 3. 上机调试 1) 对程序进行编译，纠正程序中可能出现的语法错误； 2) 调试前，先运行一遍程序看看究竟将会发生什么； 3) 如果情况不好，根据事先设计的测试方案并结合现场情况进行错误跟踪，包括单步调试. 设置观察窗输出中间变量值等手段。4. 整理实验报告 1) 实验内容：采用的算法名称； 2) 问题描述：包括目标. 任务. 条件约束描述等； 3) 设计：数据结构设计和核心算法设计. 主要功能模块的输入. 处理（算法框架）和输出； 4) 测试范例：测试结果的分析讨论. 测试过程中遇到的主要问题及所采用的解决措施； 5) 心得：包括程序的改进设想，经验和体会； 6) 程序清单：源程序，其中包括变量说明及详细的注释。四、实验目录本部分共有4个实验: 建立关系矩阵、5种关系性质判断、关系的基本运算、求相容关系的极大相容类。序号实验名称实验简介实验学时每组人数实验类型1建立关系矩阵使用VC+实现一个程序为给定的关系，建立关系矩阵41设计2关系的5种性质判断使用VC+实现一个简单的程序判断关系的五种性质61设计3关系的基本运算编程实现求关系的逆、关系的合成、实现Warshall算法求关系的传递闭包41设计4求相容关系的极大相容类编程实现求相容关系的极大相容类61设计五. 具体实验说明（下面仅给出一种方法，允许采用其他方法）实验1：建立关系矩阵1、 实验类型：学习型实验2、 实验要求和目的：理解并掌握关系的矩阵表示方法、为用序偶集合表示的关系建立相应的关系矩阵。学会用所学过的程序设计语言编程，解决关系矩阵的自动建立问题。3、 实验内容：用二维数组或向量存储关系矩阵，根据输入的用序偶集合表示的关系，建立相应的关系矩阵。分别输入两个用序偶集合表示的关系作为实验数据，输出并打印所建立的矩阵。4、 实验步骤：a) 利用vc+建立工程；b) 设计关系的矩阵表示的实现程序；实验2：关系5种性质判断1. 实验类型：学习型实验2. 实验要求和目的：理解并掌握关系的矩阵表示方法、利用关系的矩阵判断一个关系是否具有自反、反自反、对称、反对称和传递性。学会用所学过的程序设计语言编程，解决关系性质的自动判断问题。3. 实验内容：用二维数组存储关系矩阵，根据关系矩阵的特征，判断给定的关系具有哪些性质。分别输入两个关系作为实验数据，输出并打印判断结果。4. 实验步骤：a) 利用vc+建立工程；b) 设计判定关系的自反、反自反、对称、反对称、传递性质的实现程序。实验3：关系的基本运算（求关系的逆、关系的合成、关系的传递闭包） 1、 实验类型：学习型实验2、 实验要求和目的：通过本实验加深理解逆关系、合成关系和关系的闭包。掌握求逆关系、合成关系和关系传递闭包的实现方法3、 实验内容：用矩阵的转置，求得其逆关系的关系矩阵。用矩阵的布尔乘积求复合关系的关系矩阵。用Warshall算法求关系闭包。要求分别输入两组实验数据，输出并打印运行结果。4、 实验步骤：a) 利用vc+建立工程；b) 设计求矩阵的逆、布尔乘积、warshall算法的实现程序。n Warshall算法： 利用关系的矩阵表示，可通过Warshall算法计算有限集合上二元关系的传递闭包。 设A是有限集合，|A|=n, RAA. (1) 置矩阵A:=MR; (2) 置i:=1; (3) 对所有j,若Aj,i=1,则对k=1,2, , n,置Aj,k=Aj,k+Ai,k; (4) 置i:=i+1;(5) 若in,则转至(3),否则结束。实验4：求相容关系的极大相容类1、 实验类型：学习型实验2、 实验要求和目的：通过本实验加深理解相容关系的极大相容类，学习并掌握用所学过的程序设计语言实现求相容关系的极大相容类的方法3、 实验内容：用二维数组存储相容关系矩阵，用课堂上所介绍的矩阵法求给定相容关系的所有极大相容类。要求分别输入两组实验数据，输出并打印运行结果。4、 实验步骤：a) 利用vc+建立工程；b) 设计矩阵法求极大相容类的实现程序。n 关系矩阵法：设R为x1,xn上的相容关系,MR=aijnxn1) 令p=x1,xn,若n=1,则终止；2）i:=n-1;3) A:=xj|aji=1i1,则i:=i-1,转3),否则结束。华侨大学离散数学实验报告XXX实验 姓名： 专业： 班级： 学号： 日期： 摘要：.（说明实验的目的、内容， 本实验所采用的方法，所得的实验结果及分析。最后，给出实验的结论）一导言1) 问题的描述 （实验目标、任务、条件约束描述等）2) 拟采用的方法 （通过对问题的分析，描述拟采用的解决方法）二实验过程1) 算法思想流程2) 程序流程图3) 功能模块说明三结果分析1) 实验环境2) 算法设计的参数说明3) 实验结果4) 结果分析与讨论5) 算法的优缺点6) 实验的不足之处及改进设想四实验心得主要参考文献上交的文件夹格式如下