离散数学实验报告

1、“离散数学”实验报告目录一、实验目的3二、实验内容3三、实验环境3四、实验原理和实现过程（算法描述）31、实验原理2、实验过程五、实验数据及结果分析13六、源程序清单24源代码24七、其他收获及体会45一、实验目的实验一：熟悉掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。实验二：掌握关系的概念与性质，基本的关系运算，关系的各种闭包的求法。理解等价类的概念，掌握等价类的求解方法。实验三：理解图论的基本概念，图的矩阵表示，图的连通性，图的遍历，以及求图的连通支方法。二、实验内容 实验一：1. 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、条件和双条件的真值。（A

2、）2. 求任意一个命题公式的真值表（B，并根据真值表求主范式（C） 实验二：1.求有限集上给定关系的自反、对称和传递闭包。（有两种求解方法，只做一种为A，两种都做为B）2. 求有限集上等价关系的数目。（有两种求解方法，只做一种为A，两种都做为B）3. 求解商集，输入集合和等价关系，求相应的商集。（C） 实验三：以偶对的形式输入一个无向简单图的边，建立该图的邻接矩阵，判断图是否连通（A）。并计算任意两个结点间的距离（B）。对不连通的图输出其各个连通支（C）。三、实验环境C或C语言编程环境实现。四、实验原理和实现过程（算法描述）实验一：1.实验原理（1）合取：二元命题联结词。将两个命题P、Q联结起

3、来，构成一个新的命题PQ, 读作P、Q的合取, 也可读作P与Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = T, Q = T时方可PQ =T, 而P、Q只要有一为F则PQ = F。这样看来，PQ可用来表示日常用语P与Q, 或P并且Q。（2）析取：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题PQ, 读作P、Q的析取, 也可读作P或Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = F, Q = F时方可PQ =F, 而P、Q只要有一为T则PQ = T。这样看来，PQ可用来表示日常用语P或者Q。（3）条件：二元命题联结词

4、。将两个命题P、Q联结起来，构成一个新的命题PQ, 读作P条件Q, 也可读作如果P，那么Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = T, Q = F时方可PQ =F, 其余均为T。（4）双条件：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题PQ, 读作P双条件于Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为当两个命题变项P = T, Q =T时方可PQ =T, 其余均为F。（5）真值表:表征逻辑事件输入和输出之间全部可能状态的表格。列出命题公式真假值的表。通常以1表示真，0 表示假。命题公式的取值由组成命题公式的命题变元的取值和命题联

5、结词决定，命题联结词的真值表给出了真假值的算法。 真值表是在逻辑中使用的一类数学表，用来确定一个表达式是否为真或有效。（6）主范式：主析取范式：在含有n个命题变元的简单合取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单合取式为小项。由若干个不同的小项组成的析取式称为主析取范式;与A等价的主析取范式称为A的主析取范式。任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的。主合取范式：在含有n个命题变元的简单析取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单析取式为大项。由若干个不同的大项组成的合取式称为主

6、合取范式;与A等价的主合取范式称为A的主合取范式。任意含n个命题变元的非永真命题公式A都存在与其等价的主合取范式,并且是惟一的。2.实验过程（1）A题部分，首先是对各个输入量的处理，要确定输入的为0或1，否则则为出错，接下来就是运算处理，在C语言中本身支持的有与或非这三种，可以用!,&&,|来表示，而在这个实验中，不是与或非的可以通过转化而变为与或非的形式，具体流程图如下：开始P为1或0P为1或0运算是否继续结束YYYNNN输入P值输入Q值输出结果求合取、析取、条件和双条件的真值流程图（2）B，C题部分，首先是输入一个合理的式子，然后从式子中查找出变量的个数，开辟一个二进制函数

