离散数学实验二c语言(输出关系矩阵,输出矩阵性质,输出自反闭包,对称闭包,传递闭包,判断矩阵是否为等价关系,相容关系,偏序关系)

离散数学实验二

一、算法描述,算法思想

(一)相关数据结构
typedef struct Set *S; //存放集合
struct Set
{
    int size; //集合的元素个数
    char *A;   //存放该集合的元素
};

Set存放有限集合A,该集合的元素个数为size,size可以用来判断该集合是否为空集,然后集合中的元素就放在A数组里。

typedef struct Confirm *C; //存放关系的序偶<x, y>
struct Confirm
{
    int x, y;
};

Confirm存放一个序偶<x, y>。

typedef struct Relation *R; //存放关系矩阵
struct Relation
{
    int n, size;   // n行 n列矩阵,序偶个数为size
    int r[10][10]; //关系矩阵
    C c;           //存放该关系的序偶
};

Relation存放集合A的关系,r为一个n行,n列的关系矩阵,size为其中的序偶数,c即存放该关系的所有序偶。

int flagz = 1, flagfz = 1, flagd = 1, flagfd = 1, flagc = 1; // flagz判断是否为自反,flagfz判断是否为反自反,
// flagd判断是否为对称,flagfd判断是否为反对称,flagc判断是否为传递

设置全局变量,方便判断矩阵关系。

(二)相关算法实现
1、输出关系矩阵R
void PrintRelation(R re) //打印关系矩阵
{
    printf("关系矩阵如下:\n");
    for (int i = 0; i < re->n; i++)
    {
        for (int j = 0; j < re->n; j++)
            printf("%d ", re->r[i][j]);
        printf("\n");
    }
    printf("\n");
}

用户输入的为一个关系矩阵,只要将其存储下,然后直接输出即可,注意换行。

2、输出R具有的性质
void PrintCharacter(S s, R re) //判断该矩阵的性质
if (s->size == 0) //空集,关系具有所有性质
    {
        printf("该关系具有以下性质:\n");
        printf("自反性\n");
        printf("反自反性\n");
        printf("对称性\n");
        printf("反对称性\n");
        printf("传递性\n");
        return;
    }

(1)首先是判断该集合是否为空,如果集合为空集,则具有所有的性质。

for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j && !re->r[i][j]) //不可能为自反关系
                flagz = 0;
            if (i == j && re->r[i][j]) //不可能为反自反关系
                flagfz = 0;
            if (re->r[i][j] && !re->r[j][i] && i != j) //不可能为对称关系
                flagd = 0;
            if (re->r[i][j] && re->r[j][i] && i != j) //不可能为反对称关系
                flagfd = 0;
        }
    }

(2)确定该集合不为空后,接下来先根据矩阵来判断自反性,反自反性,对称性,反对称性。

如果出现横纵坐标相同的点,但是其不为1,说明该集合存在a属于集合s,但不具有<a, a>序偶,则该矩阵不可能具有自反关系,将flagz = 0;

如果出现横纵坐标相同的点,但是其为1,说明该集合存在a属于该集合,且有<a, a>序偶,则该矩阵不可能具有反自反关系,将flagfz = 0;

如果出现横纵坐标不相同,且相反的两点,但是其为1,说明该集合存在a,b属于该集合,且有<a, b>,<b,a>序偶,则该矩阵不可能具有反对称关系,将flagfd = 0;

如果出现横纵坐标不相同,且相反的两点,但是其只有一个为1,说明该集合存在a,b属于该集合,且有<a, b>,没有<b,a>序偶,则该矩阵不可能具有对称关系,将flagd = 0;

    for (int i = 1; i <= re->size; i++) //判断是否具有传递性
    {
        if (!flagc)
        break;
        int x = re->c[i].x, y = re->c[i].y; //若存在<x, y>
        if (x == y)
            continue;
        for (int j = 0; j < n; j++) //找<y, j>
        {
            if (re->r[y][j] && !re->r[x][j]) //是否存在<x, j>
            {
                flagc = 0;
                break;
            }
        }
    }

