离散数学实验报告--四个实验!!!

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

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

3、5;B的一个合于R=(x,y)A×B|xRy的子集合设R是集合A上的二元关系：自反关系：对任意的xA,都满足<x,x>R，那么称R是自反的，或称R具有自反性，即R在A上是自反的Û("x)(xA)(<x,x>R)=1对称关系：对任意的x,yA，如果<x,y>R，那么<y,x>R，那么称关系R是对称的，或称R具有对称性，即R在A上是对称的 Û ("x)("y)(xA) (yA)(<x,y>R)(<y,x>R)=1传递关系：对任意的x,y,zA，如果<x,y>

4、;R且<y,z>R，那么<x,z>R，那么称关系R是传递的，或称R具有传递性，即R在A上是传递的Û ("x)("y)("z)(xA)(yA)(zA)(<x,y>R)(<y,z>R)(<x,z>R)=1 三、实验原理：通过二元关系与关系矩阵的联系，可以引入N维数组，以数组的运算来实现二元关系的判断。图示：性质关系矩阵特性自反性主对角线元素全为1反自反性主对角线元素全为0对称性对称矩阵反对称性非主对角线上的元素等于1且与之对称的元素等于0传递性矩阵M*M中1所在的位置，M中与之相对应位置鲜红都为1四

5、、实验环境：Windows 7 Ultimate DEV C+五、实验语言：C 语言六、程序源代码：#include"stdio.h"#define N 4main() int i,j,k; int f,e,z; int MNN; printf("判断R是否为自反关系、对称关系、是否可传递？n"); printf("请输入一个4*4的矩阵。n"); for(i=0;i<N;i+) /*输入一个4*4的矩阵*/ for(j=0;j<N;j+) scanf("%d",&Mij); for(i=0;i

6、<N;i+) for(j=0;j<N;j+) printf("%4d",Mij); printf("n"); for(i=0;i<N;i+) if(Mii=1)/判断自反性 if(i=N-1 e=0; else ; else if(Mii=0)/判断反自反性 if(i=N-1) e=1; else ; else e=2; break; for(i=0;i<N;i+) for(j=0;j<N;j+) if(Mij!=Mji)/判断对称性 f=1; break; for(i=0;i<N;i+) for(j=0;j<N

7、;j+) if(Mij=1)/判断反对称性 if(Mji=0) if(i=(N-1)&&j=N-1) f=0; else break; if(f!=0&&f!=1) f=2; for(i=0;i<N;i+)/判断可传递性 for(j=0;j<N;j+) if(Mij=1) continue; else for(k=0;k<N;k+) if(Mik*Mki=0) continue; else z=0; if(e=0) printf("关系R是自反关系n"); else if(e=1) printf("关系R是反自反关

8、系n"); else if(e=2) printf("关系R是反自反关系n"); if(f=0) printf("关系R是反对称关系n"); else if(f=1) printf("关系R不是对称关系n"); else if(f=2) printf("关系R是对称关系n"); if(z=0) printf("关系R是不可传递关系n"); else printf("关系R是可传递关系n"); system("PAUSE");七、程序运行截图：i、

9、程序启动截图： ii、程序输入截图：iii、程序运行结果截图:八、实验总结：实验简洁高效地判断二元关系的性质。实验二、编程求一个二元关系的自反闭包、对称闭包、传递闭包一、前言引语一个二元关系可能具有某种性质，也可能不具有这种性质。现在讨论怎样使一个二元关系变成具有指定性质的新关系，并且还要满足最小性条件。二、数学原理 自反闭包、对称闭包、传递闭包设R是定义在A上的二元关系，假设存在A上的关系R满足：1) R是自反的(或对称的、或可传递的)，2) RÍ R， 3) 对A上任何其它满足 1和 2的关系R，都有： RÍ R。 那么称R为R的自反闭包(或对称闭包、或传递闭包)，分别

10、记为r(R)、(s(R)和t(R)。三、实验原理 Warshall算法的根本思想对每个结点从第一列开始，找出所有具有到此结点的有向边的结点即该列中元素为1的所在行的结点，再将这些结点所在行同该结点所在行进行逻辑加后作为这些结点所在的新行添加新的有向边反映了如果这些结点没有到其它结点的有向边，但有到该结点的有向边，再通过该结点间接到达其它结点，根据传递闭包的定义，这些结点就必然有一条有向边到达其它结点。§ 设R是集合上的二元关系,Mr是R的关系矩阵§ (1)置新矩阵A:=Mr § (2)置(列) j:=1 § (3) 对所有的i(1in) 如A(i,j)=

11、1,那么对k=1,2,n A(i,k):=A(i,k) Ú A(j,k)§ (即将A的第i行与A的第j行进行逻辑加后送回A的第i行)§ (4)j:=j+1§ (5)如jn转(3),否那么停止。四、实验环境：Windows 7 Ultimate DEV C+五、实验编程语言： C语言六、实验程序源代码/source file: War.cpp#include<stdio.h>void War(int m,int n) int i,j,k;设置临时变量int a = 0, b = 0;设置临时变量int arr1010;for(a = 0; a

12、< m; +a)printf("请输入矩阵第%d行元素:",a);for(b = 0; b < n; +b)scanf("%d",&arrab);printf("n");for(i = 0; i < m; i+)for( j= 0; j < m; j+)if(arrji = 1)for(k = 0;k < n; k+)arrjk=arrik | arrjk;printf("所得的可传递闭包关系矩阵是：n");for(i = 0;i < m; +i)for(j = 0;j

13、< n; +j)printf("%d ",arrij);printf("n");/file: test.cpp#include<stdio.h>void main() printf("利用Warshall算法求二元关系的可传递闭包n");void War(int , int);int m, n;printf("请输入矩阵的行数(必须小于10：");scanf("%d", &m);printf("请输入矩阵的列数(必须小于10：");scanf(&qu