7、，用来生成真值表，然后用函数运算，输出结果，并根据结果归类给范式，最后输出范式。函数部分，主要是3个函数，一个为真值表递加函数，通过二进制的加法原理递进产生，一个为分级运算函数，这个函数是通过判断括号，选出最内级括号的内容执行运算函数，这样一级一级向外运算，最后得出最终结果，剩下一个为主运算函数，按照运算符号的优先级按顺序进行运算，如先将所有非运算运算完，再执行与运算。如此运算。开始输入式子计算变量个数生成真值表输出真值表变量赋值运算式子输出结果归类主范式输出主范式结束循环是否结束YN主函数开始检查括号是否是最内级括号运算内容是否是最后结果返回结果结束开始结束YYNN非运算与运算或运算蕴含运算

8、等值运算返回结果主运算函数分级运算函数实验二：A题型 求有限集上等价关系的数目。集合上的等价关系与该集合的划分之间存在一一对应关系。一个等价关系对应一个划分，一个划分也对应一个等价关系。我们把n个元素的集合划分成k块的方法数叫第二类Stirling数，表示为S(n,k)。给定S(n,n) = S(n,1) = 1，有递归关系：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

9、元集合上的等价关系数目，最后将其输出即可。A题型的流程图如下所示：开始输入要计算的集合的元素数nSum=0k=1（）k<n？S（n，k）=1Sum=Sum+S（n，k）k+S(n,k)=S(n-1,k-1)+k*S(n-1,k)S（n，k）=1Sum=Sum+S（n，k）输出Sum结束YNC题型 求解商集，输入集合和等价关系，求相应的商集商集即等价类构成的集合，要求商集，首先需要判断输入的关系是否为等价关系，否则没有商集。判断输入的关系是否为等价关系的算法如下：(1)将输入的关系转换为关系矩阵，这里定义了一个函数translate()，转换的方法为：依次查找输入的关系中的二元组的两个元素

10、在集合中的位置，例如<a，b>，若a在集合A中的位置为i，b在集合A中的位置为j，就令存放关系矩阵的二维数组Mij=1,这样就将输入的关系R转换为关系矩阵的形式。(2)定义三个函数zifan(),duichen()和chuandi()，分别的作用是判断输入的关系是否自反、对称和传递。由等价关系的定义知，若三个函数的返回值均为1，则输入的关系是等价关系。判断的方法是：若关系矩阵M中所有的Mii=1，则是自反关系；若M中所有的Mij=Mji，则是对称关系；若Mij=1并且Mjk=1，那么一定有Mik=1，则是传递关系。判断了所输入的关系为等价关系后就可以求其商集了，由于商集即等价类构成

11、的集合，所以要求其等价类。确定集合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-find sets)的方法。并查集是一种树型的数据结构，多棵树构成一个森林，每棵树构成一个集合，树中的每个节点就

12、是该集合的元素，找一个代表元素作为该树(集合)的祖先。并查集支持以下三种操作：(1) Make_Set(x) 把每一个元素初始化为一个集合初始化后每一个元素的父亲节点是它本身，每一个元素的祖先节点也是它本身。(2) Find_Set(x) 查找一个元素所在的集合查找一个元素所在的集合，只要找到这个元素所在集合的祖先即可。判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。(3) Union(x,y) 合并x,y所在的两个集合合并两个不相交集合操作很简单：首先设置一个数组Fatherx，表示x的"父亲"的编号。那么，合并两个不相交集合的方法就是，找到其中一个集

13、合的祖先，将另外一个集合的祖先指向它。C题型的流程图如下所示：开始输入集合A输入A上的关系R转换为关系矩阵M是否为等价关系？求解商集A/R输出商集结束是否实验三：1、实验原理（1）建立图的邻接矩阵，判断图是否连通根据图的矩阵表示法建立邻接矩阵A，并利用矩阵的乘法和加法求出可达矩阵，从而判断图的连通性。连通图的定义：在一个无向图 G 中，若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径)，则称vi和vj是连通的。如果 G 是有向图，那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。判断连通图的实现：在图中，从任意点出发在剩余的点中，找到所

