离散数学测试题

离散数学半期考核。

专业软件工程。

指导老师蒲在毅。

学生姓名曾舜尧。

学号 201113340348（11级）

提交日期 2012年5月1日

利用warshall算法求二元关系的可传递闭包。

学生：曾舜尧指导老师：蒲在毅。

摘要。本实验主要是研究利用warshall算法求二元关系的可传递闭，实验主要内容是。

研究当集合的阶数n较大时，求二元关系的可传递闭包的工作量时相当庞大的。

幸运的时1962年提出了一个计算r+的有效方法，可在计算机上编程。

实现。采用c语言函数写出这个算法。程序中用temp[i][j]表示关系矩阵mr的。

第i行第j列元素，用||表示逻辑或计算。计算r+的函数名为warshall,它的两。

个形式参数m和n分别表示关系矩阵m和矩阵的行数。函数的实现实际上是一个。

三重循环结构。

关键词。二元关系关系矩阵可传递闭包 warshall算法三重循环。

引言。离散数学》是现代数学的一个重要分支，也是计算机科学技术，电子信息技术，生物技术等。

的核心基础课程。二元关系是离散数学中重要内容。世界上的事物都在一定范围内以某种方。

式互相联系，例如天体之间可以用的是同一星系来划分，人们之间可以用是否有共同的祖先来。

定血缘。类似的数学或者计算机科学中的研究对象也以各种不同形式互相联系着，例如整数之。

间以大小，整除或同余关系互相联系着，命题公式之间以是否具有相同的主合取范式相联系，程序中两个变量可以是否占有同一内存地址相联系。总之，事物之间总可以根据需要确定相。

应的关系。从数学的角度来看，这类联系就是某个集合中元素之间存在的关系。一个二元关系。

可能具有某种性质，也可能不具有这种性质。关系闭包就是使一个二元关系变成具有指定性。

质的关系，并且还要满足最小条件。

warshall算法的基本思想。

对每个结点（从第一列开始），找出所有具有到此结点的有向边的结点（即该列中元素为1的所在行的结点），再将这些结点所在行同该结点所在行进行逻辑加后作为这些结点所在的新行（添加新的有向边）（反映了如果这些结点没有到其它结点的有向边，但有到该结点的有向边，再通过该结点间接到达其它结点，根据传递闭包的定义，这些结点就必然有一条有向边到达其它结点。）

设r是集合上的二元关系，mr是r的关系矩阵。

(1)置新矩阵a:=mr

(2)置(列) j:=1

(3) 对所有的i(1≤i≤n)

如a(i,j)=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)如j≤n转(3),否则停止。

主要实验流程图。

实验源**。

#include<>

void main()

printf("利用warshall算法求二元关系的可传递闭包");

void warshall(int,int);

int m[20][20],n;

printf("请输入矩阵的行数n: "

scanf("%d",&n);

warshall(m[20][20],n);

void warshall(int m[20][20],int n)

int i , j, k;

int m[20][20];

for(i=0;i

printf("可传递闭包关系矩阵是：");

for(i=0;i

printf("");

**测试。c语言中测试。

网络**检查。

分析原因。1.由于使用了数组来储存数据，但是我们无法给数组定义确切的大小，因此要重新定义函数，将原来的定义的函数中的m[换成一个变量，然后在定义一个固定大小的数组来存放数据。

改进方法后重新写的**如下。

#include<>

void warshall(int k,int n)

int i , j, t;

int temp[20][20];

for(int a=0;a

for(i=0;i

printf("可传递闭包关系矩阵是：");

for(i=0;iprintf("\t\t");

for(j=0;j

printf("%d ",temp[i][j]);

printf("");

void main()

printf("利用warshall算法求二元关系的可传递闭包");

void warshall(int,int);

int k , n;

printf("请输入矩阵的行数i: "

scanf("%d",&k);

printf("请输入矩阵的列数j: "

scanf("%d",&n);

warshall(k,n);

试验结果截图展示。

1、启动程序。

2、输入矩阵并得到结果。

实验总结。程序编写时要注意各个符号定义，要学会自己独立解决出现的各个问题。

warshall算法给我们提供了一个求二元关系传递闭包的高效方法。综合现代计算机技术，利用warshall算法我们可轻松的求出一个二元关系的可传递闭包。

指导老师评阅意见。

指导老师（签字。

年月日。

离散数学测试题

《离散数学》试题

离散数学试题

离散数学试题

其他用户还读了