算法设计及分析课程设计.doc

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