中南大學(xué)離散數(shù)學(xué)實驗報告(實驗2AC)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上“離散數(shù)學(xué)”實驗報告(實驗2AC)專 業(yè) 班 級 學(xué) 號 姓 名 日期：2011.12.12目錄一、實驗?zāi)康?二、實驗內(nèi)容3三、實驗環(huán)境3四、實驗原理和實現(xiàn)過程（算法描述）3A題型3C題型4五、實驗數(shù)據(jù)及結(jié)果分析7A題型7B題型9六、源程序清單11A題型11B題型12七、其他收獲及體會18一、實驗?zāi)康恼莆贞P(guān)系的概念與性質(zhì)，基本的關(guān)系運(yùn)算，關(guān)系的各種閉包的求法。理解等價類的概念，掌握等價類的求解方法。二、實驗內(nèi)容1. 求有限集上給定關(guān)系的自反、對稱和傳遞閉包。（有兩種求解方法，只做一種為A，兩種都做為B）2. 求有限集上等價關(guān)系的數(shù)目。（有兩種求解方法，只做一種為A，兩

2、種都做為B）3. 求解商集，輸入集合和等價關(guān)系，求相應(yīng)的商集。（C）三、實驗環(huán)境C或C語言編程環(huán)境實現(xiàn)。四、實驗原理和實現(xiàn)過程（算法描述）A題型 求有限集上等價關(guān)系的數(shù)目。集合上的等價關(guān)系與該集合的劃分之間存在一一對應(yīng)關(guān)系。一個等價關(guān)系對應(yīng)一個劃分，一個劃分也對應(yīng)一個等價關(guān)系。我們把n個元素的集合劃分成k塊的方法數(shù)叫第二類Stirling數(shù)，表示為S(n,k)。給定S(n,n) = S(n,1) = 1，有遞歸關(guān)系：S(n,k) = S(n 1,k 1) + kS(n 1,k)集合上所有等價類的個數(shù)即為k從1到n，所有S(n,k)之和。這個問題的算法比較簡單，僅需兩步就可完成，首先根據(jù)上式，定

3、義一個遞歸函數(shù)S（n,k），然后對k從1到n，求取sum=S（n，k），sum的值就是給定n元集合上的等價關(guān)系數(shù)目，最后將其輸出即可。A題型的流程圖如下所示：開 始輸入要計算的集合的元素數(shù)nSum=0k=1（）kn？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結(jié)束YNC題型 求解商集，輸入集合和等價關(guān)系，求相應(yīng)的商集商集即等價類構(gòu)成的集合，要求商集，首先需要判斷輸入的關(guān)系是否為等價關(guān)系，否則沒有商集。判斷輸入的關(guān)系是否為等價關(guān)系的算法如下：(1)將輸入的關(guān)系轉(zhuǎn)換為關(guān)系矩陣，這里定義

4、了一個函數(shù)translate()，轉(zhuǎn)換的方法為：依次查找輸入的關(guān)系中的二元組的兩個元素在集合中的位置，例如，若a在集合A中的位置為i，b在集合A中的位置為j，就令存放關(guān)系矩陣的二維數(shù)組Mij=1,這樣就將輸入的關(guān)系R轉(zhuǎn)換為關(guān)系矩陣的形式。(2)定義三個函數(shù)zifan(),duichen()和chuandi()，分別的作用是判斷輸入的關(guān)系是否自反、對稱和傳遞。由等價關(guān)系的定義知，若三個函數(shù)的返回值均為1，則輸入的關(guān)系是等價關(guān)系。判斷的方法是：若關(guān)系矩陣M中所有的Mii=1，則是自反關(guān)系；若M中所有的Mij=Mji，則是對稱關(guān)系；若Mij=1并且Mjk=1，那么一定有Mik=1，則是傳遞關(guān)系。判斷

