離散數學2集合論

1、南京工程學院實 驗 報 告課程名稱 離散數學 實驗項目名稱 集合論 實驗學生班級 K網絡工程121 實驗學生姓名 王云峰 學號 240121525 實驗時間 11月8日 實驗地點 信息樓 實驗成績評定 指導教師簽字 年月日一、實驗目的和要求集合論是一切數學的基礎，也是計算機科學不可或缺的，在數據結構、數據庫理論、開關理論、自動機理論和可計算理論等領域都有廣泛的應用。集合的運算規(guī)則是集合論中的重要內容。通過該組實驗，目的是讓學生更加深刻地理解集合的概念和性質，并掌握集合的運算規(guī)則等。實驗要是實現求任意兩個集合的交集、并集、差集。二、實驗主要儀器和設備計算機三、實驗方法與步驟（需求分析、算法設計思

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<