离散数学实验报告

离散数学实验报告...离散数学实验报告姓名：学号：班级：实验地点：实验时间：1实验目的和要求运用最小生成树思想和求最小生成树程序解决实际问题。实际问题描述如下：八口海上油井相互间距离如下表，其中1号井离海岸最近，为5km。问从海岸经1号井铺设油管把各井连接起来，怎样连油管长度最短（为便于检修，油管只准在油井处分叉）？从～到 2 3 4 5 6 7 8 1 1.3 2.1 0.9 0.7 1.8 2.0 1.8 2 0.9 1.8 1.2 2.8 2.3 1.1 3 2.6 1.7 2.5 1.9 1.0 4 0.7 ...

...离散数学实验报告姓名：学号：班级：实验地点：实验时间：1实验目的和要求运用最小生成树思想和求最小生成树程序解决实际问题。实际问题描述如下：八口海上油井相互间距离如下表，其中1号井离海岸最近，为5km。问从海岸经1号井铺设油管把各井连接起来，怎样连油管长度最短（为便于检修，油管只准在油井处分叉）？从～到 2 3 4 5 6 7 8 1 1.3 2.1 0.9 0.7 1.8 2.0 1.8 2 0.9 1.8 1.2 2.8 2.3 1.1 3 2.6 1.7 2.5 1.9 1.0 4 0.7 1.6 1.5 0.9 5 0.9 1.1 0.8 6 0.6 1.0 7 0.52实验环境和工具实验环境：Windows7旗舰版工具：Dev-C++5.8.33实验过程3.1算法流程图YNYN3.2程序核心代码//油管铺设问题Prim算法实现#include<iostream>#include<iomanip>usingnamespacestd;#defineMAXV10#defineINF32767//INF表示∞typedefintInfoType;typedefstruct{intno;//顶点编号InfoTypeinfo;//顶点其他信息}VertexType;//顶点类型typedefstruct{//图的定义floatedges[MAXV][MAXV];//邻接矩阵intvexnum;//顶点数VertexTypevexs[MAXV];//存放顶点信息}MGraph;//图的邻接矩阵类型/*输出邻接矩阵g*/voidDispMat(MGraphg){inti,j;for(i=0;i<g.vexnum;i++){for(j=0;j<g.vexnum;j++)if(g.edges[i][j]==INF)cout<<setw(6)<<"∞";elsecout<<setw(6)<<g.edges[i][j];cout<<endl;}}voidprim(MGraphg,intv){//从顶点V0出发，按Prim算法构造G的最小生成树//输出最小生成树的每条边及其权值floatVlength[MAXV];inti,j,k;intcloest[MAXV];floatmin;floatsum=0.0;for(i=0;i<g.vexnum;i++){Vlength[i]=g.edges[v][i];cloest[i]=v;}for(i=1;i<g.vexnum;i++){min=INF;//min为其中最大的一条边=MAXVfor(j=0;j<g.vexnum;j++){//找n-1条边if(Vlength[j]!=0&&Vlength[j]<min){min=Vlength[j];k=j;}}cout<<"连接油井<"<<cloest[k]+1<<","<<k+1<<">"<<"长度为:"<<min<<endl;sum+=min;Vlength[k]=0;Vlength[cloest[k]]=0;for(j=0;j<g.vexnum;j++){//选择当前代价最小的边if(g.edges[k][j]!=0&&g.edges[k][j]<Vlength[j]){Vlength[j]=g.edges[k][j];cloest[j]=k;}}}cout<<"管道总长度为："<<sum<<endl;}intmain(){inti,j,u=3;MGraphg;floatA[MAXV][10];g.vexnum=8;for(i=0;i<g.vexnum;i++)for(j=0;j<g.vexnum;j++)A[i][j]=INF;A[0][1]=1.3;A[0][2]=2.1;A[0][3]=0.9;A[0][4]=0.7;A[0][5]=1.8;A[0][6]=2.0;A[0][7]=1.8;A[1][2]=0.9;A[1][3]=1.8;A[1][4]=1.2;A[1][5]=2.8;A[1][6]=2.3;A[1][7]=1.1;A[2][3]=2.6;A[2][4]=1.7;A[2][5]=2.5;A[2][6]=1.9;A[2][7]=1.0;A[3][4]=0.7;A[3][5]=1.6;A[3][6]=1.5;A[3][7]=0.9;A[4][5]=0.9;A[4][6]=1.1;A[4][7]=0.8;A[5][6]=0.6;A[5][7]=1.0;A[6][7]=0.5;for(i=0;i<g.vexnum;i++)for(j=0;j<g.vexnum;j++)A[j][i]=A[i][j];for(i=0;i<g.vexnum;i++)/*建立图的邻接矩阵*/for(j=0;j<g.vexnum;j++)g.edges[i][j]=A[i][j];cout<<endl;cout<<"各油井间距离:\n";DispMat(g);cout<<endl;cout<<"最优铺设方案 :\n";prim(g,0);cout<<endl;return0;}3.3运行结果3.4运行结果分析程序实现了输出需要铺设管道的油井编号，并给出了每条管道长度以及总长度，基本实现了题目要求。进一步优化，根据用户输入的任意网络的数据，在屏幕打印出管道连接的设计图纸。4实验心得离散数学作为一门培养抽象思维、离散思维、程序化思维的一门学科，仅凭课堂教学的过程难以习得如何运用这些思维的方法。增加的本次实验环节，将课堂所学的一些算法与实际背景相连接，理论与程序代码实现相关联。让我在算法分析以及编程语言的使用上有不少收获。在实验中体验用计算机解决实际问题的过程亦是充满乐趣。开始结束inti,j;MGraphg;floatA[MAXV][10];g.vexnum;在屏幕上打印运行结果A[i][j]=INF;J<g.vexnumdispMat(g);prim(g,0);i=0;j=0;g.vexnum=8;表中数据赋值给A[MAXV][10]i<g.vexnum精选文档精选文档精选文档

                    本文档为【离散数学实验报告】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

离散数学实验报告

你可能还喜欢