算法程序設(shè)計(jì)實(shí)驗(yàn)報(bào)告

1、程序設(shè)計(jì)課程設(shè)計(jì)姓 名：王學(xué) 號(hào)：20100034班 級(jí)：軟件工程00班指導(dǎo)教師： 王會(huì)青 成 績(jī)：2010年6月實(shí)驗(yàn)一.構(gòu)造可以使n個(gè)城市連接的最小生成樹(shù)專(zhuān)業(yè)：_軟件工程_ 班級(jí)：_軟件 姓名：_王_ 學(xué)號(hào)：_20100034完成日期：_2010/6/26_一、【問(wèn)題描述】給定一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)，用Prim算法或Kruskal算法建立最小生成樹(shù)，并計(jì)算得到的最小生成樹(shù)的代價(jià)。1 城市間的道路網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義采用課本中給出的定義，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無(wú)窮大值。2 顯示出城市間道路網(wǎng)的鄰接矩陣。3 最小生成樹(shù)中包括的邊及其權(quán)

2、值，并顯示得到的最小生成樹(shù)的總代價(jià)。4 輸入城市數(shù)、道路數(shù)輸入城市名輸入道路信息執(zhí)行Kruskal 算法執(zhí)行 Prim 算法輸出最小生成樹(shù)二、【問(wèn)題分析】1. 抽象數(shù)據(jù)類(lèi)型結(jié)構(gòu)體數(shù)組的定義：#ifndef ADJACENCYMATRIXED/防止該頭文件被重復(fù)引用#define ADJACENCYMATRIXED/而引起的數(shù)據(jù)重復(fù)定義#define INFINITY32767/最大值#define MAX_VERTEX_NUM20/最大頂點(diǎn)個(gè)數(shù)typedef intVRType;/權(quán)值，即邊的值typedef charInfoType;/附加信息的類(lèi)型，后面使用時(shí)會(huì)定義成一個(gè)指針typedef

3、 charVertexTypeMAX_VERTEX_NUM;/頂點(diǎn)類(lèi)型typedef enum DG=1, DN, UDG, UDN GraphKind;/有向圖，有向網(wǎng)，無(wú)向圖，無(wú)向網(wǎng)typedef struct ArcCellVRTypeadj;/VRType 是頂點(diǎn)關(guān)系類(lèi)型。對(duì)無(wú)權(quán)圖，用 1 或 0 表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類(lèi)型。InfoType*info;/該弧關(guān)系信息的指針ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexTypevexsMAX_VERTEX_NUM;/頂點(diǎn)向量AdjMatrix

4、arcs;/鄰接矩陣intvexnum, arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)GraphKindkind;/圖的種類(lèi)標(biāo)志MGraph;typedef struct/普里姆算法輔助數(shù)組的定義VertexTypeadjvex;VRTypelowcost;closedgeMAX_VERTEX_NUM;#endif/結(jié)束if2 程序模塊MGraph G;/網(wǎng) G，唯一的全局變量int main(int argc, char * argv);/主函數(shù)Status LocateVex(MGraph G, VertexType v);/判斷城市 v 在網(wǎng) G 中的位置Status CreateUDN(MGr

5、aph &G);/創(chuàng)建網(wǎng) G 的鄰接矩陣void DisplayNet(MGraph G);/以鄰接矩陣的形式顯示網(wǎng) Gvoid MiniSpanTree_KRUSKAL(MGraph G);/最小生成樹(shù)的 Kruskal 算法void MiniSpanTree_PRIM(MGraph G, VertexType u);/最小生成樹(shù)的 Prim 算法Status Minimum(closedge closeEdge, int n); /Prim 算法中求下一個(gè)城市的函數(shù)void DeleteInfo(MGraph &G);/釋放堆內(nèi)存上動(dòng)態(tài)申請(qǐng)的空間3.流程圖創(chuàng)建用鄰接矩陣表示

