《[理学]算法设计技巧与分析程序设计.doc》由会员分享，可在线阅读，更多相关《[理学]算法设计技巧与分析程序设计.doc（37页珍藏版）》请在三一办公上搜索。
1、Yangqiuyan第 37 页2023/4/27课程设计成绩考勤成绩( %)报告及程序成绩( %)总评成绩指导老师签名：算法分析与设计课 程 设 计 报 告 学院（系）： 信息与计算科学 班 级： 110010101 学生姓名： 杨秋燕 学号11001010128 指导教师： 董 世 都 时间：从2012年 6月25日 到 2012年6月29日目录 计算一元钱硬币有多少种表达方式1 完成一维的最接近点对问题2 校园导航问题3 学校超市选址问题4题目一 硬币问题问题描述：计算一元钱硬币有多少种表达方式。例如，可以使用1元钱完成，也可以使用两个5角完成。这里可供选择的货币单位从1分到1元。编写程
2、序计算出每一种组合方式。（）解决问题所用的方法：穷举法算法描述： 算法名称:嵌套循环 输出：各种面值币值的个数：一分：i个,两分：j个,五分：k个,一角：l个,五角：m个,一元：n个，总共的换法：count 算法实现细节：过程：1. for i0 to 1002. for j0 to 503. for k0 to 204. for l0 to 105. for m0 to 26. for n0 to 17. if i*1+j*2+k*5+l*10+m*50+n*100=100 then count+1 and 输出各种面值的个数8. 输出总共的换法count 算法的时间复杂度:O（1）算法实例
3、： 数据输出：题目二 以为最接近点对问题问题描述：完成一维的最接近点对问题（p121）（）解决问题所用的方法：动态规划算法描述： 算法名称CLOSESTPAIR 输入：平面上n个点的集合S 输出：S中两点的最小距离 算法实现细节（可以用流程图，伪代码）过程：1、if high-low+13 then用直接方法计算 2、else3、 mid (low+high)/24、 x0x(Smid)5、 cp(low,mid)6、 cp(mid+1,high)7、 mid8、 k09、 for i1 to n从Y轴中取出T10、 if |x(Yi-x0)| then11、 kk+112、 TkYi13、
4、end if14、 end fork是T的大小15、 将初始化成大于的值16、 for i1 to k-1 计算的值17、 for ji+1 to mini+7，k18、 if d（Ti,Tj） then d(Ti,Tj)19、 end for20、 end for21、 min22、end if23、Return 算法的时间复杂度算法实例： 数据的输入：3 18 15 24 7 21 8 0 数据的输出：最近点对,其距离为1（屏幕截图）题目三 校园导航问题问题描述：校园导航问题：设计你所在学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达
5、另一场所的最佳路径（最短路径）。()解决问题所用的方法：采用了简单循环和嵌入。算法描述： 算法名称：FLOYD 输入：n*n维矩阵l1n,1n,以便对有向图G=（1，2，n，E）中的边的长度为li,j。 输出：矩阵D，使得Di,j等于i到j的距离。 算法实现细节（可以用流程图，伪代码）：过程： 1、Dl 将输入矩阵l复制到D 2、for k1 to n 3、 for i1 to n 4、 for j1 to n 5、 Di，j=minDi，j，Di，k+Dk,j 6、 end for 7、 end for 8、 end for 算法的时间复杂度：O(n3)算法实例： 数据的输入：2 2 10
6、4 9 数据的输出： 1 重庆理工大学大门 ：这里有明德楼（教师办公室），有一块刻有重庆理工大学字样的大石头2 实验楼：这里有三栋实验楼，两个借阅厅，旧的图书馆3 重庆理工大学中门4 教学一区：这里有第一、第二、第三、第四四栋教学楼5 教二区：这里有第五、第六两栋教学楼6 新图书馆：这里还有超市、三食堂、打印楼等7 一食堂8 男身宿舍9 女生宿舍10 小卖部11 二食堂12 足球场13 篮球场14 体育馆：这里有游泳池等实验楼教一区一食堂新图书馆小卖部教一区一食堂女生宿舍 题目四 学校超市选址问题问题描述：学校超市选址问题（带权有向图的中心点）：对于某一学校超市，其他各单位到其的距离不同，同时
7、各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。()解决问题所用的方法：Floyd算法利用动态规划思想，通过把问题分解为子问题来解决任意两点见的最短路径问题。设G=(V, E, w)是一个带权有向图，其边V=v1, v2, , vn。对于kn，考虑其结点V的一个子集。对于V中任何两个结点vi、vj，考虑从vi到vj的中间结点都在vk中的所有路径，设是其中最短的，并设的路径长度为。如果结点vk不在从vi到vj的最短路径上，则；反之则可以把分为两段，其中一段从vi到vk，另一段从vk到vj，这样便得到表达式。算法描述： 算法名称：Floyd 算法实现细节（可以用流程图，伪代码）开始M
8、ain（）输入基本信息建立邻接矩阵的存储结构输出i-j的路径和路径长度Aij=INF,i!=jFloyd算法输出超市的最佳地址：i结束Floyed（Gh）GreatMgraph（Gh）i到j不存在路算法的时间复杂度：O(n3)算法实例： 数据的输入（可以有屏幕截图）:据的输出（可以有屏幕截图）：课程设计总结算法设计技巧与分析课程设计完成了，对我来说这是一项不小的挑战，它不仅检验了我的学习情况，也考验了我的意志力，受益匪浅！通过一学期的学习，我知道算法设计技巧与分析是一门理论性强、思维抽象、难度较大的课程，它不仅仅求我们必须看懂算法，还要要求我们要有良好的C语言功底，会编写算法。它让我深刻的体会
9、到仅仅是学会了书本上的东西是远远不够的，只有学会了书本上的东西加上实践，我们才能真真能学到的。现在我真真切切的了解了实践才能检验真理，我们做任何事情，都不能脱离实践。源代码1、计算一元钱硬币有多少种表达方式1#includevoid main()int i,j,k,l,m,n,count;count=0;for(i=0;i=100;i+)for(j=0;j=50;j+)for(k=0;k=20;k+)for(l=0;l=10;l+)for(m=0;m=2;m+)for(n=0;n=1;n+)if(i*1+j*2+k*5+l*10+m*50+n*100=100)count+; printf(第%
10、d种换法:一分%d个,两分%d个,五分%d个,一角%d个,五角%d个,一元%d个n,count,i,j,k,l,m,n);printf(总共有%d种换法,count);2、 完成一维的最接近点对问题2#include iostream.h#define M 20struct cpair/表示具有最近距离的点对(d1,d2)的距离distfloat dist;float d1,d2;int input(float s,int n)/s为一维点集，n为s中的元素个数coutsn;while(sn!=0)n+;cinsn;return n;float max(float s,int b,int e)
11、/返回sb到se中的最大值float m1=sb;for(int i=b+1;i=e;i+)if(m1si) m1=si;return m1;float min(float s,int b,int e)/返回sb到se中的最小值float m1=sb;for(int i=b+1;isi) m1=si;return m1;/返回s中的具有最近距离的点对及其距离cpair cpair1(float s,int n)cpair temp=1000,0,0;/当点集中元素的个数不足2时,返回具有无穷大的dist值(此处设为1000)的tempif(n2) return temp;float m1=ma
12、x(s,0,n-1),m2=min(s,0,n-1);float m=(m1+m2)/2;/找出点集中的中位数int j=0,k=0;/将点集中的各元素按与m的大小关系分组float s1M,s2M;for(int i=0;in;i+)if(si=m) s1j=si;j+;else s2k=si;k+;cpair d1=cpair1(s1,j),d2=cpair1(s2,k);/递归float p=max(s1,0,j-1),q=max(s2,0,k-1);/返回s中的具有最近距离的点对及其距离if(d1.distd2.dist)if(q-p)d1.dist)temp.dist=(q-p);t
13、emp.d1=q; temp.d2=p;return temp;else return d1;elseif(q-p)d2.dist)temp.dist=(q-p);temp.d1=q; temp.d2=p;return temp;else return d2;void main()int n,m;float sM;cpair dist;m=input(s,n);dist=cpair1(s,m);coutn该一维点集中最近点对为(dist.d1,dist.d2),其距离为dist.distendl;3、 校园导航问题3#include #include #include #define Max
14、32767#define NUM 15typedef struct VertexTypeint number;char *sight;VertexType;typedef structVertexType vexNUM; int arcsNUMNUM;int vexnum; MGraph;MGraph G;int PNUMNUM;long int DNUM;/void CreateMGraph(int v)/创建图的函数int i,j;G.vexnum=v;for(i=1;iG.vexnum;+i) G.vexi.number=i; G.vex0.sight=各个景点名字;G.vex1.sig
15、ht=重庆理工大学大门;G.vex2.sight=实验楼;G.vex3.sight=重庆理工大学中门;G.vex4.sight=教一区;G.vex5.sight=教二区;G.vex6.sight=新图书馆;G.vex7.sight=一食堂;G.vex8.sight=男生宿舍;G.vex9.sight=女生宿舍;G.vex10.sight=小卖部;G.vex11.sight=二食堂;G.vex12.sight=足球场;G.vex13.sight=篮球场;G.vex14.sight=体育馆;for(i=1;iG.vexnum;+i)for(j=1;jG.vexnum;+j)G.arcsij=Max
16、;G.arcs12=G.arcs21=212;G.arcs13=G.arcs31=901;G.arcs24=G.arcs42=399; G.arcs212=G.arcs122=1200;G.arcs35=G.arcs53=207;G.arcs47=G.arcs74=301;G.arcs412=G.arcs124=1023;G.arcs56=G.arcs65=102;G.arcs67=G.arcs76=110;G.arcs78=G.arcs87=255;G.arcs49=G.arcs94=1300;G.arcs411=G.arcs114=1800;G.arcs56=G.arcs65=750;G.
17、arcs67=G.arcs76=180;G.arcs68=G.arcs86=241;G.arcs610=G.arcs106=250;G.arcs611=G.arcs116=720;G.arcs78=G.arcs87=140;G.arcs79=G.arcs97=350;G.arcs810=G.arcs108=405;G.arcs913=G.arcs139=1225;G.arcs911=G.arcs119=700;G.arcs910=G.arcs109=390;G.arcs911=G.arcs119=95;G.arcs1011=G.arcs1110=765;G.arcs1112=G.arcs121
18、1=699;G.arcs1114=G.arcs1411=605;G.arcs1213=G.arcs1312=550;G.arcs1314=G.arcs1413=896;void Map()/地图展示函数printf(t *重庆理工大学地图导航系统* n);printf( n); printf( n);printf( 1重理工大门3重理工中门 n);printf( n);printf( n);printf( 5教二区 n);printf( n);printf( 6新图书馆 n); printf( n);printf( 2实验楼4教学一区7一食堂 8男生宿舍 n);printf( n);print
19、f( n);printf( n);printf( 9女生宿舍 10小卖部 n);printf( n); printf( 11二食堂 n);printf( 12足球场 n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( 14体育馆 n);printf( 13篮球场 n); printf( n);printf( * n); void Info()/资料介绍函数 printf(1 重庆理工大学大门 ：这里有明德楼（教师办公室），有一块刻有重庆理工大学字样的大石头n);printf(2 实验楼：这里有三栋实验楼，两个借阅厅
20、，旧的图书馆 n);printf(3 重庆理工大学中门： n);printf(4 教学一区：这里有第一、第二、第三、第四四栋教学楼n);printf(5 教二区：这里有第五、第六两栋教学楼n);printf(6 新图书馆：这里还有超市、三食堂、打印楼等n);printf(7 一食堂：n);printf(8 男身宿舍： n);printf(9 女生宿舍： n);printf(10 小卖部： n);printf(11 二食堂： n);printf(12 足球场： n);printf(13 篮球场： n);printf(14 体育馆：这里有游泳池等 n);void Dijkstra(int num)
21、/迪杰斯特拉算法最短路径int v,w,i,t;int finalNUM;int min;for(v=1;vNUM;v+)finalv=0; Dv=G.arcsnumv;for(w=1;wNUM;w+) Pvw=0;if(DvMax)Pvnum=1;Pvv=1; Dnum=0;finalnum=1;for(i=1;iNUM;+i)min=Max; for(w=1;wNUM;+w)if(!finalw)if(Dwmin)v=w;min=Dw;finalv=1; for(w=1;wNUM;+w)if(!finalw&(min+G.arcsvw)Dw)Dw=min+G.arcsvw;for(t=0;
22、tNUM;t+)Pwt=Pvt;Pww=1;char Menu()/主菜单char c;int flag;dosystem(cls);flag=1;Map();printf(tt欢迎使用重庆理工大学导航图系统n);printf(tt 1.查询地点之间最短路径 n);printf(tt 2.重庆理工大学大学景点介绍n);printf(tt e.退出 n);printf(ttt请输入您的选择：);scanf(%c,&c);if(c=1|c=2|c=e)flag=0;while(flag);return c;void Display(int sight1,int sight2)/输出函数int a,
23、b,c,d,q=0;a=sight2; if(a!=sight1)printf(nt从%s到%s的最短路径是,G.vexsight1.sight,G.vexsight2.sight);printf(t(最短距离为 %dm.)nnt,Da); printf(t%s,G.vexsight1.sight); d=sight1;for(c=0;cNUM;+c)Pasight1=0;for(b=0;bNUM;b+)if(G.arcsdb%s,G.vexb.sight); q=q+1;Pab=0;d=b; if(q%8=0) printf(n);void main()/主函数int v0,v1;char
24、e;char ck;CreateMGraph(NUM);dosystem(cls);ck=Menu();switch(ck)case 1:gate:system(cls);Map();doprintf(nnttt请选择出发地序号（114）：);scanf(%d,&v0);if(v014)printf(nntttt输入错误!n);while(v014);doprintf(ttt请选择目的地序号（114）：);scanf(%d,&v1);if(v114|v1=v0)printf(nntttt输入错误!n);while(v114|v1=v0);Dijkstra(v0);Display(v0,v1);
25、printf(nntttt按回车键继续,按e退回首页n);getchar();scanf(%c,&e);if(e=e)break;goto gate;case2:system(cls);Info();printf(nntttt按回车键返回首页.n);getchar();getchar();break;while(ck!=e);4、学校超市选址问题4#include #include #include #include #include malloc.h#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW
26、 -1#define INF 32767const int MAXVEX=100;typedef char Vextype;typedef char Vextype;typedef structVextype vexsMAXVEXMAXVEX; /单位名称（顶点信息）；int adjMAXVEXMAXVEX;/单位之间的相通情况（是否有边）；int disMAXVEXMAXVEX;/单位间距离（边的长度）；int fMAXVEX;/各单位去超市的频率；int n;/顶点数和边数；int e;Mgraph;void CreatMgraph(Mgraph *G) int i,j,k;printf(
27、请输入单位个数:n);scanf(%d,&(G-n);printf(请输入单位间的路径数:n);scanf(%d,&(G-e);printf(请输入单位名称:n);for(i=0;in;i+)printf(请输入第%d个单位名称:n,i);scanf(%s,&G-vexsi);for(i=0;in;i+) /结构体的初始化；for(j=0;jn;j+)G-adjij=0;G-disij=0;G-fi=0;for(k=0;ke;k+)printf(请输入相通的两单位 (输入格式:i,j):n);scanf(%d,%d,&i,&j);/在距离上体现为无向；printf(请输入相通两个单位间的距离(
28、格式：dis)：n);scanf(%d,&(G-disij);G-adjij=1;G-adjji=1;G-disji=G-disij;for(k=0;kn;k+)printf(请输入第%d个单位去超市的相对频率:n,k);scanf(%d,&(G-fk);for(i=0;in;i+) /以距离和频率之积作为权值；for(j=0;jn;j+)G-disij*=G-fi; /最终权值非完全无向； if(G-adjij=0&i!=j)G-disij=INF;void Floyed(Mgraph *G) /带权有向图求最短路径floyd算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;int countMAXVEX;for(i=0;in;i+) /初始化A和path数组for(j=0;jn;j+) /置初值；Aij=G-disij;pathij=-1;counti=0;for(k=0;kn;k+) /k代表运算步骤for(i=0;in;i+)for(j=0;jn;j+)if(Aij(Aik+Akj) /从i经j到k的一条路径更短Aij=Aik+Akj;pathij=k;printf(nFloyed算法求解如下:n);for(i=0;in;i+)for(j=0;jn;j+)if(i!=