(3)接下来是根据矩阵中为1的点,即该集合所具有的序偶来判断是否具有传递关系。

若存在<x, y>,我们去找<y, j>,看是否存在<x, j>,如果不存在则不具有传递关系,flagc = 0。

(4)最后将所有关系输出即可。

3、输出R的自反闭包,对称闭包,传递闭包
void PrintBibao(R re) //计算自反闭包,对称闭包,传递闭包矩阵
    //自反闭包
    int n = re->n;
    R tmp = CopyRelation(re);
    for (int i = 0; i < n; i++)
        tmp->r[i][i] = 1;
    printf("自反闭包矩阵:\n");
    PrintRelation(tmp);
    DestoryRelation(tmp);

(1)计算自反闭包,首先将原矩阵复制到tmp中,将所有横纵坐标相同的点都该为1,即为自反闭包。

    //对称闭包
    tmp = CopyRelation(re);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i != j && tmp->r[i][j])
            {
                tmp->r[j][i] = 1;
            }
        }
    }
    printf("对称闭包矩阵:\n");
    PrintRelation(tmp);
    DestoryRelation(tmp);

(2)计算对称闭包,首先将原矩阵复制到tmp中,将横纵坐标不同的的,原矩阵中存在的为1的点,将其的对称点也改为1,即为对称闭包。

    //传递闭包
    tmp = CopyRelation(re);
    R ans = InitRelationTmp(n);
    AddRelation(ans, re);

    for (int i = 0; i < n-1; i++)
    {
        tmp = Multiply(tmp, re); //最多乘n次
        AddRelation(ans, tmp);
    }
    printf("传递闭包矩阵:\n");
    PrintRelation(ans);
    DestoryRelation(tmp);
    free(ans);

(3)计算传递闭包,首先将原矩阵复制到tmp中,将tmp与原矩阵乘矩阵的行(列)数次,将每次计算的大于1的数改为1,每次将矩阵相加,返回即可。

4、判断R是否为等价关系,相容关系,偏序关系
void PanRelation(R re) //判断矩阵的关系
{
    printf("具有的关系为:\n");
    if (flagz == 1 && flagd == 1 && flagc == 1) //如果为自反,对称,传递则为等价关系
        printf("等价关系\n");
    if (flagz == 1 && flagd == 1) //若为自反,对称则为相容关系
        printf("相容关系\n");
    if (flagz == 1 && flagfd == 1 && flagc == 1) //若为自反,反对称,传递为偏序关系
        printf("偏序关系\n");
}

(1)等价关系:若R具有自反性,对称性,传递性。

(2)相容关系:若R具有自反性,对称性。

(3)偏序关系:若R具有自反性,反对称性,传递性。

(三)流程图

main()函数

void PrintRelation(R re) 打印关系矩阵

void PrintCharacter(S s, R re) 判断该关系矩阵的性质

void PrintBibao(R re) 计算自反闭包,对称闭包,传递闭包矩阵

void PanRelation(R re) 判断矩阵的关系

(四)程序运行截图与样例说明

输入:元素个数、集合的每个元素(用单个字符表示)、该集合的关系矩阵。

输出:关系矩阵、关系矩阵性质、自反闭包、对称闭包、传递闭包矩阵、关系矩阵的关系。

分析:该关系矩阵的序偶为<1,2>,<2,1>,<2,3>,<3,4>。

可以看出该关系矩阵不具有自反性,对称性,反对称性,传递性。

具有反自反性。

且计算的自反闭包,对称闭包,传递闭包与答案相同。

判断的关系也正确。

(五)代码