6、的城市道路網(wǎng)輸入城市數(shù)G.vexnum、道路數(shù)G.arcnum輸入城市名G.vexsi輸入表示道路的兩個(gè)城市及道路值G.arcsij.adj返回 OKPrim算法化輔助數(shù)組closeEdgefor (i=1; i<G.vexnum; +i)求下一個(gè)城市k = Minimum(closeEdge, G.vexnum)輸出找到的道路標(biāo)記城市，避免重復(fù)輸出總耗費(fèi)4.數(shù)據(jù)類(lèi)型定義為了用鄰接矩陣表示圖 G ，先是定義二維數(shù)組的每一個(gè)元素含道路值然后在圖的定義中定義一個(gè)此二維數(shù)組的結(jié)構(gòu)成員。并且在圖中還定義一個(gè)用來(lái)存放城市的一維數(shù)組及int 型的城市數(shù)級(jí)道路數(shù)。用二維數(shù)組的兩個(gè)下標(biāo)表示道路，這兩個(gè)下

7、標(biāo)又在一位數(shù)組中對(duì)應(yīng)兩個(gè)城市。這樣就建立起了一個(gè)城市到城市之間的道路網(wǎng)。4. 程序主要模塊說(shuō)明：該程序共含5個(gè)模塊，本人負(fù)責(zé)其中2個(gè)模塊構(gòu)造：*LocateVex(MGraph G, VertexType v)*Status LocateVex(MGraph G, VertexType v);while (strcmp(G.vexsi, v) i+;返回 i；* CreateUDN*輸入城市數(shù)、道路數(shù)；for (i=0; i<城市數(shù); +i) 輸入城市名；for (i=0; i<城市數(shù); +i)for(j=0; j<城市數(shù); +j)初始化鄰接矩陣：道路值= INFINITY;

8、for (i=0; i<城市數(shù); +i)for(j=0; j<城市數(shù); +j)輸入兩個(gè)城市表示道路，輸入道路值；PRIM算法* MiniSpanTree_PRIM*void MiniSpanTree_PRIM(MGraph G, VertexType u)定義輔助數(shù)組：closedge closeEdge;初始化：strcpy(closeEdgej.adjvex, u);closeEdgej.lowcost = G.arcskj.adj;for (i=1; i<G.vexnum; +i)在其余G.vexnum-1個(gè)城市中找到離輔助數(shù)組中標(biāo)記的道路最小值；顯示找到的道路；標(biāo)記新

9、找到的城市；* Minimum*Status Minimum(closedge closeEdge, int n)在輔助數(shù)組中找到道路值最小的道路的兩點(diǎn)城市：if (closeEdgei.lowcost != 0) && (minTemp > closeEdgei.lowcost)返回該城市在 G 中的位置三、【功能實(shí)現(xiàn)】#include <iostream.h>#include <stdio.h>#include <string.h>#include <windows.h>#include "TypeDefine

10、.h"#include "AdjacencyMatrix.h"#include "InitializeFunction.h"#include "MiniSpanTree_KRUSKAL.h"#include "MiniSpanTree_PRIM.h"#include "DisplayNet.h"#include "DeleteInfo.h"MGraph G;/全局變量Gint main(int argc, char * argv);/主函數(shù)Status Locate

11、Vex(MGraph G, VertexType v);/判斷城市 v 在網(wǎng) G 中的位置Status CreateUDN(MGraph &G);/創(chuàng)建網(wǎng) G 的鄰接矩陣void DisplayNet(MGraph G);/以鄰接矩陣的形式顯示網(wǎng) Gvoid MiniSpanTree_KRUSKAL(MGraph G);/最小生成樹(shù)的 Kruskal 算法void MiniSpanTree_PRIM(MGraph G, VertexType u);/最小生成樹(shù)的 Prim 算法Status Minimum(closedge closeEdge, int n);/Prim 算法中求下一個(gè)

12、城市的函數(shù)void DeleteInfo(MGraph &G);/釋放堆內(nèi)存上動(dòng)態(tài)申請(qǐng)的空間int main(int argc, char * argv)CreateGraph(G);DisplayNet(G);MiniSpanTree_KRUSKAL(G);MiniSpanTree_PRIM(G, G.vexs0);DeleteInfo(G);cout<<endl<<endl;system("pause");return 0;/intializeFunction.hStatus CreateDG(MGraph &G)return 0

13、;Status CreateDN(MGraph &G)return 0;Status CreateUDG(MGraph &G)return 0;Status CreateUDN(MGraph &G);Status LocateVex(MGraph G, VertexType v)/判斷輸入的頂點(diǎn)v在G中的位置。/根據(jù)頂點(diǎn)的類(lèi)型，可重載此函數(shù)。目前為charint i=0;while (strcmp(G.vexsi, v) i+;return i;Status CreateGraph(MGraph &G)/采用數(shù)組（鄰接矩陣）表示法，構(gòu)造圖G.G.kind = U

14、DN;/默認(rèn)構(gòu)造無(wú)向網(wǎng)/*printf("+n");printf("|1:有向圖 2:無(wú)向圖 3:有向網(wǎng) 4:無(wú)向網(wǎng)n");printf("|請(qǐng)選擇: bb");scanf("%d", &G.kind);printf("+n");*/switch (G.kind)case DG: return CreateDG(G);/構(gòu)造有向圖Gcase DN: return CreateDN(G);/構(gòu)造有向網(wǎng)Gcase UDG: return CreateUDG(G);/構(gòu)造無(wú)向圖Gcase UD

15、N: return CreateUDN(G);/構(gòu)造無(wú)向網(wǎng)Gdefault : return ERROR;/CreateGraphStatus CreateUDN(MGraph &G)/采用數(shù)組（鄰接矩陣）表示法，構(gòu)造圖G.int i, j, k;VertexType v1, v2;VRType w;printf(" 構(gòu)造可以使N個(gè)城市連接的最小生成樹(shù)n");printf("請(qǐng)輸入城市數(shù)、道路數(shù)(至少6個(gè)城市，10條道路)：");cin>>G.vexnum>>G.arcnum;for (i=0; i<G.vexnum

16、; +i)/構(gòu)造頂點(diǎn)向量printf("請(qǐng)輸入第 %d 個(gè)城市名（共 %d 個(gè)）:", i+1, G.vexnum);cin>>G.vexsi;for (i=0; i<G.vexnum; +i)/初始化鄰接矩陣for (j=0; j<G.vexnum; +j)G.arcsij.adj = INFINITY;/G. = NULL;printf("請(qǐng)輸入一條道路連接的兩個(gè)城市名及權(quán)值:n");for (k=0; k<G.arcnum; +k)/構(gòu)造鄰接矩陣printf("共%3d條道路，第%3d條

17、道路：", G.arcnum,k+1);cin>>v1>>v2>>w;/輸入一條邊依附的頂點(diǎn)及權(quán)值i = LocateVex(G, v1);/確定v1、v2在G中的位置j = LocateVex(G, v2);G.arcsij.adj = w;/弧<v1,v2>的權(quán)值G.arcsji = G.arcsij;/置<v1,v2>的對(duì)稱(chēng)弧<v2,v1>return OK;/CreateUDN/MiniSpan Tree PRIM.hStatus Minimum(closedge closeEdge, int n)int

18、 i, flag, minTemp = INFINITY;for (i=0; i<n; +i)if (closeEdgei.lowcost != 0) && (minTemp > closeEdgei.lowcost)minTemp = closeEdgei.lowcost;flag = i;return flag;void MiniSpanTree_PRIM(MGraph G, VertexType u)/用普里姆算法從第 u 個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng) G 的最小生成樹(shù) T，輸出 T 的各條邊。/記錄從頂點(diǎn)集 U 到 V-U 的代價(jià)最小的邊的輔助數(shù)組定義見(jiàn) "A

19、djacencyMatrix.h"int i, j, k, totalCost=0;closedge closeEdge;k = LocateVex(G, u);for (j=0; j<G.vexnum; +j)/輔助數(shù)組初始化if (j != k)strcpy(closeEdgej.adjvex, u);closeEdgej.lowcost = G.arcskj.adj;cout<<"nn+n"cout<<"|用Prim算法求最小生成樹(shù)的各條邊依次為：n-"closeEdgek.lowcost = 0;/初始，U

20、=u;for (i=1; i<G.vexnum; +i)/選擇其余 G.vexnum-1 個(gè)頂點(diǎn)k = Minimum(closeEdge, G.vexnum);/求出 T 的下一個(gè)結(jié)點(diǎn)：第 k 頂點(diǎn)/此時(shí) closeEdgek.lowcost = MINcloseEdgevi.lowcost | closeEdgevi.lowcost > 0, viV-Ucout<<'<'<<closeEdgek.adjvex<<','<<G.vexsk<<'>'/輸出生成樹(shù)的

21、邊totalCost += closeEdgek.lowcost;closeEdgek.lowcost = 0;/第 k 頂點(diǎn)并入 U 集for (j=0; j<G.vexnum; +j)if (G.arcskj.adj < closeEdgej.lowcost)/新頂點(diǎn)并入 U 后重新選擇最小邊strcpy(closeEdgej.adjvex, G.vexsk);closeEdgej.lowcost = G.arcskj.adj;cout<<"n|總代價(jià)："<<totalCost<<endl;cout<<&quo

22、t;+/n"/MiniSpanTree四、【實(shí)例測(cè)試及運(yùn)行結(jié)果】五、【心得體會(huì)】通過(guò)本周的課程設(shè)計(jì)，我有不少收獲。既鞏固和加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專(zhuān)業(yè)一門(mén)重要的專(zhuān)業(yè)技術(shù)基礎(chǔ)課程，還提高了我綜合運(yùn)用本課程所學(xué)知識(shí)的能力。而且，并不是單純的看看教材就能解決我們的實(shí)際問(wèn)題，所以還要去查找各種我們所需要的資料，所以這次課程設(shè)計(jì)也培養(yǎng)了我選用參考書(shū)，查閱手冊(cè)及文獻(xiàn)資料的能力。要完成一個(gè)課程設(shè)計(jì)的課題并不是一次就能編譯成功的，中間會(huì)出現(xiàn)很多的大問(wèn)題小問(wèn)題，改錯(cuò)是個(gè)很繁瑣的問(wèn)題。通過(guò)這次課程設(shè)計(jì)培養(yǎng)了我獨(dú)立思考，深入研究，分析問(wèn)題，解決問(wèn)題的能力。在以后的學(xué)習(xí)過(guò)程中我將要注意

23、以下幾點(diǎn)：1、認(rèn)真上好專(zhuān)業(yè)實(shí)驗(yàn)課，多在實(shí)踐中鍛煉自己。2、寫(xiě)程序的過(guò)程要考慮周到，嚴(yán)密。3、在做設(shè)計(jì)的時(shí)候要有信心，有耐心，切勿浮躁。4、認(rèn)真的學(xué)習(xí)課本知識(shí)，掌握課本中的知識(shí)點(diǎn)，并在此基礎(chǔ)上學(xué)會(huì)靈活運(yùn)用。5、在課余時(shí)間里多寫(xiě)程序，熟練掌握在調(diào)試程序的過(guò)程中所遇到的常見(jiàn)錯(cuò)誤，以便能節(jié)省調(diào)試程序的時(shí)間。實(shí)驗(yàn)二：統(tǒng)計(jì)數(shù)字 專(zhuān)業(yè)：_軟件工程_ 班級(jí)：_軟件_ 姓名：_王_ 學(xué)號(hào)：_20100034完成日期：_2010/6/28_1.【問(wèn)題描述】 某次科研調(diào)查時(shí)得到了n個(gè)自然數(shù)，每個(gè)數(shù)均不超過(guò)1500000000（1.5*109）。已知不相同的數(shù)不超過(guò)10000個(gè)，現(xiàn)在需要統(tǒng)計(jì)這些自然數(shù)各自出現(xiàn)的次數(shù)，

24、并按照自然數(shù)從小到大的順序輸出統(tǒng)計(jì)結(jié)果。 2【設(shè)計(jì)需求及分析】 （1）設(shè)計(jì)要求 原始數(shù)據(jù)保存在文件count.in中，文件包含n+1行。第1行是整數(shù)n(1<=n<=200000)，表示自然數(shù)的個(gè)數(shù)；第2n+1行每行一個(gè)自然數(shù)。 結(jié)果保存在文件count的尾部，其中結(jié)果包含m行（m為n個(gè)自然數(shù)中不相同數(shù)的個(gè)數(shù)），按照自然數(shù)從小到大的順序輸出。每行輸出兩個(gè)整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù)，其間用一個(gè)空格隔開(kāi)。 (2)設(shè)計(jì)思路 首先必須有文件的打開(kāi)和關(guān)閉語(yǔ)句，將文件的內(nèi)容讀取到數(shù)組a中，然后對(duì)數(shù)組進(jìn)行排列和對(duì)比，計(jì)數(shù)。最終輸出數(shù)據(jù)和次數(shù)。并寫(xiě)入文件的尾部。 A為容納數(shù)據(jù)的數(shù)組，fope

25、n為文件打開(kāi)函數(shù)，fscanf為文件讀取函數(shù)，然后進(jìn)行冒泡排序。排序之后的內(nèi)容由while設(shè)置條件，用if進(jìn)行判斷。在不等于時(shí)，中間嵌套了一個(gè)while循環(huán)，進(jìn)行往后的排查。最后輸出數(shù)據(jù)和次數(shù)。 下面是關(guān)鍵步驟： FILE* fp=fopen("count.txt","a+"); /用只讀/的方式打開(kāi)文件 if(fp=NULL) printf("無(wú)文件"); /若沒(méi)有文件則返回1 return -1; for(i=0;i<9;i+) fscanf(fp,"%d",&ai); /讀取文件 fscanf(

26、fp,"n"); int j,t; for (i=1;i<9;i+) for(j=0;j<9-i;j+) if(aj>aj+1) /冒泡排序 t=aj; aj=aj+1; aj+1=t; for(i=0;i<9;i+) count=1; if (ai!=ai+1) printf("%dt%dn",ai,count); fprintf(fp,"%dt%dn",ai,ai); i+; 對(duì)數(shù)字的循環(huán)查找和控制條件， if(ai = ai + 1) while(ai = ai + 1) count+; i+; （3）輸

27、出輸入格式 輸入時(shí)，為豎行依此輸入文件，且為數(shù)字。且為9個(gè)以?xún)?nèi)的數(shù)字。 輸出時(shí)，分為兩行，第一列為數(shù)據(jù)，第二列為次數(shù)。 3. 【設(shè)計(jì)功能的實(shí)現(xiàn)】 #include <stdio.h> int main() int a100; /創(chuàng)建容納文件數(shù)據(jù)的數(shù)組 int i; FILE* fp=fopen("count.txt","a+"); /用只讀/的方式打開(kāi)文件 if(fp=NULL) printf("無(wú)文件"); /若沒(méi)有文件則返回1 return -1; for(i=0;i<9;i+) fscanf(fp,"