14、有相邻点循环，直到没有点可以加入为止，如果有剩余的点就是不连通的，否则就是连通的。或者也可用WallShell算法，由图的邻接矩阵判断图是否连通。（2）计算任意两个结点间的距离图中两点i，j间的距离通过检验Al中使得aij为1的最小的l值求出。路径P中所含边的条数称为路径P的长度。在图G<V,E>中，从结点Vi到Vj最短路径的长度叫从Vi到Vj的距离，记为d<Vi，Vj>。设图的邻接矩阵是A，则 所对应的aij的值表示，点Vi到点Vj距离为n的路径有aij条。若aij(1)，aij(2)，aij(n-1)，中至少有一个不为0，则可断定Vi与Vj可达，使aij(l)0的最

15、小的l即为d(Vi，Vj)。问题求解原理为：（1） 先构造初始邻接矩阵A=Vij，Vij为顶点Vi到顶点Vj的权。如果Vi和Vj之间不存在弧段或者是负向回路或者是i=j，则令Vij其值为。（2） 再构造初始中间顶点矩阵。（3） 然后开始迭代计算（迭代的次数等于顶点的个数1）（4）最后查找Vi到Vj的最短路径。计算节点Vi与Vj之间的距离的方法为：利用邻接矩阵相互间相乘后得到的矩阵来判断节点间的距离。如果c2sij=0，则这两个节点的距离为无穷大。如果c2s-2ij=0,c2s-1ij=1时，则这两点间的距离为s。（3）对不连通的图输出其各个连通支图的连通支的求法则可采用图的遍历算法，图的遍历有

16、深度优先和广度优先两种方法，其中深度优先算法又分为递归和非递归两种。在无向图中，如果任何两点可达，则称图G是连通的，如果G的子图G是连通的，没有包含G的更大的子图G是连通的，则称G是G的连通支。当有判断出关系不是连通的之后，将需要求出分支模块实现方法如下：先定义一个二维数组用来存放相应的分块，先选定一个点，并将它放在数组中，然后判断，如果后面的和他是联通的便将它也放在同一个数组中，否则将其存入其他的数组中，后面以此类推，在输出相应的数组，便可判断出连通分支。2、实验过程（1） 程序整体思路本程序完成了实验所要求的全部功能，其基本思路是“运用模块化的思想，将实现“求连通支”、“输入结点关系”、“

17、输出邻接矩阵”、“显示两结点间的距离”、“求可达矩阵”和“图的遍历”的子函数分开编写，然后将它们以子函数的形式添加到主函数main的代码后面，在要使用相应的子函数时，进行子函数调用就可以实现相应的功能了。”本程序的一大特色就是开发者灵活使用了C语言中的数组概念来进行开发，用数组来模拟矩阵的运算，通过相应的算法实现了全部的功能。（2）具体算法流程在main()系统界面显示；用dowhile循环语句和switch语句实现功能1,2,3的选择，并调用相关的子程序；用start、goto start实现控制流的转移；liantongzhi()求连通支，此子函数通过一个for循环控制遍历每个结点，并调用

18、函数DFS（）求每个结点的连通支；DFS（int a）通过实参与形参，将结点数据代入函数；定义顺序栈变量；通过for循环初始化；为a置已访问标志，已经访问了的元素为1；定义顺序栈的第一个元素；通过while循环实现结点遍历，栈不为空时执行循环；栈顶元素赋值；通过for循环寻找v的下个未访问的邻接点；通过if条件句，若x,i是边和节点i未被访问过，处理结点的访问，并进行访问标志，进栈等操作；通过if条件句，若v已访问到的出点，则将其退栈；shuru()输入结点关系；通过for循环先将矩阵所有元素赋值0；再通过另一for循环，根据输入结点的关系，将矩阵中相应的元素赋值，有关系则为1；linjiej

