离散数学关系性质的C++或C语言判断实验报告

时间：2024.5.8

1.【实验目的】

对称：

通过算法设计并编程实现对给定集合上的关系是否为对称关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法

自反：

通过算法设计并编程实现对给定集合上的关系是否为自反关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。

2.【实验内容】

已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为对称关系。假定R的关系矩阵为：

3.【实验要求】

C语言编程实现

4.【算法描述】

对称：

从给定的关系矩阵来判断关系R是否为对称是很容易的。若M（R的关系矩阵）为对称矩阵，则R是对称关系；若M为反对称矩阵，则R是反对称关系。因为R为对称的是等价关系的必要条件，所以，本算法可以作为判等价关系算法的子程序给出。

算法实现：

（1）输入关系矩阵M（M为n阶方阵）；

（2）判断对称性，对于i=2，3，….，n；j=1，2,……，i-1，若存在m_ij=m_ji，则R是对称的；

（3）判断反对称性；

（4）判断既是对称的又是反对称的；

（5）判断既不是对称的又不是反对称的；

（6）输出判断结果。

自反：

从给定的关系矩阵来断判关系R是否为自反是很容易的。若M（R的关系矩阵）的主对角线元素均为1，则R是自反关系；若M（R的关系矩阵）的主对角线元素均为0，则R是反自反关系；若M（R的关系矩阵）的主对角线元素既有1又有0，则R既不是自反关系也不是反自反关系。本算法可以作为判等价关系算法的子程序给出。

算法实现

（1）输入关系矩阵M（M为n阶方阵）。

（2）判断自反性，对于i=1，2，….，n；若存在m_ii=0，则R不是自反的；若存在m_ii=1，则R是自反的；否则R既不是自反关系也不是反自反关系。

（3）输出判断结果。

源代码

#include<stdio.h>

void z();

void r();

void main()

{

int d;

while(d)

{

printf("欢迎使用关系性质的判断系统\n\n 1. 对称关系的判断 2. 自反关系的判断\n\n请输入选项：");

scanf("%d",&d);

switch(d){

case 1: r();break;

case 2: z();break;

case 0: break;

}

printf("\n");

printf("是否还继续？是请输入1，否请输入0：");

scanf("%d",&d);

printf("\n\n");

}return 0;

}

void r()

{

int a[30][30];

int m,n,i,j,c,b,d;

c=0;

d=0;

b=0;

d=1;

printf("请输入矩阵的行数");

scanf("%d",&m);

printf("请输入矩阵的列数");

scanf("%d",&n);

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

printf("请输入矩阵关系中第%d行第%d列的数字：",i,j);

scanf("%d",&a[i][j]);

}

printf("关系矩阵M为：\n");

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

printf("%d ",a[i][j]);

printf("\n");

}

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

if(a[i][j]!=a[j][i])

{

c=1;

break;

}

if(c==0)