28、%d",&ai); /讀取文件 fscanf(fp,"n"); int j,t; for (i=1;i<9;i+) for(j=0;j<9-i;j+) if(aj>aj+1) /冒泡排序 t=aj; aj=aj+1; aj+1=t; printf("結(jié)果為：n數(shù)據(jù) 結(jié)果n"); int count; for(i=0;i<9;i+) count=1; if(ai!=ai+1) printf("%dt%dn",ai,count); printf(fp,"%dt%dn",ai,a

29、i); i+; if(ai = ai + 1) while(ai = ai + 1) count+; i+; printf("%dt%dn", ai, count); fprintf(fp,"%dt%dn", ai, count); fclose(fp); /關(guān)閉文件 return 0; 4【實(shí)例測(cè)試及運(yùn)行結(jié)果】 5.【心得體會(huì)】 本次實(shí)驗(yàn)使我對(duì)于文件的打開(kāi)和關(guān)閉語(yǔ)句有了更深的理解。有打開(kāi)必須有關(guān)閉。同時(shí)在這次的設(shè)計(jì)中，我學(xué)習(xí)到了用泛洪算法解決實(shí)際問(wèn)題的基本思維和步驟。使我對(duì)算法的層次性更加清楚，更加加深了對(duì)算法的理解。實(shí)驗(yàn)三送 貨專(zhuān)業(yè)：_軟件工程_ 班

