《24、学校超市选址问题.doc》由会员分享，可在线阅读，更多相关《24、学校超市选址问题.doc（14页珍藏版）》请在金锄头文库上搜索。
1、数学与计算机学院 课程设计说明书 课 程 名 称 算法设计与分析 课程设计 课 程 代 码 7106620 题 目 超市选址问题 年级 专业 班 学 生 姓 名 学 号 开 始 时 间 2010 年 12 月 27 日 完 成 时 间 2011 年 01 月 07 日 课程设计成绩 学习态度及平 时成绩 30 技术水平与实际能 力 20 创新 5 说明书撰写质量 45 总 分 100 指导教师签名 年 月 日 目 录 物品库存管理 1 1 引引 言言 1 1 1 1 问题的提出 1 1 2 国内外研究的现状 1 1 3 任务与分析 1 2 2 程序的主要功能程序的主要功能 1 1 2 1 输入
2、功能 1 2 2 求权值功能 2 2 3 求最优功能 2 2 4 显示功能 2 3 3 程序运行平台程序运行平台 2 2 4 4 总体设计总体设计 2 2 5 5 程序说明程序说明 2 2 6 6 模块分析模块分析 5 5 6 1 输入功能 5 6 2 求权值功能 5 6 3 求最优功能 5 6 4 显示功能 5 7 7 系统测试系统测试 6 6 8 8 结论结论 6 6 致谢致谢 7 7 参考文献参考文献 8 8 附录附录 9 9 物品库存管理 摘摘 要要 学校超市的选址问题 一般需要考虑各个单位到它的综合距离最近 其实质 是找一个综合权数最小的地点 但手工求解会造成很大的麻烦 随着计算机科
3、学的不断进步 为我们找到了机算的途径 大大地节约了劳动 资源 其中计算机图形学的发展 为我们提供了很多科学有效地算法 使得计算 快速 方便 关键词 关键词 超市选址 计算机 图形学 0 物品库存管理 1 1 引引 言言 1 1 问题的提出问题的提出 对于某一学校超市 其他各单位到其的距离不同 同时各单位人员去超市的频度也 不同 请为超市选址 要求实现总体最优 2 设计要求 1 设计该问题的核心算法 2 设计程序能有效指出学校超市可设立的地点和各单位的位置以及它们之间 的有效路径 3 程序能自动计算出最优设立点 并显示出最优设立点 1 2 国内外研究的现状国内外研究的现状 不仅超市选址 其他诸多
4、重要设施在建立前都需要对其地点 作出最优的抉择 该 问题归根到底 就是要我们运用图的原理对其找到一个离各个单位综合最近的地点 随着数学方法 当今 数学的图理论 已经较为完善 这为我们运用计算机解决该类 问题提供了条件 1 3 任务与分析任务与分析 说到求解一个地点 实现总体最优 就需要找到一个度量优 劣的标准 由于一个学校的单位数量不会超过两位数 所以用蛮力法是可行的 我们将各个单位到选址地的距离与该单位人员去超市频度的乘积作为单位的权数 再把各单位总权数相加所得的和作为该选址的一个优 劣度量标准 当然 权数和最小的为最优选址 2 2 程序的主要功能程序的主要功能 2 12 1 输入功能输入功
5、能 输入学校的单位总数 输入学校各单位名称 输入学校各单位员工去超市频度 输入学校各单位间的距离 用矩阵表示 1 物品库存管理 2 22 2 求权值功能求权值功能 求出将超市设在各个单位时 所得总的权值 返回用数组存储 2 32 3 求最优功能求最优功能 从上述的各个权值中 选出最小值为最优 并将最优值和对应的选址储存在链表中 返回头指针 2 42 4 显示功能显示功能 显示最优选址的地点 总权数以及各单位到它的距离 3 3 程序运行平台程序运行平台 Windows 操作系统 Visual C 4 4 总体设计总体设计 进入主函数 输入数据 求权值 求最优选址 输出最优信息 退出主函数 图 4
6、 1 总体流程图 5 5 程序说明程序说明 struct ZY 定义链表结构体 储存最优信息 double min int n 2 物品库存管理 ZY next void input int printf 请输入单位数量 scanf d 输入单位数量 printf n a float malloc n sizeof float 分配内存空间 for i 0 i n i a i float malloc n sizeof float 分配内存空间 b float malloc n sizeof float 分配内存空间 DW char malloc n sizeof char 分配内存空间 fo
7、r i 0 i n i DW i char malloc 20 sizeof char 分配内存空间 printf 请输入各单位的名称 n for i 0 i n i scanf s DW i 输入各单位名称 printf 请输入各单位去超市的频度 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 a i j double work sum float A float B int N 求各单位被选中后的总权值 int n N f
8、loat a A float b B int i j double s sum sum double malloc n sizeof double 分配内存空间 for i 0 i n i s 0 00 for j 0 jnext NULL 尾指针置空 for i 0 i n i if sum i min min 求最优权值 for i 0 in 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 Z
9、Y p char DW Dw int i k n N float a A float b B double min p head next min head min printf 最优选址如下 总权重 f n n min while p 显示最优选址信息 k p n printf 超市设立地点 s n DW k for i 0 inext 6 6 模块分析模块分析 6 16 1 输入功能输入功能 1 定义一个整型变量 储存输入的单位数 为矩阵等输入确定阶 2 定义一个二维的字符指针 用来储存输入的各个单位的名称 其中行数等于单位 数 因为一个单位名称一般不超过 20 个字符 所以列数取定值 2
10、0 3 定义一个一维的浮点型指针 用来储存输入的各单位去超市的频度 4 定义一个二维的浮点型指针 用来储存各单位间的距离 其中到自己的距离规定 为 0 注 注 各个单位的名称 去超市频度和它们间的距离输入顺序要一致 6 26 2 求权值功能求权值功能 对于每各单位来说 它们被选中时 所得权数就等于各个单位到它的距离乘以各 个单位去超市频度的积 再分别相加便是总权数 需要传入的参数是 指向单位间的距离矩阵的指针 指向单位去超是频度的指针 单位数量 需要返回的是 指向求得的权数的指针值 6 36 3 求最优功能求最优功能 在各个总权值中 最小的就是最优权值 我们将最优权值保留在第一个链表节点 由于
11、输入是按统一的顺序 所以最优权值在数组中的位置对应的单位就是最优选址 我们把与最优值相等的权值在数组中的位置 即下标 保留在后续节点中 6 46 4 显示功能显示功能 由于上述 最优权值在数组中的位置对应的单位就是最优选址 我们假设它在数 组中的位置是 i 那么单位名称数组中的第 i 个字符串就是最优选址的名称 距离矩阵 中第 i 列元素是各个单位到选址超市的距离 距离矩阵中第 i 列各元素与频度数组中与 该元素所在行的下标相同的值相乘就是相应单位到选址超市的权数 掌握了这各规律 一一计算后输出便是需要的结果 5 物品库存管理 7 7 系统测试系统测试 数据输入 图 7 1 输入数据窗口 显示
12、数据 图 7 2 显示最优信息窗口 8 8 结论结论 通过测试发现 当选址在临江苑和图书馆时 对应的总权值分别不大于九舍 说 明选址符合要求 6 物品库存管理 致谢致谢 首先 感谢老师的细心知道 没有老师的不求目的地教导 不可能这么快 这么 准确地完成设计 其次要感谢同学的帮助 使我能够准确 快速地获取信息帮助 7 物品库存管理 参考文献参考文献 1 严蔚敏 吴伟民 著 数据结构 C 语言版 第三版 北京 清华大学出 版社 2007 4 2 谭浩强 著 C 程序设计 第三版 北京 清华大学出版社 2006 9 3 Anany Levitin 著 潘彦 译 算法设计与分析基础 第二版 北京 清华
13、 大学出版社 2010 1 4 美 S 巴斯 著 计算机算法 设计和分析引论 朱洪等译 上海 复旦大学出 版社 1985 1 8 物品库存管理 附录 include include 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 分配内存空间 for i 0 i n i s 0
14、00 for j 0 jnext NULL 尾指针置空 for i 0 i n i if sum i min min 求最优权值 for i 0 in 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 float b B double min p head next min head min printf 最优选址如下 总权
15、重 f n n min while p 显示最优选址信息 k p n printf 超市设立地点 s n DW k for i 0 inext void input int printf 请输入单位数量 scanf d 输入单位数量 printf n a float malloc n sizeof float 分配内存空间 for i 0 i n i a i float malloc n sizeof float 分配内存空间 b float malloc n sizeof float 分配内存空间 DW char malloc n sizeof char 分配内存空间 for i 0 i n
16、 i 10 物品库存管理 DW i char malloc 20 sizeof char 分配内存空间 printf 请输入各单位的名称 n for i 0 i n i scanf s DW i 输入各单位名称 printf 请输入各单位去超市的频度 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 a i j void main float a float b double sum int n ZY head char DW input n a b DW sum work sum a b n head work min sum n print head DW n a b
