綜合訓(xùn)練項目任務(wù)書 離散數(shù)學(xué) 2

1、軟件學(xué)院綜合訓(xùn)練項目任務(wù)書課程名稱 離散數(shù)學(xué)及應(yīng)用 任課教師 開課學(xué)期 2014-2015年春季學(xué)期 遼寧工程技術(shù)大學(xué)軟件學(xué)院軟件工程系一、 綜合訓(xùn)練目的和任務(wù)離散數(shù)學(xué)及應(yīng)用是軟件工程專業(yè)的專業(yè)基礎(chǔ)核心課程之一，是計算機科學(xué)的算法理論基礎(chǔ)和軟件設(shè)計的技術(shù)基礎(chǔ)。離散數(shù)學(xué)教學(xué)不僅僅是概念、定理、公式和解題概念、定理、公式和解題，還有實驗。離散數(shù)學(xué)實驗教學(xué)，依靠計算機，讓學(xué)生主動參與發(fā)展、探究、解決問題，從中獲得離散數(shù)學(xué)研究、解決實際問題的過程體驗，產(chǎn)生成就感，進而開發(fā)學(xué)生的創(chuàng)新潛能，因而對離散數(shù)學(xué)實驗課程教學(xué)進行研究具有重要意義。利用計算機進行離散數(shù)學(xué)實驗教學(xué)，不僅是開展離散數(shù)學(xué)研究性學(xué)習(xí)的一種有

2、效方式，而且也為數(shù)據(jù)結(jié)構(gòu)及程序設(shè)計課程教學(xué)的開展提升了層次。綜合訓(xùn)練項目要求學(xué)生在完成程序設(shè)計的同時能夠?qū)懗霰容^規(guī)范的設(shè)計報告。嚴(yán)格實施綜合訓(xùn)練項目這一環(huán)節(jié)，對于學(xué)生基本程序設(shè)計素養(yǎng)的培養(yǎng)和軟件工作者工作作風(fēng)的訓(xùn)練，將起到顯著的促進作用。二、綜合訓(xùn)練基本要求1通過綜合訓(xùn)練項目，要求對離散數(shù)學(xué)中集合、關(guān)系的應(yīng)用和圖論的應(yīng)用等方面加深對課程內(nèi)容的理解與掌握。同時，在程序設(shè)計方法以及上機操作等基本技能方面受到比較系統(tǒng)的訓(xùn)練。2按照綜合訓(xùn)練項目要求，以學(xué)生為主、指導(dǎo)教師指導(dǎo)為輔，認真、獨立地完成綜合訓(xùn)練項目的任務(wù)，有問題及時主動與指導(dǎo)教師溝通。3按照教學(xué)要求學(xué)生分組完成綜合訓(xùn)練項目或獨立完成，學(xué)生要發(fā)

3、揮自主學(xué)習(xí)的能力，充分利用時間，按時完成設(shè)計內(nèi)容。4每個項目結(jié)束后，通過答辯與點評的形式進行驗收，根據(jù)點評意見，學(xué)生對項目進行整改后，提交項目報告與程序，教師給出該項目成績。三、綜合訓(xùn)練內(nèi)容綜合訓(xùn)練項目二 圖論及其應(yīng)用1目的 掌握圖論的基本思想，能夠利用計算機實現(xiàn)對圖的存儲及分析，并解決相關(guān)實際應(yīng)用問題。2 實現(xiàn)功能模塊 一、圖的存儲及應(yīng)用 1)圖的存儲； 2）對該圖中每個節(jié)點的度數(shù)進行計算; 3）求出圖中從到長度為n的通路（回路）數(shù)目，其中節(jié)點和長度通 過鍵盤輸入; 4)通過求可達性矩陣判斷該圖的連通性情況； 5)是否是歐拉圖進行判斷； 6）如果該圖是無向圖，判斷該圖是否為二分圖，并給出對應(yīng)

4、的節(jié)點集V1與 V2； 7）如果該圖是二分圖，判斷是否存在匹配，輸出其中一種匹配(*) 8）最小生成樹(*) 通過 Crim 算法，Crus算法求出相關(guān)該圖的最小生成樹 二、二叉樹的存儲及遍歷(*) 1)二叉樹的存儲(*) 2）二叉樹遍歷(前序遍歷，中序遍歷，后序遍歷)(*) 3)最優(yōu)碼的構(gòu)建(*) 帶*的部分為可選功能。 以上功能模塊演示必須有2個測試用例（一個有向圖，一個無向圖，圖中至少6個節(jié)點），相關(guān)數(shù)據(jù)操作全部對文本文件進行讀寫。 3時間安排:項目執(zhí)行過程及時間安排階段內(nèi)容時間1任務(wù)布置。第13周周三2學(xué)生查閱資料,自行分析問題,提出解決方案,教師輔導(dǎo)答疑,初步完成訓(xùn)練項目。1316周