30、級(jí)：_軟件 姓名：_王_ 學(xué)號(hào)：_20100034完成日期：_2010/6/26_1.【問(wèn)題描述】小明希望設(shè)計(jì)一個(gè)方案，從編號(hào)為1的交叉路口出發(fā)，每次必須沿街道去往街道另一端的路口，再?gòu)男碌穆房诔霭l(fā)去往下一個(gè)路口，直到所有的街道都經(jīng)過(guò)了正好一次。輸入數(shù)據(jù)格式輸入的第一行包含兩個(gè)整數(shù)n, m(1n10, n-1m20)，表示交叉路口的數(shù)量和街道的數(shù)量，交叉路口從1到n標(biāo)號(hào)。接下來(lái)m行，每行兩個(gè)整數(shù)a, b，表示和標(biāo)號(hào)為a的交叉路口和標(biāo)號(hào)為b的交叉路口之間有一條街道，街道是雙向的，小明可以從任意一端走向另一端。兩個(gè)路口之間最多有一條街道。輸出輸出格式如果小明可以經(jīng)過(guò)每條街道正好一次，則輸出一行包含

31、m+1個(gè)整數(shù)p1, p2, p3, ., pm+1，表示小明經(jīng)過(guò)的路口的順序，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔。如果有多種方案滿(mǎn)足條件，則輸出字典序最小的一種方案，即首先保證p1最小，p1最小的前提下再保證p2最小，依此類(lèi)推。如果不存在方案使得小明經(jīng)過(guò)每條街道正好一次，則輸出一個(gè)整數(shù)-1。測(cè)試數(shù)據(jù)一輸入：輸出：4 51 21 31 42 43 41 2 4 1 3 4輸出說(shuō)明：城市的地圖和小明的路徑如下圖所示。測(cè)試數(shù)據(jù)二輸入：輸出：4 61 21 31 42 43 42 3-1輸出說(shuō)明：城市的地圖如下圖所示，不存在滿(mǎn)足條件的路徑。2【問(wèn)題分析】 該算法使用歐拉回路，對(duì)于歐拉圖，從一個(gè)節(jié)點(diǎn)出發(fā)，從

