实验二离散报告.docx
《实验二离散报告.docx》由会员分享，可在线阅读，更多相关《实验二离散报告.docx（18页珍藏版）》请在冰点文库上搜索。
实验二离散报告
实验报告
课程名称
离散数学
实验名称
集合上二元关系性质判定的实现
指导单位
计算机科学与技术系
实验报告
实验名称
集合上二元关系性质判定的实现
指导教师
实验类型
验证
实验学时
4
实验时间
一、实验目的和要求
内容：
编程实现任意集合上二元关系的性质判定。
要求：
能正确判定任意二元关系的自反性、对称性、传递性、反自反性和反对称性。
二、实验环境（实验设备）
X86计算机
IDE:
CodeBlocks16.01
编译器：
GUNGCC
三、实验原理及内容
输入集合已经集合上面的序偶关系，输出关系满足的性质。
整体思路为将关系转换成矩阵，根据矩阵判断关系的性质。
若矩阵主对角线元素都是1，则满足自反性。
若矩阵主对角线元素都是0，则满足反自反性。
若矩阵所有元素关于主对角线对称，则满足对称性。
若矩阵中出现了关于主对角线对称的元素，则不满足反对称性，否则满足反对称性。
若矩阵的传递闭包等于矩阵自己，则矩阵满足传递性。
为了能够处理集合中含有字母的情况，程序将所有输入当成字符串来处理，然后将每一个字符与矩阵下标进行键值映射，这样，在序偶关系中，通过字符就可以很轻松的找到对应的下标，从而很轻松将序偶关系用矩阵表示。
程序定义的全局变量有：
chara[200];//保存输入的集合A字符串
charR[300];//保存输入的序偶R字符串
mapM;//保存字符与矩阵下标的映射（需#include
intX[200][200];//关系对应的矩阵
intlen;//集合A中含有的元素数量
inttmp[200][200];//求传递闭包过程中，用来保存矩阵的传递闭包
inttmp1[200][200];//求传递闭包过程中，用来保存矩阵的N次方。
第一步：
将集合中的元素与矩阵下标映射
由于集合A中可能含有字母，为了后面能够更加方便的将序偶关系转换成矩阵，第一步先将集合A中所以元素与矩阵下标进行映射，并统计集合A中元素个数。
引用STL库文件#include
代码为：
intinit（）
{
inti=0;
intl=strlen（a）;
intj=0;
for（i=0;i{
if（（a[i]>='a'&&a[i]<='z'）||（a[i]>='A'&&a[i]<='Z'）||（a[i]>='0'&&a[i]<='9'））
{
M[a[i]]=j++;
}
}
returnj;
}
算法复杂度分析：
对输入的字符串进行循环遍历，时间复杂度为O（n）。
第二步，将关系转换成矩阵
由于上一步中已经将集合中元素与矩阵下标进行了映射,那定位关系中第一元素和第二元素就可以直接用语句M[R[I]],将关系转换成矩阵也就容易多了，X[M[R[i+1]]][M[R[i+3]]]表示序偶对应的矩阵元素。
代码:
voidsolve（）
{
inti,j;
i=j=0;
intl=strlen（R）;
while（i{
if（R[i]=='<'）
{
if（find（a,a+strlen（a）,R[i+1]）==a+strlen（a）||find（a,a+strlen（a）,R[i+3]）==a+strlen（a））
{
printf（"输入有误，关系R中包含非法元素\n"）;
exit（0）;
}
X[M[R[i+1]]][M[R[i+3]]]=1;
i+=5;
}
else
{
i++;
}
}
}
算法复杂度分析：
对输入的序偶字符串进行遍历，时间复杂度是O（n）。
用矩阵进行运算，空间复杂度是O（n^2）。
第三步：
根据矩阵求满足的性质
（1）.自反性
如果矩阵中主对角线元素都是1，那么就满足自反性，否则不满足。
判断的时候只要找到第一个对角线元素不是1，就可以断定不满足自反性
代码：
boolJudgeZiFan（）
{
inti;
intflag=1;
for（i=0;i{
if（X[i][i]!
=1）
{
flag=0;
break;
}
}
if（flag）
{
returntrue;
}
else
{
returnfalse;
}
}
算法复杂度分析：
由于只要扫描对角线元素，所以时间复杂度是O（n）。
（2）反自反性
如果矩阵中主对角线元素都是0，那么就满足反自反性，否则，就不满足。
判断的时候扫描对角线元素，只要出现1就可断定不满足反自反性。
代码：
boolJudgeFanZiFan（）
{
for（inti=0;i{
if（X[i][i]>0）
{
returnfalse;
}
}
returntrue;
}
（3）对称性
如果对矩阵中，每一个X[i][j]，都有M[j][i]=1，那么就满足对称性，否则，不满足对称性。
若出现X[i][j]==1&&X[j][i]==0,就可以断定不满足对称性。
判断的时候只要扫描上三角矩阵即可。
boolJudgeDuiCheng（）
{
inti,j;
for（i=0;i{
for（j=0;j{
if（X[i][j]）
{
if（X[j][i]!
=1）
{
returnfalse;
}
}
}
}
returntrue;
}
算法复杂度分析：
扫描上三角矩阵，时间复杂度是O（n^2）。
（4）反对称性
如果矩阵中出现了关于主对角线对称的元素，那么就不满足反对称性，否则，满足反对称性。
判断的时候只要出现了X[i][j]==1&&X[j][i]==1就可以断定不满足反对称性。
判断的时候也只要扫描上三角矩阵。
代码：
boolJudgeFanDuiCheng（）
{
for（inti=0;i{
for（intj=i+1;j{
if（X[i][j]）
{
if（X[j][i]）
{
returnfalse;
}
}
}
}
returntrue;
}
算法复杂度分析：
扫描上三角矩阵，时间复杂度是O（n^2）
（5）.传递性
如果矩阵的传递闭包等于矩阵自己，那么就满足传递性，否则不满足。
求矩阵的传递闭包首先定义一个求矩阵的幂的运算，这个地方只要求矩阵和X矩阵相乘就可以。
还要定义一个特殊的求矩阵相加的运算，如果相加后矩阵元素大于1，就把元素置为1.最后只要比较一下传递闭包是不是与X相等就行了。
具体步骤是先定义两个全局数组tmp[][],和tmp1[][]，首先初始化为X矩阵。
tmp1用来累计和矩阵X的乘积，每次都和X相乘一次tmp1的幂就增加1，然后将tmp1与tmp矩阵相加（元素大于1就置成1），如此循环。
函数cal（）为tmp1与X相乘，函数combine为tmp1与tmp相加。
代码：
boolJudgeChuanDi（）
{
inti,j;
for（i=0;i{
for（j=0;j{
tmp[i][j]=X[i][j];
tmp1[i][j]=X[i][j];
}
}
for（i=2;i<=len;i++）
{
cal（）;
combine（）;
}
for（inti=0;i{
for（intj=0;j{
if（tmp[i][j]!
=X[i][j]）
{
returnfalse;
}
}
}
returntrue;
}
求矩阵的幂的运算：
首先0将X矩阵拷贝到tmp1[200][200]，然后每次都将tmp1与X相乘
代码：
voidcal（）
{
intxtmp[200][200];
intk,p;
for（inti=0;i{
for（intj=0;j{
intsum=0;
for（k=0;k{
sum+=tmp1[i][k]*X[k][j];
}
if（sum==0）
{
xtmp[i][j]=0;
}
else
{
xtmp[i][j]=1;
}
}
}
for（inti=0;i{
for（intj=0;j{
tmp1[i][j]=xtmp[i][j];
}
}
}
矩阵相加的运算：
如果相加后元素大于1，就置为1
代码：
voidcombine（）
{
for（inti=0;i{
for（intj=0;j{
if（tmp1[i][j]||tmp[i][j]）
{
tmp[i][j]=1;
}
}
}
}
算法复杂度分析：
主函数中，初始化tmp和tmp1时间复杂度是O（n^2）。
调用循环len-1次，然后每次cal函数进行矩阵相乘的复杂度是O（n^3），combine进行矩阵相加是O（n^2）。
这个运算步骤的时间复杂度是O（n^4），最后将tmp与X比较的时间复杂度是O（n^2）。
综上，时间复杂度是O（n^4）。
空间复杂度分析：
由于定义了两个临时数组tmp[]和tmp1[][]，每一个是O（n^2）,所以，空间复杂度是O（n^2）。
主函数进行数据的读入，输出，以及函数的调用
Main函数代码：
intmain（）
{
memset（tmp,0,sizeof（tmp））;
memset（tmp1,0,sizeof（tmp1））;
memset（a,0,sizeof（a））;
memset（R,0,sizeof（R））;
printf（"请输入集合A,以逗号隔开各元素,回车结束\n"）;
gets（a）;
len=init（）;
printf（"请输入关系R，格式,......回车结束\n"）;
gets（R）;
solve（）;
boolZiFan=JudgeZiFan（）;
boolDuiCheng=JudgeDuiCheng（）;
boolChuanDi=JudgeChuanDi（）;
boolFanZiFan=JudgeFanZiFan（）;
boolFanDuiCheng=JudgeFanDuiCheng（）;
printf（"性质为:
\n"）;
if（ZiFan）
{
printf（"自反性\n"）;
}
if（FanZiFan）
{
printf（"反自反性\n"）;
}
if（DuiCheng）
{
printf（"对称性\n"）;
}
if（FanDuiCheng）
{
printf（"反对称性\n"）;
}
if（ChuanDi）
{
printf（"传递性\n"）;
}
return0;
}
程序测试：
案例一：
课本112页例题5
输入集合为1,2,3,4
关系为<1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>
结果正确。
案例二：
输入集合为a,b,c
输入关系为,,
结果正确。
案例三：
课本131页例题1
输入集合：
1,2,3,4
输入关系：
<1,1>,<1,4>,<4,1>,<4,4>,<2,2>,<2,3>,<3,2>,<3,3>
结果正确
案例四：
输入集合a,b,c,d
输入关系：
,,,
结果正确
案例五：
程序容错性测试
结果正确
四、实验小结（包括问题和解决方法、心得体会、意见与建议等）
1.个人感觉这个程序的难点是传递性的判断，因为要求传递闭包，涉及到矩阵的乘法和加法，矩阵相乘在循环的时候，循环变量要弄清楚，容易出错。
2.这个程序只能处理小批量数据，最多将矩阵行列改成几千，处理包含几千元素的集合。
对于包含上万元素的集合的数据，如果还用二维数据，会爆栈，应该改为三元组表示的稀疏矩阵
3.程序的容错性。
如果不按照提示的规则输入，比如多几个空格标点，程序能恰当处理，如果关系中出现了集合以外的元素，程序能判断并提示。
但是关系一定要以的形式出现，否则程序将不能识别，导致结果出错。
五、指导教师评语
成绩
批阅人
日期
升级会员 