離散數(shù)學(xué)實(shí)驗(yàn)報(bào)告

1、“離散數(shù)學(xué)”實(shí)驗(yàn)報(bào)告目錄一、實(shí)驗(yàn)?zāi)康?二、實(shí)驗(yàn)內(nèi)容3三、實(shí)驗(yàn)環(huán)境3四、實(shí)驗(yàn)原理和實(shí)現(xiàn)過(guò)程（算法描述）31、實(shí)驗(yàn)原理2、實(shí)驗(yàn)過(guò)程五、實(shí)驗(yàn)數(shù)據(jù)及結(jié)果分析13六、源程序清單24源代碼24七、其他收獲及體會(huì)45一、實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)一：熟悉掌握命題邏輯中的聯(lián)接詞、真值表、主范式等，進(jìn)一步能用它們來(lái)解決實(shí)際問(wèn)題。實(shí)驗(yàn)二：掌握關(guān)系的概念與性質(zhì)，基本的關(guān)系運(yùn)算，關(guān)系的各種閉包的求法。理解等價(jià)類的概念，掌握等價(jià)類的求解方法。實(shí)驗(yàn)三：理解圖論的基本概念，圖的矩陣表示，圖的連通性，圖的遍歷，以及求圖的連通支方法。二、實(shí)驗(yàn)內(nèi)容 實(shí)驗(yàn)一：1. 從鍵盤輸入兩個(gè)命題變?cè)狿和Q的真值，求它們的合取、析取、條件和雙條件的真值。（A

2、）2. 求任意一個(gè)命題公式的真值表（B，并根據(jù)真值表求主范式（C） 實(shí)驗(yàn)二：1.求有限集上給定關(guān)系的自反、對(duì)稱和傳遞閉包。（有兩種求解方法，只做一種為A，兩種都做為B）2. 求有限集上等價(jià)關(guān)系的數(shù)目。（有兩種求解方法，只做一種為A，兩種都做為B）3. 求解商集，輸入集合和等價(jià)關(guān)系，求相應(yīng)的商集。（C） 實(shí)驗(yàn)三：以偶對(duì)的形式輸入一個(gè)無(wú)向簡(jiǎn)單圖的邊，建立該圖的鄰接矩陣，判斷圖是否連通（A）。并計(jì)算任意兩個(gè)結(jié)點(diǎn)間的距離（B）。對(duì)不連通的圖輸出其各個(gè)連通支（C）。三、實(shí)驗(yàn)環(huán)境C或C語(yǔ)言編程環(huán)境實(shí)現(xiàn)。四、實(shí)驗(yàn)原理和實(shí)現(xiàn)過(guò)程（算法描述）實(shí)驗(yàn)一：1.實(shí)驗(yàn)原理（1）合?。憾}聯(lián)結(jié)詞。將兩個(gè)命題P、Q聯(lián)結(jié)起

3、來(lái)，構(gòu)成一個(gè)新的命題PQ, 讀作P、Q的合取, 也可讀作P與Q。這個(gè)新命題的真值與構(gòu)成它的命題P、Q的真值間的關(guān)系為只有當(dāng)兩個(gè)命題變項(xiàng)P = T, Q = T時(shí)方可PQ =T, 而P、Q只要有一為F則PQ = F。這樣看來(lái)，PQ可用來(lái)表示日常用語(yǔ)P與Q, 或P并且Q。（2）析?。憾}聯(lián)結(jié)詞。將兩個(gè)命題P、Q聯(lián)結(jié)起來(lái)，構(gòu)成一個(gè)新的命題PQ, 讀作P、Q的析取, 也可讀作P或Q。這個(gè)新命題的真值與構(gòu)成它的命題P、Q的真值間的關(guān)系為只有當(dāng)兩個(gè)命題變項(xiàng)P = F, Q = F時(shí)方可PQ =F, 而P、Q只要有一為T則PQ = T。這樣看來(lái)，PQ可用來(lái)表示日常用語(yǔ)P或者Q。（3）條件：二元命題聯(lián)結(jié)詞

4、。將兩個(gè)命題P、Q聯(lián)結(jié)起來(lái)，構(gòu)成一個(gè)新的命題PQ, 讀作P條件Q, 也可讀作如果P，那么Q。這個(gè)新命題的真值與構(gòu)成它的命題P、Q的真值間的關(guān)系為只有當(dāng)兩個(gè)命題變項(xiàng)P = T, Q = F時(shí)方可PQ =F, 其余均為T。（4）雙條件：二元命題聯(lián)結(jié)詞。將兩個(gè)命題P、Q聯(lián)結(jié)起來(lái)，構(gòu)成一個(gè)新的命題PQ, 讀作P雙條件于Q。這個(gè)新命題的真值與構(gòu)成它的命題P、Q的真值間的關(guān)系為當(dāng)兩個(gè)命題變項(xiàng)P = T, Q =T時(shí)方可PQ =T, 其余均為F。（5）真值表:表征邏輯事件輸入和輸出之間全部可能狀態(tài)的表格。列出命題公式真假值的表。通常以1表示真，0 表示假。命題公式的取值由組成命題公式的命題變?cè)娜≈岛兔}聯(lián)

