传递闭包c语言
① C++编写warshall算法的传递闭包,1.利用求传递闭包的Warshall算法，给定关系R，编写求R的可传递闭包的c语言
最佳答案
#include <stdio.h>
#include <stdlib.h>
#define N 20
#define M 20
main()
{
int i,j,k,m,n;
int r1[M],r2[M],a[N],mr[N][N]={0};
FILE * fp;
printf("程序自动调用c:/stone2.txt文件内相应数据\n");
fp=fopen("c:\\stone2.txt","r");
fscanf(fp,"%d",&n); /*读取集合元素个数*/
for(i=0;i<n;i++) /*读取集合元素*/
fscanf(fp,"%d",&a[i]);
fscanf(fp,"%d",&m); /*读取关系个数*/
for(k=0;k<m;k++)
fscanf(fp,"%d,%d",&r1[k],&r2[k]); /*读取关系*/
fclose(fp);
printf("自反闭包r(R):\n{");
for(i=0;i<n;i++) printf("<%d,%d>,",a[i],a[i]); /*输出自反闭包*/
for(k=0;k<m;k++)
{
if(r1[k]!=r2[k]) printf("<%d,%d>,",r1[k],r2[k]);
else continue;
}
printf("\b}\n");
printf("对称闭包s(R):\n{"); /*输出对称闭包*/
for(k=0;k<m;k++)
{
if(r1[k]!=r2[k]) printf("<%d,%d>,<%d,%d>,",r1[k],r2[k],r2[k],r1[k]);
else printf("<%d,%d>,",r1[k],r2[k]);
}
printf("\b}\n");
k=0;
for(i=0;i<n,k<m;i++)
{
if(r1[k]!=a[i]) continue;
else
{
for(j=0;j<n,k<m;j++) /*关系转换成矩阵*/
{
if(r2[k]!=a[j]) continue;
else
{
mr[i][j]=1;
k++; i=0;j=0;
break;
}
}
}
}
printf("关系所对应的关系矩阵:\n");
for(i=0;i<n;i++)
{ /*打印关系矩阵*/
for(j=0;j<n;j++)
printf("%5d",mr[i][j]);
printf("\n");
}
for(k=0;k<n;k++)
for(i=0;i<n;i++) /*warshall*/
for(j=0;j<n;j++)
mr[i][j]+=mr[i][j]+mr[i][k]*mr[k][j];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{ /*把mr[]非0项赋值为1*/
if(!mr[i][j]) continue;
else mr[i][j]=1;
}
printf("传递闭包对应关系矩阵:\n");
for(i=0;i<n;i++)
{ /*输出传递闭包对应的关系矩阵*/
for(j=0;j<n;j++)
printf("%5d",mr[i][j]);
printf("\n");
}
system("PAUSE");
}
自己写的,三个闭包都有,包括传递闭包,看注释就知道了,还是用文件读写,方便数据输入
② 用C++如何编出关系的传递闭包，其中一段的程序我已给出，各位高手帮帮忙啊谢谢了，大神帮忙啊
#include<iostream> #include<memory> using namespace std; int main() { int r[101][101]; int a=0,b=0,c=0,n=0; cout<<"请输入关系矩阵的阶数"<<endl; cin>>n; for (a=1;a<=n;a++) { cout<<"请输入矩阵的第"<<a<<"行,中间一空格隔开."<<endl; for (b=1;b<=n;b++) cin>>r[a][b]; } cout<<endl<<"原矩阵为"<<endl; for (a=1;a<=n;a++) { for (b=1;b<=n;b++) cout<<r[a][b]<<" "; cout<<endl; } //以上输入矩阵完成 bool _finish=0; for(;;) { _finish=0; for(a=1;a<=n;a++) for(b=1;b<=n;b++) for(c=1;c<=n;c++) if ((r[a][b]==1)&&(r[b][c]==1)&&r[a][c]==0) { r[a][c]=1; _finish=1; } if (_finish ==0) break; } cout<<endl<<"t(r)的关系矩阵为"<<endl; for(a=1;a<=n;a++) { for(b=1;b<=n;b++) cout<<r[a][b]<<" "; cout<<endl; } return 0; }
③ 用C语言求一个关系矩阵的传递闭包
首先,矩阵的并运算不是很对,执行结果好象是第二条赋值语句,没有实现并的概念;
然后,设计到返回数组首地址的函数中,尝试一下把所有需要返回的数组定义为全局变量或者主函数中的参数变量,因为子函数执行完毕后,所申请的内存会被释放,地址便无效;
再次,函数调用,传递数组的首地址才对,而不是数组某一个元素;
最后,子函数定义中,参数变量是二维数组,要写上数组的维数,例如void tran(int a[6][6],int b[6][6]),不然会因为维数不确定而报错.
④ 求计算机求解关系R的传递闭包 C语言算法
传递闭包,最简单的技术是采用 【弗洛伊德算法】
Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。
Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
Floyd-Warshall算法的原理是动态规划。
设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。
1.若最短路径经过点k，则Di,j,k = Di,k,k − 1 + Dk,j,k − 1；
2.若最短路径不经过点k，则Di,j,k = Di,j,k − 1。
因此，Di,j,k = min(Di,k,k − 1 + Dk,j,k − 1,Di,j,k − 1)。
在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。
代码请见：
⑤ 用c语言编 一个关系的传递闭包
说明：以关系矩阵形式计算传递闭包： #include"stdio.h" #define N 1000 main() { int i,j,a[N][N],b[N][N],c[N][N],s=0,k,e[N][N],m,n; printf("请输入你的关系矩阵的阶n(n<=1000):\n"); scanf("%d",&n); printf("请输入你的关系矩阵:\n"); for(i=0;i<n;i++) for(j=0;j<n;j++) { scanf("%d",&a[i][j]); e[i][j]=a[i][j]; b[i][j]=a[i][j]; } for(m=1;m<n;m++) { for(i=0;i<n;i++) for(j=0;j<n;j++) { for(s=0,k=0;k<n;k++) s+=b[i][k]*a[k][j]; c[i][j]=s; if(e[i][j]==0&&c[i][j]!=0) e[i][j]=c[i][j]; } for(i=0;i<n;i++) for(j=0;j<n;j++) b[i][j]=c[i][j]; } for(i=0;i<n;i++) for(j=0;j<n;j++) if(e[i][j]!=0) printf("<%d,%d>,",i+1,j+1); printf("\n"); }
⑥ C语言编写的"求一个关系矩阵的传递闭包"
我自己写的，绝对可以
#include"stdio.h"
#define N 1000
main()
{
int i,j,a[N][N],b[N][N],c[N][N],s=0,k,e[N][N],m,n;
printf("请输入你的关系矩阵的阶n(n<=1000):\n");
scanf("%d",&n);
printf("请输入你的关系矩阵:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
e[i][j]=a[i][j];
b[i][j]=a[i][j];
}
for(m=1;m<n;m++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
for(s=0,k=0;k<n;k++)
s+=b[i][k]*a[k][j];
c[i][j]=s;
if(e[i][j]==0&&c[i][j]!=0)
e[i][j]=c[i][j];
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
b[i][j]=c[i][j];
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(e[i][j]!=0)
printf("<%d,%d>,",i+1,j+1);
printf("\n");
}
⑦ 离散数学Warshall算法求传递闭包C语言实现
#include <stdio.h>#include <stdlib.h>#define N 20#define M 20main(){ int i,j,k,m,n; int r1[M],r2[M],a[N],mr[N][N]={0}; FILE * fp; printf（＂程序自动调用c:/stone2.txt文件内相应数据\n＂）; fp=fopen(＂c:\\stone2.txt＂,＂r＂); fscanf(fp,＂%d＂,&n)； /*读取集合元素个数*/ for(i=0;i<n;i++) /*读取集合元素*/ fscanf(fp,＂%d＂,&a[i]); fscanf(fp,＂%d＂,&m)； /*读取关系个数*/ for(k=0;k<m;k++) fscanf(fp,＂%d,%d＂,&r1[k],&r2[k])； /*读取关系*/ fclose(fp); printf（＂自反闭包r(R):\n{＂); for(i=0;i<n;i++) printf(＂<%d,%d>,＂,a[i],a[i])； /*输出自反闭包*/ for(k=0;k<m;k++) { if(r1[k]!=r2[k]) printf(＂<%d,%d>,＂,r1[k],r2[k]); else continue; } printf(＂\b}\n＂); printf（＂对称闭包s(R):\n{＂）； /*输出对称闭包*/ for(k=0;k<m;k++) { if(r1[k]!=r2[k]) printf(＂<%d,%d>,<%d,%d>,＂,r1[k],r2[k],r2[k],r1[k]); else printf(＂<%d,%d>,＂,r1[k],r2[k]); } printf(＂\b}\n＂); k=0; for(i=0;i<n,k<m;i++) { if(r1[k]!=a[i]) continue; else { for(j=0;j<n,k<m;j++) /*关系转换成矩阵*/ { if(r2[k]!=a[j]) continue; else { mr[i][j]=1; k++; i=0;j=0; break; } } } } printf（＂关系所对应的关系矩阵：\n＂）; for(i=0;i<n;i++) { /*打印关系矩阵*/ for(j=0;j<n;j++) printf(＂%5d＂,mr[i][j]); printf(＂\n＂); } for(k=0;k<n;k++) for(i=0;i<n;i++) /*warshall*/ for(j=0;j<n;j++) mr[i][j]+=mr[i][j]+mr[i][k]*mr[k][j]; for(i=0;i<n;i++) for(j=0;j<n;j++) { /*把mr[]非0项赋值为1*/ if(!mr[i][j]) continue; else mr[i][j]=1; } printf（＂传递闭包对应关系矩阵：\n＂）; for(i=0;i<n;i++) { /*输出传递闭包对应的关系矩阵*/ for(j=0;j<n;j++) printf(＂%5d＂,mr[i][j]); printf(＂\n＂); } system(＂PAUSE＂)；}自己写的，三个闭包都有，包括传递闭包，看注释就知道了，还是用文件读写，方便数据输入
⑧ (离散数学)输入一个关系矩阵,用C语言编程求出它的自反闭包,对称闭包和传递闭包
我用面向对象写的 自己改一下
#include<iostream.h>
template<class T>
void Warshall( T *a , int m , int n )
{
int i = 0,j = 0;
for( i = 0 ; i < n ; i++ )
{
for( j = 0 ; j < m ; j++ )
{
if( a[j][i] == 1 )
{
int k = 0;
for( int x = 0 ; x < n ; x++ )
{
a[j][k] = a[j][k] || a[i][k];
k++;
}
}
}
}
for( i = 0 ; i < m ; i++ )
{
for( j = 0 ; j < n ; j++ )
{
cout << a[i][j] << '\t';
}
cout<<endl;
}
}
void main()
{
int ai[4][4] = { {0,1,0,0} , {1,0,1,0} , {0,0,0,1} , {0,0,0,0} };
Warshall(ai,4,4);
}
⑨ 用c语言编写传递闭包时 A[j][k]=A[j][k]||A[i][k];为什么这么写
C语言不支持内嵌函数，没有闭包。
⑩ 编程：求一个关系的传递闭包（C语言）
利用关系的矩阵表示，可以通过Warshall算法计算有限集合上的二元关系的传递闭包。