19、uzhen()输出邻接矩阵；通过for循环，依次按格式输出邻接矩阵的元素；julijuzhen()根据A的n次方矩阵及其中元素，判断并显示两结点间的距离；调用子函数linjiejuzhen()，以确定并显示距离为1的两结点；通过for循环显示距离为1的结点对；再通过一系列的for循环，计算A的n次方矩阵并显示结果，根据其中的元素，判断并显示结点间的距离；详细算法请见附录相关部分的注释；kedajuzhen()求可达矩阵；通过一系列for循环，根据公式，计算可达矩阵；通过for循环，将矩阵中不为0的一切值赋为1以生成可达矩阵并显示；通过for循环和if条件句的组合，根据可达矩阵的元素特点，判断图

20、的连通性，若可达矩阵矩阵中有0，则跳出循环，显示不可连接；根据判断结果显示内容，不可连通或可连通；五、实验数据及结果分析实验一：正确输入结果错误控制非运算与运算或运算蕴含运算等值运算带括号运算实验二：等价关系计算错误控制计算关系r和它的关系矩阵，以及计算出的商集输入不是等价关系实验三：输入界面输入无向图的边建立图的邻接矩阵计算节点间的距离判断图的连通性输出图的连通支六、源程序清单实验一：exp1a.cpp#include <iostream>using namespace std;int main()int p=-1,q=-1;int a3; start:cout<<&

21、quot;请输入p的值（0或1），输入空格，再输入q的值（0或1）"<<endl;cin>>p;cin>>q;if(p=0|p=1)&&(q=0|q=1) a0=p&&q;a1=p|q;a2=(!p)|q; a3=(!p)|q)&&(!q)|p); else cout<<"输入有误，请重新输入"<<endl;goto start; cout<<"nn合取：p/q="<<a0<<endl; cout<

22、;<"nn析取：p/q="<<a1<<endl; cout<<"nn条件：p->q="<<a2<<endl; cout<<"nn双条件：p<->q="<<a3<<endl;test1bc.c#include "stdio.h"#include "stdlib.h"#include "string.h"#include "conio.h"#

23、include "math.h"#define N 50void panduan(int bN,int f);/赋值函数int tkh (char szN, char ccuN, int icuN, int h0);/分级运算函数int fkh (char szN, char ccuN, int icuN, int h0);/主运算函数main() int i1,i2,d=1,icuN,kh=0,jg,j=0,h0;/icuN用于存放变量值,kh括号计数,jg存放结果 int bj=0,hqN,h=0,x=0,xqN;/hqN存放合取结果xqN存放析取结果 char szN

24、,ccuN,sz0N,s;/szN存放式子,ccuN存放变量,sz0N也是用于存放式子hq0=-1;xq0=-1;printf("* *n"); printf("* (运算真值表，主范式，支持括号) *n");printf("* *n"); printf("* 用!表示非 *n"); printf("* 用&表示与 *n"); printf("* 用|表示或 *n"); printf("* 用表示蕴含 *n"); printf("* 用表

25、示等值 *n");printf("* *n");printf("*nn"); printf("请输入一个合法的命题公式:n");/输入式子 gets(sz);/读取式子 strcpy(sz0,sz);/复制式子for(i1=0;i1<strlen(sz);i1+) if(szi1=')' | szi1='(')/存储括号数量kh+;if(szi1>='a' && szi1<='z' | szi1>='A'

26、&& szi1<='Z') for(i2=0;i2<j;i2+) /判断并储存变量。 if(ccui2=szi1)/去除重复变量 d=0;if(d=1) ccuj=szi1;j+; d=1; printf("n该式子中的变量个数为：%dn",j);/输出变量个数 h0=j; printf("n输出真值表如下：n n"); /输出真值表表头for(i1=0;i1<h0;i1+)printf(" %c ",ccui1);printf(" ");puts(sz);prin

27、tf("n"); for(i1=0;i1<j;i1+) /先将所有的变量赋值为零。icui1=0; for(i2=0;i2<j;i2+)/输出真值表前项printf(" %d ",icui2); jg=tkh(sz,ccu,icu,h0); /用函数求结果 if(jg=0)/结果为0，合取加1hqh+=bj; else /否则，析取加1xqx+=bj; printf(" %dn",jg);/输出运算结果strcpy(sz,sz0);for(i1=0;i1<(int)pow(2,j)-1;i1+) +bj; pandu