14、ot;%d", &n);War(m, n);system ( “PAUSE);return 0;七、实验截图i.程序启动画面：ii.输入关系矩阵的行数和列数以及关系矩阵的各个元素。 iii.得出结果，并打印在屏幕上。八、实验总结如果当一个集合的元素的个数n很大时，求在该集合上的二元关系的可传递闭包是非常复杂的。幸好Warshall算法给我们提供了一个求二元关系的可传递闭包的高效方法。结合计算机程序技术，利用warshall算法我们可以轻松的求出一个二元关系的可传递闭包。本次实验便捷高效地到达了实验的目的。实验三、编程求一个二元关系的复合运算一、实验引语：关系作为集合，除了具有

15、一般的运算功能外，还具有自身独特的复合运算。二、数学原理设R是集合A到B的二元关系，S是集合B到C的二元关系，那么R。S = x，z A C|(y B)(x，y) R y，zS称为R和S的复合关系。三、实验原理：矩阵的运算四、实验环境：Windows 7 Ultimate DEV C+五、实验语言：C语言六、实验程序源代码#include"stdio.h"#include"string.h"#define M 3#define N 3#define P 3main() int i,j,k,x; char p; int ANM,BMP,CNP; print

16、f("关系的复合运算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的矩阵); printf("B:n"); for(i=1;i<=M;i+) for(j=1;j<=P;j+) scanf("%4d",&Bij); printf("

17、;n"); printf("经过复合运算后得到C:n"); for(i=1;i<=N;i+) for(j=1;j<=P;j+) x=0; for(k=1;k<=M;k+) x=x+Aik*Bkj; if(x>0) Cij=1; else Cij=0; printf("%4d",Cij); printf("n"); system("PAUSE"); return 0;七、程序运行截图：i、程序启动截图：ii、程序输入截图:iii、程序运行结果截图：八、实验总结：本实验利用计算机技术，

18、快速便捷地实现了关系的运算，极大提高了效率。实验四：编程实现拓扑排序算法一、实验引言一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成,，任务之间具有先后关系，任务的先后顺序可用有向图表示。二、数学原理：拓扑排序 i定义：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。 ii实现方法： 从有向图中选择一个没有前驱的顶点并输出它。 从网中删去该顶点并删去从该顶点发出的全部有向边。 重复上述两步直到剩余的网中不存在没有前驱的顶点。三、实验原理首先对有向图，我们采取邻接表作为数据结构。且将表头指针改为头结点，其数据域存放该结点的入度，入度设为零的结

19、点即没有前趋。在建立邻接表输入之前，表头向量的每个结点的初始状态为数据域VEX入度为零，指针域NXET为空，每输入一条弧< J, K > 建立链表的一个结点，同时令k 的入度加1，因此在输入结束时，表头的两个域分别表示顶点的入度和指向链表的第一个结点指针。在拓扑排序的过程之中，输入入度为零即没有前趋的顶点，同时将该顶点的直接后继的入度减1。1、查邻接表中入度为零的顶点，并进栈。2、当栈为空时，进行拓扑排序。a、退栈，输出栈顶元素V。b、在邻接表中查找Vj的直接后继Vk，将Vk的入度减一，并令入度减至零的顶点进栈。3、假设栈空时输出的顶点数不是N个那么说明有向回路，否那么拓扑排序结束

20、。为建立存放入度为零的顶点的栈，不需要另分配存储单元，即可借入入度为零的数据域。一方面，入度为零的顶点序号即为表头结点的序号，另一方面，借用入度为零的数据域存放带链栈的指针域下一个入度的顶点号。四、实验环境：Windows 7 Ultimate DEV C+五、实验语言：C+六、程序源代码#include<iostream>#include<cmath>#include<cstdio>#include<algorithm>#include<stack>using namespace std;#define MAX 9999stack&

21、lt;int>mystack;int indegreeMAX;struct node int adjvex; node* next;adjMAX;int Create(node adj,int n,int m)/邻接表建表函数，n代表定点数，m代表边数 int i; node *p; for(i=0;i<=n-1;i+) adji.adjvex=i; adji.next=NULL; for(i=0;i<=m-1;i+) cout<<"请输入第"<<i<<"条边:" int u,v; cin>&g

22、t;u>>v; p=new node; p->adjvex=v; p->next=adju.next; adju.next=p; return 1;void print(int n)/邻接表打印函数 int i; node *p; for(i=0;i<=n-1;i+) p=&adji; while(p!=NULL) cout<<p->adjvex<<' ' p=p->next; cout<<endl; void topsort(node adj,int n) int i; node *p; memset(indegree,0,sizeof(indegree); for(i=0;i<=n-1;i+) p=adji.next; while(p!=NULL) indegreep->adjvex+; p=p->next; for(i=0;i<=n-1;i+) if(indegreei=0) mystack.push(i); int count=