0807刘超09090830009实验1ABC.docx
- 文档编号:5878866
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:39
- 大小:395.41KB
0807刘超09090830009实验1ABC.docx
《0807刘超09090830009实验1ABC.docx》由会员分享,可在线阅读,更多相关《0807刘超09090830009实验1ABC.docx(39页珍藏版)》请在冰点文库上搜索。
0807刘超09090830009实验1ABC
“离散数学”实验报告
(实验2)
专业自动化
班级0807班
学号0909083009
姓名刘超
日期:
2010年12月18日
目录
目录2
1.实验内容2
2.实验目的3
3.实验环境3
4.实验原理和实现过程(算法描述)4
4.1实验A和B:
4
4.1.1流程图4
4.1.2算法分析6
4.3实验C8
4.3.1流程图8
4.3.2C题C语言算法的分析9
5.实验数据及结果分析14
5.1实验一14
5.1.1运行界面14
5.1.2循环输入界面14
5.2实验二15
5.2.1输出容错界面15
5.2.2全析取运行界面15
5.2.3全合取运行界面16
5.2.4全条件运行界面16
5.2.5双条件运行界面17
5.2.6混合运算运行界面17
5.3实验三18
5.3.1主范式输出主界面(主析取和主合取是在一起)18
6.其他收获和体会18
7.源程序清单19
7.1A、B题程序附录19
7.2BC题程序附录22
1.实验内容
1.求有限集上给定关系的自反、对称和传递闭包。
(有两种求解方法,只做一种为A,两种都做为B)
2.求有限集上等价关系的数目。
(有两种求解方法,只做一种为A,两种都做为B)
3.求解商集,输入集合和等价关系,求相应的商集。
(C)
2.实验目的
1、掌握离散数学中涉及的相关概念。
2、培养学生的逻辑思维能力和算法设计的思想。
3、熟练掌握C/C++语言程序设计的基本方法和各种调试手段。
4、掌握关系的概念与性质,基本的关系运算,关系的各种闭包的求法。
5、理解等价类和商的概念,掌握等价类和商的求解方法。
3.实验环境
C或C++语言编程环境实现
4.实验原理和实现过程(算法描述)
4.1实验A和B:
4.1.1流程图
4.1.2算法分析
1、根据提示先输入有限元素的个数,根据元素个数输入相应的元素,存放于数组a[i]中,并把相应的个数值放入n中,输入这些元素的关系R,将关系R中的元素存放于数组b[]中,长度为放入自变量vv中。
2、取出数字并进行储存,先判断它是否在‘0’-‘9’之间,假如在这中间的话就那个相应的数放入C[]这个数组中
for(i=0;i {if(b[i]>'0'&&b[i]<='9') c[j++]=(int)(b[i]-'0');} 3、判断数组c[]中的数字是输入的第几个元素,并将该数字在数组a[]中的对应的位置下标存放于数组s[]中,例如C[0]=2,而a[1]=2,则s[0]=1; for(i=0;i {for(ss=0;ss if(c[i]==a[ss]){ s[k++]=ss;break;}} 4、确定行标和列标即判断出相应该关系在关系矩阵中的位置,的由m=s[i];x=s[i+1];d[m][x]=1;确定在关系矩阵M中的位置,并将该位置的元素置1,这样求出关系矩阵 for(i=0;i {m=s[i];x=s[i+1];d[m][x]=1;} 5、将关系矩阵复制保存,分别放入五个数组e,g,sum,q,z中,以便后面进行自反、传递、对称进相互不干扰。 6、求解关系R的自反闭包: 根据R的自反闭包为R关系并上集合a上的相等关系即r(R)=RvI,所有我们先把行标和列标相同的元素置1,也就是把它对角线上的值全要,代码如下: for(i=0;i for(i=0;i =0)printf("<%d,%d>",a[i],a[j]); 7、求解关系R的对称闭包: 根据关系R的对称闭包为关系R并上关系R的逆即s(R)=RU⌒R,将关系R对应的矩阵M加上关系R_对应的矩阵M’即为对称闭包,用for(i=0;i for(i=0;i for(j=0;j if(g[i][j]==1) printf("<%d,%d>",a[i],a[j]); 7.求解关系R的传递闭包方法一: 传递的思路就是把第一个的列标和第二个的行标相同的数置1,即t(R)= 第一种求传递的思想就是我们找到了一个中间的K,当t[i][j]中存在一个K,使t[i][k]=1&&t[k][j]=1,那么t[i][j]就是1,然后我们把这个处理的结果矩阵和原来的矩阵同与就可以求出第一传递矩阵,而输出的方法也和自反对称一样,当矩阵里哪个元素不为0时,我们就把它对应的a[i]和a[j]输出,具体代码如下: for(i=0;i for(j=0;j t[i][j]=0; for(i=0;i for(j=0;j { {for(k=0;k t[i][j]=t[i][j]+y[i][k]*c[k][j]; } } for(i=0;i for(j=0;j { sum[i][j]=sum[i][j]+t[i][j];/*sum为所求的第一种传递闭包*/ } 8、第二种传递闭包求法是: 寻找一个一个后面的K,也就是我们已经确立了d[j][i]=1,只要在存在一个k,使d[i][k]=1,那么d[j][k]也为1,这里我们用的是Warshall算法这个算法的精髓如下: 设R的关系矩阵为M (1)令矩阵A=M (2)置i=1 (3)对所有的j,若A[j,i]=1,则 对于k=1,2,…,n,令A[j,k]=A[j,k]+A[i,k] (4)i=i+l. (5)若i≤n,则转到(3),否则结束。 核心代码如下。 for(i=0;i for(j=0;j { if(d[j][i]==1) { for(k=0;k d[j][k]=d[j][k]+d[i][k]; } } 4.3实验C 4.3.1流程图 4.3.2C题C语言算法的分析 C题要求商集即等价类构成的集合,要求商集,首先需要判断输入的关系是否为等价关系,否则没有商集。 该程序实现如下: (1)定义以为数组set[30]来存储输入的集合A,定义数组set[50]来存储原始输入等价关系,定义rset1[30]找出集合中的元素,定义rset2[50]找出等价关系中的元素,将等价关系矩阵化并定义两位数组set2[20][20]来存储等价关系矩阵,定义二维数组数组mr[20][20]来存储关系的传递闭包矩阵。 (2)(i)输入集合A,提示用户输入小写字母作为元素,可以以任何方式输入集合,然后把输入的小写字母存放到rset1[i]中,再把字母的个数存放到j中核心程序如下: for(i=0;i if((set[i]<='z')&&(set[i]>='a')){ rset1[j]=set[i]; j++;}} (ii)输入等价关系R,并把其中的小写字母存入数组rset2中实现程序如下: for(i=0;i if((equ[i]<='z')&&(equ[i]>='a')){ rset2[k]=equ[i]; k++;}} (3)(i)当关系R输入后,为了方便判断关系R是否为等价关系,则先形成R的关系矩阵。 形成关系R矩阵算法为: 当输入的一个二元组为时,在数组A(用set[30]存储)中查找若: set1[i]=a,set1[j]=b,则R的关系矩阵set2[20][20]中的元素set2[i][j]=1,按此方法直到将关系R中的二元组查找完,然后再把对应的R显示出业,核心程序实现如下: for(a=0;a for(b=0;b for(c=0;c if((rset2[c]==rset1[a])&&(rset2[c+1]==rset1[b])){ set2[a][b]=1; c++; break;} else{ set2[a][b]=0; c++;}}}} (4)通过形成的R的关系矩阵来平判断R是不是等价关系,由于等价关系充要条件是: 自反的、对称的和传递的,则可以依次判断set2[20][20]是否满足自反、对称、传递,若同时满足自反、对称、传递,则R是等价关系,否则R不是等价关系,提示输入的关系不是等价关系,让用户重新输入,直到用户输入的是等价关系为止。 判断关系R是否为自反、对称和传递的程序实现如下: (i)判断是否自反: for(i=0;i if(set2[i][i]! =1){ printf("该输入关系R不是等价关系,请重新输入! \nR="); for(p=0;p rset2[p]='0';} for(b=0;b for(c=0;c set2[b][c]='0';} gotostar; break;}} (ii)判断是否对称 flag=0; for(i=0;i for(a=0;a { if(set2[a][i]! =set2[i][a]) { flag=1; printf("该输入关系R不是等价关系,请重新输入! \nR="); for(p=0;p { rset2[p]='0'; } for(b=0;b { for(c=0;c set2[b][c]='0'; } gotostar; break;}} if(flag==1)break; } (iii)判断关系矩阵是否满足传递: flag=0; for(i=0;i { for(a=0;a { if(mr[i][a]! =set2[i][a]) { flag=1; printf("该输入关系R不是等价关系,请重新输入! \nR="); for(p=0;p { rset2[p]='0'; } for(b=0;b { for(c=0;c set2[b][c]='0'; } gotostar; break; }}}} (5)(I)最后求商集,算法如下: 确定集合A={a1,a2,a3,…,an}关于R的等价类的算法如下: (i)令A中每一个元素自成一个子集,如A1={a1},A2={a2},…,An={an} (ii)对R中每个二元组 假设x属于 Ai,y属于Aj,若Ai<>Aj,则将Ai并入Aj,并置Ai为空;或将Aj并入Ai,并置Aj为空。 一般将元素少的集合合并到元素多的集合。 (iii)A1,A2,…,An中所有非空子集构成的集合即为所求商集。 (II)程序实现如下: (i)求商集: c=0;//求出矩阵中每行值为1的元素,放入数组cun[20][20] for(a=0;a { for(b=0;b { if(set2[a][b]==1) { lian[c]=rset1[b]; cun[a][m]=rset1[b]; m++; c++; } } m=0; } for(a=0;a//数组中不是元素的部分,全部赋值为零 { for(b=0;b { if((cun[a][b]>='a')&&(cun[a][b]<='z')) continue; else cun[a][b]='0'; } } for(a=0;a { for(b=a+1;b { if(cun[a][0]==cun[b][0]) { for(m=0;m { cun[b][m]='0'; } } } } for(i=0;i { for(a=0;a { for(c=0;c { cun[j][c]='0'; } if(cun[a][0]! ='0')continue; else for(b=0;b { temp=cun[a+1][b]; cun[a+1][b]=cun[a][b]; cun[a][b]=temp; } } } (ii)输出商集: printf("\n商集A÷R="); flag=0; printf("{"); for(i=0;i { if(flag==0)printf("{"); for(a=0;a { if(cun[i][0]=='0') { flag=1; break; } if(cun[i][a]=='0') { flag0=1; break; } else { flag=0; if(a==0) printf("%c",cun[i][a]); else { printf(",%c",cun[i][a]); } } } if(flag==1)break; if((flag0==1)&&(cun[i+1][0]=='0')) { printf("}"); flag=1; flag0=0; } else { printf("},"); flag=0; flag0=0; } } printf("}\n"); for(a=0;a }} 5.实验数据及结果分析 5.1实验一 5.1.1运行界面 输出结果如上所示,每个闭包之间用“――”隔开,上面的算法中已经说的很清楚,所以这里就不在一一分析了 5.2实验二 5.2.1输出容错界面 按界面上的要求来输入你想要的命题公式,并且公式的字母只能是大写,否则给出的是错误提示,同时要求你再次输入。 5.2.2全析取运行界面 5.2.3全合取运行界面 5.2.4全条件运行界面 5.2.5双条件运行界面 5.2.6混合运算运行界面 当按要求输入正确的时候,系统会给出真值表,并且是按顺序给出,界面如上图所示。 5.3实验三 5.3.1主范式输出主界面(主析取和主合取是在一起) 析取范式表示的是最大项之各,合取范式表达的最小项之积,从界面上我们可以明显看出。 6.其他收获和体会 此次实验主要是针对离散数学中的连接词与或非、真值表、主范式,同时也是考查C语言或C++语言的应用能力。 经过经过此次实验我对离散数学中的连结词,真值表,主范式等概念有了更进一步的认识,同时加深了我对C语言的理解。 所以为了完成此次实验,我在网上找了好些资料,再把C语言书初略看了一下,同时我还特意去图书馆找了几本关于这方面的书籍,尽管如此,但是还是遇到了不少问题。 虽然这个过程比较艰难,但后面总算还是和预期的一样,做出了两题。 虽然不是很理想,但我还是很开心,因为在这个过程中我学到了很多知识,而且最后我完成了这个实验,这让我充满了成就感,下面说一下我的总体收获: 1.加深对课堂讲授内容的理解 通过本次实验,对离散数学合取,析取,条件,蕴含有了更深一步的理解,最主要的对数据结构有了初步的认识。 2.加深了对C语言的理解和认识 一个c语言程序从编辑、编译、连接到运行,都要在一定的外部操作环境下才能进行。 所谓"环境"就是所用的计算机系统硬件、软件条件,只有学会使用这些环境,才能进行程序开发工作。 通过上机实验,熟练地掌握c语言开发环境,为以后真正编写计算机程序解决实际问题打下基础。 同时,在今后遇c语言程序设计心得到其它开发环境时就会触类旁通,很快掌握新系统的使用。 3.实际解决问题的能力提高 完成程序的编写,决不意味着万事大吉。 你认为万无一失的程序,实际上机运行时可能不断出现c语言心得麻烦。 比如说一开始那个最外面的循环总是只能输入一次,再次输入P时总是提示错误,后面经过多次尝试,用一个fflush(stdio),清除缓存,就可以用了 通过这次为数不多的三天上机实验,我对离散数学一些概念有了初步的了解,同时我对C语言有进一步的加强,这对我们将来到社会工作将会有莫大的帮助。 同时它让我知道,只要你努力,任何东西都不会太难。 7.源程序清单 7.1A、B题程序附录 #include #include voidf(inte[20][20],intd[20][20]); voidf1(); #defineprintprintf("-----------------------\n"); intt[20][20],sum[20][20],d[20][20]={0},q[20][20],z[20][20],n; intmain() { inta[20],c[10],s[10],e[20][20],g[20][20]; inti,k=0,j=0,m,x,ss,vv,zzuan; charb[30]; printf("\n\t\t\t实验二第一题\n"); printf("\t\t\t刘超\n"); printf("\t\t\t自动化0807班\n"); printf("\t\t1.求有限集上给定关系的自反、对称\n"); printf("\t和传递闭包。 (有两种求解方法,只做一种为A,两种都做为B)\n\n"); printf("输入有限集元素的个数: "); scanf("%d",&n); printf("输入有限集元素(请以空格表示数据分隔): "); for(i=0;i scanf("%d",&a[i]); printf("输入关系R如{<1,2><2,3><1,3>}: "); scanf("%s",b); vv=strlen(b); for(i=0;i { if(b[i]>'0'&&b[i]<='9') c[j++]=(int)(b[i]-'0'); } for(i=0;i { for(ss=0;ss if(c[i]==a[ss]) { s[k++]=ss; break; } } zzuan=j; for(i=0;i { m=s[i]; x=s[i+1]; d[m][x]=1; } for(i=0;i for(j=0;j {/*分别把d[i][j]存放到五个数组,以便后来每次处理时相互之间没有影响*/ e[i][j]=d[i][j];/*用作输出自反闭包*/ g[i][j]=d[i][j];/*用作输出对称闭包*/ sum[i][j]=d[i][j];/*用作输出第一种传递闭包*/ q[i][j]=d[i][j]; z[i][j]=d[i][j]; } /*----------------------------------------------------------*/ print; for(i=0;i e[i][i]=1; printf("自反闭包为: \n"); printf("{"); for(i=0;i for(j=0;j if(e[i][j]! =0) printf("<%d,%d>",a[i],a[j]); printf("}\n");/*输出自反闭包*/ /*------------------------------------------------------------*/ print; printf("对称闭包为: \n"); printf("{"); for(i=0;i for(j=0;j if(g[i][j]==1) g[j][i]=1; for(i=0;i for(j=0;j if(g[i][j]==1) printf("<%d,%d>",a[i],a[j]); printf("}\n");/*输出对称闭包*/ /*--------------------------------------------------------------*/ print; for(i=1;i f(z,q); printf("第一种传递闭包为: \n"); printf("{"); for(i=0;i for(j=0;j if(sum[i][j]! =0) printf("<%d,%d>",a[i],a[j]); printf("}\n");/*输出第一种传递闭包*/ /*----------------------------------------------------------------*/ print; f1(); printf("第二种传递闭包为: \n"); printf("{");
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 0807 09090830009 实验 ABC