中南大学离散数学实验报告2Word文档格式.docx
- 文档编号:8243607
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:18
- 大小:280.36KB
中南大学离散数学实验报告2Word文档格式.docx
《中南大学离散数学实验报告2Word文档格式.docx》由会员分享,可在线阅读,更多相关《中南大学离散数学实验报告2Word文档格式.docx(18页珍藏版)》请在冰点文库上搜索。
S(n,k)=S(n−1,k−1)+kS(n−1,k)
集合上所有等价类的个数即为k从1到n,所有S(n,k)之和。
这个问题的算法比较简单,仅需两步就可完成,首先根据上式,定义一个递归函数S(n,k),然后对k从1到n,求取sum=∑S(n,k),sum的值就是给定n元集合上的等价关系数目,最后将其输出即可。
实验A的流程图如下所示:
实验C求解商集,输入集合和等价关系,求相应的商集
商集即等价类构成的集合,要求商集,首先需要判断输入的关系是否为等价关系,否则没有商集。
判断输入的关系是否为等价关系的算法如下:
(1)将输入的关系转换为关系矩阵,这里定义了一个函数translate(),转换的方法为:
依次查找输入的关系中的二元组的两个元素在集合中的位置,例如<
a,b>
,若a在集合A中的位置为i,b在集合A中的位置为j,就令存放关系矩阵的二维数组M[i][j]=1,这样就将输入的关系R转换为关系矩阵的形式。
(2)定义三个函数zifan(),duichen()和chuandi(),分别的作用是判断输入的关系是否自反、对称和传递。
由等价关系的定义知,若三个函数的返回值均为1,则输入的关系是等价关系。
判断的方法是:
若关系矩阵M中所有的M[i][i]=1,则是自反关系;
若M中所有的M[i][j]=M[j][i],则是对称关系;
若M[i][j]=1并且M[j][k]=1,那么一定有M[i][k]=1,则是传递关系。
判断了所输入的关系为等价关系后就可以求其商集了,由于商集即等价类构成的集合,所以要求其等价类。
确定集合A={a1,a2,a3,…,an}关于R的等价类的算法如下:
(1)令A中每一个元素自成一个子集,A1={a1},A2={a2},…,An={an}
(2)对R中每个二元组<
x,y>
,判定x和y所属子集。
假设x属于Ai,y属于Aj,若Ai<
>
Aj,则将Ai并入Aj,并置Ai为空;
或将Aj并入Ai,并置Aj为空。
一般将元素少的集合合并到元素多的集合。
(3)A1,A2,…,An中所有非空子集构成的集合即为所求商集。
集合的并运算采用并查集(union-findsets)的方法。
并查集是一种树型的数据结构,多棵树构成一个森林,每棵树构成一个集合,树中的每个节点就是该集合的元素,找一个代表元素作为该树(集合)的祖先。
并查集支持以下三种操作:
(1)Make_Set(x)把每一个元素初始化为一个集合
初始化后每一个元素的父亲节点是它本身,每一个元素的祖先节点也是它本身。
(2)Find_Set(x)查找一个元素所在的集合
查找一个元素所在的集合,只要找到这个元素所在集合的祖先即可。
判断两个元素是否属于同一集合,只要看他们所在集合的祖先是否相同即可。
(3)Union(x,y)合并x,y所在的两个集合
合并两个不相交集合操作很简单:
首先设置一个数组Father[x],表示x的"
父亲"
的编号。
那么,合并两个不相交集合的方法就是,找到其中一个集合的祖先,将另外一个集合的祖先指向它。
实验C的流程图如下所示:
五、实验数据及结果分析:
以下是实验过程中的实验数据截图:
实验A
以上三图显示了集合元素数为3、4、5的等价关系数目分别为5、15、52,根据原递归式计算也是此值。
说明程序正确。
上图显示的是当输入错误的情况,当输入错误时提示错误,再次输入后正确计算出其结果。
由以上图示数据可以看出程序完整地实现了实验A的要求。
实验C
(1)运行程序开始提示输入集合A:
(2)输入集合并回车,频幕上显示要计算的集合A,并提示下一步输入集合上的等价关系R:
(3)输入集合A上的一个等价关系R并回车,显示关系R和它的关系矩阵,以及计算出的商集:
(4)再次运行程序,此次输入的关系不是等价关系,则会出现提示:
您输入的不是等价关系,没有商集,请重新输入!
(5)重新输入一个等价关系,输出其正确的计算结果:
由以上实验数据可以看出,程序完整地实现了题目要求。
当然程序编写及调试过程中还遇到很多错误,都一一解决了,但没有截取数据。
六、源程序清单:
#include<
stdio.h>
intS(intx,inty)/*定义递归函数*/
{
intt;
if(y==1||y==x)
{t=1;
}
else{t=S(x-1,y-1)+y*S(x-1,y);
returnt;
main()
intk,n,sum=0;
printf("
请输入有限集合的元素个数:
\n"
);
scanf("
%d"
&
n);
getchar();
if(n<
=0||n>
100)
printf("
输入错误,请重新输入!
scanf("
for(k=1;
k<
=n;
k++)
sum=sum+S(n,k);
/*调用递归函数*/
给定%d元有限集上等价关系的数目为:
\n%d"
n,sum);
#include"
stdio.h"
ctype.h"
string.h"
stdlib.h"
math.h"
#defineMAX20
#defineSTUstructstu
intM[MAX][MAX];
/*存放关系矩阵*/
charA[MAX];
/*存放有限集合*/
charB[MAX];
/*存放等价关系*/
inti,j,p,q,n,l,k,t,y;
STU
intm;
chartree[20];
};
STUequ[20];
voidmake_set(STUequ[],charA[],intn)/*使集合A中的元素自成一个子集*/
inti;
for(i=0;
i<
n;
i++)
{
equ[i].m=1;
equ[i].tree[0]=A[i];
equ[i].tree[1]='
\0'
;
}
find_set(intj)/*查找二元组中元素所属集合*/
j;
if(M[j][i])
{
break;
}
if(i==j)
return-1;
}
else
returni;
voidunionit(STUequ[],intj,inti)/*合并二元组中元素所属集合*/
equ[j].tree[equ[j].m]=equ[i].tree[0];
equ[i].tree[0]='
equ[i].m=0;
equ[j].m=equ[j].m+1;
equ[j].tree[equ[j].m]='
voiddisp(STUequ[],intn)/*输出商集*/
A/R={"
if(equ[i].m!
=0)
printf("
{%s}"
equ[i].tree);
}"
voidcaculate(STUequ[],charA[],intn)/*计算商集*/
intp;
make_set(equ,A,n);
p=find_set(i);
if(p!
=-1){
unionit(equ,p,i);
disp(equ,n);
/*调用输出商集函数*/
voidgetguanxi()/*获得关系R并输出显示*/
gets(B);
l=strlen(B);
您输入的关系为:
R={"
for(j=0;
j<
l;
j=j+2)
printf("
<
"
%c,"
B[j]);
%c"
B[j+1]);
"
}\n"
voidtranslate()/*转换为关系矩阵的函数*/
intp,q,i=0,j;
while(B[i]!
='
)
{
if((B[i]>
A'
)&
&
(B[i]<
Z'
||B[i]>
a'
z'
))
for(j=0;
j++)
if(B[i]==A[j])
{
p=j;
break;
i++;
while(B[i]!
for(j=0;
{
q=j;
M[p][q]=1;
}
if(j==n)
i++;
else
}
else
i++;
voiddisplay()/*输出关系矩阵函数*/
inti,j;
%2d"
M[i][j]);
intzifan()/*判断输入的关系是否自反函数*/
intcount=0;
if(M[i][i]==1)
count++;
if(count==n)
return1;
return0;
intduichen()/*判断输入的关系是否对称函数*/
for(j=i+1;
if(M[i][j]!
=M[j][i])
return0;
intchuandi()/*判断输入的关系是否传递函数*/
intflag=1;
if(flag==0)break;
if(flag==0)break;
for(k=0;
if((M[i][j]==1&
M[j][k]==1&
M[i][k]!
=1))
{
flag=0;
break;
}
returnflag;
voidclearM()/*第一次输入不是等价关系,重新输入前矩阵清零*/
M[j][i]=0;
voidmain()
请输入一个有限集合(a-z/A-Z):
gets(A);
n=strlen(A);
您输入的集合为:
A={"
i++)/*输出集合*/
%2c"
A[i]);
请输入这个集合上的一个等价关系R:
getguanxi();
/*调用获得关系R并输出显示函数*/
translate();
/*调用转换为关系矩阵函数*/
R的关系矩阵为:
display();
/*调用输出关系矩阵函数*/
t=zifan()&
duichen()&
chuandi();
/*判断关系是否等价*/
while(t!
=1)
clearM();
/*矩阵清零*/
t=zifan()&
您所输入的集合和等价关系相应的商集为:
caculate(equ,A,n);
/*调用计算商集函数*/
getchar();
七、其他收获和体会:
。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中南 大学 离散数学 实验 报告