5、結(jié)詞決定，命題聯(lián)結(jié)詞的真值表給出了真假值的算法。 真值表是在邏輯中使用的一類數(shù)學(xué)表，用來(lái)確定一個(gè)表達(dá)式是否為真或有效。（6）主范式：主析取范式：在含有n個(gè)命題變?cè)暮?jiǎn)單合取式中,若每個(gè)命題變?cè)c其否定不同時(shí)存在,而兩者之一出現(xiàn)一次且僅出現(xiàn)一次,稱該簡(jiǎn)單合取式為小項(xiàng)。由若干個(gè)不同的小項(xiàng)組成的析取式稱為主析取范式;與A等價(jià)的主析取范式稱為A的主析取范式。任意含n個(gè)命題變?cè)姆怯兰倜}公式A都存在與其等價(jià)的主析取范式,并且是惟一的。主合取范式：在含有n個(gè)命題變?cè)暮?jiǎn)單析取式中,若每個(gè)命題變?cè)c其否定不同時(shí)存在,而兩者之一出現(xiàn)一次且僅出現(xiàn)一次,稱該簡(jiǎn)單析取式為大項(xiàng)。由若干個(gè)不同的大項(xiàng)組成的合取式稱為主

6、合取范式;與A等價(jià)的主合取范式稱為A的主合取范式。任意含n個(gè)命題變?cè)姆怯勒婷}公式A都存在與其等價(jià)的主合取范式,并且是惟一的。2.實(shí)驗(yàn)過(guò)程（1）A題部分，首先是對(duì)各個(gè)輸入量的處理，要確定輸入的為0或1，否則則為出錯(cuò)，接下來(lái)就是運(yùn)算處理，在C語(yǔ)言中本身支持的有與或非這三種，可以用!,&&,|來(lái)表示，而在這個(gè)實(shí)驗(yàn)中，不是與或非的可以通過(guò)轉(zhuǎn)化而變?yōu)榕c或非的形式，具體流程圖如下：開(kāi)始P為1或0P為1或0運(yùn)算是否繼續(xù)結(jié)束YYYNNN輸入P值輸入Q值輸出結(jié)果求合取、析取、條件和雙條件的真值流程圖（2）B，C題部分，首先是輸入一個(gè)合理的式子，然后從式子中查找出變量的個(gè)數(shù)，開(kāi)辟一個(gè)二進(jìn)制函數(shù)

7、，用來(lái)生成真值表，然后用函數(shù)運(yùn)算，輸出結(jié)果，并根據(jù)結(jié)果歸類給范式，最后輸出范式。函數(shù)部分，主要是3個(gè)函數(shù)，一個(gè)為真值表遞加函數(shù)，通過(guò)二進(jìn)制的加法原理遞進(jìn)產(chǎn)生，一個(gè)為分級(jí)運(yùn)算函數(shù)，這個(gè)函數(shù)是通過(guò)判斷括號(hào)，選出最內(nèi)級(jí)括號(hào)的內(nèi)容執(zhí)行運(yùn)算函數(shù)，這樣一級(jí)一級(jí)向外運(yùn)算，最后得出最終結(jié)果，剩下一個(gè)為主運(yùn)算函數(shù)，按照運(yùn)算符號(hào)的優(yōu)先級(jí)按順序進(jìn)行運(yùn)算，如先將所有非運(yùn)算運(yùn)算完，再執(zhí)行與運(yùn)算。如此運(yùn)算。開(kāi)始輸入式子計(jì)算變量個(gè)數(shù)生成真值表輸出真值表變量賦值運(yùn)算式子輸出結(jié)果歸類主范式輸出主范式結(jié)束循環(huán)是否結(jié)束YN主函數(shù)開(kāi)始檢查括號(hào)是否是最內(nèi)級(jí)括號(hào)運(yùn)算內(nèi)容是否是最后結(jié)果返回結(jié)果結(jié)束開(kāi)始結(jié)束YYNN非運(yùn)算與運(yùn)算或運(yùn)算蘊(yùn)含運(yùn)算