{

for(i=0;i<m;i++)

{

for(j=0;j<n;j++){

if(a[i][j]==1){

if(a[j][i]!=0){

c=2;

break;

}

if(c==2) printf("该矩阵是对称性的\n");

else

if(c==0) printf("该矩阵是既对称又反对称的\n");

}

else

if(c==1){

for(i=0;i<m;i++){

for(j=0;j<n;j++){

if(a[i][j]==1){

if(a[j][i]!=0){

c=2;

break;

}

if(c==2) printf("该矩阵不是对称的又不是反对称的\n");

else{

printf("该矩阵是反对称性的\n");

}

}}

void z()

{

int m,n,i,j,a[80][80],c;

c=0;

printf("请输入矩阵的行数");

scanf("%d",&m);

printf("请输入矩阵的列数");

scanf("%d",&n);

for(i=0;i<m;i++){

for(j=0;j<n;j++){

printf("请输入矩阵关系中第%d行第%d列的数字：",i,j);

scanf("%d",&a[i][j]);

}

printf("关系矩阵M为：\n");

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

printf("%d ",a[i][j]);

printf("\n");

}

for(i=0;i<m;i++){

if(a[i][i]!=0){

c=1;break;

}

if(c==1) printf("该矩阵是自反性的\n");

if(c==0) printf("该矩阵是反自反性的\n");

}

第二篇：离散数学C语言上机题

广东工业大学计算机科学与技术张法光

离散数学C语言上机题

Anyview

可视化编程作业系统

二元关系章节编程题

6.01③ 试设计一算法，

实现集合的卡氏积运算。

实现下列函数：

/**

* 进行两个集合的卡氏积运算

* @param pA：要进行卡氏积运算的集合

* @param pB：要进行卡氏积运算的集合

* @return: 将pA和pB进行卡氏积运算后得到的集合

pCartersianSet CartesianProduct(pOriginalSet pA, pOriginalSet pB)

{

pCartersianSet pC=createNullCartersianSet(); //空卡

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

{ // 空卡 ←序偶插入 ← 建立序偶 ← 条件语句

for(resetOriginalSet(pB);!isEndOfOriginalSet(pB);nextOriginalSetPos(pB))

OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),g etCurrentOriginalSetElem(pB)));

}

return pC;

}

6.02② 试设计一算法，

给定集合A、集合B和集合C，判断集合C是否为A到B的一个二元关系。

实现下列函数：

/**

* 给定集合A、集合B和集合C，判断集合C是否为A到B的一个二元关系。 * @param pA：集合A

* @param pB：集合B

* @param pC：集合C

* @return: 如果集合C是A到B的一个二元关系，则返回true，否则返回false。 */

boolean isBinaryRelation(pOriginalSet pA, pOriginalSet pB, pCartersianSet pC)

{

pCartersianSet pD=createNullCartersianSet();

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

{ // 空卡 ←序偶插入 ← 建立序偶 ← 条件语句

for(resetOriginalSet(pB);!isEndOfOriginalSet(pB);nextOriginalSetPos(pB))

OrderedCoupleInsertToCartersianSet(pD,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pB)));

}

for(resetCartersianSet(pC);!isEndOfCartersianSet(pC); nextCartersianSetPos(pC)) {

if(isInCartersianSet(pD,getCurrentCartersianSetElem(pC)))

;//满足条件，执行空语句，继续循环

else return false;

}

return true;

}

6.03② 试设计一算法，求集合A上的恒等关系。

实现下列函数：

/**

* 给定集合A，求集合A上的恒等关系。

* @param pSet：原始集合

* @return: 集合A上的恒等关系。

pCartersianSet IdentityRelation(pOriginalSet pA)

{ pCartersianSet pB=createNullCartersianSet();

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

{ // 空卡 ←序偶插入 ← 建立序偶 ← 条件语句

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

if(getCurrentOriginalSetElem(pA)==getCurrentOriginalSetElem(pA))//The same elements

OrderedCoupleInsertToCartersianSet(pB,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA)));

}

return pB;

}

6.04③ 试设计一算法，求两个卡氏积集合的复合运算。

实现下列函数：

/**

* 给定两个集合，求该两个集合的复合运算。

* @param pA：卡氏积集合

* @param pB：卡氏积集合

* @return: pA与pB的复合运算结果。

pCartersianSet CompositeOperation(pCartersianSet pA, pCartersianSet pB)

{ pCartersianSet pC=createNullCartersianSet();

for(resetCartersianSet(pA);!isEndOfCartersianSet(pA); nextCartersianSetPos(pA))

{

for(resetCartersianSet(pB);!isEndOfCartersianSet(pB); nextCartersianSetPos(pB))

if(isEqualOriginalSetElem(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pA)),

getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pB))))

//获取A卡氏积中序偶的第二元 //获取第二元

OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getFirstElemOfOrderedCouple(get

CurrentCartersianSetElem(pA)),getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(p

B))) );

}

return pC;

}

6.05② 试设计一算法，求一个关系的逆运算。

实现下列函数：

/**

* 求一个关系的逆运算。

* @param pA：卡氏积集合

* @return: pA的逆运算结果。

pCartersianSet InverseOperation(pCartersianSet pA)

{ pCartersianSet pB=createNullCartersianSet();

for(resetCartersianSet(pA);!isEndOfCartersianSet(pA); nextCartersianSetPos(pA))

{OrderedCoupleInsertToCartersianSet(pB,createOrderedCouple(getSecondElemOfOrderedCouple

(getCurrentCartersianSetElem(pA)),getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(

pA))) );

}

return pB;

}

6.06④ 试设计一算法，对某集合A上的一个二元关系，求该关系的幂运算。

实现下列函数：

/**

* 求一个关系的幂运算。

* @param pA：原始集合

* @param pBinaryRelationR： pA上的关系R

* @param n：幂运算的次数，且n >= 0

* @return: pBinaryRelationSet的n次幂运算结果。

pCartersianSet CompositeOperation(pCartersianSet pA, pCartersianSet pB)

{ pCartersianSet pC=createNullCartersianSet();

for(resetCartersianSet(pA);!isEndOfCartersianSet(pA); nextCartersianSetPos(pA))

{

for(resetCartersianSet(pB);!isEndOfCartersianSet(pB); nextCartersianSetPos(pB))

if(isEqualOriginalSetElem(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pA)),

getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pB))))

//获取A卡氏积中序偶的第二元 //获取第二元

OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getFirstElemOfOrderedCouple(get

CurrentCartersianSetElem(pA)),getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(p

B))) );

}

return pC;

}

pCartersianSet PowOperation(pOriginalSet pA,

pCartersianSet pBinaryRelationR,

int n)

{

pCartersianSet pC=createNullCartersianSet();

pC=copyCartersianSet(pBinaryRelationR);

if(n==0)

{

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

{for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA)));

}

return pC;

}

if(n==1)

{return pBinaryRelationR;}

for(int i=1;i<n;i++)

{pC=CompositeOperation(pC,pBinaryRelationR); }

return pC;

}

6.02② 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有自反性。

实现下列函数：

/**

* 判断一个关系是否具有自反性。

* @param pA：原始集合

* @param pBinaryRelationR：卡氏积集合，该集合是一个pA上的二元关系

* @return: 如果pBinaryRelationSet具有自反性；则返回true，否则返回false。 */

boolean IsReflexivity(pOriginalSet pA, pCartersianSet pBinaryRelationR)

{ pCartersianSet pC=createNullCartersianSet();

//获取 IA

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

{

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA)));

}

for(resetCartersianSet(pC);!isEndOfCartersianSet(pC); nextCartersianSetPos(pC)) {

if(isInCartersianSet(pBinaryRelationR,getCurrentCartersianSetElem(pC)))

;//满足条件，执行空语句，继续循环

else return false;

}

return true;

}

6.08② 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有反自反性。

实现下列函数：

/**

* 判断一个关系是否具有反自反性。

* @param pA：原始集合

* @param pBinaryRelationR：卡氏积集合，该集合是一个pA上的二元关系

* @return: 如果pBinaryRelationSet具有反自反性；则返回true，否则返回false。 */

boolean IsAntiReflexivity(pOriginalSet pA, pCartersianSet pBinaryRelationR)

{ pCartersianSet pC=createNullCartersianSet();

//获取 IA

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

{

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA)));

}