#include <stdio.h>
#include <stdlib.h>
typedef struct Confirm *C; //存放关系的序偶<x, y>
struct Confirm
{
    int x, y;
};
typedef struct Relation *R; //存放关系矩阵
struct Relation
{
    int n, size;   // n行 n列矩阵,序偶个数为size
    int r[10][10]; //关系矩阵
    C c;           //存放该关系的序偶
};
typedef struct Set *S; //存放集合
struct Set
{
    int size; //集合的元素个数
    char *A;   //存放该集合的元素
};
int flagz = 1, flagfz = 1, flagd = 1, flagfd = 1, flagc = 1; // flagz判断是否为自反,flagfz判断是否为反自反,
// flagd判断是否为对称,flagfd判断是否为反对称,flagc判断是否为传递

S InitSet(int size) //创建集合
{
    S s = (S)malloc(sizeof(struct Set));
    s->A = (char *)malloc(sizeof(char) * size);
    s->size = size;

    printf("注意:集合的每个元素用单个字符来表示\n");
    for (int i = 0; i < size; i++)
        scanf("%d", &s->A[i]);
    return s;
}
R InitRelation(int n) //创建关系矩阵
{
    int now = 0;
    R re = (R)malloc(sizeof(struct Relation));
    re->n = n;
    re->c = (C)malloc(sizeof(struct Confirm) * n);
    
    printf("请输入该集合的关系矩阵(n*n):\n");
    for (int i = 0; i < re->n; i++)
    {
        for (int j = 0; j < re->n; j++)
        {
            scanf("%d", &re->r[i][j]);
            if (re->r[i][j])
            {
                re->c[++now].x = i;
                re->c[now].y = j;
            }
        }
    }
    re->size = now;
    return re;
}
R InitRelationTmp(int n)
{
    R tmp = (R)malloc(sizeof(struct Relation));
    tmp->n = n;
    for (int i=0; i<tmp->n; i++)
    {
        for (int j=0; j<tmp->n; j++)
        tmp->r[i][j] = 0;
    }
    return tmp;
}

void DestorySet(S s) //释放集合内存
{
    free(s->A);
    free(s);
}
void DestoryRelation(R re) //释放关系矩阵内存
{
    free(re->c);
    free(re);
}

void PrintRelation(R re) //打印关系矩阵
{
    printf("关系矩阵如下:\n");
    for (int i = 0; i < re->n; i++)
    {
        for (int j = 0; j < re->n; j++)
            printf("%d ", re->r[i][j]);
        printf("\n");
    }
    printf("\n");
}
R Multiply(R re, R re2) //计算两矩阵相乘,且将相乘后的大于1的数改为1
{
    int n = re->n, tmp = 0, i, j;
    R ans = InitRelationTmp(n);
    for (i = 0; i < n; i++) //每一行
    {
        for (j = 0; j < n; j++) //该行的列
        {
            tmp = 0;
            for (int k = 0; k < n; k++)
            {
                tmp += re->r[i][k] * re2->r[k][j];
            }
            if (tmp >= 1)
                {
                    ans->r[i][j] = 1;
                }
        }
    }
    return ans; //返回得出的矩阵
}
void AddRelation(R re1, R re2)
{
    int n = re1->n;
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            re1->r[i][j] += re2->r[i][j];
            if (re1->r[i][j]>1)
            re1->r[i][j] = 1;
        }
    }
}