8、等值運(yùn)算返回結(jié)果主運(yùn)算函數(shù)分級(jí)運(yùn)算函數(shù)實(shí)驗(yàn)二：A題型 求有限集上等價(jià)關(guān)系的數(shù)目。集合上的等價(jià)關(guān)系與該集合的劃分之間存在一一對(duì)應(yīng)關(guān)系。一個(gè)等價(jià)關(guān)系對(duì)應(yīng)一個(gè)劃分，一個(gè)劃分也對(duì)應(yīng)一個(gè)等價(jià)關(guān)系。我們把n個(gè)元素的集合劃分成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)集合上所有等價(jià)類的個(gè)數(shù)即為k從1到n，所有S(n,k)之和。這個(gè)問(wèn)題的算法比較簡(jiǎn)單，僅需兩步就可完成，首先根據(jù)上式，定義一個(gè)遞歸函數(shù)S（n,k），然后對(duì)k從1到n，求取sum=S（n，k），sum的值就是給定n

9、元集合上的等價(jià)關(guān)系數(shù)目，最后將其輸出即可。A題型的流程圖如下所示：開(kāi)始輸入要計(jì)算的集合的元素?cái)?shù)nSum=0k=1（）k<n？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題型 求解商集，輸入集合和等價(jià)關(guān)系，求相應(yīng)的商集商集即等價(jià)類構(gòu)成的集合，要求商集，首先需要判斷輸入的關(guān)系是否為等價(jià)關(guān)系，否則沒(méi)有商集。判斷輸入的關(guān)系是否為等價(jià)關(guān)系的算法如下：(1)將輸入的關(guān)系轉(zhuǎn)換為關(guān)系矩陣，這里定義了一個(gè)函數(shù)translate()，轉(zhuǎn)換的方法為：依次查找輸入的關(guān)系中的二元組的兩個(gè)元素

10、在集合中的位置，例如<a，b>，若a在集合A中的位置為i，b在集合A中的位置為j，就令存放關(guān)系矩陣的二維數(shù)組Mij=1,這樣就將輸入的關(guān)系R轉(zhuǎn)換為關(guān)系矩陣的形式。(2)定義三個(gè)函數(shù)zifan(),duichen()和chuandi()，分別的作用是判斷輸入的關(guān)系是否自反、對(duì)稱和傳遞。由等價(jià)關(guān)系的定義知，若三個(gè)函數(shù)的返回值均為1，則輸入的關(guān)系是等價(jià)關(guān)系。判斷的方法是：若關(guān)系矩陣M中所有的Mii=1，則是自反關(guān)系；若M中所有的Mij=Mji，則是對(duì)稱關(guān)系；若Mij=1并且Mjk=1，那么一定有Mik=1，則是傳遞關(guān)系。判斷了所輸入的關(guān)系為等價(jià)關(guān)系后就可以求其商集了，由于商集即等價(jià)類構(gòu)成

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

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

13、合的祖先，將另外一個(gè)集合的祖先指向它。C題型的流程圖如下所示：開(kāi)始輸入集合A輸入A上的關(guān)系R轉(zhuǎn)換為關(guān)系矩陣M是否為等價(jià)關(guān)系？求解商集A/R輸出商集結(jié)束是否實(shí)驗(yàn)三：1、實(shí)驗(yàn)原理（1）建立圖的鄰接矩陣，判斷圖是否連通根據(jù)圖的矩陣表示法建立鄰接矩陣A，并利用矩陣的乘法和加法求出可達(dá)矩陣，從而判斷圖的連通性。連通圖的定義：在一個(gè)無(wú)向圖 G 中，若從頂點(diǎn)vi到頂點(diǎn)vj有路徑相連(當(dāng)然從vj到vi也一定有路徑)，則稱vi和vj是連通的。如果 G 是有向圖，那么連接vi和vj的路徑中所有的邊都必須同向。如果圖中任意兩點(diǎn)都是連通的，那么圖被稱作連通圖。判斷連通圖的實(shí)現(xiàn)：在圖中，從任意點(diǎn)出發(fā)在剩余的點(diǎn)中，找到所

14、有相鄰點(diǎn)循環(huán)，直到?jīng)]有點(diǎn)可以加入為止，如果有剩余的點(diǎn)就是不連通的，否則就是連通的。或者也可用WallShell算法，由圖的鄰接矩陣判斷圖是否連通。（2）計(jì)算任意兩個(gè)結(jié)點(diǎn)間的距離圖中兩點(diǎn)i，j間的距離通過(guò)檢驗(yàn)Al中使得aij為1的最小的l值求出。路徑P中所含邊的條數(shù)稱為路徑P的長(zhǎng)度。在圖G<V,E>中，從結(jié)點(diǎn)Vi到Vj最短路徑的長(zhǎng)度叫從Vi到Vj的距離，記為d<Vi，Vj>。設(shè)圖的鄰接矩陣是A，則 所對(duì)應(yīng)的aij的值表示，點(diǎn)Vi到點(diǎn)Vj距離為n的路徑有aij條。若aij(1)，aij(2)，aij(n-1)，中至少有一個(gè)不為0，則可斷定Vi與Vj可達(dá)，使aij(l)0的最