for(resetCartersianSet(pC);!isEndOfCartersianSet(pC); nextCartersianSetPos(pC)) {

if(!isInCartersianSet(pBinaryRelationR,getCurrentCartersianSetElem(pC)))

;//满足条件，执行空语句，继续循环

else return false;

}

return true;

}

6.09③ 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有自反性或者反自反性。

在实际运算中，A无需给出。

实现下列函数：

/**

* 判断一个关系是否具有自反性或者反自反性。对一个关系R是否具有自反性或者反自反性，

* 有四种可能：是自反的；是反自反的；既是自反的也是反自反的、

* 既不是自反的也不是反自反的。

* @param pA：原始集合

* @param pBinaryRelationR：卡氏积集合，该集合是一个pA上的二元关系

* @return: 返回一个Reflexivity_Type枚举类型值。

* 如果pBinaryRelationSet具有自反性，则返回REFLEXIVITY;

* 如果pBinaryRelationSet具有反自反性，则返回ANTI_REFLEXIVITY; * 如果pBinaryRelationSet既具有自反性，也具有反自反性，则返回 * REFLEXIVITY_AND_ANTI_REFLEXIVITY;

* 如果pBinaryRelationSet既不具有自反性，也不具有反自反性，则返回 * NOT_REFLEXIVITY_AND_NOT_ANTI_REFLEXIVITY;

//自反函数

boolean IsReflexivity(pOriginalSet pA, pCartersianSet pBinaryRelationR)

{ pCartersianSet pC=createNullCartersianSet();

//获取 IA

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

{

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA)));

}

for(resetCartersianSet(pC);!isEndOfCartersianSet(pC); nextCartersianSetPos(pC)) {

if(isInCartersianSet(pBinaryRelationR,getCurrentCartersianSetElem(pC)))

;//满足条件，执行空语句，继续循环

else return false;

}

return true;

}

//反自反函数

boolean IsAntiReflexivity(pOriginalSet pA, pCartersianSet pBinaryRelationR)

{ pCartersianSet pC=createNullCartersianSet();

//获取 IA

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

{

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA)));

}

for(resetCartersianSet(pC);!isEndOfCartersianSet(pC); nextCartersianSetPos(pC)) {

if(!isInCartersianSet(pBinaryRelationR,getCurrentCartersianSetElem(pC)))

;//满足条件，执行空语句，继续循环

else return false;

}

return true;

}

Reflexivity_Type DetermineReflexivity(pOriginalSet pA,

pCartersianSet pBinaryRelationR)

{

if(IsReflexivity(pA,pBinaryRelationR)&&IsAntiReflexivity(pA,pBinaryRelationR)) return REFLEXIVITY_AND_ANTI_REFLEXIVITY;

else if(!IsReflexivity(pA,pBinaryRelationR)&&!IsAntiReflexivity(pA,pBinaryRelationR)) return NOT_REFLEXIVITY_AND_NOT_ANTI_REFLEXIVITY;

else if(IsReflexivity(pA,pBinaryRelationR))

return REFLEXIVITY;

else

return ANTI_REFLEXIVITY;

}

6.10④ 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有对称性或者反对称性。

实现下列函数：

/**

* 判断一个关系是否具有对称性或者反对称性。对一个关系R是否具有对称性或者反对称性，

* 有四种可能：是对称的；是反对称的；；既是对称的也是反对称的；既不是对称的也不是 * 反对称的。

* @param pBinaryRelationR：卡氏积集合，该集合是一个pA上的二元关系

* @return: 返回一个Symmetry_Type枚举类型值。

* 如果pBinaryRelationSet具有对称性，则返回SYMMETRY;

* 如果pBinaryRelationSet具有反对称性，则返回ANTI_SYMMETRY; * 如果pBinaryRelationSet既具有对称性，也具有对称性，则返回

* SYMMETRY_AND_ANTI_SYMMETRY;

* 如果pBinaryRelationSet既不具有对称性，也不具有反对称性，则返回 * NOT_SYMMETRY_AND_NOT_ANTI_SYMMETRY;

Symmetry_Type DetermineSymmetry(pCartersianSet pBinaryRelationR)

{int a,b,c; a=b=c=0;

if(!isNullCartersianSet(pBinaryRelationR))

{

for(resetCartersianSet(pBinaryRelationR);!isEndOfCartersianSet(pBinaryRelationR);nextCartersianSetPos(pBinaryRelationR))

{

if(isInCartersianSet(pBinaryRelationR,createOrderedCouple(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)),

getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR))))

&&!isEqualOriginalSetElem(getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)),

getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)))) {a++;}

if(isInCartersianSet(pBinaryRelationR,createOrderedCouple(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)),

getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR))))

&&isEqualOriginalSetElem(getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)),

getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)))) {b++;}

if(!isInCartersianSet(pBinaryRelationR,createOrderedCouple(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)),

getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)))))

{c++;}

}

{

if(c==0&&a!=0)return SYMMETRY;

if(a==0&&c==0)return SYMMETRY_AND_ANTI_SYMMETRY;

if(a==0&&c!=0)return ANTI_SYMMETRY;

else return NOT_SYMMETRY_AND_NOT_ANTI_SYMMETRY;

}

if(isNullCartersianSet(pBinaryRelationR))

return SYMMETRY_AND_ANTI_SYMMETRY;

}

6.11④ 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有传递性。

实现下列函数：

/**

* 判断一个关系是否具有传递性。

* @param pA：原始集合

* @param pBinaryRelationR：卡氏积集合，该集合是一个pA上的二元关系 * @return: 如果pBinaryRelationR具有传递性，则返回true，否则返回false */

