离散数学实验 C ++关系的运算(幂运算,闭包运算).doc

实验2 关系的运算（1） 关系的幂运算输入：集合A，二元关系集合R，幂次n输出：R的n次幂要求：尽量使运算的计算量最小（2） 关系闭包的计算输入：集合A，二元关系集合R输出：R的传递闭包t(R)要求：(a) 采用Warshall 算法（89页）(b) 编写代码判断输出t(R)为传递闭包程序代码:#include#include#includeusing namespace std;typedef vector vector Mat;class Relationvectors;/集合Mat A;/关系矩阵Mat B;Mat C;Mat E;Mat D100; /用来存储矩阵int n;public:void inputs();/将集合存入向量中void inputa();/将读入的关系转化为关系矩阵void print();/输出关系矩阵void mi();int Warshall(); ;/定义类int n,m;/全局变量，下文中使用void Relation:inputs()couta;)s.push_back(a);if(getchar()=n)break;/将集合存入向量中void Relation:inputa()/将读入的关系转化为关系矩阵cout输入关系;int i,j,e,r;for(i=0;is.size();i+)vector u;for(j=0;jhz;) if(h=0&z=0)break;for(i=0;is.size();i+)if(si=h) e=i;if(si=z) r=i;Aer=1;Ber=1;Eer=1;/Cer=1;/读入关系，将关系对应的矩阵中的位置元素变为1if(getchar()=n)break;void Relation:print()for(int i=0;is.size();i+)for(int j=0;js.size();j+)coutAij ;coutn; /读入幂次if(n=0) /0次幂for(int k=0;ks.size();+k)for(int j=0;js.size();+j)if(k=j)cout1 ; /对角线上元素为1elsecout0 ;coutendl;elsefor(i=1;in;+i)for(int h=0;hs.size();+h)for(int d=0;ds.size();+d)int m=0;for(int x=0;x1)for(a=0;as.size();+a)for(b=0;bs.size();+b)if(Cab!=D0ab) break;if(b!=s.size()break; /检验是否重复if(a=s.size()&b=s.size()break;/重复则跳出不再幂乘for(int k=0;ks.size();k+)for(int j=0;js.size();j+)Bkj=Ckj;Di-1=B;c=i;if(a=s.size()&b=s.size()int q;q=(n-i)%c; /找出结果位置if(q=0) q=c;for(int e=0;es.size();e+)for(int f=0;fs.size();f+)coutDq-1ef ; /输出coutendl;return;else/1次幂for(int h=0;hs.size();h+)for(int n=0;ns.size();n+)coutBhn ;coutendl;int Relation:Warshall()for(int i=0;is.size();+i)for(int j=0;js.size();+j)if(Aji=1)for(int k=0;ks.size();+k)Ajk=Ajk+Aik;if(Ajk!=0&Ajk!=1)Ajk=1;print();int a=1;int b=1;/for(int p=0;ps.size();+p)for(int l=0;ls.size();+l)if (Apl=0)for (int x=0;xs.size();+x)if(Apx*Axl=1)a=0;if(a=0)coutwrong!endl;elsefor(int p=0;ps.size();+p)for(int l=0;ls.size();+l)if(Apl=1&Epl=0)Apl=0; /再判断传递性for(int p=0;ps.size();+p)for(int l=0;ls.size();+l)if (Apl=0)for (int x=0;xs.size();+x)if(Apx*Axl=1)b=0;if(b=1)coutwrong!endl;return 0;Apl=1;coutright!endl;/return 1;void mai