5、課后完成3學(xué)生演示,研討及點評。第17周周一4改進原有系統(tǒng),提交優(yōu)化后的程序及項目報告,并答辯。第17周三四、成果形式（1）本課程綜合訓(xùn)練項目按小組完成,每5人一組。每組需提交項目報告及程序源代碼。（2）通過演示及答辯檢驗學(xué)生對綜合知識掌握的程度及分析問題解決問題的能力。五、評價方式1評價內(nèi)容 (1)提交綜合訓(xùn)練項目報告。 (2)提交完成的程序源代碼。 (3)演示并進行項目答辯。2評價標(biāo)準(zhǔn) (1)綜合訓(xùn)練項目報告 20%項目比例備注報告格式規(guī)范程度30%圖表質(zhì)量10%報告內(nèi)容全面、清晰程度45%總結(jié)深刻程度10%參考文獻5%(2)程序 50%項目比例備注程序運行情況25%功能實現(xiàn)情況40%算法

6、清晰程度15%人機交互、界面及菜單10%獨立完成情況10%(3)項目答辯 20% 自述邏輯是否清晰，內(nèi)容是否全面？回答問題思路是否清晰，回答是否正確?（4）工作量分值 10% 每組同學(xué)根據(jù)自己在項目中工作量,給出每個人分值,小組成員工作量分值之和為10分。 3.成績構(gòu)成每組的程序分(50分)和答辯分（20分）由學(xué)生和教師共同給出。報告成績（20分）由教師評定，每組每個人工作量得分由本組成員協(xié)商給出。五、綜合訓(xùn)練項目報告模板 綜合訓(xùn)練項目報告模板見附錄。注：有些代碼書寫的不規(guī)范，文檔也有不認真處，分享出來，僅供參考。 本人微博：Z於Z的微博_微博   &#

7、160;  源代碼文檔下載鏈接備用鏈接： 密碼：us7q軟 件 學(xué) 院 綜合訓(xùn)練項目報告書課程名稱 離散數(shù)學(xué)及應(yīng)用 項目名稱 圖論及其應(yīng)用 專業(yè)班級 軟件14-3班 組 別 第一組 成 員 董帥帥 任課教師 馮永安 二一五年 六月目 錄1 設(shè)計時間12 設(shè)計任務(wù)13 設(shè)計內(nèi)容13.1問題分析13.2程序設(shè)計23.3測試與分析33.4 代碼64 總結(jié)與展望175 參考文獻17成員分工18成績評定181 設(shè)計時間 2015年6月2號2 設(shè)計任務(wù) 實現(xiàn)存儲圖及進行圖論應(yīng)用的操作功能。3 設(shè)計內(nèi)容 掌握圖論的基本思想，能夠利用計算機實現(xiàn)對圖的存儲及分析，并解決相關(guān)實際應(yīng)用問題。 實

8、現(xiàn)功能 1) 圖的存儲; 2) 對該圖中每個節(jié)點的度數(shù)進行計算; 3) 求出圖中從Vi到Vj長度為n的通路（回路）數(shù)目，其中節(jié)點和長度通過鍵盤 輸入; 4) 通過求可達性矩陣判斷該圖的連通性情況; 5) 是否是歐拉圖進行判斷; 6) 如果該圖是無向圖，判斷該圖是否為二分圖，并給出對應(yīng)的節(jié)點集V1與V2;3.1問題分析 原始圖采用文本文檔的存儲，形式采用結(jié)點間的關(guān)系矩陣。4表示4個結(jié)點1表示有向圖(0表示無向圖)下面是矩陣。 文本示例: 圖一 矩陣文本示例 對節(jié)點的度的計算 定理 4.2.2 1) 在無向圖G=<V , E>中，與結(jié)點v(vV)關(guān)聯(lián)的邊的條數(shù)，稱為該結(jié) 點的度。 2)

9、 在有向圖G=<V , E>中，以結(jié)點v(vV)為始點引出的邊的條數(shù)(引出 度數(shù))與以結(jié)點 v(vV)為終點引出的邊的條數(shù)(引入度數(shù))之和稱為 該結(jié)點的度數(shù)。 度數(shù)計算就是： 對于關(guān)系矩陣A deg(v1)=a1n+an1-a11 deg(v2)=a2n+an2-a22 deg(v3)=a3n+an3-a33 。 deg(vi)=ain+ani-aii 求圖中從到長度為n的通路（回路）數(shù)目 通過求出鄰接矩陣A2,A3,A4,A5.中的元素下標(biāo)即Vi到Vj，元素的數(shù)值就 是長度為2,3,4,5.的通路(回路)的條數(shù) 通過求可達性矩陣判斷該圖的連通性情況 利用鄰接矩陣求出可達性矩陣，根

