離散數(shù)學實驗報告--四個實驗!!!

1、word可編輯 離散數(shù)學 課程設計學 院 計算機學院學生姓名 學 號 指導教師 評閱意見 提交日期 2022 年 11 月 25 日引言 離散數(shù)學 是現(xiàn)代數(shù)學的一個重要分支，也是計算機科學與技術，電子信息技術，生物技術等的核心根底課程。它是研究離散量如整數(shù)、有理數(shù)、有限字母表等的數(shù)學結構、性質及關系的學問。它一方面充分地描述了計算機科學離散性的特點，為學生進一步學習算法與數(shù)據(jù)結構、程序設計語言、操作系統(tǒng)、編譯原理、電路設計、軟件工程與方法學、數(shù)據(jù)庫與信息檢索系統(tǒng)、人工智能、網(wǎng)絡、計算機圖形學等專業(yè)課打好數(shù)學根底；另一方面，通過學習離散數(shù)學課程，學生在獲得離散問題建模、離散數(shù)學理論、計算機求解方

2、法和技術知識的同時，還可以培養(yǎng)和提高抽象思維能力和嚴密的邏輯推理能力，為今后愛念族皮及用計算機處理大量的日常事務和科研工程、從事計算機科學和應用打下堅實根底。特別是對于那些從事計算機科學與理論研究的高層次計算機人員來說，離散數(shù)學更是必不可少的根底理論工具。實驗一、 編程判斷一個二元關系的性質是否具有自反性、反自反性、對稱性、反對稱性和傳遞性一、前言引語：二元關系是離散數(shù)學中重要的容。因為事物之間總是可以根據(jù)需要確定相應的關系。從數(shù)學的角度來看，這類聯(lián)系就是某個集合中元素之間存在的關系。二、數(shù)學原理：自反、對稱、傳遞關系設A和B都是的集合，R是A到B的一個確定的二元關系，那么集合R就是A

3、5;B的一個合于R=(x,y)A×B|xRy的子集合設R是集合A上的二元關系：自反關系：對任意的xA,都滿足<x,x>R，那么稱R是自反的，或稱R具有自反性，即R在A上是自反的Û("x)(xA)(<x,x>R)=1對稱關系：對任意的x,yA，如果<x,y>R，那么<y,x>R，那么稱關系R是對稱的，或稱R具有對稱性，即R在A上是對稱的 Û ("x)("y)(xA) (yA)(<x,y>R)(<y,x>R)=1傳遞關系：對任意的x,y,zA，如果<x,y>

4、;R且<y,z>R，那么<x,z>R，那么稱關系R是傳遞的，或稱R具有傳遞性，即R在A上是傳遞的Û ("x)("y)("z)(xA)(yA)(zA)(<x,y>R)(<y,z>R)(<x,z>R)=1 三、實驗原理：通過二元關系與關系矩陣的聯(lián)系，可以引入N維數(shù)組，以數(shù)組的運算來實現(xiàn)二元關系的判斷。圖示：性質關系矩陣特性自反性主對角線元素全為1反自反性主對角線元素全為0對稱性對稱矩陣反對稱性非主對角線上的元素等于1且與之對稱的元素等于0傳遞性矩陣M*M中1所在的位置，M中與之相對應位置鮮紅都為1四

5、、實驗環(huán)境：Windows 7 Ultimate DEV C+五、實驗語言：C 語言六、程序源代碼：#include"stdio.h"#define N 4main() int i,j,k; int f,e,z; int MNN; printf("判斷R是否為自反關系、對稱關系、是否可傳遞？n"); printf("請輸入一個4*4的矩陣。n"); for(i=0;i<N;i+) /*輸入一個4*4的矩陣*/ for(j=0;j<N;j+) scanf("%d",&Mij); for(i=0;i

6、<N;i+) for(j=0;j<N;j+) printf("%4d",Mij); printf("n"); for(i=0;i<N;i+) if(Mii=1)/判斷自反性 if(i=N-1 e=0; else ; else if(Mii=0)/判斷反自反性 if(i=N-1) e=1; else ; else e=2; break; for(i=0;i<N;i+) for(j=0;j<N;j+) if(Mij!=Mji)/判斷對稱性 f=1; break; for(i=0;i<N;i+) for(j=0;j<N

7、;j+) if(Mij=1)/判斷反對稱性 if(Mji=0) if(i=(N-1)&&j=N-1) f=0; else break; if(f!=0&&f!=1) f=2; for(i=0;i<N;i+)/判斷可傳遞性 for(j=0;j<N;j+) if(Mij=1) continue; else for(k=0;k<N;k+) if(Mik*Mki=0) continue; else z=0; if(e=0) printf("關系R是自反關系n"); else if(e=1) printf("關系R是反自反關

8、系n"); else if(e=2) printf("關系R是反自反關系n"); if(f=0) printf("關系R是反對稱關系n"); else if(f=1) printf("關系R不是對稱關系n"); else if(f=2) printf("關系R是對稱關系n"); if(z=0) printf("關系R是不可傳遞關系n"); else printf("關系R是可傳遞關系n"); system("PAUSE");七、程序運行截圖：i、

9、程序啟動截圖： ii、程序輸入截圖：iii、程序運行結果截圖:八、實驗總結：實驗簡潔高效地判斷二元關系的性質。實驗二、編程求一個二元關系的自反閉包、對稱閉包、傳遞閉包一、前言引語一個二元關系可能具有某種性質，也可能不具有這種性質?，F(xiàn)在討論怎樣使一個二元關系變成具有指定性質的新關系，并且還要滿足最小性條件。二、數(shù)學原理 自反閉包、對稱閉包、傳遞閉包設R是定義在A上的二元關系，假設存在A上的關系R滿足：1) R是自反的(或對稱的、或可傳遞的)，2) RÍ R， 3) 對A上任何其它滿足 1和 2的關系R，都有： RÍ R。 那么稱R為R的自反閉包(或對稱閉包、或傳遞閉包)，分別

