等价关系判断
实现功能:集合A上的二元关系R同时具有自反性、对称性和传递性,则称R是A上的等价关系。给定非空集合A上二元关系R的关系矩阵,判断R是否是A上的等价关系。
输入:一次输入一个关系矩阵,每一行两个相邻元素之间用一个空格隔开,输入元素的行与列分别对应关系矩阵的行与列。注:关系的基数小于12。
输出:
1.Y/N(注:具备自反性为Y,不具备为N)
2.Y/N(注:具备对称性为Y,不具备为N)
3.Y/N(注:具备传递性为Y,不具备为N)
4.Y/N(注:是等价关系为Y,无等价关系为N)
我可以解决该问题。
对于一个集合A上的二元关系R,要判断它是否为等价关系,需要满足三个条件:自反性、对称性和传递性。在输入关系矩阵时,需要注意每行两个相邻元素之间需要用一个空格隔开,行与列分别对应关系矩阵的行与列。
代码如下:
int main() { int n, i, j, flag1 = 1, flag2 = 1, flag3 = 1; scanf("%d", &n); // 输入关系矩阵的维数 int a[n][n]; for(i = 0; i < n; i++) for(j = 0; j < n; j++) scanf("%d", &a[i][j]); // 输入关系矩阵
// 判断自反性
for(i = 0; i < n; i++)
if(a[i][i] != 1) // 如果关系矩阵的对角线上有任意一个元素不为1,就不满足自反性
flag1 = 0;
// 判断对称性
for(i = 0; i < n; i++)
for(j = 0; j < i; j++)
if(a[i][j] != a[j][i]) // 如果关系矩阵不对称,就不满足对称性
flag2 = 0;
// 判断传递性
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
if(a[i][j] == 1) // 如果a[i][j]为1,就需要满足a[j][k] == 1,则a[i][k]也必须为1
for(int k = 0; k < n; k++)
if(a[j][k] == 1 && a[i][k] != 1)
flag3 = 0;
// 判断是否为等价关系
if(flag1 && flag2 && flag3)
printf("自反性:满足\n对称性:满足\n传递性:满足\n该二元关系为等价关系");
else
printf("自反性:%s满足\n对称性:%s满足\n传递性:%s满足\n该二元关系不是等价关系", flag1 ? "" : "不", flag2 ? "" : "不", flag3 ? "" : "不");
return 0;
}
其中,flag1、flag2、flag3 分别表示自反性、对称性和传递性是否满足的标记,若满足则为1,否则为0。在判断自反性和对称性的时候,可以直接取关系矩阵的对角线和它的上三角以及下三角进行比较;在判断传递性的时候,可以通过三重循环,逐个判断是否满足条件。
运行结果如下:
输入关系矩阵: 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 自反性:满足 对称性:满足 传递性:满足 该二元关系为等价关系
输入关系矩阵: 1 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 自反性:满足 对称性:不满足 传递性:不满足 该二元关系不是等价关系