15、小的l即為d(Vi，Vj)。問(wèn)題求解原理為：（1） 先構(gòu)造初始鄰接矩陣A=Vij，Vij為頂點(diǎn)Vi到頂點(diǎn)Vj的權(quán)。如果Vi和Vj之間不存在弧段或者是負(fù)向回路或者是i=j，則令Vij其值為。（2） 再構(gòu)造初始中間頂點(diǎn)矩陣。（3） 然后開(kāi)始迭代計(jì)算（迭代的次數(shù)等于頂點(diǎn)的個(gè)數(shù)1）（4）最后查找Vi到Vj的最短路徑。計(jì)算節(jié)點(diǎn)Vi與Vj之間的距離的方法為：利用鄰接矩陣相互間相乘后得到的矩陣來(lái)判斷節(jié)點(diǎn)間的距離。如果c2sij=0，則這兩個(gè)節(jié)點(diǎn)的距離為無(wú)窮大。如果c2s-2ij=0,c2s-1ij=1時(shí)，則這兩點(diǎn)間的距離為s。（3）對(duì)不連通的圖輸出其各個(gè)連通支圖的連通支的求法則可采用圖的遍歷算法，圖的遍歷有

16、深度優(yōu)先和廣度優(yōu)先兩種方法，其中深度優(yōu)先算法又分為遞歸和非遞歸兩種。在無(wú)向圖中，如果任何兩點(diǎn)可達(dá)，則稱圖G是連通的，如果G的子圖G是連通的，沒(méi)有包含G的更大的子圖G是連通的，則稱G是G的連通支。當(dāng)有判斷出關(guān)系不是連通的之后，將需要求出分支模塊實(shí)現(xiàn)方法如下：先定義一個(gè)二維數(shù)組用來(lái)存放相應(yīng)的分塊，先選定一個(gè)點(diǎn)，并將它放在數(shù)組中，然后判斷，如果后面的和他是聯(lián)通的便將它也放在同一個(gè)數(shù)組中，否則將其存入其他的數(shù)組中，后面以此類推，在輸出相應(yīng)的數(shù)組，便可判斷出連通分支。2、實(shí)驗(yàn)過(guò)程（1） 程序整體思路本程序完成了實(shí)驗(yàn)所要求的全部功能，其基本思路是“運(yùn)用模塊化的思想，將實(shí)現(xiàn)“求連通支”、“輸入結(jié)點(diǎn)關(guān)系”、“

17、輸出鄰接矩陣”、“顯示兩結(jié)點(diǎn)間的距離”、“求可達(dá)矩陣”和“圖的遍歷”的子函數(shù)分開(kāi)編寫，然后將它們以子函數(shù)的形式添加到主函數(shù)main的代碼后面，在要使用相應(yīng)的子函數(shù)時(shí)，進(jìn)行子函數(shù)調(diào)用就可以實(shí)現(xiàn)相應(yīng)的功能了。”本程序的一大特色就是開(kāi)發(fā)者靈活使用了C語(yǔ)言中的數(shù)組概念來(lái)進(jìn)行開(kāi)發(fā)，用數(shù)組來(lái)模擬矩陣的運(yùn)算，通過(guò)相應(yīng)的算法實(shí)現(xiàn)了全部的功能。（2）具體算法流程在main()系統(tǒng)界面顯示；用dowhile循環(huán)語(yǔ)句和switch語(yǔ)句實(shí)現(xiàn)功能1,2,3的選擇，并調(diào)用相關(guān)的子程序；用start、goto start實(shí)現(xiàn)控制流的轉(zhuǎn)移；liantongzhi()求連通支，此子函數(shù)通過(guò)一個(gè)for循環(huán)控制遍歷每個(gè)結(jié)點(diǎn)，并調(diào)用

18、函數(shù)DFS（）求每個(gè)結(jié)點(diǎn)的連通支；DFS（int a）通過(guò)實(shí)參與形參，將結(jié)點(diǎn)數(shù)據(jù)代入函數(shù)；定義順序棧變量；通過(guò)for循環(huán)初始化；為a置已訪問(wèn)標(biāo)志，已經(jīng)訪問(wèn)了的元素為1；定義順序棧的第一個(gè)元素；通過(guò)while循環(huán)實(shí)現(xiàn)結(jié)點(diǎn)遍歷，棧不為空時(shí)執(zhí)行循環(huán)；棧頂元素賦值；通過(guò)for循環(huán)尋找v的下個(gè)未訪問(wèn)的鄰接點(diǎn)；通過(guò)if條件句，若x,i是邊和節(jié)點(diǎn)i未被訪問(wèn)過(guò)，處理結(jié)點(diǎn)的訪問(wèn)，并進(jìn)行訪問(wèn)標(biāo)志，進(jìn)棧等操作；通過(guò)if條件句，若v已訪問(wèn)到的出點(diǎn)，則將其退棧；shuru()輸入結(jié)點(diǎn)關(guān)系；通過(guò)for循環(huán)先將矩陣所有元素賦值0；再通過(guò)另一for循環(huán)，根據(jù)輸入結(jié)點(diǎn)的關(guān)系，將矩陣中相應(yīng)的元素賦值，有關(guān)系則為1；linjiej