10、記為r(R)、(s(R)和t(R)。三、實驗原理 Warshall算法的根本思想對每個結點從第一列開始，找出所有具有到此結點的有向邊的結點即該列中元素為1的所在行的結點，再將這些結點所在行同該結點所在行進行邏輯加后作為這些結點所在的新行添加新的有向邊反映了如果這些結點沒有到其它結點的有向邊，但有到該結點的有向邊，再通過該結點間接到達其它結點，根據(jù)傳遞閉包的定義，這些結點就必然有一條有向邊到達其它結點。§ 設R是集合上的二元關系,Mr是R的關系矩陣§ (1)置新矩陣A:=Mr § (2)置(列) j:=1 § (3) 對所有的i(1in) 如A(i,j)=

11、1,那么對k=1,2,n A(i,k):=A(i,k) Ú A(j,k)§ (即將A的第i行與A的第j行進行邏輯加后送回A的第i行)§ (4)j:=j+1§ (5)如jn轉(3),否那么停止。四、實驗環(huán)境：Windows 7 Ultimate DEV C+五、實驗編程語言： C語言六、實驗程序源代碼/source file: War.cpp#include<stdio.h>void War(int m,int n) int i,j,k;設置臨時變量int a = 0, b = 0;設置臨時變量int arr1010;for(a = 0; a

12、< m; +a)printf("請輸入矩陣第%d行元素:",a);for(b = 0; b < n; +b)scanf("%d",&arrab);printf("n");for(i = 0; i < m; i+)for( j= 0; j < m; j+)if(arrji = 1)for(k = 0;k < n; k+)arrjk=arrik | arrjk;printf("所得的可傳遞閉包關系矩陣是：n");for(i = 0;i < m; +i)for(j = 0;j

13、< n; +j)printf("%d ",arrij);printf("n");/file: test.cpp#include<stdio.h>void main() printf("利用Warshall算法求二元關系的可傳遞閉包n");void War(int , int);int m, n;printf("請輸入矩陣的行數(shù)(必須小于10：");scanf("%d", &m);printf("請輸入矩陣的列數(shù)(必須小于10：");scanf(&qu

14、ot;%d", &n);War(m, n);system ( “PAUSE);return 0;七、實驗截圖i.程序啟動畫面：ii.輸入關系矩陣的行數(shù)和列數(shù)以及關系矩陣的各個元素。 iii.得出結果，并打印在屏幕上。八、實驗總結如果當一個集合的元素的個數(shù)n很大時，求在該集合上的二元關系的可傳遞閉包是非常復雜的。幸好Warshall算法給我們提供了一個求二元關系的可傳遞閉包的高效方法。結合計算機程序技術，利用warshall算法我們可以輕松的求出一個二元關系的可傳遞閉包。本次實驗便捷高效地到達了實驗的目的。實驗三、編程求一個二元關系的復合運算一、實驗引語：關系作為集合，除了具有

15、一般的運算功能外，還具有自身獨特的復合運算。二、數(shù)學原理設R是集合A到B的二元關系，S是集合B到C的二元關系，那么R。S = x，z A C|(y B)(x，y) R y，zS稱為R和S的復合關系。三、實驗原理：矩陣的運算四、實驗環(huán)境：Windows 7 Ultimate DEV C+五、實驗語言：C語言六、實驗程序源代碼#include"stdio.h"#include"string.h"#define M 3#define N 3#define P 3main() int i,j,k,x; char p; int ANM,BMP,CNP; print

