离散数学2集合论

1、南京工程学院实 验 报 告课程名称 离散数学 实验项目名称 集合论 实验学生班级 K网络工程121 实验学生姓名 王云峰 学号 240121525 实验时间 11月8日 实验地点 信息楼 实验成绩评定 指导教师签字 年月日一、实验目的和要求集合论是一切数学的基础，也是计算机科学不可或缺的，在数据结构、数据库理论、开关理论、自动机理论和可计算理论等领域都有广泛的应用。集合的运算规则是集合论中的重要内容。通过该组实验，目的是让学生更加深刻地理解集合的概念和性质，并掌握集合的运算规则等。实验要是实现求任意两个集合的交集、并集、差集。二、实验主要仪器和设备计算机三、实验方法与步骤（需求分析、算法设计思

2、路、流程图等）（1）求任意两个集合的交集、并集、差集。（2）求任意一个集合的幂集。（3）求任意一个集合的所有m元子集。（4）求任意个元素的全排列。集合的表示采用列举法，如A=a,b,c,d。（1）求任意两个集合的交集、并集、差集。ABx|xAxBABx|xAxBABx|xAxÏB（2）求任意一个集合的幂集。P(A)Ai|iJ，其中Ji|i是二进制数且i。（3）求任意一个集合的所有m元子集。按照（2）求出子集并判断是否符合要求。（4）求任意个元素的全排列。设S=1,2,3,n，(a1,a2,an)和(b1,b2,bn)是S的两个全排列，若存在i1,2,n，使得对一切j=1,2,i有aj

3、=bj且ai+1<bi+1，则称排列(a1,a2,an)字典序的小于(b1,b2,bn)。记为(a1,a2,an)<(b1,b2,bn)。若(a1,a2,an)<(b1,b2,bn)，且不存在(c1,c2,cn)使得(a1,a2,an)< (c1,c2,cn)<(b1,b2,bn)，则称(b1,b2,bn)为(a1,a2,an)的下一个排列。求一个排列(a1,a2,an)的下一个排列的算法如下：（1）求满足关系式aj-1<aj的j的最大值，设为i，即i=maxj|aj-1<aj（2）求满足关系式ai-1<ak的k的最大值，设为j，即j=maxk|

4、ai-1<ak（3）ai-1与aj互换得序列(b1,b2,bn)（4）将(b1,b2,bn)中部分bi,bi+1,bn的顺序逆转，得到(b1,b2,bi-1,bn,bi)便是所求得下一个排列。四、实验原始纪录（源程序、数据结构等）#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>void Set_To_Array(char *Set,char *Array)/集合转化为一维字符数组int i,j;j=0;for(i=1;i<(int)strlen(

5、Set)-1;i=i+2)Arrayj+=Seti;Arrayj='0'void Array_To_Set(char *Array,char *Set)/一维字符数组转化为集合int i,j;j=0; Setj+=''for(i=0;Arrayi!='0'i+)Setj+=Arrayi;Setj+=','if(j>1)Setj-1=''Setj='0'else Setj+=''Setj='0'void Get_ISet()/集合的交运算int i,j,k;cha

