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

关系的幂运算输入：集合A,二元关系集合R,幂次n输出：R的n次幂关系闭包的计算输入：集合A,二元关系集合R输出：R的传递闭包t(R)采用Warshall 算法(89页)编写代码判断输出t(R)为传递闭包

实验2 关系的运算

（1） 关系的幂运算

输入：集合A，二元关系集合R，幂次n 输出：R的n次幂

要求：尽量使运算的计算量最小

（2） 关系闭包的计算

输入：集合A，二元关系集合R

输出：R的传递闭包t(R)

要求：

(a) 采用Warshall 算法（89页）

(b) 编写代码判断输出t(R)为传递闭包 程序代码:

#include<iostream>

#include<sstream>

#include<vector>

using namespace std;

typedef vector< vector <int> > Mat;

class Relation{

vector<int>s;//集合

Mat A;//关系矩阵

Mat B;

Mat C;

关系的幂运算输入：集合A,二元关系集合R,幂次n输出：R的n次幂关系闭包的计算输入：集合A,二元关系集合R输出：R的传递闭包t(R)采用Warshall 算法(89页)编写代码判断输出t(R)为传递闭包

Mat E;

Mat D[100]; //用来存储矩阵

int n;

public:

void inputs();//将集合存入向量中

void inputa();//将读入的关系转化为关系矩阵 void print();//输出关系矩阵

void mi();

int Warshall();

};//定义类

int n,m;//全局变量，下文中使用

void Relation::inputs(){

cout<<"输入集合";

for(int a;cin>>a;){

s.push_back(a);

if(getchar()=='\n')

break;}

}//将集合存入向量中

void Relation::inputa(){//将读入的关系转化为关系矩阵

关系的幂运算输入：集合A,二元关系集合R,幂次n输出：R的n次幂关系闭包的计算输入：集合A,二元关系集合R输出：R的传递闭包t(R)采用Warshall 算法(89页)编写代码判断输出t(R)为传递闭包

cout<<"输入关系";

int i,j,e,r;

for(i=0;i<s.size();i++){

vector<int> u;

for(j=0;j<s.size();j++){

int ia=0; u.push_back(ia);}

A.push_back(u);

B.push_back(u);

C.push_back(u);

E.push_back(u);

}//创建二维向量，初始化，是每个元素为0 for(int h,z;cin>>h>>z;){

if(h==0&&z==0)

A[e][r]=1;B[e][r]=1; E[e][r]=1;//C[e][r]=1;//读入关系，将关系对应的矩阵中的位 break; for(i=0;i<s.size();i++){ } if(s[i]==h) e=i; if(s[i]==z) r=i;

关系的幂运算输入：集合A,二元关系集合R,幂次n输出：R的n次幂关系闭包的计算输入：集合A,二元关系集合R输出：R的传递闭包t(R)采用Warshall 算法(89页)编写代码判断输出t(R)为传递闭包

置元素变为1

if(getchar()=='\n')

break;

}

}

void Relation::print(){

for(int i=0;i<s.size();i++){

for(int j=0;j<s.size();j++) cout<<A[i][j]<<" ";

cout<<endl;

}

}//输出关系矩阵

void Relation::mi(){

int a,b,i,c;

cin>>n; //读入幂次 if(n==0){ //0次幂

for(int k=0;k<s.size();++k){ for(int j=0;j<s.size();++j){ if(k==j) cout<<"1 "; //对角线上元素为1

关系的幂运算输入：集合A,二元关系集合R,幂次n输出：R的n次幂关系闭包的计算输入：集合A,二元关系集合R输出：R的传递闭包t(R)采用Warshall 算法(89页)编写代码判断输出t(R)为传递闭包

else

cout<<"0 ";

}

cout<<endl;

}

}

else{

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

for(int h=0;h<s.size();++h){ for(int d=0;d<s.size();++d){ int m=0;

for(int x=0;x<s.size();++x){ m=m+B[h][x]*A[x][d]; 行第d列的元素对应相乘的和 }

C[h][d]=m;

}

}

if(i>1){

for(a=0;a<s.size();++a){

for(b=0;b<s.size();++b){ if(C[a][b]!=D[0][a][b]) //第h

关系的幂运算输入：集合A,二元关系集合R,幂次n输出：R的n次幂关系闭包的计算输入：集合A,二元关系集合R输出：R的传递闭包t(R)采用Warshall 算法(89页)编写代码判断输出t(R)为传递闭包

} } } break; if(b!=s.size())break; }//检验是否重复 if(a==s.size()&&b==s.size()){ } for(int k=0;k<s.size();k++){ } for(int j=0;j<s.size();j++){ } D[i-1]=B; c=i; B[k][j]=C[k][j]; break;//重复则跳出不再幂乘 if(a==s.size()&&b==s.size()){ int q; q=(n-i)%c; //找出结果位置 if(q==0) q=c; for(int e=0;e<s.size();e++){ for(int f=0;f<s.size();f++){

关系的幂运算输入：集合A,二元关系集合R,幂次n输出：R的n次幂关系闭包的计算输入：集合A,二元关系集合R输出：R的传递闭包t(R)采用Warshall 算法(89页)编写代码判断输出t(R)为传递闭包

}

}

} } cout<<D[q-1][e][f]<<" "; //输出 cout<<endl; return; }else{//1次幂 } for(int h=0;h<s.size();h++){ } for(int n=0;n<s.size();n++){ } cout<<endl; cout<<B[h][n]<<" ";

int Relation::Warshall(){ for(int i=0;i<s.size();++i){

for(int j=0;j<s.size();++j){ if(A[j][i]==1){ for(int k=0;k<s.size();++k){

关系的幂运算输入：集合A,二元关系集合R,幂次n输出：R的n次幂关系闭包的计算输入：集合A,二元关系集合R输出：R的传递闭包t(R)采用Warshall 算法(89页)编写代码判断输出t(R)为传递闭包

} } } } if(A[j][k]!=0&&A[j][k]!=1) A[j][k]=1;

print();

int a=1;int b=1;//

for(int p=0;p<s.size();++p){

}

if(a==0){cout<<"wrong!"<<endl;} else{ for(int l=0;l<s.size();++l){ } if (A[p][l]==0){ } for (int x=0;x<s.size();++x){ } if(A[p][x]*A[x][l]==1) a=0;

关系的幂运算输入：集合A,二元关系集合R,幂次n输出：R的n次幂关系闭包的计算输入：集合A,二元关系集合R输出：R的传递闭包t(R)采用Warshall 算法(89页)编写代码判断输出t(R)为传递闭包

for(int l=0;l<s.size();++l){ } if(A[p][l]==1&&E[p][l]==0){ A[p][l]=0; //再判断传递性 } for(int p=0;p<s.size();++p){ } if(b==1){ } A[p][l]=1; cout<<"wrong!"<<endl; return 0; for(int l=0;l<s.size();++l){ } if (A[p][ …… 此处隐藏：2172字，全部文档内容请下载后查看。喜欢就下载吧 ……