離散數(shù)學(xué)實驗報告

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

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

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

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

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

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

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

8、等值運算返回結(jié)果主運算函數(shù)分級運算函數(shù)實驗二：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ù)上式，定義一個遞歸函數(shù)S（n,k），然后對k從1到n，求取sum=S（n，k），sum的值就是給定n

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

10、在集合中的位置，例如<a，b>，若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)系。判斷了所輸入的關(guān)系為等價關(guān)系后就可以求其商集了，由于商集即等價類構(gòu)成

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

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

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

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

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

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

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

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

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

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

21、quot;請輸入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<<"輸入有誤，請重新輸入"<<endl;goto start; cout<<"nn合取：p/q="<<a0<<endl; cout<

22、;<"nn析取：p/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);/分級運算函數(shù)int fkh (char szN, char ccuN, int icuN, int h0);/主運算函數(shù)main() int i1,i2,d=1,icuN,kh=0,jg,j=0,h0;/icuN用于存放變量值,kh括號計數(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("* (運算真值表，主范式，支持括號) *n");printf("* *n"); printf("* 用!表示非 *n"); printf("* 用&表示與 *n"); printf("* 用|表示或 *n"); printf("* 用表示蘊含 *n"); printf("* 用表

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

26、&& szi1<='Z') for(i2=0;i2<j;i2+) /判斷并儲存變量。 if(ccui2=szi1)/去除重復(fù)變量 d=0;if(d=1) ccuj=szi1;j+; d=1; printf("n該式子中的變量個數(shù)為：%dn",j);/輸出變量個數(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+)/輸出真值表前項printf(" %d ",icui2); jg=tkh(sz,ccu,icu,h0); /用函數(shù)求結(jié)果 if(jg=0)/結(jié)果為0，合取加1hqh+=bj; else /否則，析取加1xqx+=bj; printf(" %dn",jg);/輸出運算結(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);/輸出真值表前項 printf(" %dn",jg);/輸出運算結(jié)果 if(hq0=-1)/不存在合取范式時 printf("n該命題公式不存在主合取范式。n");else printf("n該命題公式的主合取范

29、式：nt");for(i1=0;i1<h;i1+) if (i1>0)/判斷并添加符號printf("/"); printf("M(%d)",hqi1); /輸出主合取范式 if(xq0=-1)/不存在析取范式時 printf("n該命題公式不存在主析取范式。n");else printf("nn該命題公式的主析取范式：nt");for(i1=0;i1<x;i1+) if (i1>0)/判斷并添加符號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)/分級運算函數(shù)int i,j,h,s,kh=0,wzN,a; char xs1N,ckhN; /xs1用來保存括號內(nèi)的字符 ckh用來保存括號。 s=

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

32、,icu,h0);/運行最內(nèi)級括號的式子，得到結(jié)果 if(a=1)/判斷并存儲結(jié)果szwzi-1=1;elseszwzi-1=-2; for(j=wzi-1+1;j<s+wzi-1-wzi;j+)/將括號后內(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)/主運算函數(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)/判斷是否是最后一項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)/如果是前運算結(jié)果的0，則P1等于0 p1=0; if(p1=-1)/如果是數(shù)字，直接給P1 p1=szi+1;dtj+2=!p1;/非運算szi=j+2;j+; p1=0;for(i1=i+1;i1<s-j;

34、i1+) szi1=szi1+1;/將后續(xù)式子前移一項 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) /如果為前計算結(jié)果，將結(jié)果賦值并給P1 p1=dti2; if(szi+1=i2) /如果為前計算結(jié)果，將結(jié)果賦值并給P2 p2=dti2; i

35、f(szi-1=-2)/如果是前運算結(jié)果的0，則P1等于0 p1=0; if(szi+1=-2)/如果是前運算結(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;/與運算szi-1=j+2;j+;j2+; p1=-1; p2=-1; for(i1=i;i1<s-j1-2*j2;i1+)/將后續(xù)式子前移兩項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) /如果為前計算結(jié)果，將結(jié)果賦值并給P1 p1=dti2; if(szi+1=i2)/如果為前計算結(jié)果，將結(jié)果賦值并給P2 p2=dti2; if(szi-1=-2)/如果是前運算結(jié)果的0，則P1等于0 p1=0; if(szi+1=-2)/如果是前運算結(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;/或運算szi-1=j+2;j+;j3+; p1=-1; p2=-1; for(i1=i;i1<s-j1-2*j2-2*j3;i1+)/將后續(xù)式子前移兩項szi1=szi1+2;i-; for(i=0;i<s-j1-2*j2-2*j3-2*j4;i+) / 處理蘊含。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) /如果為前計算結(jié)果，將結(jié)果賦值并給P1 p1=dti2; if(szi+1=i2) /如果為前計算結(jié)果，將結(jié)果賦值并給P2 p2=dti2;if(szi-1=-2)/如果是前運算結(jié)果的0，則P1等于0 p1=0;if(szi+1=-2)/如果是前運算結(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;/蘊含運算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ù)式子前移兩項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) /如果為前計算結(jié)果，將結(jié)

40、果賦值并給P1 p1=dti2; if(szi+1=i2) /如果為前計算結(jié)果，將結(jié)果賦值并給P2 p2=dti2; if(szi-1=-2)/如果是前運算結(jié)果的0，則P1等于0 p1=0; if(szi+1=-2)/如果是前運算結(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);/等值運算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ù)式子前移兩項szi1=szi1+2;i-; return dtj+1;/返回結(jié)果 實驗二：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<<"請輸入有限集合的元素個數(shù)："<<endl;cin>>n;if(n<=0|n

42、>100)cout<<"輸入錯誤，請重新輸入！"<<endl;cin>>n;for(k=1;k<=n;k+)sum=sum+S(n,k); /*調(diào)用遞歸函數(shù)*/cout<<"給定"<<n<<"元有限集上等價關(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; /*存放等價關(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中的元素自成一個子集*/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) /*計算商集*/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)系是否對稱函數(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() /*第一次輸入不是等價關(guān)系,重新輸入前矩陣清零*/int i,j;for(i=0;i<n;i+)for(j=0;j<n;j+) Mji = 0;void main()printf("請輸入一個有限集合(a-z/A-Z):n");gets(A);n=strlen(A);printf("