19、uzhen()輸出鄰接矩陣；通過(guò)for循環(huán)，依次按格式輸出鄰接矩陣的元素；julijuzhen()根據(jù)A的n次方矩陣及其中元素，判斷并顯示兩結(jié)點(diǎn)間的距離；調(diào)用子函數(shù)linjiejuzhen()，以確定并顯示距離為1的兩結(jié)點(diǎn)；通過(guò)for循環(huán)顯示距離為1的結(jié)點(diǎn)對(duì)；再通過(guò)一系列的for循環(huán)，計(jì)算A的n次方矩陣并顯示結(jié)果，根據(jù)其中的元素，判斷并顯示結(jié)點(diǎn)間的距離；詳細(xì)算法請(qǐng)見(jiàn)附錄相關(guān)部分的注釋；kedajuzhen()求可達(dá)矩陣；通過(guò)一系列for循環(huán)，根據(jù)公式，計(jì)算可達(dá)矩陣；通過(guò)for循環(huán)，將矩陣中不為0的一切值賦為1以生成可達(dá)矩陣并顯示；通過(guò)for循環(huán)和if條件句的組合，根據(jù)可達(dá)矩陣的元素特點(diǎn)，判斷圖

20、的連通性，若可達(dá)矩陣矩陣中有0，則跳出循環(huán)，顯示不可連接；根據(jù)判斷結(jié)果顯示內(nèi)容，不可連通或可連通；五、實(shí)驗(yàn)數(shù)據(jù)及結(jié)果分析實(shí)驗(yàn)一：正確輸入結(jié)果錯(cuò)誤控制非運(yùn)算與運(yùn)算或運(yùn)算蘊(yùn)含運(yùn)算等值運(yùn)算帶括號(hào)運(yùn)算實(shí)驗(yàn)二：等價(jià)關(guān)系計(jì)算錯(cuò)誤控制計(jì)算關(guān)系r和它的關(guān)系矩陣，以及計(jì)算出的商集輸入不是等價(jià)關(guān)系實(shí)驗(yàn)三：輸入界面輸入無(wú)向圖的邊建立圖的鄰接矩陣計(jì)算節(jié)點(diǎn)間的距離判斷圖的連通性輸出圖的連通支六、源程序清單實(shí)驗(yàn)一：exp1a.cpp#include <iostream>using namespace std;int main()int p=-1,q=-1;int a3; start:cout<<&

21、quot;請(qǐng)輸入p的值（0或1），輸入空格，再輸入q的值（0或1）"<<endl;cin>>p;cin>>q;if(p=0|p=1)&&(q=0|q=1) a0=p&&q;a1=p|q;a2=(!p)|q; a3=(!p)|q)&&(!q)|p); else cout<<"輸入有誤，請(qǐng)重新輸入"<<endl;goto start; cout<<"nn合?。簆/q="<<a0<<endl; cout<

22、;<"nn析?。簆/q="<<a1<<endl; cout<<"nn條件：p->q="<<a2<<endl; cout<<"nn雙條件：p<->q="<<a3<<endl;test1bc.c#include "stdio.h"#include "stdlib.h"#include "string.h"#include "conio.h"#

23、include "math.h"#define N 50void panduan(int bN,int f);/賦值函數(shù)int tkh (char szN, char ccuN, int icuN, int h0);/分級(jí)運(yùn)算函數(shù)int fkh (char szN, char ccuN, int icuN, int h0);/主運(yùn)算函數(shù)main() int i1,i2,d=1,icuN,kh=0,jg,j=0,h0;/icuN用于存放變量值,kh括號(hào)計(jì)數(shù),jg存放結(jié)果 int bj=0,hqN,h=0,x=0,xqN;/hqN存放合取結(jié)果xqN存放析取結(jié)果 char szN

24、,ccuN,sz0N,s;/szN存放式子,ccuN存放變量,sz0N也是用于存放式子hq0=-1;xq0=-1;printf("* *n"); printf("* (運(yùn)算真值表，主范式，支持括號(hào)) *n");printf("* *n"); printf("* 用!表示非 *n"); printf("* 用&表示與 *n"); printf("* 用|表示或 *n"); printf("* 用表示蘊(yùn)含 *n"); printf("* 用表

25、示等值 *n");printf("* *n");printf("*nn"); printf("請(qǐng)輸入一個(gè)合法的命題公式:n");/輸入式子 gets(sz);/讀取式子 strcpy(sz0,sz);/復(fù)制式子for(i1=0;i1<strlen(sz);i1+) if(szi1=')' | szi1='(')/存儲(chǔ)括號(hào)數(shù)量kh+;if(szi1>='a' && szi1<='z' | szi1>='A'

26、&& szi1<='Z') for(i2=0;i2<j;i2+) /判斷并儲(chǔ)存變量。 if(ccui2=szi1)/去除重復(fù)變量 d=0;if(d=1) ccuj=szi1;j+; d=1; printf("n該式子中的變量個(gè)數(shù)為：%dn",j);/輸出變量個(gè)數(shù) h0=j; printf("n輸出真值表如下：n n"); /輸出真值表表頭for(i1=0;i1<h0;i1+)printf(" %c ",ccui1);printf(" ");puts(sz);prin