32、某個(gè)節(jié)點(diǎn)開(kāi)始，然后查出一個(gè)從這個(gè)出發(fā)回到這個(gè)點(diǎn)的環(huán)路徑。這種方法不保證每個(gè)邊都被遍歷。如果有某個(gè)點(diǎn)的邊沒(méi)有被遍歷就讓這個(gè)點(diǎn)為起點(diǎn)，這條邊為起始邊，把它和當(dāng)前的環(huán)銜接上。這樣直至所有的邊都被遍歷。這樣，整個(gè)圖就被連接到一起了。具體步驟:1。如果此時(shí)與該點(diǎn)無(wú)相連的點(diǎn)，那么就加入路徑中2。如果該點(diǎn)有相連的點(diǎn)，那么就加入隊(duì)列之中，遍歷這些點(diǎn)，直到?jīng)]有相連的點(diǎn)。3。處理當(dāng)前的點(diǎn)，刪除走過(guò)的這條邊，并在其相鄰的點(diǎn)上進(jìn)行同樣的操作，并把刪除的點(diǎn)加入到路徑中去。4。這個(gè)其實(shí)是個(gè)遞歸過(guò)程。3【功能實(shí)現(xiàn)】#include<iostream> #include<stack> #include

33、<vector> #include<algorithm> #include<cstdio>#include <windows.h>using namespace std; const int maxn=10005; stack<int> st; vector<int> vecmaxn; bool mapmaxnmaxn; int vismaxn; int cpmaxn; int n,m; void pd(int a) cpa=1; vector<int>:iterator it; for(it=veca.beg