16、f("關系的復合運算n"); printf(“請輸入一個3*3的矩陣); printf("A:n"); for(i=1;i<=N;i+) for(j=1;j<=M;j+) scanf("%4d",&Aij); printf("n"); printf(“請輸入一個3*3的矩陣); printf("B:n"); for(i=1;i<=M;i+) for(j=1;j<=P;j+) scanf("%4d",&Bij); printf("

17、;n"); printf("經(jīng)過復合運算后得到C:n"); for(i=1;i<=N;i+) for(j=1;j<=P;j+) x=0; for(k=1;k<=M;k+) x=x+Aik*Bkj; if(x>0) Cij=1; else Cij=0; printf("%4d",Cij); printf("n"); system("PAUSE"); return 0;七、程序運行截圖：i、程序啟動截圖：ii、程序輸入截圖:iii、程序運行結果截圖：八、實驗總結：本實驗利用計算機技術，

18、快速便捷地實現(xiàn)了關系的運算，極大提高了效率。實驗四：編程實現(xiàn)拓撲排序算法一、實驗引言一個復雜的工程通?？梢苑纸獬梢唤M小任務的集合，完成這些小任務意味著整個工程的完成,，任務之間具有先后關系，任務的先后順序可用有向圖表示。二、數(shù)學原理：拓撲排序 i定義：由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。 ii實現(xiàn)方法： 從有向圖中選擇一個沒有前驅的頂點并輸出它。 從網(wǎng)中刪去該頂點并刪去從該頂點發(fā)出的全部有向邊。 重復上述兩步直到剩余的網(wǎng)中不存在沒有前驅的頂點。三、實驗原理首先對有向圖，我們采取鄰接表作為數(shù)據(jù)結構。且將表頭指針改為頭結點，其數(shù)據(jù)域存放該結點的入度，入度設為零的結

19、點即沒有前趨。在建立鄰接表輸入之前，表頭向量的每個結點的初始狀態(tài)為數(shù)據(jù)域VEX入度為零，指針域NXET為空，每輸入一條弧< J, K > 建立鏈表的一個結點，同時令k 的入度加1，因此在輸入結束時，表頭的兩個域分別表示頂點的入度和指向鏈表的第一個結點指針。在拓撲排序的過程之中，輸入入度為零即沒有前趨的頂點，同時將該頂點的直接后繼的入度減1。1、查鄰接表中入度為零的頂點，并進棧。2、當棧為空時，進行拓撲排序。a、退棧，輸出棧頂元素V。b、在鄰接表中查找Vj的直接后繼Vk，將Vk的入度減一，并令入度減至零的頂點進棧。3、假設?？諘r輸出的頂點數(shù)不是N個那么說明有向回路，否那么拓撲排序結束

20、。為建立存放入度為零的頂點的棧，不需要另分配存儲單元，即可借入入度為零的數(shù)據(jù)域。一方面，入度為零的頂點序號即為表頭結點的序號，另一方面，借用入度為零的數(shù)據(jù)域存放帶鏈棧的指針域下一個入度的頂點號。四、實驗環(huán)境：Windows 7 Ultimate DEV C+五、實驗語言：C+六、程序源代碼#include<iostream>#include<cmath>#include<cstdio>#include<algorithm>#include<stack>using namespace std;#define MAX 9999stack&

21、lt;int>mystack;int indegreeMAX;struct node int adjvex; node* next;adjMAX;int Create(node adj,int n,int m)/鄰接表建表函數(shù)，n代表定點數(shù)，m代表邊數(shù) int i; node *p; for(i=0;i<=n-1;i+) adji.adjvex=i; adji.next=NULL; for(i=0;i<=m-1;i+) cout<<"請輸入第"<<i<<"條邊:" int u,v; cin>&g

22、t;u>>v; p=new node; p->adjvex=v; p->next=adju.next; adju.next=p; return 1;void print(int n)/鄰接表打印函數(shù) int i; node *p; for(i=0;i<=n-1;i+) p=&adji; while(p!=NULL) cout<<p->adjvex<<' ' p=p->next; cout<<endl; void topsort(node adj,int n) int i; node *p; memset(indegree,0,sizeof(indegree); for(i=0;i<=n-1;i+) p=adji.next; while(p!=NULL) indegreep->adjvex+; p=p->next; for(i=0;i<=n-1;i+) if(indegreei=0) mystack.push(i); int count=