boolean IsTransitive(pOriginalSet pA, pCartersianSet pBinaryRelationR)

{

pOriginalSetElem First1,Second1;

pOriginalSetElem First2,Second2;

pCartersianSet pB=copyCartersianSet(pBinaryRelationR);

pCartersianSet pC=copyCartersianSet(pBinaryRelationR);

if(!isNullCartersianSet(pBinaryRelationR))

{

for(resetCartersianSet(pC);!isEndOfCartersianSet(pC);nextCartersianSetPos(pC)) {

First1=getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pC));

Second1=getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pC)); for(resetCartersianSet(pB);!isEndOfCartersianSet(pB);nextCartersianSetPos(pB)) {

First2=getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pB));

Second2=getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pB)); if(isEqualOriginalSetElem(First2,Second1))

{

if(!isInCartersianSet(pBinaryRelationR,createOrderedCouple(First1,Second2))) return false;}

}

else return true;

return true;

}

6.12③ 试设计一算法，对某集合A上的一个二元关系R，求R的自反闭包。

实现下列函数：

/**

* 判断一个关系R的自反闭包

* @param pA：原始集合

* @param pBinaryRelationR：卡氏积集合，该集合是一个pA上的二元关系

* @return: pBinaryRelationR的自反闭包

*/ 方法：//A的自反关系加上R即可

