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

1、離散數(shù)學(xué)實(shí)驗(yàn)報(bào)告姓 名：學(xué) 號(hào)：班 級(jí)：實(shí)驗(yàn)地點(diǎn)：實(shí)驗(yàn)時(shí)間：1 實(shí)驗(yàn)?zāi)康暮鸵筮\(yùn)用最小生成樹思想和求最小生成樹程序解決實(shí)際問題。實(shí)際問題描述如下：八口海上油井相互間距離如下表，其中1號(hào)井離海岸最近，為5km。問從海岸經(jīng)1號(hào)井鋪設(shè)油管把各井連接起來(lái)，怎樣連油管長(zhǎng)度最短（為便于檢修，油管只準(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.52 實(shí)驗(yàn)環(huán)境和工具實(shí)驗(yàn)環(huán)境：Windows 7 旗艦版工具：Dev-C+ 5.8.33 實(shí)驗(yàn)過(guò)程

2、開始3.1 算法流程圖結(jié)束int i,j;MGraph g;float AMAXV10;g.vexnum;在屏幕上打印運(yùn)行結(jié)果Aij=INF;J<g.vexnumYdispMat(g);prim(g,0);i=0;j=0;g.vexnum=8;NY表中數(shù)據(jù)賦值給AMAXV10i<g.vexnumN3.2 程序核心代碼/油管鋪設(shè)問題 Prim算法實(shí)現(xiàn)#include <iostream>#include<iomanip>using namespace std;#define MAXV 10#define INF 32767 /INF表示typedef int

3、InfoType;typedef structint no; /頂點(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;i<g.vexnum;i+) for (j=0;j<g.vexnum;j+) if (g.edgesij=I

4、NF) cout<<setw(6)<<"" else cout<<setw(6)<<g.edgesij; cout<<endl; 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;i<g.vexnum;i+) Vlengthi=g.edgesvi; cloesti=v

5、; for(i=1;i<g.vexnum;i+) min=INF; /min為其中最大的一條邊=MAXV for(j=0;j<g.vexnum;j+) /找n-1條邊 if(Vlengthj!=0&&Vlengthj<min) min=Vlengthj; k=j; cout<<"連接油井<"<<cloestk+1<<","<<k+1<<">"<<"長(zhǎng)度為:"<<min<<en

6、dl; sum+=min; Vlengthk=0; Vlengthcloestk=0;for(j=0;j<g.vexnum;j+) /選擇當(dāng)前代價(jià)最小的邊 if(g.edgeskj!=0&&g.edgeskj<Vlengthj) Vlengthj=g.edgeskj; cloestj=k; cout<<"管道總長(zhǎng)度為："<<sum<<endl; int main() int i,j,u=3; MGraph g; float AMAXV10; g.vexnum=8; for (i=0;i<g.vexnum;

7、i+) for (j=0;j<g.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;i<g.ve

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