算法设计与分析课程设计

1 课程设计 大作业 报告课程设计 大作业 报告 课程名称 算法设计与分析 设计题目 医院病床安排 院 系 信息技术学院 班 级 10 级计科 1 班 设 计 者 学 号 指导教师 设计时间 信 息 技 术 学 院 2 昆明学院课程设计 大作业 任务书昆明学院课程设计 大作业 任务书 姓 名 院 系 信息技术学院 专 业 计算机网络工程方向学 号 任务起止日期 2013 7 8 至 2013 7 11 课程设计题目 医院病床安排 课程设计要求 在处理每一个题目的时候 要从分析题目的需求入手 按设计抽象数据类型 构思算法 通过类的设计实现抽象数据类型 编制上机程序代码并调试的步骤完成题目 最终写出完 整的分析报告 见到题目 案头工作准备不足 忙于上机敲程序不是优秀程序员的工作风 格 注意设计与实现过程的经验积累 编码应尽量利用前阶段的成熟数据结构包 加大代 码的重用率 工作计划及安排 7 月 8 日 第一天 分好组并确定要完成的课程设计题目 上网查资料 7 月 9 日 第二天 根据第一天上网搜的资料开始着手做该课程设计题目 7 月 10 日 第三天 基本完成该课程设计所要求的内容 7 月 11 日 第四天 完善内容和调整格式准备答辩 指导教师签字 年 月 日 3 课程设计 大作业 成绩课程设计 大作业 成绩 学号 姓名 指导教师 课程设计题目 医院病床安排 总结 在本次的课程设计中 我遇到很多意想不到的问题 并没有开始我想的那样简 单 我开始的想法是先到先服务 但是最后想到问题的要求是要使等待的时间 最短 所以这个想法是不正确的 通过老师的提示和上网查阅资料 最后得出结 论就是用贪心算法来解决该问题才是最合理的 使每一个病人按住院时间短的 先入住 那就节省了后面等待入住病人的时间 相反之 如果使住院时间长的病 人先入住 那么后面等待入住的病人等待的时间就越长 这样就会使总体的等 待时间就越长 而平均等待时间 总等待时间 病人总数 我们这里讨论的是病 人总数一定 那么就只有总等待时间越小 平均等待时间就越短 故该问题的解 决方法就是用贪心算法策略 住院时间短的病人先住院 通过该次实训 也表现出了我们对课本理论知识的欠缺 团队合作精神也有待提高 今后需丰 富自己的理论知识和提高团队合作的精神 也要加强自己的动手能力 为步入 社会打下良好的实践动手能力 指导教师评语 成绩 填表时间 2013 年 7 月 11 日指导教师签名 4 课程设计 大作业 报告课程设计 大作业 报告 一 一 题目分析题目分析 随机产生 n 个病人 现医院有 m 张病床 m 张病床上当前已经有 p pn 时 病人可直接入住 当 x n 时 按住院时间短的先入住 分析 假设病人等待的时间为 T1 T2 T3 Tn 即总等待时间 T T1 T1 T2 T1 T2 T3 T1 T2 Tn 其中 T1 为第一个人的等待时间 T1 T2 是第二个人的等待时间 T1 T2 T3 Tn 是第 n 个人的等待时间 平均等待时间 总等待时间 病人总数 因等待时间是个确定的常数 所以 只可以从总等待时间这个变量下手 那如何使病人等待总时间最小呢 举例分 5 析 假设有三个病人分别为 n1 n2 n3 他们要住院的时间分别为 2 4 5 天 如果按病人 n1 n2 n3 顺序住院 那么总等待时间为 2 2 4 8 如果按病人 n1 n3 n2 顺序住院 那么总等待时间为 2 2 5 9 如果按病人 n3 n2 n1 顺序住院 那么总等待时间为 5 5 4 14 综上所述 要使总等待时间最短 那么安排最短住院时间病人先住院是符 合的 依次按空出床位给住院时间短的病人住院 那样得出的总等待时间就会 为最短 最后推出平均等待为最小 这种思路想法是按照贪心算法局部最优想 出来的 三三 程序代码程序代码 import java util Scanner import java util Arrays public class BestFuWu static public double greedy int x int s int n x length Arrays sort x System out println Arrays toString x int st new int n int su new int n int i 1 j 1 while is 6 j s 1 j s 1 循环分配病人到每一个病床上 double t 0 for i 1 i s i System out println 第 i 个病床队列上所有病人的等待时间 su i su i t su i t n 1 return t public static void main String args Scanner in new Scanner System in int n 等待病床的病人人数 int s 病床的个数 double t 平均住院时间 System out println 请输入等待病床的病人人数 n in nextInt int x new int n 1 System out println 请输入病床个数 s in nextInt System out println 请输入每个病人需要住院的时间 for int i 1 i n i System out println No i x i in nex