27、tf("n"); for(i1=0;i1<j;i1+) /先將所有的變量賦值為零。icui1=0; for(i2=0;i2<j;i2+)/輸出真值表前項(xiàng)printf(" %d ",icui2); jg=tkh(sz,ccu,icu,h0); /用函數(shù)求結(jié)果 if(jg=0)/結(jié)果為0，合取加1hqh+=bj; else /否則，析取加1xqx+=bj; printf(" %dn",jg);/輸出運(yùn)算結(jié)果strcpy(sz,sz0);for(i1=0;i1<(int)pow(2,j)-1;i1+) +bj; pandu

28、an(icu,j-1); /賦值變量jg=tkh(sz,ccu,icu,h0); if(jg=0)/結(jié)果為0，合取加1hqh+=bj; else /否則，析取加1xqx+=bj; strcpy(sz,sz0); /恢復(fù)被修改的數(shù)組。for(i2=0;i2<j;i2+) printf(" %d ",icui2);/輸出真值表前項(xiàng) printf(" %dn",jg);/輸出運(yùn)算結(jié)果 if(hq0=-1)/不存在合取范式時(shí) printf("n該命題公式不存在主合取范式。n");else printf("n該命題公式的主合取范

29、式：nt");for(i1=0;i1<h;i1+) if (i1>0)/判斷并添加符號(hào)printf("/"); printf("M(%d)",hqi1); /輸出主合取范式 if(xq0=-1)/不存在析取范式時(shí) printf("n該命題公式不存在主析取范式。n");else printf("nn該命題公式的主析取范式：nt");for(i1=0;i1<x;i1+) if (i1>0)/判斷并添加符號(hào)printf("/"); printf("m(%d)

30、",xqi1);/輸出主析取范式 printf("n"); printf("n歡迎下次再次使用！n ");/結(jié)束getch();void panduan(int bN,int f) / 二進(jìn)制賦值。int i; i=f; if(bf=0)/加1bf=1; else/進(jìn)位 bf=0;panduan(b,-i); int tkh (char szN,char ccuN,int icuN,int h0)/分級(jí)運(yùn)算函數(shù)int i,j,h,s,kh=0,wzN,a; char xs1N,ckhN; /xs1用來(lái)保存括號(hào)內(nèi)的字符 ckh用來(lái)保存括號(hào)。 s=

31、strlen(sz);for(i=0;i<s;i+) if(szi='(' | szi=')')/判斷括號(hào) wzkh=i;/存儲(chǔ)括號(hào)位置 ckhkh=szi;/存儲(chǔ)括號(hào)類型kh+; if(kh=0) return fkh(sz,ccu,icu,h0);/如果無(wú)括號(hào)，直接運(yùn)行else for(i=0;i<kh;i+) if(ckhi=')')/找到第一個(gè)）break; for(j=wzi-1+1,h=0;j<wzi;j+,h+) /存儲(chǔ)最內(nèi)級(jí)括號(hào)中的內(nèi)容xs1h=szj;xs1h='0' a=fkh(xs1,ccu

32、,icu,h0);/運(yùn)行最內(nèi)級(jí)括號(hào)的式子，得到結(jié)果 if(a=1)/判斷并存儲(chǔ)結(jié)果szwzi-1=1;elseszwzi-1=-2; for(j=wzi-1+1;j<s+wzi-1-wzi;j+)/將括號(hào)后內(nèi)容前移szj=szj+wzi-wzi-1;szj='0' return tkh(sz,ccu,icu,h0);/循環(huán)執(zhí)行 int fkh(char szN,char ccuN,int icuN,int h0)/主運(yùn)算函數(shù) int i,h=0,j=0,j1=0,j2=0,j3=0,j4=0,j5=0,i1,i2,p1=-1,p2=-1,s;char dtN; s=str

33、len(sz);if(s=1) if(sz0=-2)/判斷是否是最后一項(xiàng)return 0;else return 1; /1 就是sz0的值、else for(i=0;i<s-j;i+) /先處理非if(szi='!')for(i1=0;i1<h0;i1+) if(szi+1=ccui1)/將變量賦值并給P1 p1=icui1; if(szi+1=-2)/如果是前運(yùn)算結(jié)果的0，則P1等于0 p1=0; if(p1=-1)/如果是數(shù)字，直接給P1 p1=szi+1;dtj+2=!p1;/非運(yùn)算szi=j+2;j+; p1=0;for(i1=i+1;i1<s-j;

34、i1+) szi1=szi1+1;/將后續(xù)式子前移一項(xiàng) p1=-1; j1=j; for(i=0;i<s-j1-2*j2;i+) / 處理與if(szi='&')for(i1=0;i1<h0;i1+) if(szi-1=ccui1)/將變量賦值并給P1 p1=icui1; if(szi+1=ccui1)/將變量賦值并給P2 p2=icui1; for(i2=2;i2<j+2;i2+) if(szi-1=i2) /如果為前計(jì)算結(jié)果，將結(jié)果賦值并給P1 p1=dti2; if(szi+1=i2) /如果為前計(jì)算結(jié)果，將結(jié)果賦值并給P2 p2=dti2; i

35、f(szi-1=-2)/如果是前運(yùn)算結(jié)果的0，則P1等于0 p1=0; if(szi+1=-2)/如果是前運(yùn)算結(jié)果的0，則P2等于0 p2=0; if(p1=-1) /如果是數(shù)字，直接給P1 p1=(int)(szi-1); if(p2=-1)/如果是數(shù)字，直接給P2 p2=(int)(szi+1); dtj+2=p1 && p2;/與運(yùn)算szi-1=j+2;j+;j2+; p1=-1; p2=-1; for(i1=i;i1<s-j1-2*j2;i1+)/將后續(xù)式子前移兩項(xiàng)szi1=szi1+2; i=i-1; for(i=0;i<s-j1-2*j2-2*j3;i+

36、) / 處理或。if(szi='|') for(i1=0;i1<h0;i1+) if(szi-1=ccui1)/將變量賦值并給P1 p1=icui1; if(szi+1=ccui1)/將變量賦值并給P2 p2=icui1;for(i2=2;i2<j+2;i2+) if(szi-1=i2) /如果為前計(jì)算結(jié)果，將結(jié)果賦值并給P1 p1=dti2; if(szi+1=i2)/如果為前計(jì)算結(jié)果，將結(jié)果賦值并給P2 p2=dti2; if(szi-1=-2)/如果是前運(yùn)算結(jié)果的0，則P1等于0 p1=0; if(szi+1=-2)/如果是前運(yùn)算結(jié)果的0，則P2等于0 p2=

37、0; if(p1=-1)/如果是數(shù)字，直接給P1 p1=szi-1; if(p2=-1)/如果是數(shù)字，直接給P2 p2=szi+1; dtj+2=p1 | p2;/或運(yùn)算szi-1=j+2;j+;j3+; p1=-1; p2=-1; for(i1=i;i1<s-j1-2*j2-2*j3;i1+)/將后續(xù)式子前移兩項(xiàng)szi1=szi1+2;i-; for(i=0;i<s-j1-2*j2-2*j3-2*j4;i+) / 處理蘊(yùn)含。if(szi='') for(i1=0;i1<h0;i1+) if(szi-1=ccui1)/將變量賦值并給P1 p1=icui1; i

38、f(szi+1=ccui1)/將變量賦值并給P2 p2=icui1;for(i2=2;i2<j+2;i2+) if(szi-1=i2) /如果為前計(jì)算結(jié)果，將結(jié)果賦值并給P1 p1=dti2; if(szi+1=i2) /如果為前計(jì)算結(jié)果，將結(jié)果賦值并給P2 p2=dti2;if(szi-1=-2)/如果是前運(yùn)算結(jié)果的0，則P1等于0 p1=0;if(szi+1=-2)/如果是前運(yùn)算結(jié)果的0，則P2等于0 p2=0;if(p1=-1)/如果是數(shù)字，直接給P1 p1=szi-1;if(p2=-1)/如果是數(shù)字，直接給P2 p2=szi+1;dtj+2=!p1 | p2;/蘊(yùn)含運(yùn)算szi-1

39、=j+2;j+;j4+;p1=-1;p2=-1;for(i1=i;i1<s-j1-2*j2-2*j3-2*j4;i1+)/將后續(xù)式子前移兩項(xiàng)szi1=szi1+2;i-; for(i=0;i<s-j1-2*j2-2*j3-2*j4-2*j5;i+) / 處理等值。if(szi='') for(i1=0;i1<h0;i1+) if(szi-1=ccui1)/將變量賦值并給P1 p1=icui1; if(szi+1=ccui1)/將變量賦值并給P2 p2=icui1;for(i2=2;i2<j+2;i2+) if(szi-1=i2) /如果為前計(jì)算結(jié)果，將結(jié)

40、果賦值并給P1 p1=dti2; if(szi+1=i2) /如果為前計(jì)算結(jié)果，將結(jié)果賦值并給P2 p2=dti2; if(szi-1=-2)/如果是前運(yùn)算結(jié)果的0，則P1等于0 p1=0; if(szi+1=-2)/如果是前運(yùn)算結(jié)果的0，則P2等于0 p2=0; if(p1=-1)/如果是數(shù)字，直接給P1 p1=szi-1; if(p2=-1)/如果是數(shù)字，直接給P2 p2=szi+1;dtj+2=(!p1 | p2)&&(!p2 | p1);/等值運(yùn)算szi-1=j+2;j+;j5+; p1=-1; p2=-1; for(i1=i;i1<s-j1-2*j2-2*j3-

41、2*j4-2*j5;i1+)/將后續(xù)式子前移兩項(xiàng)szi1=szi1+2;i-; return dtj+1;/返回結(jié)果 實(shí)驗(yàn)二：exp2a.cpp#include <iostream>using namespace std;int 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;cout<<"請(qǐng)輸入有限集合的元素個(gè)數(shù)："<<endl;cin>>n;if(n<=0|n

42、>100)cout<<"輸入錯(cuò)誤，請(qǐng)重新輸入！"<<endl;cin>>n;for(k=1;k<=n;k+)sum=sum+S(n,k); /*調(diào)用遞歸函數(shù)*/cout<<"給定"<<n<<"元有限集上等價(jià)關(guān)系的數(shù)目為:"<<sum<<endl;test2c.c# include "stdio.h"# include "ctype.h"# include "string.h&qu