5、了所輸入的關(guān)系為等價關(guān)系后就可以求其商集了，由于商集即等價類構(gòu)成的集合，所以要求其等價類。確定集合A=a1,a2,a3,an關(guān)于R的等價類的算法如下：(1) 令A(yù)中每一個元素自成一個子集，A1=a1,A2=a2,An=an(2) 對R中每個二元組，判定x和y所屬子集。假設(shè)x屬于Ai，y屬于Aj，若AiAj，則將Ai并入Aj，并置Ai為空；或?qū)j并入Ai，并置Aj為空。一般將元素少的集合合并到元素多的集合。(3) A1 ,A2,An中所有非空子集構(gòu)成的集合即為所求商集。集合的并運(yùn)算采用并查集(union-find sets)的方法。并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，多棵樹構(gòu)成一個森林，每棵樹構(gòu)成一個

6、集合，樹中的每個節(jié)點就是該集合的元素，找一個代表元素作為該樹(集合)的祖先。并查集支持以下三種操作：(1) Make_Set(x) 把每一個元素初始化為一個集合初始化后每一個元素的父親節(jié)點是它本身，每一個元素的祖先節(jié)點也是它本身。(2) Find_Set(x) 查找一個元素所在的集合查找一個元素所在的集合，只要找到這個元素所在集合的祖先即可。判斷兩個元素是否屬于同一集合，只要看他們所在集合的祖先是否相同即可。(3) Union(x,y) 合并x,y所在的兩個集合合并兩個不相交集合操作很簡單：首先設(shè)置一個數(shù)組Fatherx，表示x的父親的編號。那么，合并兩個不相交集合的方法就是，找到其中一個集合

7、的祖先，將另外一個集合的祖先指向它。C題型的流程圖如下所示：開 始輸入集合A輸入A上的關(guān)系R轉(zhuǎn)換為關(guān)系矩陣M是否為等價關(guān)系？求解商集A/R輸出商集結(jié) 束是否五、實驗數(shù)據(jù)及結(jié)果分析以下是實驗過程中的實驗數(shù)據(jù)截圖：A題型 以上三圖顯示了集合元素數(shù)為3、4、5的等價關(guān)系數(shù)目分別為5、15、52，根據(jù)原遞歸式計算也是此值。說明程序正確。 上圖顯示的是當(dāng)輸入錯誤的情況，當(dāng)輸入錯誤時提示錯誤，再次輸入后正確計算出其結(jié)果。由以上圖示數(shù)據(jù)可以看出程序完整地實現(xiàn)了實驗A的要求。C題型(1)運(yùn)行程序開始提示輸入集合A：(2)輸入集合并回車，頻幕上顯示要計算的集合A，并提示下一步輸入集合上的等價關(guān)系R：(3)輸入集

8、合A上的一個等價關(guān)系R并回車，顯示關(guān)系R和它的關(guān)系矩陣，以及計算出的商集：(4)再次運(yùn)行程序，此次輸入的關(guān)系不是等價關(guān)系，則會出現(xiàn)提示：您輸入的不是等價關(guān)系，沒有商集，請重新輸入！(5)重新輸入一個等價關(guān)系，輸出其正確的計算結(jié)果：由以上實驗數(shù)據(jù)可以看出，程序完整地實現(xiàn)了題目要求。當(dāng)然程序編寫及調(diào)試過程中還遇到很多錯誤，都一一解決了，但沒有截取數(shù)據(jù)六、源程序清單A題型#includeint S(int x,int y) /*定義遞歸函數(shù)*/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;

9、printf(請輸入有限集合的元素個數(shù)：n);scanf(%d,&n);getchar();if(n100)printf(輸入錯誤，請重新輸入！n);scanf(%d,&n);getchar();for(k=1;k=n;k+)sum=sum+S(n,k); /*調(diào)用遞歸函數(shù)*/printf(給定%d元有限集上等價關(guān)系的數(shù)目為:n%d,n,sum);getchar();C題型# include stdio.h# include ctype.h# include string.h# include stdlib.h# include math.h#define MAX 20#define STU

10、struct stuint MMAXMAX; /*存放關(guān)系矩陣*/char AMAX; /*存放有限集合*/char BMAX; /*存放等價關(guān)系*/int i,j,p,q,n,l,k,t,y;STU int m; char tree20;STU equ20;void make_set(STU equ,char A,int n) /*使集合A中的元素自成一個子集*/ int i; for(i=0;in;i+) equi.m=1; equi.tree0=Ai; equi.tree1=0; find_set(int j) /*查找二元組中元素所屬集合*/ int i; for(i=0;ij;i+)

