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

1、.wd.wdPAGE7 / NUMPAGES7.wd離散數(shù)學(xué)實(shí)驗(yàn)報(bào)告姓 名：學(xué) 號(hào)：班 級(jí)：實(shí)驗(yàn)地點(diǎn)：實(shí)驗(yàn)時(shí)間：實(shí)驗(yàn)?zāi)康暮鸵筮\(yùn)用最小生成樹思想和求最小生成樹程序解決實(shí)際問題。實(shí)際問題描述如下：八口海上油井相互間距離如下表，其中1號(hào)井離海岸最近，為5km。問從海岸經(jīng)1號(hào)井鋪設(shè)油管把各井連接起來，若何連油管長度最短為便于檢修，油管只準(zhǔn)在油井處分叉從到234567811.32.10.90.71.82.01.820.91.81.22.82.31.132.61.72.51.91.040.71.61.50.950.91.10.860.61.070.5實(shí)驗(yàn)環(huán)境和工具實(shí)驗(yàn)環(huán)境：Windows 7 旗艦版工具

2、：Dev-C+ 5.8.3實(shí)驗(yàn)過程開場算法流程圖完畢int i,j;MGraph g;float AMAXV10;g.vexnum;在屏幕上打印運(yùn)行結(jié)果Aij=INF;Jg.vexnumYdispMat(g);prim(g,0);i=0;j=0;g.vexnum=8;NY表中數(shù)據(jù)賦值給AMAXV10ig.vexnumN程序核心代碼/油管鋪設(shè)問題 Prim算法實(shí)現(xiàn)#include #includeusing namespace std;#define MAXV 10#define INF 32767 /INF表示typedef int InfoType;typedef structint no;

3、 /頂點(diǎn)編號(hào) InfoType info; /頂點(diǎn)其他信息 VertexType; /頂點(diǎn)類型typedef struct /圖的定義float edgesMAXVMAXV; /鄰接矩陣 int vexnum; /頂點(diǎn)數(shù) VertexType vexsMAXV; /存放頂點(diǎn)信息 MGraph; /圖的鄰接矩陣類型/*輸出鄰接矩陣g*/ void DispMat(MGraph g) int i,j; for (i=0;ig.vexnum;i+) for (j=0;jg.vexnum;j+) if (g.edgesij=INF) coutsetw(6); else coutsetw(6)g.edg

4、esij; coutendl; void prim(MGraph g,int v) /從頂點(diǎn)V0出發(fā)，按Prim算法構(gòu)造G的最小生成樹 /輸出最小生成樹的每條邊及其權(quán)值 float VlengthMAXV;int i, j, k;int cloestMAXV;float min;float sum = 0.0;for(i=0;ig.vexnum;i+) Vlengthi=g.edgesvi; cloesti=v; for(i=1;ig.vexnum;i+) min=INF; /min為其中最大的一條邊=MAXV for(j=0;jg.vexnum;j+) /找n-1條邊 if(Vlengthj

5、!=0&Vlengthjmin) min=Vlengthj; k=j; cout連接油井cloestk+1,k+1長度為:minendl; sum+=min; Vlengthk=0; Vlengthcloestk=0;for(j=0;jg.vexnum;j+) /選擇當(dāng)前代價(jià)最小的邊 if(g.edgeskj!=0&g.edgeskjVlengthj) Vlengthj=g.edgeskj; cloestj=k; cout管道總長度為：sumendl; int main() int i,j,u=3; MGraph g; float AMAXV10; g.vexnum=8; for (i=0;i

6、g.vexnum;i+) for (j=0;jg.vexnum;j+) Aij=INF;A01=1.3; A02=2.1; A03=0.9;A04=0.7; A05=1.8; A06=2.0;A07=1.8; A12=0.9; A13=1.8;A14=1.2; A15=2.8; A16=2.3;A17=1.1; A23=2.6; A24=1.7;A25=2.5; A26=1.9; A27=1.0;A34=0.7; A35=1.6; A36=1.5;A37=0.9; A45=0.9; A46=1.1;A47=0.8; A56=0.6; A57=1.0;A67=0.5; for (i=0;ig.v

7、exnum;i+) for (j=0;jg.vexnum;j+) Aji=Aij; for (i=0;ig.vexnum;i+) /*建設(shè)圖的鄰接矩陣*/ for (j=0;jg.vexnum;j+) g.edgesij=Aij; coutendl; cout各油井間距離:n; DispMat(g); coutendl; cout最優(yōu)鋪設(shè)方案:n; prim(g,0); coutendl; return 0;運(yùn)行結(jié)果運(yùn)行結(jié)果分析程序?qū)崿F(xiàn)了輸出需要鋪設(shè)管道的油井編號(hào)，并給出了每條管道長度以及總長度， 根本實(shí)現(xiàn)了題目要求。進(jìn)一步優(yōu)化，根據(jù)用戶輸入的任意網(wǎng)絡(luò)的數(shù)據(jù)，在屏幕打印出管道連接的設(shè)計(jì)圖紙。實(shí)驗(yàn)心得離散數(shù)學(xué)作為一門培養(yǎng)抽象思維、離散思維、程序化思維的一門學(xué)科，僅憑課堂