<center> 离散数学实验报告 </center> <center> 计算机科学与技术系 </center>

目录
第一章 实验概述 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具体算法流程
自反性算法实现

  1. 输入关系矩阵M(M为n阶方阵)。
  2. 判断自反性,对于i=1,2,….,n;若存在mii=0,则R不是自反的;若存在mii=1,则R是自反的;否则R既不是自反关系也不是反自反关系。
  3. 输出判断结果。
    对称性算法实现:
  4. 输入关系矩阵M(M为n阶方阵);
  5. 判断对称性,对于i=2,3,….,n;j=1,2,……,i-1,若存在mij=mji,则R是对称的;
  6. 判断反对称性;
  7. 判断既是对称的又是反对称的;
  8. 判断既不是对称的又不是反对称的;
  9. 输出判断结果。
    传递性算法实现
  10. 输入关系矩阵M(M为n阶方阵)。
  11. 判断传递性,对于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既不是自反关系也不是反自反关系。
  12. 输出判断结果。

第三章 实验数据及结果分析

第四章 实验收获和心得体会
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;
    }