pCartersianSet ReflexiveClosure(pOriginalSet pA, pCartersianSet pBinaryRelationR) {

pCartersianSet pC=copyCartersianSet(pBinaryRelationR);

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

{ // 空卡 ←序偶插入 ← 建立序偶 ← 条件语句

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA)));

}

return pC;

}

6.13③ 试设计一算法，对某集合A上的一个二元关系R，求R的对称闭包。在实际计算中，无需给出集合A。

实现下列函数：

/**

* 判断一个关系R的对称闭包

* @param pBinaryRelationR：卡氏积集合，该集合是一个pA上的二元关系

* @return: pBinaryRelationR的自反闭包

// 方法：把<y,x>插入 pD即可其中pD为R的复制函数值

易错点：因为无需给出A。所以循环利用 pBinaryRelationR 即可。双重循环出错。 pCartersianSet SymmetricClosure(pCartersianSet pBinaryRelationR)

{

pCartersianSet pD=copyCartersianSet(pBinaryRelationR);

for(resetCartersianSet(pBinaryRelationR);!isEndOfCartersianSet(pBinaryRelationR);nextCartersianSetPos(pBinaryRelationR))

{

pOrderedCouple

xuou=createOrderedCouple(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)),

getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR))); // 定义xuou为序偶<y,x>

if(!isInCartersianSet(pBinaryRelationR,xuou)) // 判断序偶<y,x>是否在pR

{

OrderedCoupleInsertToCartersianSet(pD,xuou); // 插入序偶<y,x>

}

return pD;

}

6.14⑤ 试设计一算法，对某集合A上的一个二元关系R，求R的传递闭包。

实现下列函数：

/**

* 判断一个关系R的传递闭包

* @param pA：原始集合

* @param pBinaryRelationR：卡氏积集合，该集合是一个pA上的二元关系

* @return: pBinaryRelationR的传递闭包

pCartersianSet TransitiveClosure(pOriginalSet pA, pCartersianSet pBinaryRelationR) {

pCartersianSet pB=copyCartersianSet(pBinaryRelationR);

pCartersianSet pD=copyCartersianSet(pBinaryRelationR);

if(!isNullCartersianSet(pBinaryRelationR)) //非空

{

//假定：R为<x,y> ; pD为 <y,z>

for(resetCartersianSet(pBinaryRelationR);!isEndOfCartersianSet(pBinaryRelationR);nextCartersianSetPos(pBinaryRelationR))

{

if(!isEqualOriginalSetElem(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)),

getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR))))

//R中序偶第二元不等于第一元即y!=x; 排除两元相等的情况

{

for(resetCartersianSet(pD);!isEndOfCartersianSet(pD);nextCartersianSetPos(pD))

if(isEqualOriginalSetElem(getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pD)), getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)))

// R中序偶的第二元相等和pD中序偶第一元相等即 R为<x,y> ; pD为 <y,z> 中 Ry=pDy ;

&&!isInCartersianSet(pD,createOrderedCouple(getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)),

getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pD)))))

//xuou 不在pD 即<x,z>不属于pD ; */

