生日快乐祝福语朋友离散数学实验报告（实验2关系的闭包运算）
离散数学实验报告（实验2 关系的闭包运算）
远走它乡⼀、实验⽬的
利⽤矩阵求解有限集上给定关系的⾃反、对称和传递闭包，熟悉关系的闭包运算。
⼆、实验内容
随机⽣成关系矩阵，输出⾃反、对称和传递闭包。
三、实验环境
采⽤C/C++语⾔为编程语⾔实现。
四、实验过程
1. 算法分析
在三种闭包中⾃反和对称闭包的求解很容易，对矩阵表⽰的关系，其⾃反闭包只要将矩阵的主对⾓线全部置为1就可；对称闭包则加上关系的转置矩阵（逻辑加法）；传递闭包则有两种算法（⼆选⼀即可）：
算法1：直接根据 计算，过程略。
算法2：Warshall算法(1962)
设R的关系矩阵为M
(1)令矩阵A=M
(2)置i=1
(3)对所有的j，若A[j，i]=1，则
对于 k=1，2，…，n，令A[j，k]=A[j，k]+A[i，k]
注：此处为逻辑加，可以使⽤运算符||
(4) i=i+l．
//使⽤的是Visual Studio 2019，有"scanf_s"与"scanf"的区别
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 100
int matrix[N][N];//存储随机⽣成的关系矩阵
int n;//⽤于存储关系矩阵的阶数
void RClosure();//计算⾃反闭包
void SClosure();//计算对称闭包
void TClosure();//计算传递闭包
void Input();
void Output();
int main()
{
Input();
老年人旅游适合去哪里
RClosure();
SClosure();
TClosure();
return0;
}
void Output(int a[N][N])
{
for(int i =0; i < n; i++)
{
for(int j =0; j < n; j++)
{
printf("%d ", a[i][j]);
}
printf("\n");
}
}
娇美>上不下要
void Input()
{
printf("请输⼊该关系矩阵的阶数(⼩于等于100)：\n");
scanf_s("%d",&n);
if(n <0|| n>100)
if(n <0|| n>100)
{
printf("⾮法输⼊！\n");
exit(0);
}
for(int i =0; i < n; i++)
{
srand((unsigned)time(NULL));// 初始化随机数
for(int j =0; j < n; j++)
{
matrix[i][j]={rand()%2};
}
}
}
void RClosure()
鸡蛋吐司
{
int a[N][N];
走进校园
for(int i =0; i < n; i++)
{
for(int j =0; j < n; j++)
{
a[i][j]= matrix[i][j];
}
}
for(int i =0; i < n; i++)
{
a[i][i]=1;//让所有主对⾓线的元素全是1
}
printf("⾃反闭包是：\n");
Output(a);
}
void SClosure()慢性胃炎吃什么食物好
{
int a[N][N];
for(int i =0; i < n; i++)
{
for(int j =0; j < n; j++)
{
a[i][j]= matrix[i][j];
}
}
for(int i =0; i < n; i++)
{
for(int j =0; j < n; j++)
{
if(a[i][j]==1)
//如果第i⾏第j列元素是1，那让第j⾏第i列的元素也为1 a[j][i]=1;
}
}
printf("对称闭包是：\n");
Output(a);
}
void TClosure()
{
int a[N][N];
for(int i =0; i < n; i++)
{
for(int j =0; j < n; j++)
{
a[i][j]= matrix[i][j];
}
}
}
int i, j, k;
for(i =0; i < n; i++)
{
for(j =0; j < n; j++)
{
if(a[j][i]>=1)
{
for(k =0; k < n; k++)
{
a[j][k]= a[j][k]|| a[i][k];//逻辑加“||“
}
}
}
}
for(i =0; i < n; i++)
{
for(j =0; j < n; j++)
{
if(a[i][j]>1)
a[i][j]=1;
}
}
printf("warshall算法实现传递闭包：\n"); Output(a);
}