34、in();it!=veca.end();it+) if(!cp*it) pd(*it); void dfs(int a) vector<int>:iterator it; for(it=veca.begin();it!=veca.end();it+) if(!mapa*it) mapa*it=1; map*ita=1; dfs(*it); st.push(*it); void prt() st.push(1); while(!st.empty() /printf("%d ",st.top(); int ss=st.top(); st.pop(); printf(

35、"%d ",ss); int main() int num=0; /memset(cp,0,sizeof(cp); /memset(vis,0,sizeof(vis); /memset(map,0,sizeof(map); for(int i=0;i<maxn;+i) cpi=visi=0; scanf("%d %d",&n,&m); int a,b; for(int i=0;i<m;+i) scanf("%d %d",&a,&b); veca.push_back(b); vecb.push

36、_back(a); visa+; visb+; int flag=0; pd(1); for(int i=1;i<=n;+i) if(cpi=0) flag=1; else break; if(flag) printf("-1n"); else for(int i=1;i<=n;+i) sort(veci.begin(),veci.end(); if(visi%2=1) +num; if(num=0|num=2) if(num=2) if(vis1%2=1) dfs(1); prt(); else printf("-1n"); else df

37、s(1); prt(); else printf("-1n"); system("Pause"); return 0; 4 【實(shí)驗(yàn)結(jié)果】5【心得體會(huì)】 通過(guò)這個(gè)實(shí)驗(yàn)，我掌握了歐拉回路的基本思想。明白了用歐拉算法解決實(shí)際問(wèn)題的具體步驟。而且明白了用算法解決實(shí)際問(wèn)題的思維方法。 實(shí)驗(yàn)4.消除類(lèi)游戲 專(zhuān)業(yè)：_軟件工程_ 班級(jí)：_軟件 姓名：_王_ 學(xué)號(hào)：_20100034完成日期：_2010/6/28_1【問(wèn)題描述】消除類(lèi)游戲是深受大眾歡迎的一種游戲，游戲在一個(gè)包含有n行m列的游戲棋盤(pán)上進(jìn)行，棋盤(pán)的每一行每一列的方格上放著一個(gè)有顏色的棋子，當(dāng)一行或一列上有連續(xù)

38、三個(gè)或更多的相同顏色的棋子時(shí)，這些棋子都被消除。當(dāng)有多處可以被消除時(shí)，這些地方的棋子將同時(shí)被消除?，F(xiàn)在給你一個(gè)n行m列的棋盤(pán)(1n,m30)，棋盤(pán)中的每一個(gè)方格上有一個(gè)棋子，請(qǐng)給出經(jīng)過(guò)一次消除后的棋盤(pán)。請(qǐng)注意：一個(gè)棋子可能在某一行和某一列同時(shí)被消除。輸入數(shù)據(jù)格式：輸入的第一行包含兩個(gè)整數(shù)n, m，用空格分隔，分別表示棋盤(pán)的行數(shù)和列數(shù)。接下來(lái)n行，每行m個(gè)整數(shù)，用空格分隔，分別表示每一個(gè)方格中的棋子的顏色。顏色使用1至9編號(hào)。輸出數(shù)據(jù)格式：輸出n行，每行m個(gè)整數(shù)，相鄰的整數(shù)之間使用一個(gè)空格分隔，表示經(jīng)過(guò)一次消除后的棋盤(pán)。如果一個(gè)方格中的棋子被消除，則對(duì)應(yīng)的方格輸出0，否則輸出棋子的顏色編號(hào)。【測(cè)

39、試數(shù)據(jù)】為方便調(diào)試程序，可將輸入數(shù)據(jù)先寫(xiě)入一個(gè)文本文件，然后從文件讀取數(shù)據(jù)處理，這樣可避免每次運(yùn)行程序時(shí)都要從鍵盤(pán)輸入數(shù)據(jù)。測(cè)試數(shù)據(jù)一輸入：輸出：4 52 2 3 1 23 4 5 1 42 3 2 1 32 2 2 4 42 2 3 0 23 4 5 0 42 3 2 0 30 0 0 4 4輸出說(shuō)明：棋盤(pán)中第4列的1和第4行的2可以被消除，其他的方格中的棋子均保留。測(cè)試數(shù)據(jù)二輸入：輸出：4 52 2 3 1 23 1 1 1 12 3 2 1 32 2 3 3 32 2 3 0 23 0 0 0 02 3 2 0 32 2 0 0 0輸出說(shuō)明：棋盤(pán)中所有的1以及最后一行的3可以被同時(shí)消除，其他的方格中的棋子均保留。