离散实验报告(二).doc

该【离散实验报告(二) 】是由【taoapp】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【离散实验报告(二) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。“离散数学”实验报告
专业:计算机嵌入式
班级:10455341
学号: 1045534125
姓名:孟腾腾
指导老师:闫仁武
日期:2011/11/15
一、实验内容
求有限集上给定关系的自反、对称和传递闭包
二、实验思路
设计思路
在三种闭包中自反和对称闭包的求解很容易,对矩阵表示的关系,其自反闭包只要将矩阵的主对角线全部置为1就可;对称闭包则加上关系的转置矩阵,并将相加后大于1的元素值设置为1就可得到;传递闭包则有两种算法:
算法R是集合X上的二元关系,则其自反闭包为
r(R)=RUI(x)(I(x)为恒等关系)
R是集合X上的二元关系,则其对称闭包为
s(R)=RUR^c
R是集合X上的二元关系,则其传递闭包为
直接根据计算,过程略
方法二:Warshall算法(1962)
设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),否则结束.
三、流程图
主函数
开始
声明各子函数
输入关系矩阵
输入z
z=1;调用自反函数
z=2,调用传递1算法函数
z=3调用传递2函数
z=4,条用对称函数
结束
四、程序清单
//:Definestheentrypointfortheconsoleapplication.
//
#include""
intconstMax=20;
classRelation
{
protected:
intLen,A[Max],R[Max][Max];
intIndex(intx);
public:
Relation(){Len=0;};
Relation(int*p,intQ[Max][Max],intn);
intIsofA(intx);
intIsofR(intx,inty);
RelationUnionA(RelationR1);
RelationCrossR(RelationR1);
RelationC_r();
RelationC_s();
RelationC_t();
RelationC_t(int);
intReflexive();
intSymmetric();
intTransitive();
intEquivalent_Relations();
voidPrintA();
voidPrintR();
};
intRelation::Index(intx)
{
inti;
for(i=0;i<Len;i++)
if(A[i]==x)return(i);
return(-1);
};
Relation::Relation(int*p,intQ[Max][Max],intn)
{
inti,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;
};
intRelation::Reflexive()
{
for(inti=0;i<Len;i++)
if(!R[i][i])return(0);
return(1);
};
intRelation::Symmetric()
{
inti,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);
};
intRelation::IsofA(intx)
{
for(inti=0;i<Len;i++)
if(A[i]==x)return(1);
return(0);
};
intRelation::IsofR(intx,inty)
{
inti,j;
i=Index(x);
j=Index(y);
if(i==-1||j==-1||R[i][j]==0)return(0);
return(1);
};
RelationRelation::UnionA(RelationR1)
{
inti,j;
Relationt;
for(i=0;i<Len;i++)[i]=A[i];
=Len;
for(j=0;j<;j++)
{
for(i=0;i<Len;i++)
if([i]==[j])break;
if(i>=Len)[++]=[j];
};
for(i=0;i<;i++)
for(j=0;j<;j++)
[i][j]=0;
return(t);
};
RelationRelation::CrossR(RelationR1)
{
inti,j;
Relationt;
for(i=0;i<Len;i++)
{
[i]=A[i];
for(j=0;j<Len;j++)
[i][j]=R[i][j]&&[i][j];
};
=Len;
return(t);
};
RelationRelation::C_r()
{
inti,j;
Relationt;
for(i=0;i<Len;i++)
{
[i]=A[i];
for(j=0;j<Len;j++)
{
[i][j]=R[i][j];
if(i==j)[i][j]=1;
};
};
=Len;
return(t);
};
RelationRelation::C_s()
{
inti,j;
Relationt;
for(i=0;i<Len;i++)
{
[i]=A[i];
for(j=i;j<Len;j++)
{
if(R[i][j]==1)[i][j]=[j][i]=1;
else
{
if(R[j][i]==1)[i][j]=[j][i]=1;
[i][j]=[j][i]=0;
};
};
};
=Len;
return(t);
};
RelationRelation::C_t()
{
inti,j,k,l,v;
Relationt;
intM[Max][Max],N[Max][Max];
for(i=0;i<Len;i++)
{
[i]=A[i];
for(j=0;j<Len;j++)
[i][j]=M[i][j]=R[i][j];
};
for(i=1;i<Len;i++)
{
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++)
{
[j][k]=[j][k]||N[j][k];
M[j][k]=N[j][k];
};
};
=Len;
return(t);
};
RelationRelation::C_t(intx)
{
inti,j,l;
Relationt;
for(i=0;i<Len;i++)
{
[i]=A[i];
for(j=0;j<Len;j++)
[i][j]=R[i][j];
};
for(i=0;i<Len;i++)
{
for(j=0;j<Len;j++)
if([j][i]==1)
{
for(l=0;l<Len;l++)
[j][l]=[j][l]||[i][l];
};
};
=Len;
return(t);
};
intRelation::Transitive()
{
Relationt;
t=C_t(1);
for(inti=0;i<Len;i++)
for(intj=0;j<Len;j++)
if(R[i][j]!=[i][j])return(0);
return(1);
};
intRelation::Equivalent_Relations()
{
return(this->Reflexive()&&Symmetric()&&Transitive());
};
voidRelation::PrintA()
{
inti;
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;
};
voidRelation::PrintR()
{
inti,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;
};
intmain(intargc,char*argv[])
{
intB[10]={10,11,12,13,14,15,16,17,18,19};
intC[6]={30,31,12,16};
intM1[Max][Max]={{0,1,0,1},{1,1,0,1},{0,0,1,0},{0,1,0,1}};
RelationR1,R2(C,M1,4);
RelationRb(B,M1,4);
();
();
cout<<(12)<<"isof12!"<<endl;
cout<<(15)<<"isof15!"<<endl;
cout<<(10,11)<<"isof10-11!"<<endl;
cout<<(9,11)<<"isof9-11!"<<endl;
cout<<(10,21)<<"isof10-21!"<<endl;
R1=(Rb);
();
cout<<"等价:"<<()<<endl;
cout<<"R2\n";
();
cout<<"R1\n";
();
cout<<"Reflexive:"<<()<<endl;
cout<<"Symmetric:"<<()<<endl;
cout<<"Transitive:"<<()<<endl;
R1=();
();cout<<"C_r\n";cout<<"Reflexive:"<<()<<endl;
R1=();
();cout<<"C_s\n";cout<<"Symmetric:"<<()<<endl;
R1=();
();cout<<"C_t\n";
R1=(1);cout<<"Transitive:"<<()<<endl;
();cout<<"C_r\n";
cout<<"等价:"<<()<<endl;
Rb=(R1);
cout<<"Cross\n";
cout<<"Rb\n";
();
cout<<"HelloWorld!\n";
return0;
}
根据程序运行结果可知程序运行正确。
五、运行结果说明
程序运行结果: