算法设计与分析课程设计

《算法设计与分析课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计（大作业）报告课程名称：算法设计与分析设计题目：医院病床安排院系：信息技术学院班级：10级计科1班设计者：学号：指导教师：设计时间：信息技术学院7昆明学院课程设计（大作业）任务书姓名：院（系）：信息技术学院专业：计算机网络工程方向学号：任务起止日期：2013-7-8至2013-7-11课程设计题目：医院病床安排课程设计要求：在处理每一个题目的时候，要从分析题目的需求入手，按设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型、编制上机程序代码并调试的步骤完成题目，最终写出完整的分析报告。见到题目，案头工作准备不足，忙于上机敲程序不是优秀程序员的工作风格。注意设

2、计与实现过程的经验积累，编码应尽量利用前阶段的成熟数据结构包，加大代码的重用率。工作计划及安排：7月8日：（第一天）分好组并确定要完成的课程设计题目，上网查资料；7月9日：（第二天）根据第一天上网搜的资料开始着手做该课程设计题目；7月10日：（第三天）基本完成该课程设计所要求的内容；7月11日：（第四天）完善内容和调整格式准备答辩；指导教师签字年月日7课程设计（大作业）成绩学号：姓名：指导教师：课程设计题目：医院病床安排总结：在本次的课程设计中,我遇到很多意想不到的问题,并没有开始我想的那样简单,我开始的想法是先到先服务,但是最后想到问题的要求是要使等待的时间最短,所以这

3、个想法是不正确的,通过老师的提示和上网查阅资料,最后得出结论就是用贪心算法来解决该问题才是最合理的,使每一个病人按住院时间短的先入住,那就节省了后面等待入住病人的时间,相反之,如果使住院时间长的病人先入住,那么后面等待入住的病人等待的时间就越长,这样就会使总体的等待时间就越长,而平均等待时间=总等待时间/病人总数,我们这里讨论的是病人总数一定,那么就只有总等待时间越小,平均等待时间就越短,故该问题的解决方法就是用贪心算法策略——住院时间短的病人先住院。通过该次实训，也表现出了我们对课本理论知识的欠缺，团队合作精神也有待提高，今后需丰富自己的理论知识和提高团队合作的精神。也

4、要加强自己的动手能力，为步入社会打下良好的实践动手能力。最短务到指导教师评语：成绩：填表时间：2013年7月11日指导教师签名：7课程设计（大作业）报告一、题目分析随机产生n个病人，现医院有m张病床，m张病床上当前已经有p(p<=m)位正在住院的病人，每个已经住院或准备住院的病人都有对应自身的住院时长。合理安排所有病人，使所有病

5、人在最短等待时间完成住院治疗。病人看病的流程是:挂号,排队等待安排住院时间,住院,手术,出院等几个阶段。医院实行先到先服务的原则。既如果问诊时有剩余床位，可立即入住，如果没有，则排队等待，同时医院对急诊病人有特殊照顾，如果是外伤，则不需要排队，可直接接受服务。既外伤病人有较高的优先权。其排队流程可如下图所示：因为病人n是确定的常数，我们在分析该问题时不考虑后面病人的增加，平均等待时间=总等待时间/病人总数，因为病人总数n是确定的，所以只要下去分析如何使总等待时间最小就行。二、算法设计与思路总体思想：设剩余的床位为x，则x=m-p，当x>n时，病人可直接入住；当x

6、住院时间短的先入住。分析：假设病人等待的时间为T1,T2,T3……Tn即总等待时间T=T1+(T1+T2)+(T1+T2+T3)+…+(T1+T2+…+Tn)其中T1为第一个人的等待时间，(T1+T2)是第二个人的等待时间，……，(T1+T2+T3+…+Tn)是第n个人的等待时间。平均等待时间=总等待时间/病人总数，因等待时间是个确定的常数，所以只可以从总等待时间这个变量下手，那如何使病人等待总时间最小呢？举例分析：假设有三个病人分别为n1,n2,n3，他们要住院的时间分别为2，4，5（天）7如果按病人n1,n2,n3顺序住院，那么总等待时间为2+（2+4）=8；如果按病

7、人n1,n3,n2顺序住院，那么总等待时间为2+（2+5）=9；如果按病人n3,n2,n1顺序住院，那么总等待时间为5+（5+4）=14；…………………………………………综上所述，要使总等待时间最短，那么安排最短住院时间病人先住院是符合的，依次按空出床位给住院时间短的病人住院，那样得出的总等待时间就会为最短，最后推出平均等待为最小，这种思路想法是按照贪心算法局部最优想出来的。三、程序代码importjava.util.Scanner;importjava.util.Arrays;publicclassBestFuWu{stat