学校超市选址问题_第1页
学校超市选址问题_第2页
学校超市选址问题_第3页
学校超市选址问题_第4页
学校超市选址问题_第5页
已阅读5页,还剩9页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、数学与计算机学院课程设计说明书课 程 名 称: 算法设计与分析-课程设计 课 程 代 码: 7106620 题 目: 超市选址问题 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 2010 年 12 月 27 日完 成 时 间: 2011 年 01 月 07 日课程设计成绩:学习态度及平时成绩(30)技术水平与实际能力(20)创新(5)说明书撰写质量(45)总 分(100)指导教师签名: 年 月 日目 录 1 引 言11.1 问题的提出11.2国内外研究的现状11.3任务与分析12 程序的主要功能12.1输入功能12.2求权值功能22.3 求最优功能22.4显示功能23 程序运

2、行平台24 总体设计25 程序说明26 模块分析56.1输入功能56.2求权值功能56.3求最优功能56.4显示功能57 系统测试68 结论6致谢7参考文献8附录9 摘 要 学校超市的选址问题,一般需要考虑各个单位到它的综合距离最近。其实质是找一个综合权数最小的地点,但手工求解会造成很大的麻烦。随着计算机科学的不断进步,为我们找到了机算的途径,大大地节约了劳动资源。其中计算机图形学的发展,为我们提供了很多科学有效地算法。使得计算快速,方便。关键词:超市选址、计算机、图形学1 引 言 1.1 问题的提出 对于某一学校超市,其他各单位到其的距离不同,同时各单位人员去超市的频度也不同。请为超市选址,

3、要求实现总体最优。2设计要求:(1)设计该问题的核心算法;(2)设计程序能有效指出学校超市可设立的地点和各单位的位置以及它们之间的有效路径; (3)程序能自动计算出最优设立点,并显示出最优设立点。1.2国内外研究的现状 不仅超市选址,其他诸多重要设施在建立前都需要对其地点,作出最优的抉择。该问题归根到底,就是要我们运用图的原理对其找到一个离各个单位综合最近的地点。随着数学方法。当今,数学的图理论,已经较为完善。这为我们运用计算机解决该类问题提供了条件。1.3任务与分析说到求解一个地点,实现总体最优。就需要找到一个度量优、劣的标准。由于一个学校的单位数量不会超过两位数,所以用蛮力法是可行的。我们

4、将各个单位到选址地的距离与该单位人员去超市频度的乘积作为单位的权数,再把各单位总权数相加所得的和作为该选址的一个优、劣度量标准。当然,权数和最小的为最优选址2 程序的主要功能2.1输入功能输入学校的单位总数;输入学校各单位名称;输入学校各单位员工去超市频度;输入学校各单位间的距离(用矩阵表示)。2.2求权值功能求出将超市设在各个单位时,所得总的权值,返回用数组存储。2.3 求最优功能从上述的各个权值中,选出最小值为最优。并将最优值和对应的选址储存在链表中,返回头指针。2.4显示功能显示最优选址的地点、总权数以及各单位到它的距离。3 程序运行平台 Windows操作系统 Visual C+4 总

