文档介绍：1
课程设计（大作业）报告
课程名称： 算法设计与分析
设计题目： 医院病床安排
院 系： 信息技术学院
班 级： 10 级计科1班
设 院时间长的病人先入住,那么后面等待入住的病人等待的时间就越长,这样就会使总体的等待时间就越长,而平均等待时间=总等待时间/病人总数,我们这里讨论的是病人总数一定,那么就只有总等待时间越小,平均等待时间就越短,故该问题的解决方法就是用贪心算法策略——住院时间短的病人先住院。通过该次实训，也表现出了我们对课本理论知识的欠缺，团队合作精神也有待提高，今后需丰富自己的理论知识和提高团队合作的精神。也要加强自己的动手能力，为步入社会打下良好的实践动手能力。
指导教师评语：
成绩：
填表时间：2013年7月11日 指导教师签名：
4
课程设计（大作业）报告
题目分析
随机产生n个病人，现医院有m张病床，m张病床上当前已经有p(p<=m)位正在住院的病人，每个已经住院或准备住院的病人都有对应自身的住院时长。合理安排所有病人，使所有病人在最短等待时间完成住院治疗。
病人看病的流程是:挂号,排队等待安排住院时间,住院,手术,出院等几个阶段。医院实行先到先服务的原则。既如果问诊时有剩余床位，可立即入住，如果没有，则排队等待，同时医院对急诊病人有特殊照顾，如果是外伤，则不需要排队，可直接接受服务。既外伤病人有较高的优先权。其排队流程可如下图所示：
因为病人n是确定的常数，我们在分析该问题时不考虑后面病人的增加，平均等待时间=总等待时间/病人总数，因为病人总数n是确定的，所以只要下去分析如何使总等待时间最小就行。
算法设计与思路
总体思想： 设剩余的床位为x，则x=m-p，当x>n时，病人可直接入住；当x<n时，按住院时间短的先入住。
分析：假设病人等待的时间为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（天）
5
如果按病人n1,n2,n3顺序住院，那么总等待时间为2+（2+4）=8；
如果按病人n1,n3,n2顺序住院，那么总等待时间为2+（2+5）=9；
如果按病人n3,n2,n1顺序住院，那么总等待时间为5+（5+4）=14；
…………………………………………
综上所述，要使总等待时间最短，那么安排最短住院时间病人先住院是符合的，依次按空出床位给住院时间短的病人住院，那样得出的总等待时间就会为最短，最后推出平均等待为最小，这种思路想法是按照贪心算法局部最优想出来的。
三、程序代码
import ;