10、據(jù)性質(zhì) 4.4.2 進行判斷圖的連通性情況。 1. 無向線圖G是連通圖當(dāng)且僅當(dāng)它的可達性矩陣P的所有元素都均為1； 2. 有向線圖G是強連通圖當(dāng)且僅當(dāng)它的可達性矩陣P的所有元素都均為1； 3. 有向線圖G是單向連通圖當(dāng)且僅當(dāng)它的可達性矩陣P及其轉(zhuǎn)置矩陣PT經(jīng)布爾 運算加后所得矩陣P1PPT中除對主角元外的其余元素均為1； 4. 有向線圖G是弱連通圖當(dāng)且僅當(dāng)它的鄰接矩陣A及其轉(zhuǎn)置矩陣AT經(jīng)布爾加運 算后所得矩陣BAAT作為鄰接矩陣而求出的可達性矩陣PB中所有元素均為1。3.2程序設(shè)計 1）程序流程圖圖二 程序流程圖 2）數(shù)據(jù)輸入輸出與存儲 a.原始矩陣通過txt文本進行存儲 b.文本提取的矩陣信

11、息通過二維數(shù)組進行存儲 c.計算出結(jié)點的度和通路直接輸出屏幕 d.連通性的判斷，計算出的鄰接矩陣和可達性矩陣由于數(shù)據(jù)過多，直接寫入txt 文件中，連通性在屏幕顯示。3.3測試與分析3.3.1測試 圖三 讀取4結(jié)點矩陣文件 圖四 計算結(jié)點的度 圖五 計算通路(回路) 圖六 判斷連通性 圖八 讀取8結(jié)點矩陣文件及連通性判斷 圖七 4結(jié)點的鄰接矩陣和可達性矩陣 圖九 8結(jié)點的鄰接矩陣和可達性矩陣 圖十 8結(jié)點的鄰接矩陣和可達性矩陣 圖十一 8結(jié)點的鄰接矩陣和可達性矩陣3.3.2分析1. 測試的數(shù)據(jù)太少，對程序檢驗的不夠徹底2. 鄰接矩陣和可達性矩陣中的元素數(shù)值可能很大，當(dāng)這種情況發(fā)生時文本的排版不利

12、于閱讀3. 在判斷弱連通時，再次進行了計算B矩陣的鄰接矩陣和可達性矩陣，可將A和B的鄰接矩陣和可達性矩陣的算法提取出來，單獨成一個方法，提高代碼的可讀性和利用率，減少代碼量。3.4 代碼import java.io.*;import java.util.Scanner;class Graphint data = new int1010;/存儲矩陣數(shù)據(jù)int limt;/方陣的階數(shù)int isDirected;/有向還是無向File file;/用來指向jieguo.txtFileReader reader;/用于讀取矩陣字符流BufferedReader br;/從矩陣字符輸入流中讀取文本內(nèi)容

13、FileWriter writer;/寫入結(jié)果的到文件/*構(gòu)造函數(shù)初始化圖，獲得矩陣，存入到data數(shù)組中*/Graph(String path) throws IOExceptionint ch;int row; intlist;tryreader = new FileReader(path);catch(FileNotFoundException e)path=math.sc.nextLine();math.path=path;reader = new FileReader(path);br = new BufferedReader(reader);limt = br.read()-

14、9;0'/讀取方陣階數(shù)br.skip(1);isDirected = br.read()-'0'/讀取圖的有向row=0;list=0;while(ch = br.read()!= -1)/讀取矩陣if(ch>='0'&&ch<='9')datalistrow+=ch-'0'if(row=limt)list+;row=0;file = new File("D:/jieguo.txt");/創(chuàng)建存儲結(jié)果的txt文件writer = new FileWriter(file,tru

15、e);/打開寫入流/2.計算節(jié)點的度void getDegree()int i,j,count;for(i=0;i<limt;i+)count= 0;for(j=0;j<limt;j+)count+=dataij+dataji;System.out.printf("V%d節(jié)點的度為%dn", i+1, count-dataii);/3.長度為n的通路void getEntry()int length;int start,end;int i,j,k,times;System.out.printf("輸入長度:");length=math.sc.

16、nextInt();System.out.printf("輸入起始結(jié)點:V");start=math.sc.nextInt();System.out.printf("輸入起始結(jié)點:V");end=math.sc.nextInt();int temp1=new int limtlimt;int temp2=new int limtlimt;for(i=0;i<limt;i+)for(j=0;j<limt;j+)temp1ij=dataij;for(times=1;times<length;times+)for(i=0;i<limt;

17、i+)for(j=0;j<limt;j+)for(k=0;k<limt;k+)temp2ij+=temp1ik*datakj;for(i=0;i<limt;i+)for(j=0;j<limt;j+)temp1ij=temp2ij;System.out.println("V"+start+"到"+"V"+end+"的通路(回路)有"+temp1start-1end-1);/4.判斷連通性void isConnected() throws IOExceptionint i,j,k,times;i

