目录
第一章 实验概述 3
1.1 实验目的 3
1.2 实验内容 3
1.3 实验环境 3
第二章 实验原理和实现过程 4
2.1 实验原理 4
2.2 实验过程(算法描述) 4
2.2.1 程序整体思路 4
2.2.2具体算法流程 4
第三章 实验数据及结果分析 6
第四章 实验收获和心得体会 6
4.1 实验收获 6
4.2 心得体会 6
第五章 实验源程序清单 8
5.1 程序代码 8
第一章 实验概述
1.1 实验目的
理解关系的基本概念,关系的矩阵表示,关系的四种性质及对应闭包的构造方法。
通过实验,帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算,培养逻辑思维;通过实验提高学生编写实验报告、总结实验结果的能力,提高理论联系实际的能力;使学生具备程序设计的思想,能够独立完成简单的算法设计和分析。通过实验报告的编写,掌握目录、页码等文档编辑技巧。
1.2 实验内容
键盘输入一个关系的关系矩阵,先判定关系性质,再计算其自反闭包、对称闭包和传递闭包。
基本要求:程序需具有基本的容错控制,在输入错误时有处理手段;程序界面友好,需要输入的地方有输入说明,说明输入的内容和格式要求等;实验原理和实现过程应该详细分析问题,给出解决思路,描述算法思想,不能用源程序代替算法;测试数据应全面,包括非法输入的处理结果等都应包含在内;程序代码关键部分要加注释。实验报告文档要求有目录格式,封面不编页码,目录和正文单独编页码。
1.3 实验环境
C或C++语言编程环境实现。
第二章 实验原理和实现过程
2.1 实验原理
关系的基本概念,关系的矩阵表示,关系的四种性质及对应闭包的构造方法。
2.2 实验过程(算法描述)
2.2.1 程序整体思路
自反性:
从给定的关系矩阵来断判关系R是否为自反是很容易的。若M(R的关系矩阵)的主对角线元素均为1,则R是自反关系;若M(R的关系矩阵)的主对角线元素均为0,则R是反自反关系;若M(R的关系矩阵)的主对角线元素既有1又有0,则R既不是自反关系也不是反自反关系。本算法可以作为判等价关系算法的子程序给出。
对称性:
从给定的关系矩阵来判断关系R是否为对称是很容易的。若M(R的关系矩阵)为对称矩阵,则R是对称关系;若M为反对称矩阵,则R是反对称关系。因为R为对称的是等价关系的必要条件,所以,本算法可以作为判等价关系算法的子程序给出。
传递性:
从给定的关系矩阵来断判关系R是否为传递是很容易的。若M(R的关系矩阵)为传递矩阵,则R是传递关系;若M为非传递矩阵,则R是非传递关系;本算法可以作为判等价关系算法的子程序给出。
2.2.2具体算法流程
自反性算法实现
- 输入关系矩阵M(M为n阶方阵)。
- 判断自反性,对于i=1,2,….,n;若存在mii=0,则R不是自反的;若存在mii=1,则R是自反的;否则R既不是自反关系也不是反自反关系。
- 输出判断结果。
对称性算法实现: - 输入关系矩阵M(M为n阶方阵);
- 判断对称性,对于i=2,3,….,n;j=1,2,……,i-1,若存在mij=mji,则R是对称的;
- 判断反对称性;
- 判断既是对称的又是反对称的;
- 判断既不是对称的又不是反对称的;
- 输出判断结果。
传递性算法实现 - 输入关系矩阵M(M为n阶方阵)。
- 判断传递性,对于i=1,2,….,n,j=1,2,….,n,k=1,2,….,n;若任意mij=1, mjk=1,且mik=1,则R是传递的;若任意mij=1, mjk=1,且mik=0,则R是非传递的;否则R既不是自反关系也不是反自反关系。
- 输出判断结果。
第三章 实验数据及结果分析
第四章 实验收获和心得体会
1、更好地理解掌握计算机科学技术常用的离散数学中的关系的概念、性质和运算,培养逻辑思维;
2、通过实验提高编写实验报告、总结实验结果的能力,提高理论联系实际的能力;
3、具备程序设计的思想,能够独立完成简单的算法设计和分析;
4、通过实验提高了报告的编写,掌握目录、页码等文档编辑技巧;
5、学会用计算机编程语言解决离散数学问题;
6、具有基本的程序调试能力;
7、学会分析问题,给出解决思路,描述算法思想;
第五章 实验源程序清单
/* *@Author: STZG *@Language: C++ */
#include <bits/stdc++.h>
using namespace std;
const int N=100+10;
int n;
int a[N][N];//原关系矩阵
int b[N][N];//自反闭包
int c[N][N];//对称闭包
int d[N][N];//传递闭包
int main()
{
cout<<"请输入关系矩阵大小(0<n<=100):"<<endl;
scanf("%d",&n);
while(n<=0||n>100){
cout<<"关系矩阵大小不符合要求,请重新输入(0<n<=100):"<<endl;
scanf("%d",&n);
}
cout<<"请输入关系矩阵(0/1):"<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
d[i][j]=c[i][j]=b[i][j]=a[i][j];
}
}
bool flag[5]={1,1,1,1,1};
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j){
b[i][j]=1;//求自反性
if(!a[i][j]){
flag[0]=0;//判断自反性
}else{
flag[1]=0;//判断反自反性
}
}
if(a[i][j]){
c[j][i]=1;//求对称
if(!a[j][i])flag[2]=0;
if(i!=j&&a[j][i])flag[3]=0;
}
for(int k=1;k<=n;k++){
if(a[i][j]&&a[j][k]&&!a[i][k])flag[4]=0;//判断传递性
if(d[i][j]&&d[j][k]&&!d[i][k])d[i][k]=1;//求传递性
}
}
}
cout<<(flag[0]||flag[1]?flag[0]?"自反性":"反自反性":"既不是自反性也不是反自反性")<<"、"
<<(flag[2]||flag[3]?flag[2]?"对称性":"反对称性":"既不是对称性也不是反对称性")<<"、"
<<(flag[4]?"传递性":"非对称性")<<endl;
cout<<"自反闭包:"<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d%c",b[i][j]," \n"[j==n]);
}
}
cout<<"对称闭包:"<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d%c",c[i][j]," \n"[j==n]);
}
}
cout<<"传递闭包:"<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d%c",d[i][j]," \n"[j==n]);
}
}
//cout << "Hello world!" << endl;
return 0;
}