11、 if(Mji) break; if(i=j) return -1; else return 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;void disp(STU equ,int n) /*輸出商集*/int i;printf(A/R= ); for(i=0;in;i+)if(equi.m!=0)printf(%s ,equi.tree);p

12、rintf( );void caculate(STU equ,char A,int n) /*計算商集*/int p; make_set(equ,A,n); for(i=0;in;i+) p = find_set(i); if(p!=-1) unionit(equ,p,i); disp(equ,n); /*調(diào)用輸出商集函數(shù)*/void getguanxi() /*獲得關(guān)系R并輸出顯示*/ gets(B);l=strlen(B);printf(您輸入的關(guān)系為：n); printf(R= );for(j=0;jl;j=j+2)printf( ); printf( n);void translate

13、() /*轉(zhuǎn)換為關(guān)系矩陣的函數(shù)*/int p,q,i=0,j; while(Bi!=0) if(Bi=A)&(Bi=a)&(Bi=z) for(j=0;jn;j+) if (Bi=Aj) p=j; break; i+; while(Bi!=0) for(j=0;jn;j+) if (Bi=Aj) q=j; Mpq=1; break; if(j=n) i+; else i+; break; elsei+;void display() /*輸出關(guān)系矩陣函數(shù)*/int i,j; for(i=0;in;i+)for(j=0;jn;j+) printf(%2d,Mij);printf(n);int zi

14、fan() /*判斷輸入的關(guān)系是否自反函數(shù)*/int count = 0;for(i=0;in;i+)if(Mii=1)count+;if(count = n) return 1;elsereturn 0;int duichen() /*判斷輸入的關(guān)系是否對稱函數(shù)*/ for(i=0;in;i+)for(j=i+1;jn;j+)if(Mij!=Mji) return 0;printf(n);return 1;int chuandi() /*判斷輸入的關(guān)系是否傳遞函數(shù)*/int flag=1; for(i=0;in;i+) if(flag=0)break;for(j=0;jn;j+) if(fl

15、ag=0)break;for(k=0;kn;k+)if(Mij=1&Mjk=1&Mik!=1) flag=0;break; return flag;void clearM() /*第一次輸入不是等價關(guān)系,重新輸入前矩陣清零*/ int i,j; for(i=0;in;i+) for(j=0;jn;j+) Mji = 0;void main()printf(請輸入一個有限集合(a-z/A-Z):n); gets(A);n=strlen(A);printf(您輸入的集合為：n);printf(A=);for(i=0;in;i+) /*輸出集合*/printf(%2c,Ai); printf( n)

16、;printf(請輸入這個集合上的一個等價關(guān)系R:n);getguanxi(); /*調(diào)用獲得關(guān)系R并輸出顯示函數(shù)*/ translate(); /*調(diào)用轉(zhuǎn)換為關(guān)系矩陣函數(shù)*/printf(R的關(guān)系矩陣為：n);display(); /*調(diào)用輸出關(guān)系矩陣函數(shù)*/t=zifan()&duichen()&chuandi(); /*判斷關(guān)系是否等價*/while(t!=1) printf(您輸入的不是等價關(guān)系，沒有商集，請重新輸入！n); getguanxi(); /*調(diào)用獲得關(guān)系R并輸出顯示函數(shù)*/ clearM(); /*矩陣清零*/ translate(); /*調(diào)用轉(zhuǎn)換為關(guān)系矩陣函數(shù)*/ printf(R的關(guān)系矩陣為：n); display(); /*調(diào)用輸出關(guān)系矩陣函數(shù)*/t=zifan()&duichen()&chuandi(); /*判斷關(guān)系是否等價*/printf(您所輸入的集合和等價關(guān)系相應(yīng)的商集為：n);caculate(equ,A,n); /*調(diào)用計算商集函數(shù)*/getchar();七、其他收獲和體會相對于上一次的實驗，由于積累了經(jīng)驗，并且掌握了一定的技巧，所以本次實驗相對來說更得心應(yīng)手，但在實驗期間還是碰到了許多困難。本次實驗中，我選擇了2. 求有限集上等價關(guān)系的數(shù)目和3. 求解商集，輸入集合和等價關(guān)系，求相應(yīng)的商集。首先我還