OrderedCoupleInsertToCartersianSet(pB,createOrderedCouple(getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)),

getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pD))));

// 把符合条件的<x,z>插入到pB ;

}

return pB;

}

6.15③ 实现Warshall算法，求某关系的传递闭包。

实现下列函数：

/**

* 对某集合A上的一个二元关系，求该关系的传递闭包。该关系使用矩阵表示。 * @param pM：二元关系矩阵

* @return: pM的传递闭包的关系矩阵

pMatrix Warshall(pMatrix pM)

{

int i,j,a,b;

int n=getDim(pM);//维数

pMatrixBase p;

p=outToBuffer(pM);//首元素

if(n>=1)//非一维

{

for(i=0;i<n ;i++)

for(j=0;j<n;j++)

{

a=converToInt(*(p+(i*n+j)));

if(a==1)

for(b=0;b<n;b++)

if(converToInt(*(p+(j*n+b)))==1)

putValue(p+(i*n+b),1);

}

for(i=0;i<n ;i++)

{

for(j=0;j<n;j++)

{

a=converToInt(*(p+(i*n+j)));

if(a==1)

for(b=0;b<n;b++)

if(converToInt(*(p+(j*n+b)))==1)

putValue(p+(i*n+b),1);}

}

return createMatrix(p,n);

}

return pM;

}

第七章题目

一

7.01③ 试设计一算法，对某集合A上的一个二元关系R，判断R是否为等价关系。

实现下列函数：

/**

* 对某集合A上的一个二元关系R，判断R是否为等价关系

* @param pA：原始集合

* @param pBinaryRelationR：卡氏积集合，该集合是一个pA上的二元关系

* @return: 如果R是A上的等价关系，则返回true；否则返回false

boolean IsReflexivity(pOriginalSet pA, pCartersianSet pBinaryRelationR)

{ pCartersianSet pC=createNullCartersianSet();

//获取 IA

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

{

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pA)));

}

for(resetCartersianSet(pC);!isEndOfCartersianSet(pC); nextCartersianSetPos(pC)) {

if(isInCartersianSet(pBinaryRelationR,getCurrentCartersianSetElem(pC)))

;//满足条件，执行空语句，继续循环

else return false;

}

return true;

}

Symmetry_Type DetermineSymmetry(pCartersianSet pBinaryRelationR)

{int a,c; a=c=0;

if(!isNullCartersianSet(pBinaryRelationR))

{

for(resetCartersianSet(pBinaryRelationR);!isEndOfCartersianSet(pBinaryRelationR);nextCartersianSetPos(pBinaryRelationR))

{

if(isInCartersianSet(pBinaryRelationR,createOrderedCouple(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)),

getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR))))

&&!isEqualOriginalSetElem(getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)),

getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)))) {a++;}

if(!isInCartersianSet(pBinaryRelationR,createOrderedCouple(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)),

getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)))))

{c++;}

}

if(c==0&&a!=0)return SYMMETRY;

}

if(isNullCartersianSet(pBinaryRelationR))

return SYMMETRY_AND_ANTI_SYMMETRY;

}

boolean IsTransitive(pOriginalSet pA, pCartersianSet pBinaryRelationR)

{ int i=1;int j=1;int k=1;int d=0;

pOriginalSet pB=copyOriginalSet(pA);

pOriginalSet pC=copyOriginalSet(pA);

{

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

{

for(resetOriginalSet(pB);!isEndOfOriginalSet(pB);nextOriginalSetPos(pB))

{if(!isInCartersianSet(pBinaryRelationR,createOrderedCouple(getCurrentOriginalSetElem(pA),ge

tCurrentOriginalSetElem(pB)) ) )

i++; }

}

for(resetOriginalSet(pB);!isEndOfOriginalSet(pB);nextOriginalSetPos(pB))

{

for(resetOriginalSet(pC);!isEndOfOriginalSet(pC);nextOriginalSetPos(pC))

{if(!isInCartersianSet(pBinaryRelationR,createOrderedCouple(getCurrentOriginalSetElem(pB),getCurrentOriginalSetElem(pC)) ) )

j++;}

}

for(resetOriginalSet(pA);!isEndOfOriginalSet(pA);nextOriginalSetPos(pA))

{

for(resetOriginalSet(pC);!isEndOfOriginalSet(pC);nextOriginalSetPos(pC))

{if(!isInCartersianSet(pBinaryRelationR,createOrderedCouple(getCurrentOriginalSetElem(pA),getCurrentOriginalSetElem(pC)) ) )

k++;

}

if(i==1&&j==1&&k==1) //<x,y>?R ,<y,z>?R , <x,z>?R 均属于R

return true;

else if(i!=1||j!=1) //<x,y>或<y,z>不属于R

return true;

else

return false;

}

boolean isEquivalentRelation(pOriginalSet pA, pCartersianSet pBinaryRelationR)

{if(isNullCartersianSet(pBinaryRelationR)&&isNullOriginalSet(pA))

return true;

if(!isNullCartersianSet(pBinaryRelationR))

{

if(IsReflexivity(pA,pBinaryRelationR)==true

&&DetermineSymmetry(pBinaryRelationR)==SYMMETRY

&&IsTransitive(pA,pBinaryRelationR)==true)

{return true;

}

return false;

}

二

7.02⑤ 试设计一算法，对某集合A上的一个二元关系R，求商集A/R。

实现下列函数：

/**

* 对某集合A上的一个二元关系R，判断R是否为等价关系

* @param pSetA：原始集合

* @param pBinaryRelationR：卡氏积集合，该集合是一个pA上的二元关系

* @return: 商集A/R。商集中的每一个元素都是等价类集合。是pCompoundSet复合集合类型；其元素是原始集合，即等价类集合是pOriginalSet类型。

* 注意：在求解过程中，请勿对pSetA和pBinaryRelationR进行任何的加工型操作。 * 即请勿修改该集合的结构，包括增加或删除集合中的元素，或者对

* pSetA和pBinaryRelationR进行赋值操作。

pCompoundSet QuotientSet(pOriginalSet pSetA, pCartersianSet pBinaryRelationR)

{

pOriginalSet pA=createNullOriginalSet();

pCompoundSet pB=createNullCompoundSet();

if(!isNullCartersianSet(pBinaryRelationR))

for(resetOriginalSet(pSetA);!isEndOfOriginalSet(pSetA);nextOriginalSetPos(pSetA)) {

pA=createNullOriginalSet();

for(resetCartersianSet(pBinaryRelationR);!isEndOfCartersianSet(pBinaryRelationR);nextCartersianSetPos(pBinaryRelationR))

{

if(isEqualOriginalSetElem(getCurrentOriginalSetElem(pSetA),getFirstElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR))))

//条件插入

elemInsertToOriginalSet(pA,getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pBinaryRelationR)));

}

if(!isNullOriginalSet(pA))

originalSetInsertToCompoundSet(pB,pA);

}

return pB;

}

7.02⑤ 试设计一算法，对某集合A上的一个二元关系R，求商集A/R。

实现下列函数：

/**

* 对某集合A上的一个二元关系R，判断R是否为等价关系

* @param pSetA：原始集合

* @param pBinaryRelationR：卡氏积集合，该集合是一个pA上的二元关系

* @return: 商集A/R。商集中的每一个元素都是等价类集合。是pCompoundSet复合集合类型；其元素是原始集合，即等价类集合是pOriginalSet类型。

* 注意：在求解过程中，请勿对pSetA和pBinaryRelationR进行任何的加工型操作。 * 即请勿修改该集合的结构，包括增加或删除集合中的元素，或者对

* pSetA和pBinaryRelationR进行赋值操作。

三

7.03⑤ 试设计一算法，求某集合A上的模n同余关系。

实现下列函数：

/**

* 对某集合A上的一个二元关系R，判断R是否为等价关系

* @param pSet：原始集合

* @param n：模

* @return: 集合A上的模n同余关系

* 注意：在求解过程中，请勿对pSetA和pBinaryRelationR进行任何的加工型操作。 * 即请勿修改该集合的结构，包括增加或删除集合中的元素。

pCartersianSet CongruenceRelation(pOriginalSet pSet, int n)

{

pOriginalSet A=copyOriginalSet(pSet);

pOriginalSet B=copyOriginalSet(pSet);

pCartersianSet pC=createNullCartersianSet();

pOrderedCouple xuou;

if(!isNullCartersianSet(pSet))

for(resetOriginalSet(B);!isEndOfOriginalSet(B);nextOriginalSetPos(B))

{

for(resetOriginalSet(A);!isEndOfOriginalSet(A);nextOriginalSetPos(A))

{

if((originalSetElemToInt(getCurrentOriginalSetElem(B))-originalSetElemToInt(getCurrentOriginalSetElem(A)))%n==0)

{

if(!isInCartersianSet(pC,createOrderedCouple(getCurrentOriginalSetElem(B),getCurrentOriginalSetElem(A))))

xuou=createOrderedCouple(getCurrentOriginalSetElem(B),getCurrentOriginalSetElem(A)); OrderedCoupleInsertToCartersianSet(pC,xuou);

}

return pC;

}

四

7.04③ 试设计一算法，对某集合A上的一个二元关系R，判断R是否为偏序关系。

实现下列函数：

/**

* 对某集合A上的一个二元关系R，判断R是否为偏序关系

* @param pA：原始集合

* @param pBinaryRelationR：卡氏积集合，该集合是一个pA上的二元关系

* @return: 如果R是A上的偏序关系，则返回true；否则返回false

// R为自反，反对称和传递的则R为偏序关系调用三者函数