void PrintCharacter(S s, R re) //判断该矩阵的性质
{
    int n = re->n;
    if (s->size == 0) //空集,关系具有所有性质
    {
        printf("该关系具有以下性质:\n");
        printf("自反性\n");
        printf("反自反性\n");
        printf("对称性\n");
        printf("反对称性\n");
        printf("传递性\n");
        return;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j && !re->r[i][j]) //不可能为自反关系
                flagz = 0;
            if (i == j && re->r[i][j]) //不可能为反自反关系
                flagfz = 0;
            if (re->r[i][j] && !re->r[j][i] && i != j) //不可能为对称关系
                flagd = 0;
            if (re->r[i][j] && re->r[j][i] && i != j) //不可能为反对称关系
                flagfd = 0;
        }
    }
    for (int i = 1; i <= re->size; i++) //判断是否具有传递性
    {
        if (!flagc)
        break;
        int x = re->c[i].x, y = re->c[i].y; //若存在<x, y>
        if (x == y)
            continue;
        for (int j = 0; j < n; j++) //找<y, j>
        {
            if (re->r[y][j] && !re->r[x][j]) //是否存在<x, j>
            {
                flagc = 0;
                break;
            }
        }
    }
    //输出性质
    printf("该关系具有以下性质:\n");
    if (flagz == 1)
        printf("自反性\n");

    if (flagfz == 1)
        printf("反自反性\n");

    if (flagd == 1)
        printf("对称性\n");

    if (flagfd == 1)
        printf("反对称性\n");

    if (flagc == 1)
        printf("传递性\n");

    if (!flagz&&!flagfz&&!flagd&&!flagfd&&!flagc)
    printf("该关系矩阵不具有自反、反自反、对称、反对称、传递性\n");
}
R CopyRelation(R re) //复制关系矩阵,方便计算
{
    R tmp = (R)malloc(sizeof(struct Relation));
    tmp->n = re->n;
    tmp->size = re->size;
    tmp->c = (C)malloc(sizeof(struct Confirm) * tmp->size);
    for (int i = 0; i < tmp->n; i++)
    {
        for (int j = 0; j < tmp->n; j++)
            tmp->r[i][j] = re->r[i][j];
    }
    for (int i = 1; i <= tmp->size; i++)
    {
        tmp->c[i].x = re->c[i].x;
        tmp->c[i].y = re->c[i].y;
    }
    return tmp; //返回该复制的矩阵
}
void PrintBibao(R re) //计算自反闭包,对称闭包,传递闭包矩阵
{
    //自反闭包
    int n = re->n;
    R tmp = CopyRelation(re);
    for (int i = 0; i < n; i++)
        tmp->r[i][i] = 1;
    printf("自反闭包矩阵:\n");
    PrintRelation(tmp);
    DestoryRelation(tmp);

    //对称闭包
    tmp = CopyRelation(re);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i != j && tmp->r[i][j])
            {
                tmp->r[j][i] = 1;
            }
        }
    }
    printf("对称闭包矩阵:\n");
    PrintRelation(tmp);
    DestoryRelation(tmp);

    //传递闭包
    tmp = CopyRelation(re);
    R ans = InitRelationTmp(n);
    AddRelation(ans, re);

    for (int i = 0; i < n-1; i++)
    {
        tmp = Multiply(tmp, re); //最多乘n次
        AddRelation(ans, tmp);
    }
    printf("传递闭包矩阵:\n");
    PrintRelation(ans);
    DestoryRelation(tmp);
    free(ans);
}
void PanRelation(R re) //判断矩阵的关系
{
    int flag = 0;
    printf("具有的关系为:\n");
    if (flagz == 1 && flagd == 1 && flagc == 1) //如果为自反,对称,传递则为等价关系
    {
        printf("等价关系\n");
        flag = 1;
    }
    if (flagz == 1 && flagd == 1) //若为自反,对称则为相容关系
    {
        printf("相容关系\n");
        flag = 1;
    }
    if (flagz == 1 && flagfd == 1 && flagc == 1) //若为自反,反对称,传递为偏序关系
    {
        printf("偏序关系\n");
        flag = 1;
    }
    if (!flag)
    printf("该关系矩阵不具有等价、相容、偏序关系\n");
}