5、体设计进入主函数输入数据求权值求最优选址输出最优信息退出主函数图4.1总体流程图5 程序说明struct ZY /定义链表结构体,储存最优信息double min;int n;ZY *next;void input(int &n,float* &a,float* &b,char* &DW)/输入信息int i,j;printf("请输入单位数量:");scanf("%d",&n);/输入单位数量 printf("n");a=(float *)malloc(n*sizeof(float*);/分配

6、内存空间for(i=0;i<n;i+)ai=(float *)malloc(n*sizeof(float);/分配内存空间b=(float *)malloc(n*sizeof(float);/分配内存空间DW=(char *)malloc(n*sizeof(char *);/分配内存空间for(i=0;i<n;i+)DWi=(char *)malloc(20*sizeof(char);/分配内存空间printf("请输入各单位的名称:n");for(i=0;i<n;i+)scanf("%s",DWi);/输入各单位名称printf(&q

7、uot;请输入各单位去超市的频度:n");for(i=0;i<n;i+)scanf("%f",b+i);/输入各单位去超市频度printf("请输入各单位间的距离矩阵:n");for(i=0;i<n;i+)/输入各单位间的距离矩阵for(j=0;j<n;j+)scanf("%f",ai+j);double*work_sum(float *A,float *B,int N)/求各单位被选中后的总权值int n=N;float *a=A;float *b=B;int i,j;double s,*sum; sum

8、=(double *)malloc(n*sizeof(double);/分配内存空间for(i=0;i<n;i+)s=0.00;for(j=0;j<n;j+) /求每个单位被选中后的权值s=s+aji*bj;sumi=s;/储存每个单位被选中后的权值return sum;/返回sumZY *work_min(double *Sum,int N)/求最优选址 double *sum=Sum;double min=sum0;int i;int n=N;ZY *head,*p;head=(ZY *)malloc(sizeof(struct ZY);/分配内存空间head->next

9、=NULL;/尾指针置空for(i=0;i<n;i+)if(sumi<=min)min=sumi;head->min=min;/求最优权值for(i=0;i<n;i+)if(sumi=min)p=(ZY *)malloc(sizeof(struct ZY);p->n=i;/记录最优选址点p->next=head->next;head->next=p;/尾指针置空return head;void print(ZY *Head,char *Dw,int N,float *A,float *B)/显示数据ZY *head=Head;ZY *p; cha

10、r *DW=Dw;int i,k,n=N;float *a=A;float *b=B; double min; p=head->next;min=head->min;printf("最优选址如下:(总权重:%f)nn",min);while(p)/显示最优选址信息k=p->n;printf("超市设立地点:%sn",DWk);for(i=0;i<n;i+)printf("%s到超市的有效路径为:%f 权重为:%fnn",DWi,aik,aik*bi);p=p->next;6 模块分析6.1输入功能1.定义

11、一个整型变量,储存输入的单位数,为矩阵等输入确定阶;2.定义一个二维的字符指针,用来储存输入的各个单位的名称,其中行数等于单位数。因为一个单位名称一般不超过20个字符,所以列数取定值20;3.定义一个一维的浮点型指针,用来储存输入的各单位去超市的频度;4.定义一个二维的浮点型指针,用来储存各单位间的距离,其中到自己的距离规定为0。注:各个单位的名称、去超市频度和它们间的距离输入顺序要一致。6.2求权值功能对于每各单位来说,它们被选中时,所得权数就等于各个单位到它的距离乘以各个单位去超市频度的积,再分别相加便是总权数。需要传入的参数是:指向单位间的距离矩阵的指针、指向单位去超是频度的指针、单位数

12、量。需要返回的是:指向求得的权数的指针值。6.3求最优功能 在各个总权值中,最小的就是最优权值,我们将最优权值保留在第一个链表节点。由于输入是按统一的顺序,所以最优权值在数组中的位置对应的单位就是最优选址。我们把与最优值相等的权值在数组中的位置(即下标)保留在后续节点中。6.4显示功能 由于上述,最优权值在数组中的位置对应的单位就是最优选址,我们假设它在数组中的位置是i,那么单位名称数组中的第i个字符串就是最优选址的名称。距离矩阵中第i列元素是各个单位到选址超市的距离,距离矩阵中第i列各元素与频度数组中与该元素所在行的下标相同的值相乘就是相应单位到选址超市的权数。掌握了这各规律,一一计算后输出

13、便是需要的结果。7 系统测试数据输入:图7.1 输入数据窗口 显示数据:图7.2 显示最优信息窗口8 结论通过测试发现,当选址在临江苑和图书馆时,对应的总权值分别不大于九舍。说明选址符合要求致谢首先,感谢老师的细心知道,没有老师的不求目的地教导,不可能这么快,这么准确地完成设计,其次要感谢同学的帮助,使我能够准确、快速地获取信息帮助。参考文献1 严蔚敏 吴伟民 著. 数据结构(C语言版)(第三版). 北京:清华大学出版社2007.42 谭浩强 著. C程序设计(第三版).北京:清华大学出版社;2006.93 Anany Levitin 著. 潘彦 译 算法设计与分析基础(第二版).北京:清华大

14、学出版社;2010.14 美 S巴斯 著.计算机算法:设计和分析引论. 朱洪等译 上海:复旦大学出版社;1985.1附录#include<stdio.h>#include<stdlib.h>struct ZY /定义链表结构体,储存最优信息double min;int n;ZY *next;double*work_sum(float *A,float *B,int N)/求各单位被选中后的总权值int n=N;float *a=A;float *b=B;int i,j;double s,*sum; sum=(double *)malloc(n*sizeof(double

15、);/分配内存空间for(i=0;i<n;i+)s=0.00;for(j=0;j<n;j+) /求每个单位被选中后的权值s=s+aji*bj;sumi=s;/储存每个单位被选中后的权值return sum;/返回sumZY *work_min(double *Sum,int N)/求最优选址 double *sum=Sum;double min=sum0;int i;int n=N;ZY *head,*p;head=(ZY *)malloc(sizeof(struct ZY);/分配内存空间head->next=NULL;/尾指针置空for(i=0;i<n;i+)if(

16、sumi<=min)min=sumi;head->min=min;/求最优权值for(i=0;i<n;i+)if(sumi=min)p=(ZY *)malloc(sizeof(struct ZY);p->n=i;/记录最优选址点p->next=head->next;head->next=p;/尾指针置空return head;void print(ZY *Head,char *Dw,int N,float *A,float *B)/显示数据ZY *head=Head;ZY *p; char *DW=Dw;int i,k,n=N;float *a=A;f

17、loat *b=B; double min; p=head->next;min=head->min;printf("最优选址如下:(总权重:%f)nn",min);while(p)/显示最优选址信息k=p->n;printf("超市设立地点:%sn",DWk);for(i=0;i<n;i+)printf("%s到超市的有效路径为:%f 权重为:%fnn",DWi,aik,aik*bi);p=p->next;void input(int &n,float* &a,float* &b,

18、char* &DW)/输入信息int i,j;printf("请输入单位数量:");scanf("%d",&n);/输入单位数量 printf("n");a=(float *)malloc(n*sizeof(float*);/分配内存空间for(i=0;i<n;i+)ai=(float *)malloc(n*sizeof(float);/分配内存空间b=(float *)malloc(n*sizeof(float);/分配内存空间DW=(char *)malloc(n*sizeof(char *);/分配内存空间for(i=0;i<n;i+)DWi=(char *)malloc(20*sizeof(char);/分配内存空间printf("请输入各单位的名称:n");for(i=0;i<n;i+)scanf("%s",DWi);/输入各单位名称printf("请输入各单位去超市的频度:n");for(i=0;i<n;i

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论