實(shí)驗(yàn)二離散報(bào)告

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