int main()
{
    int size;
    printf("请输入该集合的元素个数:\n");
    scanf("%d", &size);

    S s = InitSet(size);       //输入集合
    R re = InitRelation(size); //输入关系矩阵

    PrintRelation(re);     //打印关系矩阵
    PrintCharacter(s, re); //打印矩阵性质
    PrintBibao(re);        //打印闭包矩阵
    PanRelation(re);       //判断矩阵的关系

    DestorySet(s); //释放内存
    DestoryRelation(re);

    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/894321.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

数据分析方法(回归分析,决策树与神经网络,提升树,时间序列分析,假设检验,用户画像,竞品分析)等

1.回归分析 回归分析是一种统计方法&#xff0c;用于探索自变量&#xff08;预测变量&#xff09;和因变量&#xff08;目标变量&#xff09;之间的关系。它可以帮助预测变量的变化对目标变量的影响大小。例如&#xff0c;简单线性回归用于分析两个变量之间的线性关系&#xf…

能源领域下暖通行业现状-研究

基于AI大语言模型的暖通行业能源管理系统构建研究 一、能源管理中的突出问题 1. **能源消耗监测不准确** 现有的监测系统在获取设备实时能耗数据方面存在精度不足的问题&#xff0c;难以准确反映能源的实际使用情况。这使得节能决策缺乏可靠的数据支持&#xff0c;无法精准定位…

react18中的计算属性及useMemo的性能优化技巧

react18里面的计算属性和使用useMemo来提升组件性能的方法 计算属性 实现效果 代码实现 函数式组件极简洁的实现&#xff0c;就这样 import { useState } from "react"; function FullName() {const [firstName, setFirstName] useState("");const [la…

『 Linux 』HTTP(三)

文章目录 HTTP的请求方法HTTP的状态码模拟404状态重定向状态码状态码与浏览器的联系 TCP的短连接与长连接Connection 头部Content-Type 头部Set-Cookie 头部Session ID 本文代码参照前一篇博客 HTTP的请求方法 HTTP协议存在多种请求方法,但是较为常用的请求方法基本为GET方法与…

开源 AI 智能名片 2+1 链动模式 S2B2C 商城小程序:企业产供销全流程的创新驱动

摘要&#xff1a;本文探讨了开源 AI 智能名片、链动 21 模式以及 S2B2C 商城小程序源码在企业产供销过程中的作用。通过分析社交电商与企业产供销的关联、数据运营体系的支撑作用以及小程序功能在企业产供销中的应用等方面&#xff0c;阐述了其在产品研发、传播、营销和公关方面…

2013 lost connection to MySQL server during query

1.问题 使用navicat连接doris&#xff0c;会有这个错误。 2.解决 换低版本的navicat比如navicat11。

Leetcode—192. 统计词频【中等】(Shell)

2024每日刷题&#xff08;188&#xff09; Leetcode—192. 统计词频 实现代码 # Read from the file words.txt and output the word frequency list to stdout. cat words.txt | tr -s \n | sort | uniq -c | sort -nr | awk {print $2, $1}运行结果 之后我会持续更新&…

spring 启动失败 active: @env@

参考&#xff1a;SpringBoot启动失败报错&#xff0c;spring.profiles.active:env中环境变量无法识别报错_active: env_profileactive启动报错 ine 3, column 13:-CSDN博客

开源vGPU方案 HAMi实现细粒度GPU切分——筑梦之路

前言 为什么需要 GPU 共享、切分等方案&#xff1f; 在使用GPU的过程中我们会发现&#xff0c;直接在裸机环境使用&#xff0c;都可以多个进程共享 GPU&#xff0c;怎么到 k8s 环境就不行了&#xff1f; 1. 资源感知 在 k8s 中资源是和节点绑定的&#xff0c;对于 GPU 资源…

【MySQL】 表的增删操作

目录 1.Create&#xff08;增&#xff09; 1.1.单行数据 全列插入 1.2.多行数据 指定列插入 1.3.插入否则更新 1.4.替换数据&#xff08;REPLACE&#xff09; 2.Delete&#xff08;删&#xff09; 2.1.删除表中的某个条目 2.2.删除整张表数据 2.3.截断表 1.Create…

智汇云舟亮相WAFI世界农业科技创新大会,并参编数字农业产业图谱

10月10日&#xff0c;2024WAFI世界农业科技创新大会农食行业创新与投资峰会在北京金海湖国际会展中心举行。中国农业大学MBA教育中心主任、教授付文阁、平谷区委常委、统战部部长刘堃、华为公共事业军团数字政府首席专家刘丹、荷兰瓦赫宁根大学前校长Aalt Dijkhuizen、牧原食品…

【论文阅读】Bi-Mamba+: Bidirectional Mamba for Time Series Forecasting

文章目录 概要阅读背景知识引言创新之处 研究方法概述方法部分的核心模块多尺度打补丁&#xff08;Multi-Scale Patching&#xff09;Mamba&#xff1a;全局模式专家Local Window Transformer&#xff08;LWT&#xff09;&#xff1a;局部变化专家长短期路由器&#xff08;Long…

pikachu靶场SQL-Inject中的“delete“注入、“http header“注入、盲注、宽字节注入

"delete"注入 抓包发现在留言时有messagehhhh&submitsubmit两个参数&#xff0c;但并未涉及到数据库操作。除此之外&#xff0c;在删除留言时URL中拼接了?id的参数 构造?id59有报错回显 利用报错注入函数来查询数据&#xff0c;有空格编译不通过&#xff0c…

Agent智能体?我们要的到底是什么

What is an agent? ❝ 近年来&#xff0c;大型语言模型&#xff08;LLM&#xff09;的能力越来越强&#xff0c;应用范围也越来越广泛&#xff0c;其中一个热门方向就是智能体&#xff08;Agent&#xff09;。但在这一切的背后&#xff0c;我们真正追求的是什么&#xff1f;是…

SSM框架学习(七、MyBatis-Plus高级用法:最优化持久层开发)

目录 一、MyBatis-Plus快速入门 1.简介 2.快速入门 二、MyBatis-Plus核心功能 1.基于Mapper接口CRUD &#xff08;1&#xff09;Insert 方法 &#xff08;2&#xff09;Delete方法 &#xff08;3&#xff09;Update 方法 &#xff08;4&#xff09;Select方法 2.基于Serv…

解决在Windows中安装tensorflow2.10无法检测到GPU的问题

解决在Windows中安装tensorflow2.10无法检测到GPU的问题 官方给出的Windows本地安装方式 更新显卡驱动到最新。安装anaconda或miniconda作为python环境的管理工具。创建新的环境tf&#xff1a;conda create --name tf python3.9&#xff0c;然后进入改环境&#xff1a;conda …

【学习笔记】理解 C++ 中 reinterpret_cast 和 C 风格类型转换的区别

【学习笔记】理解 C 中 reinterpret_cast 和 C 风格类型转换的区别 在 C 中&#xff0c;类型转换是一个常见的操作&#xff0c;特别是当我们需要在不同类型之间进行数据操作时。本篇笔记将通过两个具体的例子来讨论 reinterpret_cast 和 C 风格的类型转换的区别。 示例 1&…

【uniapp】设置公共样式,实现公共背景等

目录 1、 全局渐变背景色 2.1 创建common目录 2.2 在common下新建style和images等目录 2.3 在style下新建common-style.scss 2.4 common-style输入全局渐变颜色 2.5 引入样式 2.6 业务页面引入 2.7 展示 2、全局字体颜色 2.1 新建base-style.scss文件 2.2 设置base-…

【动手学深度学习】7.6. 残差网络(ResNet)(个人向笔记)

1. ResNet精读论文视频的Introduction部分 深度卷积神经网络好&#xff0c;好在可以叠加很多层&#xff0c;每一层都可以提取不一样的特征但是网络特别深的时候&#xff0c;梯度要么爆炸要么消失&#xff0c;我们能做的就是将参数随机初始化做好&#xff0c;或者是在中间加一些…

ai聊天对话页面-uniapp

流式传输打字机效果&#xff0c;只支持uniapp内使用 &#xff0c;下载地址 https://download.csdn.net/download/qq_54123885/89899859