18、nt num1,num2;int temp1=new int limtlimt;int temp2=new int limtlimt;int A = new int limtlimtlimt;/存儲鄰接矩陣int P = new intlimtlimt;writer.write("rn-rn");writer.write("Arn");for(i=0;i<limt;i+)for(j=0;j<limt;j+)temp1ij=dataij;A0ij=dataij;writer.write(String.valueOf(A0ij);writer.w

19、rite(" ");writer.write("rn");for(times=1;times<limt;times+)writer.write("rnA");writer.write(String.valueOf(times+1);writer.write("rn");for(i=0;i<limt;i+)for(j=0;j<limt;j+)for(k=0;k<limt;k+)temp2ij+=temp1ik*datakj;for(i=0;i<limt;i+)for(j=0;j<l

20、imt;j+)temp1ij=temp2ij;Atimesij=temp2ij;writer.write(String.valueOf(Atimesij);writer.write(" ");writer.write("rn");/可達性矩陣num1=0;for(i=0;i<limt;i+)for(j=0;j<limt;j+)for(times=0;times<limt;times+)if(Atimesij>0)Pij=1;break;writer.write("rnPrn");for(i=0;i<lim

21、t;i+)for(j=0;j<limt;j+)writer.write(String.valueOf(Pij);writer.write(" ");writer.write("rn");System.out.println("鄰接矩陣，可達性矩陣的結(jié)果在D:/jieguo.txt中");if(isDirected=0)/是否全為1num1=0;for(i=0;i<limt;i+)for(j=0;j<limt;j+)if(Pij=1)num1+;if(num1=limt*limt)System.out.println(

22、"無向圖是連通圖");return;elseSystem.out.println("無向圖不是連通圖");return;if(isDirected=1)/判斷是否強連通num1=0;for(i=0;i<limt;i+)for(j=0;j<limt;j+)if(Pij=1)num1+;elsebreak;if(num1=limt*limt)System.out.println("有向圖是強連通圖");return;/判斷是否單向連通num1=0;num2=0;for(i=0;i<limt;i+)for(j=0;j<

23、;limt;j+)if(j=i|i+j=limt-1)num2+;continue;if(Pij=1|Pji=1)num1+;if(Pij!=1)break;if(num1+num2=limt*limt)System.out.println("有向圖是單向連通圖");return;/判斷是否弱連通/BAATint B = new int limtlimt;for(i=0;i<limt;i+)for(j=0;j<limt;j+)if(dataij>0|dataji>0)Bij=1;/B的鄰接矩陣writer.write("rn-rn"

24、;);writer.write("Brn");for(i=0;i<limt;i+)for(j=0;j<limt;j+)temp1ij=Bij;A0ij=Bij;writer.write(String.valueOf(A0ij);writer.write(" ");writer.write("rn");for(times=1;times<limt;times+)writer.write("rnB");writer.write(String.valueOf(times+1);writer.write(

25、"rn");for(i=0;i<limt;i+)for(j=0;j<limt;j+)for(k=0;k<limt;k+)temp2ij+=temp1ik*Bkj;for(i=0;i<limt;i+)for(j=0;j<limt;j+)temp1ij=temp2ij;Atimesij=temp2ij;writer.write(String.valueOf(Atimesij);writer.write(" ");writer.write("rn");/可達性矩陣num1=0;for(i=0;i<limt

26、;i+)for(j=0;j<limt;j+)for(times=0;times<limt;times+)if(Atimesij>0)Pij=1;break;/是否全為1writer.write("rnPrn");for(i=0;i<limt;i+)for(j=0;j<limt;j+)if(Pij=1)writer.write(String.valueOf(Pij);writer.write(" ");num1+;writer.write("rn");if(num1=limt*limt)System.out

27、.println("有向圖是弱連通圖");return;elseSystem.out.println("有向圖不是連通圖");return;/5.是否是歐拉圖/void isEuler()/6.是否二分圖/void isBigraph()public class mathstatic String path;static Scanner sc = new Scanner(System.in);public static void main(String args) throws IOException, InterruptedExceptionint c

28、hoose;Graph gra;doSystem.out.println("請輸入文件地址進入菜單");path=sc.nextLine();gra=new Graph(path);domenu();choose = sc.nextInt();switch(choose)case 1:break;case 2:gra.getDegree();System.out.println("返回主菜單");Thread.sleep(1200);break;case 3:gra.getEntry();System.out.println("返回主菜單");Thread.sleep(1200);break;case 4:gra.isConnected();System.out.println("返回主菜單");gra.writer.flush(); Runtime.getRuntime().exec("notepad.exe d:/jieguo.txt");Thread.sleep(1200);break; /case 5: / break; /case 6: / br