實驗二離散報告

實 驗 報 告課程名稱離散數(shù)學實驗名稱集合上二元關系性質判定的實現(xiàn)指導單位計算機科學與技術系實 驗 報 告實驗名稱集合上二元關系性質判定的實現(xiàn)指導教師實驗類型驗證實驗學時4實驗時間一、 實驗目的和要求內容：編程實現(xiàn)任意集合上二元關系的性質判定。要求：能正確判定任意二元關系的自反性、對稱性、傳遞性、反自反性和反對稱性。二、實驗環(huán)境(實驗設備)X86計算機IDE:CodeBlocks 16.01編譯器：GUN GCC三、實驗原理及內容輸入集合已經(jīng)集合上面的序偶關系，輸出關系滿足的性質。整體思路為將關系轉換成矩陣，根據(jù)矩陣判斷關系的性質。若矩陣主對角線元素都是1，則滿足自反性。若矩陣主對角線元素都是0，則滿足反自反性。若矩陣所有元素關于主對角線對稱，則滿足對稱性。若矩陣中出現(xiàn)了關于主對角線對稱的元素，則不滿足反對稱性，否則滿足反對稱性。若矩陣的傳遞閉包等于矩陣自己，則矩陣滿足傳遞性。為了能夠處理集合中含有字母的情況，程序將所有輸入當成字符串來處理，然后將每一個字符與矩陣下標進行鍵值映射，這樣，在序偶關系中，通過字符就可以很輕松的找到對應的下標，從而很輕松將序偶關系用矩陣表示。程序定義的全局變量有：char a200; /保存輸入的集合A字符串char R300; /保存輸入的序偶R字符串map M; /保存字符與矩陣下標的映射（需#include）int X200200; /關系對應的矩陣int len; /集合A中含有的元素數(shù)量int tmp200200; /求傳遞閉包過程中，用來保存矩陣的傳遞閉包int tmp1200200; /求傳遞閉包過程中，用來保存矩陣的N次方。 第一步：將集合中的元素與矩陣下標映射由于集合A中可能含有字母，為了后面能夠更加方便的將序偶關系轉換成矩陣，第一步先將集合A中所以元素與矩陣下標進行映射，并統(tǒng)計集合A中元素個數(shù)。引用STL庫文件#include實現(xiàn)鍵值映射。代碼為：int init() int i=0; int l=strlen(a); int j=0; for(i=0;i=a&ai=A&ai=0&ai=9) Mai=j+; return j; 算法復雜度分析：對輸入的字符串進行循環(huán)遍歷，時間復雜度為O（n）。第二步，將關系轉換成矩陣 由于上一步中已經(jīng)將集合中元素與矩陣下標進行了映射,那定位關系中第一元素和第二元素就可以直接用語句MRI,將關系轉換成矩陣也就容易多了，XMRi+1MRi+3表示序偶對應的矩陣元素。代碼:void solve() int i,j; i=j=0; int l=strlen(R); while(il) if(Ri=) if(find(a,a+strlen(a),Ri+1)=a+strlen(a)|find(a,a+strlen(a),Ri+3)=a+strlen(a) printf(輸入有誤，關系R中包含非法元素n); exit(0); XMRi+1MRi+3=1; i+=5; else i+; 算法復雜度分析：對輸入的序偶字符串進行遍歷，時間復雜度是O(n)。用矩陣進行運算，空間復雜度是O(n2)。 第三步：根據(jù)矩陣求滿足的性質 （1）.自反性 如果矩陣中主對角線元素都是1，那么就滿足自反性，否則不滿足。判斷的時候只要找到第一個對角線元素不是1，就可以斷定不滿足自反性代碼：bool JudgeZiFan() int i; int flag=1; for(i=0;ilen;i+) if(Xii!=1) flag=0; break; if(flag) return true; else return false; 算法復雜度分析：由于只要掃描對角線元素，所以時間復雜度是O(n)。（2）反自反性 如果矩陣中主對角線元素都是0，那么就滿足反自反性，否則，就不滿足。判斷的時候掃描對角線元素，只要出現(xiàn)1就可斷定不滿足反自反性。代碼： bool JudgeFanZiFan() for(int i=0;i0) return false; return true; （3）對稱性如果對矩陣中，每一個Xij，都有Mji=1，那么就滿足對稱性，否則，不滿足對稱性。若出現(xiàn)Xij=1&Xji=0,就可以斷定不滿足對稱性。判斷的時候只要掃描上三角矩陣即可。 bool JudgeDuiCheng() int i,j; for(i=0;ilen;i+) for(j=0;jlen;j+) if(Xij) if(Xji!=1) return false; return true; 算法復雜度分析：掃描上三角矩陣，時間復雜度是O(n2)。（4）反對稱性 如果矩陣中出現(xiàn)了關于主對角線對稱的元素，那么就不滿足反對稱性，否則，滿足反對稱性。判斷的時候只要出現(xiàn)了Xij=1&Xji=1就可以斷定不滿足反對稱性。判斷的時候也只要掃描上三角矩陣。代碼：bool JudgeFanDuiCheng() for(int i=0;ilen;i+) for(int j=i+1;jlen;j+) if(Xij) if(Xji) return false; return true;算法復雜度分析：掃描上三角矩陣，時間復雜度是O(n2)（5）.傳遞性如果矩陣的傳遞閉包等于矩陣自己，那么就滿足傳遞性，否則不滿足。求矩陣的傳遞閉包首先定義一個求矩陣的冪的運算，這個地方只要求矩陣和X矩陣相乘就可以。還要定義一個特殊的求矩陣相加的運算，如果相加后矩陣元素大于1 ，就把元素置為1.最后只要比較一下傳遞閉包是不是與X相等就行了。具體步驟是先定義兩個全局數(shù)組tmp,和tmp1，首先初始化為X矩陣。tmp1用來累計和矩陣X的乘積，每次都和X相乘一次tmp1的冪就增加1，然后將tmp1與tmp矩陣相加（元素大于1就置成1），如此循環(huán)。函數(shù)cal（）為tmp1與X相乘，函數(shù)combine為tmp1與tmp相加。代碼：bool JudgeChuanDi() int i,j; for(i=0;ilen;i+) for(j=0;jlen;j+) tmpij=Xij; tmp1ij=Xij; for(i=2;i=len;i+) cal(); combine(); for(int i=0;ilen;i+) for(int j=0;jlen;j+) if(tmpij!=Xij) return false; return true;求矩陣的冪的運算：首先0將X矩陣拷貝到tmp1200200，然后每次都將tmp1與X相乘代碼：void cal() int xtmp200200; int k,p; for(int i=0;ilen;i+) for(int j=0;jlen;j+) int sum=0; for(k=0;klen;k+) sum+=tmp1ik*Xkj; if(sum=0) xtmpij=0; else xtmpij=1; for(int i=0;ilen;i+) for(int j=0;jlen;j+) tmp1ij=xtmpij; 矩陣相加的運算：如果相加后元素大于1，就置為1代碼：void combine() for(int i=0;ilen;i+) for(int j=0;jlen;j+) if(tmp1ij|tmpij) tmpij=1; 算法復雜度分析：主函數(shù)中，初始化tmp和tmp1時間復雜度是O(n2)。調用循環(huán)len-1次，然后每次cal函數(shù)進行矩陣相乘的復雜度是O(n3)，combine進行矩陣相加是O(n2)。這個運算步驟的時間復雜度是O(n4)，最后將tmp與X比較的時間復雜度是O(n2)。綜上，時間復雜度是O(n4)?？臻g復雜度分析：由于定義了兩個臨時數(shù)組tmp和tmp1，每一個是O(n2),所以，空間復雜度是O(n2)。主函數(shù)進行數(shù)據(jù)的讀入，輸出，以及函數(shù)的調用Main函數(shù)代碼：int main() memset(tmp,0,sizeof(tmp); memset(tmp1,0,sizeof(tmp1); memset(a,0,sizeof(a); memset(R,0,sizeof(R); printf(請輸入集合A,以逗號隔開各元素,回車結束n); gets(a); len=init(); printf(請輸入關系R，格式,.回車結束n); gets(R); solve(); bool ZiFan=JudgeZiFan(); bool DuiCheng=JudgeDuiCheng(); bool ChuanDi=JudgeChuanDi(); bool FanZiFan=JudgeFanZiFan(); bool FanDuiCheng=JudgeFanDuiCheng(); printf(性質為:n); if(ZiFan) printf(自反性n); if(FanZiFan) printf(反自反性n); if(DuiCheng) printf(對稱性n); if(FanDuiCheng) printf(反對稱性n); if(ChuanDi) printf(傳遞性n); return 0;程序測試：案例一：課本112頁例題5輸入集合為1,2,3,4關系為 ,結果正確。案例二：輸入集合為 a,b,c輸入關系為 ,結果正確。案例三：課本131頁例題1輸入集合 ： 1,2,3,4輸入關系： ,結果正確案例四：輸入集合 a,b,c,d輸入關系：,結果正確案例五：程序容錯性測試結果正確四、實驗小結（包括問題和解決方法、心得體會、意見與建議等）1. 個人感覺這個程序的難點是傳遞性的判斷，因為要求傳遞閉包，涉及到矩陣的乘法和加法，矩陣相乘在循環(huán)的時候，循環(huán)變