离散数学闭包实验报告
专业 12计算机科学与技术
学号 12407127
姓名 周谦益
时间 20##—11--15
一、实验目的
1. 通过上机程序,进一步加深对关系中自反闭包,对称闭包,传递闭包的理解。
2. 掌握Warshall算法。
3. 学会用程序解决离散数学中的问题。
4. 增强我们编写程序的能力。
二、实验内容
求有限集上给定关系的自反、对称和传递闭包(用Warshall算法)。
三、实验环境
我的实验是在Vs2008实验环境下完成的,而所设计的程序也在这个环境下通过了编译,运行和测试。
四、实验原理和实现过程
设计思路
在三种闭包中自反和对称闭包的求解很容易,对矩阵表示的关系,其自反闭包只要将矩阵的主对角线全部置为1就可;对称闭包则只需要将矩阵中数值为1的元素关于主对角线对称的元素数值也设为1就可以了;而对于传递闭包,用Warshall算法可以很方便的计算出来。下面我就来具体分析一下每一种闭包运算的设计。
自反闭包的设计:我们只要把关系矩阵的对角线的元素全赋值为1就可以啦。具体程序如下:
求自反闭包的程序:
int Relation::Reflexive()//求自反闭包的函数
{
for(int i=0;i<Len;i++)
if(!R[i][i])return(0);
return(1);
};
对称闭包的求法:对于对称闭包,我们只只需要将矩阵中数值为1的元素的对称位置的元素数值也设为1就可以了。具体程序如下:
对称闭包:
int Relation::Symmetric()//对称闭包的函数
{
int i,j,K=Len-1;
for(i=0;i<K;i++)
for(j=i+1;j<Len;j++)
if(R[i][j]!=R[j][i])return(0);
return(1);
};
传递闭包设计:传递闭包我主要用Warshall算法来求。
书上的Walshall算法的伪代码如下:
设R的关系矩阵为M
(1)令矩阵A=M
(2)置i=1
(3)对所有的j,若A[j,i]=1,则对于 k=1,2,…,n,令A[j,k]=A[j,k]+A[i,k]
(4) i=i+l.
(5)若i≤n,则转到(3),否则结束
根据Warshall算法,我设计求出了关系的传递闭包,具体程序如下:
int Relation::Transitive()//传递闭包函数
{
Relation t;
t=C_t(1);
for(int i=0;i<Len;i++)
for(int j=0;j<Len;j++)
if(R[i][j]!=t.R[i][j])return(0);
return(1);
};
把上面的每个子函数串在一起,再加上主函数,就可以实现这次实验的要求。
程序的完整代码如下所示:
#include "stdafx.h"
#include <iostream>
using namespace std;
int const Max=20;
class Relation
{
protected:
int Len,A[Max],R[Max][Max];
int Index(int x);
public:
Relation(){Len=0;};//空集A,空关系R
Relation(int *p,int Q[Max][Max],int n);//n个元素集合A及其关系
int IsofA(int x);//x是否属于A
int IsofR(int x,int y);
Relation UnionA(Relation R1);//AUR1
Relation CrossR(Relation R1);
Relation C_r();
Relation C_s();
Relation C_t();
Relation C_t(int);
int Reflexive();
int Symmetric();//判断R是否对称
int Transitive();
int Equivalent_Relations();
void PrintA();
void PrintR();
};
int Relation::Index(int x)
{
int i;
for(i=0;i<Len;i++)
if(A[i]==x)return(i);
return(-1);
};
Relation::Relation(int *p,int Q[Max][Max],int n)
{
int i,j;
for(i=0;i<n;i++)
{
A[i]=p[i];
for(j=0;j<n;j++)
R[i][j]=Q[i][j];
};
Len=i;
};
int Relation::Reflexive()//求自反闭包的函数
{
for(int i=0;i<Len;i++)
if(!R[i][i])return(0);
return(1);
};
int Relation::Symmetric()//对称闭包的函数
{
int i,j,K=Len-1;
for(i=0;i<K;i++)
for(j=i+1;j<Len;j++)
if(R[i][j]!=R[j][i])return(0);
return(1);
};
int Relation::IsofA(int x)
{
for(int i=0;i<Len;i++)
if(A[i]==x)return(1);
return(0);
};
int Relation::IsofR(int x,int y)
{
int i,j;
i=Index(x);
j=Index(y);
if(i==-1||j==-1||R[i][j]==0)return(0);
return(1);
};
Relation Relation::UnionA(Relation R1)
{
int i,j;
Relation t;
for(i=0;i<Len;i++)t.A[i]=A[i];
t.Len=Len;
for(j=0;j<R1.Len;j++)
{
for(i=0;i<Len;i++)
if(t.A[i]==R1.A[j])break;
if(i>=Len)t.A[t.Len++]=R1.A[j];
};
for(i=0;i<t.Len;i++)
for(j=0;j<t.Len;j++)
t.R[i][j]=0;
return(t);
};
Relation Relation::CrossR(Relation R1)
{
int i,j;
Relation t;
for(i=0;i<Len;i++)
{
t.A[i]=A[i];
for(j=0;j<Len;j++)
t.R[i][j]=R[i][j] && R1.R[i][j];
};
t.Len=Len;
return(t);
};
Relation Relation::C_r()//自反闭包
{
int i,j;
Relation t;
for(i=0;i<Len;i++)
{
t.A[i]=A[i];
for(j=0;j<Len;j++)
{
t.R[i][j]=R[i][j];
if(i==j)t.R[i][j]=1;
};
};
t.Len=Len;
return(t);
};
Relation Relation::C_s()//对称闭包
{
int i,j;
Relation t;
for(i=0;i<Len;i++)
{
t.A[i]=A[i];
for(j=i;j<Len;j++)
{
if(R[i][j]==1)t.R[i][j]=t.R[j][i]=1;
else
{
if(R[j][i]==1)t.R[i][j]=t.R[j][i]=1;
else t.R[i][j]=t.R[j][i]=0;
};
};
};
t.Len=Len;
return(t);
};
Relation Relation::C_t()//传递闭包
{
int i,j,k,l,v;
Relation t;
int M[Max][Max],N[Max][Max];
for(i=0;i<Len;i++)
{
t.A[i]=A[i];
for(j=0;j<Len;j++)
t.R[i][j]=M[i][j]=R[i][j];
};
for(i=1;i<Len;i++)//共Len-1次
{
for(j=0;j<Len;j++)//行
for(k=0;k<Len;k++)//列
{
v=0;
for(l=0;l<Len;l++)//对行列加乘
v=v||M[j][l]&&R[l][k];//布尔加乘
N[j][k]=v;
};
for(j=0;j<Len;j++)
for(k=0;k<Len;k++)
{
t.R[j][k]=t.R[j][k]||N[j][k];
M[j][k]=N[j][k];
};
};
t.Len=Len;
return(t);
};
Relation Relation::C_t(int x)
{
int i,j,l;
Relation t;
for(i=0;i<Len;i++)
{
t.A[i]=A[i];
for(j=0;j<Len;j++)
t.R[i][j]=R[i][j];
};
for(i=0;i<Len;i++)
{
for(j=0;j<Len;j++)
if(t.R[j][i]==1)
{
for(l=0;l<Len;l++)
t.R[j][l]=t.R[j][l]||t.R[i][l];
};
};
t.Len=Len;
return(t);
};
int Relation::Transitive()//求传递闭包函数
{
Relation t;
t=C_t(1);
for(int i=0;i<Len;i++)
for(int j=0;j<Len;j++)
if(R[i][j]!=t.R[i][j])return(0);
return(1);
};
int Relation::Equivalent_Relations()
{
return(this->Reflexive()&&Symmetric()&&Transitive());
};
void Relation::PrintA()
{
int i;
if(Len==0)cout<<"空集\n";
else
{
for(i=0;i<Len;i++)
{
cout<<A[i]<<'\t';
if((i+1)%10==0)cout<<endl;
};
};
cout<<endl;
};
void Relation::PrintR()
{
int i,j;
if(Len==0)cout<<"空关系\n";
else
{
for(i=0;i<Len;i++)
{
cout<<"第"<<i<<"行:"<<endl;
for(j=0;j<Len;j++)
{
cout<<R[i][j]<<'\t';
if((i+1)%10==0)cout<<endl;
};
};
};
cout<<endl;
};
int main(int argc, char* argv[])
{
int B[10]={10,11,12,13,14,15,16,17,18,19};
int C[6]={30,31,12,16};
int M1[Max][Max]={{0,1,0,1},{1,1,0,1},{0,0,1,0},{0,1,0,1}};
Relation R1,R2(C,M1,4);
Relation Rb(B,M1,4);
Rb.PrintA();
Rb.PrintR();
cout<<Rb.IsofA(12)<<"isof12!"<<endl;
cout<<Rb.IsofA(15)<<"isof15!"<<endl;
cout<<Rb.IsofR(10,11)<<"isof 10-11!"<<endl;
cout<<Rb.IsofR(9,11)<<"isof 9-11!"<<endl;
cout<<Rb.IsofR(10,21)<<"isof 10-21!"<<endl;
R1=R2.CrossR(Rb);
R1.PrintR();
cout<<"等价:"<<R1.Equivalent_Relations()<<endl;
cout<<"R2\n";
R2.PrintR();
cout<<"R1\n";
R1.PrintR();
cout<<"Reflexive:"<<R1.Reflexive()<<endl;
cout<<"Symmetric:"<<R1.Symmetric()<<endl;
cout<<"Transitive:"<<R1.Transitive()<<endl;
R1=R2.C_r();
R1.PrintR();cout<<"C_r\n";cout<<"Reflexive:"<<R1.Reflexive()<<endl;
R1=R2.C_s();
R1.PrintR();cout<<"C_s\n";cout<<"Symmetric:"<<R1.Symmetric()<<endl;
R1=R2.C_t();
R1.PrintR();cout<<"C_t\n";
R1=R2.C_t(1);cout<<"Transitive:"<<R1.Transitive()<<endl;
R1.PrintR();cout<<"C_r\n";
cout<<"等价:"<<R1.Equivalent_Relations()<<endl;
Rb=R2.CrossR(R1);
cout<<"Cross\n";
cout<<"Rb\n";
Rb.PrintR();
cout<<"Hello World!\n";
return 0;
getchar();
}
五、实验输入输出和数据
程序输出时会依次输出自反闭包,对称闭包和传递闭包,并且会分别输出各个闭包的关系序偶和关系矩阵。
输入结束)。
六、心得体会
通过本次实验让我进一步加深了对关系的理解,也掌握了有关关系的一些运算,同时也提高了我的编程能力,学会了使用Warshall算法。我认为这是一次很有意义的实验。