43、ot;# include "stdlib.h"# include "math.h"#define MAX 20#define STU struct stuint MMAXMAX; /*存放關(guān)系矩陣*/char AMAX; /*存放有限集合*/char BMAX; /*存放等價(jià)關(guān)系*/int i,j,p,q,n,l,k,t,y;STUint m;char tree20;STU equ20;void make_set(STU equ,char A,int n) /*使集合A中的元素自成一個(gè)子集*/int i;for(i=0;i<n;i+) equi.m

44、=1;equi.tree0=Ai;equi.tree1='0' find_set(int j) /*查找二元組中元素所屬集合*/int i;for(i=0;i<j;i+) if(Mji) break; if(i=j) return -1; elsereturn 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&

45、#39;void disp(STU equ,int n) /*輸出商集*/int i;printf("A/R= ");for(i=0;i<n;i+)if(equi.m!=0)printf("%s ",equi.tree);printf(" ");void caculate(STU equ,char A,int n) /*計(jì)算商集*/int p; make_set(equ,A,n);for(i=0;i<n;i+) p = find_set(i);if(p!=-1)unionit(equ,p,i); disp(equ,n);

46、/*調(diào)用輸出商集函數(shù)*/void getguanxi() /*獲得關(guān)系R并輸出顯示*/gets(B);l=strlen(B);printf("您輸入的關(guān)系為：n");printf("R= ");for(j=0;j<l;j=j+2)printf("<");printf("%c,",Bj);printf("%c",Bj+1);printf("> "); printf(" n");void translate() /*轉(zhuǎn)換為關(guān)系矩陣的函數(shù)*/i