6、r *A,*B,*C,*S1,*S2,*S;A=new char; B=new char; C=new char;S1=new char; S2=new char; S=new char;printf("请输入集合A=");scanf("%s",S1); Set_To_Array(S1,A);printf("请输入集合B=");scanf("%s",S2);Set_To_Array(S2,B);if(!strlen(A)|!strlen(B)printf("AB=n");elsek=0;for(

7、i=0;Ai!='0'i+)for(j=0;Bj!='0'j+)if(Ai=Bj)Sk+=Ai;break;Sk='0'Array_To_Set(S,C);printf("AB=%sn",C);void Get_USet()/集合的并运算int i,j,k,flag;char *A,*B,*C,*S1,*S2,*S;A=new char;B=new char;C=new char;S1=new char;S2=new char;S=new char;printf("请输入集合A=");scanf("

8、;%s",S1); Set_To_Array(S1,A);printf("请输入集合B=");scanf("%s",S2);Set_To_Array(S2,B); S=A;k=strlen(S);for(i=0;Bi!='0'i+) flag=1; for(j=0;Aj!='0'j+) if(Aj=Bi)flag=0;break; if(flag)Sk+=Bi;Sk='0'Array_To_Set(S,C);printf("AB=%sn",C);void Get_DSet()/

9、集合的差运算int i,j,k,flag;char *A,*B,*C,*S1,*S2,*S;A=new char; B=new char; C=new char;S1=new char; S2=new char; S=new char;printf("请输入集合A=");scanf("%s",S1); Set_To_Array(S1,A);printf("请输入集合B=");scanf("%s",S2);Set_To_Array(S2,B);k=0;for(i=0;Ai!='0'i+) flag=1

10、; for(j=0;Bj!='0'j+)if(Ai=Bj)flag=0;break; if(flag)Sk+=Ai;Sk='0'Array_To_Set(S,C);printf("A-B=%sn",C);void Get_PSet()/求集合的幂集int i,j,k,n;char *A,*P,*S1,*S;A=new char;P=new char;S1=new char;S=new char;printf("请输入集合A=");scanf("%s",S1); Set_To_Array(S1,A);n=

11、strlen(A);printf("P(A)=");for(i=0;i<(int)pow(2,n);i+)k=0;for(j=0;j<n;j+)if(i&(int)pow(2,j)Sk+=Aj; Sk='0' Array_To_Set(S,P);if(strlen(S)=strlen(A)printf("%s",P);else printf("%s,",P);printf("n");int f(int n,int m)int s=1,i;for(i=n-m+1;i<=n;i

12、+)s=s*i;return s;void Get_SubSet()/求集合指定元素个数的子集 int i,j,m,k,ip,g; char *A,*S1,*S,*B; A=new char; S1=new char; S=new char; B=new char; printf("A=");scanf("%s",S1); printf("g=");scanf("%d",&g); Set_To_Array(S1,A); m=strlen(A); if(g<1|g>m)printf("输

13、入的元数错误");return; printf("集合A=%s的%d元子集如下：n",S1,g); for(i=1;i<=f(m,g);i+) k=0;ip=0; for(j=0;j<m;j+) if(i&(int)pow(2,j)Sk+=Aj;ip+; Sk='0' if(ip=g)Array_To_Set(S,B);printf("%sn",B); void swap(int &a, int &b) a=a+b; b=a-b; a=a-b;void swapc(char *A,int i,

14、int j) char temp; temp=Ai; Ai=Aj; Aj=temp;void Get_SArrange()int i,j,k,m,n,p,*C;char *A,*S;A=new char;S=new char;C=new int;printf("请输入集合A=");scanf("%s",S); Set_To_Array(S,A);n=strlen(A);for(k=1;k<=n;k+)Ck=k;printf("全排列如下：n");printf("%s",A);p=1;for(k=1;k<

15、=n;k+)p=p*Ck;for(m=1;m<p;m+)for(j=2;j<=n;j+)if(Cj-1<=Cj)i=j;for(k=i;k<=n;k+)if(Ci-1<Ck)j=k;swap(Ci-1,Cj);swapc(A,i-2,j-1);for(k=0;k<=n;k+)if(i+k<n-k)swap(Ci+k,Cn-k);swapc(A,i+k-1,n-k-1);printf("->%s",A); printf("n");void main() int i=1; while(i>0) Syste

16、m(“cls”); printf("1、求两个集合的交集 2、求两个集合的并集n"); printf("3、求两个集合的差集 4、求一个集合的幂集n"); printf("5、求一个集合的m元子集 6、求任意集合元素的全排列n"); printf("0、退出n"); printf("请选择要进行的操作:"); scanf("%d",&i); switch(i) case 1:Get_ISet();break; case 2:Get_USet();break; case

17、 3:Get_DSet();break; case 4:Get_PSet();break; case 5:Get_SubSet();break; case 6:Get_SArrange();break; case 0:exit(-2); default:printf("选择错误，请重新选择:nn"); 5、 实验结果及分析（计算过程与结果、数据曲线、图表等）求任意两个集合的交集、并集、差集。求任意一个集合的幂集。求任意一个集合的所有m元子集。求任意个元素的全排列。集合的表示采用列举法，如A=a,b,c,d六、实验总结与思考集合的表示采用列举法，如A=a,b,c,d。（1）求

18、任意两个集合的交集、并集、差集。ABx|xAxBABx|xAxBABx|xAxÏB（2）求任意一个集合的幂集。P(A)Ai|iJ，其中Ji|i是二进制数且i。（3）求任意一个集合的所有m元子集。按照（2）求出子集并判断是否符合要求。（4）求任意个元素的全排列。设S=1,2,3,n，(a1,a2,an)和(b1,b2,bn)是S的两个全排列，若存在i1,2,n，使得对一切j=1,2,i有aj=bj且ai+1<bi+1，则称排列(a1,a2,an)字典序的小于(b1,b2,bn)。记为(a1,a2,an)<(b1,b2,bn)。若(a1,a2,an)<(b1,b2,bn)，且不存在(c1,c2,cn)使得(a1,a2,an)< (c1,c2,cn)<(b1,b2,bn)，则称(b1,b2,bn)为(a1,a2,an)的下一个排列。求一个排列(a1,a2,an)的下一个排列的算法如下：（1）求满足关系式aj-1<aj的j的最大值，设为i，即i=maxj|aj-1<aj（2）求满足关系式ai-1<ak的k的最大值，设为j，即j=maxk|ai-1<