28、an(icu,j-1); /赋值变量jg=tkh(sz,ccu,icu,h0); if(jg=0)/结果为0，合取加1hqh+=bj; else /否则，析取加1xqx+=bj; strcpy(sz,sz0); /恢复被修改的数组。for(i2=0;i2<j;i2+) printf(" %d ",icui2);/输出真值表前项 printf(" %dn",jg);/输出运算结果 if(hq0=-1)/不存在合取范式时 printf("n该命题公式不存在主合取范式。n");else printf("n该命题公式的主合取范

29、式：nt");for(i1=0;i1<h;i1+) if (i1>0)/判断并添加符号printf("/"); printf("M(%d)",hqi1); /输出主合取范式 if(xq0=-1)/不存在析取范式时 printf("n该命题公式不存在主析取范式。n");else printf("nn该命题公式的主析取范式：nt");for(i1=0;i1<x;i1+) if (i1>0)/判断并添加符号printf("/"); printf("m(%d)

30、",xqi1);/输出主析取范式 printf("n"); printf("n欢迎下次再次使用！n ");/结束getch();void panduan(int bN,int f) / 二进制赋值。int i; i=f; if(bf=0)/加1bf=1; else/进位 bf=0;panduan(b,-i); int tkh (char szN,char ccuN,int icuN,int h0)/分级运算函数int i,j,h,s,kh=0,wzN,a; char xs1N,ckhN; /xs1用来保存括号内的字符 ckh用来保存括号。 s=

31、strlen(sz);for(i=0;i<s;i+) if(szi='(' | szi=')')/判断括号 wzkh=i;/存储括号位置 ckhkh=szi;/存储括号类型kh+; if(kh=0) return fkh(sz,ccu,icu,h0);/如果无括号，直接运行else for(i=0;i<kh;i+) if(ckhi=')')/找到第一个）break; for(j=wzi-1+1,h=0;j<wzi;j+,h+) /存储最内级括号中的内容xs1h=szj;xs1h='0' a=fkh(xs1,ccu

32、,icu,h0);/运行最内级括号的式子，得到结果 if(a=1)/判断并存储结果szwzi-1=1;elseszwzi-1=-2; for(j=wzi-1+1;j<s+wzi-1-wzi;j+)/将括号后内容前移szj=szj+wzi-wzi-1;szj='0' return tkh(sz,ccu,icu,h0);/循环执行 int fkh(char szN,char ccuN,int icuN,int h0)/主运算函数 int i,h=0,j=0,j1=0,j2=0,j3=0,j4=0,j5=0,i1,i2,p1=-1,p2=-1,s;char dtN; s=str

33、len(sz);if(s=1) if(sz0=-2)/判断是否是最后一项return 0;else return 1; /1 就是sz0的值、else for(i=0;i<s-j;i+) /先处理非if(szi='!')for(i1=0;i1<h0;i1+) if(szi+1=ccui1)/将变量赋值并给P1 p1=icui1; if(szi+1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(p1=-1)/如果是数字，直接给P1 p1=szi+1;dtj+2=!p1;/非运算szi=j+2;j+; p1=0;for(i1=i+1;i1<s-j;

34、i1+) szi1=szi1+1;/将后续式子前移一项 p1=-1; j1=j; for(i=0;i<s-j1-2*j2;i+) / 处理与if(szi='&')for(i1=0;i1<h0;i1+) if(szi-1=ccui1)/将变量赋值并给P1 p1=icui1; if(szi+1=ccui1)/将变量赋值并给P2 p2=icui1; for(i2=2;i2<j+2;i2+) if(szi-1=i2) /如果为前计算结果，将结果赋值并给P1 p1=dti2; if(szi+1=i2) /如果为前计算结果，将结果赋值并给P2 p2=dti2; i

35、f(szi-1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(szi+1=-2)/如果是前运算结果的0，则P2等于0 p2=0; if(p1=-1) /如果是数字，直接给P1 p1=(int)(szi-1); if(p2=-1)/如果是数字，直接给P2 p2=(int)(szi+1); dtj+2=p1 && p2;/与运算szi-1=j+2;j+;j2+; p1=-1; p2=-1; for(i1=i;i1<s-j1-2*j2;i1+)/将后续式子前移两项szi1=szi1+2; i=i-1; for(i=0;i<s-j1-2*j2-2*j3;i+

36、) / 处理或。if(szi='|') for(i1=0;i1<h0;i1+) if(szi-1=ccui1)/将变量赋值并给P1 p1=icui1; if(szi+1=ccui1)/将变量赋值并给P2 p2=icui1;for(i2=2;i2<j+2;i2+) if(szi-1=i2) /如果为前计算结果，将结果赋值并给P1 p1=dti2; if(szi+1=i2)/如果为前计算结果，将结果赋值并给P2 p2=dti2; if(szi-1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(szi+1=-2)/如果是前运算结果的0，则P2等于0 p2=

37、0; if(p1=-1)/如果是数字，直接给P1 p1=szi-1; if(p2=-1)/如果是数字，直接给P2 p2=szi+1; dtj+2=p1 | p2;/或运算szi-1=j+2;j+;j3+; p1=-1; p2=-1; for(i1=i;i1<s-j1-2*j2-2*j3;i1+)/将后续式子前移两项szi1=szi1+2;i-; for(i=0;i<s-j1-2*j2-2*j3-2*j4;i+) / 处理蕴含。if(szi='') for(i1=0;i1<h0;i1+) if(szi-1=ccui1)/将变量赋值并给P1 p1=icui1; i

38、f(szi+1=ccui1)/将变量赋值并给P2 p2=icui1;for(i2=2;i2<j+2;i2+) if(szi-1=i2) /如果为前计算结果，将结果赋值并给P1 p1=dti2; if(szi+1=i2) /如果为前计算结果，将结果赋值并给P2 p2=dti2;if(szi-1=-2)/如果是前运算结果的0，则P1等于0 p1=0;if(szi+1=-2)/如果是前运算结果的0，则P2等于0 p2=0;if(p1=-1)/如果是数字，直接给P1 p1=szi-1;if(p2=-1)/如果是数字，直接给P2 p2=szi+1;dtj+2=!p1 | p2;/蕴含运算szi-1

39、=j+2;j+;j4+;p1=-1;p2=-1;for(i1=i;i1<s-j1-2*j2-2*j3-2*j4;i1+)/将后续式子前移两项szi1=szi1+2;i-; for(i=0;i<s-j1-2*j2-2*j3-2*j4-2*j5;i+) / 处理等值。if(szi='') for(i1=0;i1<h0;i1+) if(szi-1=ccui1)/将变量赋值并给P1 p1=icui1; if(szi+1=ccui1)/将变量赋值并给P2 p2=icui1;for(i2=2;i2<j+2;i2+) if(szi-1=i2) /如果为前计算结果，将结

40、果赋值并给P1 p1=dti2; if(szi+1=i2) /如果为前计算结果，将结果赋值并给P2 p2=dti2; if(szi-1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(szi+1=-2)/如果是前运算结果的0，则P2等于0 p2=0; if(p1=-1)/如果是数字，直接给P1 p1=szi-1; if(p2=-1)/如果是数字，直接给P2 p2=szi+1;dtj+2=(!p1 | p2)&&(!p2 | p1);/等值运算szi-1=j+2;j+;j5+; p1=-1; p2=-1; for(i1=i;i1<s-j1-2*j2-2*j3-

41、2*j4-2*j5;i1+)/将后续式子前移两项szi1=szi1+2;i-; return dtj+1;/返回结果 实验二：exp2a.cpp#include <iostream>using namespace std;int S(int x,int y) /*定义递归函数*/int t;if(y=1|y=x)t=1;else t=S(x-1,y-1)+y*S(x-1,y);return t;main()int k,n,sum=0;cout<<"请输入有限集合的元素个数："<<endl;cin>>n;if(n<=0|n

42、>100)cout<<"输入错误，请重新输入！"<<endl;cin>>n;for(k=1;k<=n;k+)sum=sum+S(n,k); /*调用递归函数*/cout<<"给定"<<n<<"元有限集上等价关系的数目为:"<<sum<<endl;test2c.c# include "stdio.h"# include "ctype.h"# include "string.h&qu

43、ot;# include "stdlib.h"# include "math.h"#define MAX 20#define STU struct stuint MMAXMAX; /*存放关系矩阵*/char AMAX; /*存放有限集合*/char BMAX; /*存放等价关系*/int i,j,p,q,n,l,k,t,y;STUint m;char tree20;STU equ20;void make_set(STU equ,char A,int n) /*使集合A中的元素自成一个子集*/int i;for(i=0;i<n;i+) equi.m

44、=1;equi.tree0=Ai;equi.tree1='0' find_set(int j) /*查找二元组中元素所属集合*/int i;for(i=0;i<j;i+) if(Mji) break; if(i=j) return -1; elsereturn i;void unionit(STU equ,int j,int i) /*合并二元组中元素所属集合*/equj.treeequj.m = equi.tree0;equi.tree0= '0'equi.m = 0;equj.m = equj.m+1;equj.treeequj.m = '0&

45、#39;void disp(STU equ,int n) /*输出商集*/int i;printf("A/R= ");for(i=0;i<n;i+)if(equi.m!=0)printf("%s ",equi.tree);printf(" ");void caculate(STU equ,char A,int n) /*计算商集*/int p; make_set(equ,A,n);for(i=0;i<n;i+) p = find_set(i);if(p!=-1)unionit(equ,p,i); disp(equ,n);

46、/*调用输出商集函数*/void getguanxi() /*获得关系R并输出显示*/gets(B);l=strlen(B);printf("您输入的关系为：n");printf("R= ");for(j=0;j<l;j=j+2)printf("<");printf("%c,",Bj);printf("%c",Bj+1);printf("> "); printf(" n");void translate() /*转换为关系矩阵的函数*/i

47、nt p,q,i=0,j;while(Bi!='0')if(Bi>='A')&&(Bi<='Z'|Bi>='a')&&(Bi<='z')for(j=0;j<n;j+) if (Bi=Aj) p=j;break; i+;while(Bi!='0') for(j=0;j<n;j+)if (Bi=Aj) q=j; Mpq=1;break;if(j=n)i+;else i+;break; elsei+;void display() /*输出

48、关系矩阵函数*/int i,j;for(i=0;i<n;i+)for(j=0;j<n;j+)printf("%2d",Mij);printf("n");int zifan() /*判断输入的关系是否自反函数*/int count = 0;for(i=0;i<n;i+)if(Mii=1)count+;if(count = n)return 1;elsereturn 0;int duichen() /*判断输入的关系是否对称函数*/for(i=0;i<n;i+)for(j=i+1;j<n;j+)if(Mij!=Mji)retur

49、n 0;printf("n");return 1;int chuandi() /*判断输入的关系是否传递函数*/int flag=1;for(i=0;i<n;i+)if(flag=0)break;for(j=0;j<n;j+)if(flag=0)break;for(k=0;k<n;k+)if(Mij=1&&Mjk=1&&Mik!=1)flag=0;break;return flag;void clearM() /*第一次输入不是等价关系,重新输入前矩阵清零*/int i,j;for(i=0;i<n;i+)for(j=0;j<n;j+) Mji = 0;void main()printf("请输入一个有限集合(a-z/A-Z):n");gets(A);n=strlen(A);printf("