2.cpp

离散数学中求解二元关系2到100间的所有素数传递闭包的问题.

# include <iostream>
# include <math.h>
using namespace std;
int main()
{int i,j,k,m,n,b=0;
int a[50];     /*定义一个一维数组，用于存放素数*/
int c[99][99]; /*定义一个二维数组，用于二元关系R的矩阵表示*/
for (i=2;i<=100;i++)
{ k=sqrt(i);
  for (j=2;j<=k;j++)
  if (i%j==0) break;
  if (j>k){a[b]=i;b=b+1;}
}      /*求2到100间的所有素数，并将所有素数赋值给一维数组，素数个数为b个*/
cout<<"素数有：";
for (i=0;i<b;i++)
{cout<<a[i]<<" ";}  /*输出所有的素数*/

for (i=2;i<=100;i++)
{for (j=2;j<=100;j++)
    for (k=0;k<b;k++)
		if(i%a[k]==0 && j%a[k]==0){c[i-2][j-2]=1;break;}
		else c[i-2][j-2]=0; }  /*求二元关系R的对应矩阵*/

 printf ("\n");
 printf ("二元关系R的矩阵表示\n");
for (i=0;i<=98;i++)
{ for (j=0;j<=98;j++)
   cout<<c[i][j]<<" ";
cout<<endl; }    /*二元关系R的矩阵表示*/

k=0 ; 
for (i=0;i<=98;i++)
{if(c[i][i]==1) k=k+1;}             /*计算对角线上元素为1的个数*/
printf ("对角线上元素为1的个数为%d\n",k); 
if (k==99) printf ("R是自反的\n");  /*对角线上元素全为1，则R是自反的*/
if (k!=99) printf ("R不是自反的\n");/*对角线上元素不全为1，则R不是自反的*/

k=0 ; 
for (i=0;i<=98;i++)
{for (j=0;j<=98;j++)
if(c[i][j]!=c[j][i]) k=k+1;}       /*检验所有元素是否对称*/
printf ("非对称元素的个数为%d\n",k);
if (k==0) printf ("R是对称的\n");  /*所有元素都对称，则R是对称的*/
if (k!=0) printf ("R不是对称的\n");/*有元素不对称，则R不是对称的*/

for (j=0;j<=98;j++)
{for (i=0;i<=98;i++)
    if (c[i][j]==1)
	{m=i;n=j;
	for (k=0;k<=98;k++)          /*利用Warshall算法*/
	{c[m][k]=c[n][k]+c[m][k];
	if (c[m][k]==2) c[m][k]=1;}  /*求出R的传递闭包的关系矩阵*/
    }
} 

printf ("二元关系R的传递闭包的关系矩阵表示\n");
for (i=0;i<=98;i++)
{ for (j=0;j<=98;j++)
   cout<<c[i][j]<<" ";
cout<<endl; }    /*二元关系R的传递闭包的关系矩阵表示*/

printf("R的传递闭包为{\n");
for (i=0;i<=98;i++)
{ for (j=0;j<=98;j++)
  if (c[i][j]==1)                       /*根据R的传递闭包的关系矩阵*/
   cout<<"("<<i+2<<","<<j+2<<")"<<",";  /*输出R的传递闭包的集合表示*/
   cout<<endl;
 } 
printf("}\n"); 
 
return 0;      /*如程序正常结束，向操作系统返回一个零值*/
}