47、nt p,q,i=0,j;while(Bi!='0')if(Bi>='A')&&(Bi<='Z'|Bi>='a')&&(Bi<='z')for(j=0;j<n;j+) if (Bi=Aj) p=j;break; i+;while(Bi!='0') for(j=0;j<n;j+)if (Bi=Aj) q=j; Mpq=1;break;if(j=n)i+;else i+;break; elsei+;void display() /*輸出

48、關(guān)系矩陣函數(shù)*/int i,j;for(i=0;i<n;i+)for(j=0;j<n;j+)printf("%2d",Mij);printf("n");int zifan() /*判斷輸入的關(guān)系是否自反函數(shù)*/int count = 0;for(i=0;i<n;i+)if(Mii=1)count+;if(count = n)return 1;elsereturn 0;int duichen() /*判斷輸入的關(guān)系是否對(duì)稱函數(shù)*/for(i=0;i<n;i+)for(j=i+1;j<n;j+)if(Mij!=Mji)retur

49、n 0;printf("n");return 1;int chuandi() /*判斷輸入的關(guān)系是否傳遞函數(shù)*/int flag=1;for(i=0;i<n;i+)if(flag=0)break;for(j=0;j<n;j+)if(flag=0)break;for(k=0;k<n;k+)if(Mij=1&&Mjk=1&&Mik!=1)flag=0;break;return flag;void clearM() /*第一次輸入不是等價(jià)關(guān)系,重新輸入前矩陣清零*/int i,j;for(i=0;i<n;i+)for(j=0;j<n;j+) Mji = 0;void main()printf("請(qǐng)輸入一個(gè)有限集合(a-z/A-Z):n");gets(A);n=strlen(A);printf("