离散数学实验报告__四个实验

1、离散数学课程设计计算机学院学生姓名指导教师 评阅意见提交日期 2011 年11月25日引言离散数学是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等） 的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、 电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思

2、维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性）一、前言引语： 二元关系是离散数学中重要的内容。因为事物之间总是可以根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之间存在的关系。二、数学原理：自反、对称、传递关系设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合 R就 是AX B的一个合于R=（x,y）C A

3、X B|xRy的子集合设 R 是集合 A 上的二元关系： 自反关系：对任意的xe A,都满足e R,则称R是自反的，或称R具有自反性，即 R在 A上是自反的 (x)(xC A)(C R)=1对称关系：对任意的x,yC A,如果C R,那么C R,则称关系R是对称 的，或称R具有对称性，即R在A上是对称的(x)( y)(xCA)A (yCA)A(C R户(C R)=1传递关系：对任意的x,y,zCA,如果CRHR,那么CR,则称关系R是传递的，或称R具有传递性，即R在A上是传递的 (x)( y)( z)(xC A)A (y C A)A (z A)A (C R)A ( R户( R)=1三、实验原理

4、：通过二元关系与关系矩阵的联系，可以引入 N维数组，以数组的运算来实现二元关系的判断。图示：性质关系矩阵特性自反性主对角线元素全为1反自反性主对角线元素全为0对称性对称矩阵反对称性非主对角线上的元素等于1且与之对称 的元素等于0传递性矩阵(M*M )中1所在的位置，M中与 之相对应位置鲜红都为1四、实验环境：Windows 7 Ultimate DEV C+五、实验语百：C语言六、程序源代码：#include#define N 4main()int i,j,k;int f,e,z;int MNN;printf( 判断 R 是否为自反关系、对称关系、是否可传递n);printf( 请输入一个4*

5、4 的矩阵。n);for(i=0;iN;i+)/* 输入一个 4*4 的矩阵*/for(j=0;jN;j+)scanf(%d,&Mij);for(i=0;iN;i+)for(j=0;jN;j+)printf(%4d,Mij);printf(n);for(i=0;iN;i+)if(Mii=1)序启动画面：ii.输入关系矩阵的行数和列数以及关系矩阵的各个元素 iii.得出结果，并打印在屏幕上八、实验总结如果当一个集合的元素的个数n很大时，求在该集合上的二元关系的可传递闭包 是非常复杂的。幸好Warshall算法给我们提供了一个求二元关系的可传递闭包的 高效方法。结合计算机程序技术，利用warsha

6、ll算法我们可以轻松的求出一个二 元关系的可传递闭包。本次实验便捷高效地达到了实验的目的。实验三、编程求一个二元关系的复合运算一、实验引语：关系作为集合，除了具有一般的运算功能外，还具有自身独 特的复合运算。二、数学原理设R是集合A到B的二元关系，S是集合B到C的二元关系，则Ro S =(x,z)已 A xC|FyB)(x,y) ERA (y,z) S称为R和 S的复合关系。三、实验原理：矩阵的运算： Windows 7 UltimateDEV C+五、实验语言：C语言六、实验程序源代码#include#include#define M 3#define N 3#define P 3main(

7、)int i,j,k,x;char p;int ANM,BMP,CNP;printf( 关系的复合运算n);printf( “请输入一个3*3 的矩阵 ”);printf(A:n);for(i=1;i=N;i+)for(j=1;j=M;j+)scanf(%4d,&Aij);printf(n);printf( “请输入一个3*3 的矩阵 ”);for(i=1;i=M;i+)(for(j=1;j=P;j+)scanf(%4d,&Bij);printf(n);printf(经过复合运算后得到C:n);for(i=1;i=N;i+)(for(j=1;j=P;j+)(x=0;for(k=1;k0)Cij

8、=1;elseCij=0;printf(%4d,Cij);printf(n);system(PAUSE);return 0;七、程序运行截图:i、程序启动截图：ii、程序输入截图iii、程序运行结果截图:入、实验总结：本实验利用计算机技术，快速便捷地实现了关系的运算，极大提高了效率。实验四：编程实现拓扑排序算法一、实验引言一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个 工程的完成，任务之间具有先后关系，任务的先后顺序可用有向图表示。二、数学原理：拓扑排序i）定义：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之 为拓扑排序。ii）实现方法：从有向图中选择一个没

9、有前驱的顶点并输出它。从网中删去该顶点并删去从该顶点发出的全部有向边。重复上述两步直到剩余的网中不存在没有前驱的顶点。三、实验原理首先对有向图，我们采取邻接表作为数据结构。且将表头指针改为头结点，其数据域存放该结点的入度，入度设为零的结点即没有前趋。在建立邻接表输入之前，表头向量的每个结点的初始状态为数据域VEX （入度）为零，指针域NXET为空，每输入一条弧 J, K 建立链表的一个结点，同时令 k 的入度加1，因此在输入结束时，表头的两个域分别表示顶点的入度和指向链表的第一个结点指针。在拓扑排序的过程之中，输入入度为零（即没有前趋）的顶点，同时将该顶点的直接后继的入度减1。、查邻接表中入度

10、为零的顶点，并进栈。、当栈为空时，进行拓扑排序。（ a） 、退栈，输出栈顶元素V。（b）、在邻接表中查找Vj的直接后继Vk,将Vk的入度减一，并令入度减至零的顶点进栈。、若栈空时输出的顶点数不是N 个则说明有向回路，否则拓扑排序结束。为建立存放入度为零的顶点的栈，不需要另分配存储单元，即可借入入度为零的数据域。一方面，入度为零的顶点序号即为表头结点的序号，另一方面，借用入度为零的数据域存放带链栈的指针域（下一个入度的顶点号）。： Windows 7 Ultimate DEV C+五、实验语言： C+六、程序源代码#include#include#include#include#includeu

11、sing namespace std;#define MAX 9999stackmystack;int indegreeMAX;struct nodeint adjvex;node* next;adjMAX;int Create(node adj,int n,int m)djvex=i;adji.next=NULL;for(i=0;i=m-1;i+)cout请输入第iuv;p=new node;p-adjvex=v;p-next=adju.next;adju.next=p;return 1;void print(int n)ext;while(p!=NULL)indegreep-adjvex+

12、;p=p-next;for(i=0;i=n-1;i+)if(indegreei=0)(i);int count=0;while()!=0)i=();();coutiadjvex;indegreek-;if(indegreek=0)(k);coutendl;if(countn)cout有回路endl;int main()int n;int m;cout拓扑排序算法endl;coutnm;Create(adj,n,m);cout”输入的令口接表为：endl;print(n);cout拓扑排序结果为：endl;topsort(adj,n);system(pause);return 0;七、程序运行截图以下图为例：i、程序启动截图ii、程序输入截图Ji =一一 $-7靖 JILI.X皿普 .二,用话iii、程序运行结果截图fa 52- 4 3 - 5 4 -h 112 z J 3 X Ls 3 1-1 m : Jr， :.-也i1l而卢内 二口_r.:一三.,.王译 A i