综合编程实验报告-值班安排祥解

“程序设计（Ⅱ）”综合编程实验报告（2012 -2013 学年第2 学期）实验项目名称： 值班安排一、实验内容与要求医院有A、B、C、D、E、F、G7位大夫，在一星期内（星期一至星期天）每人要轮流值班一天，如果已知：（1）A大夫比C大夫晚1天值班；（2）D大夫比E大夫晚1天值班；（3）E大夫比B大夫早2天值班（4）B大夫比G大夫早4天值班；（5）F大夫比B大夫晚1天值班；（6）F大夫比C大夫早1天值班；（7）F大夫星期四值班。就可以确定周一至周日的值班人员分别为： E、D、B、F、C、A、G。编写程序，根据输入的条件，输出星期一至星期天的值班人员。输入数据时，先输入一个整数n，再输入n组条件，要求能够根据输入的条件确定唯一的值班表，且输入的n组条件中能够直接或间接得到任意两位大夫的关联关系，例如上面的条件 (2)直接显示了 D与E间的关系，而通过条件（ 1）、6）、（5）可以间接得到A与B的关系。条件的输入格式有2种：格式1：编号比较运算符编号天数其中比较运算符有2种：>或<，分别表示“早”或“晚”例如：A<C1表示：A大夫比C大夫晚1天值班格式2：编号=数值例如：F=4 表示：F大夫在星期四值班输入输出示例7A<C1D<E1E>B2B>G4F<B1F>C1F=4EDBFCAG二、系统设计1、解题思路通过寻找有等号的条件，确定其医生的位置，然后把这个医生及其位置作为已知的结点，寻找与该医生有关的条件，确定另一位医生的位置，并把该位医生作为结点，继续寻找，以此递归。2、数据结构描述可以定义一个二维字符数组保存条件数据，大小为10*20，但从a[1]开始存放，以便与输入数据（位置值）匹配，另外用a[][0]来标记条件，还有定义为全局变量，因为函数里要用到。3、程序框架结构定义全局字符数组 s[30]来存放排好序的医生的位置。定义voidfunc(charnode,intka) ；4、关键算法描述（1）初始化用来存放顺序的数组为 '0'for(i=0;i<=29;i++)// 初始化用来存放顺序的数组为 '0's[i]='0';（2）存放测试数据的条件及标记这些条件for(i=1;i<=n;i++)// 存放测试数据的条件及标记这些条件{a[i][0]='0';scanf("%s",&a[i][1]);}（3）寻找条件中有等于号的，确定该位医生的值班时间，并通过该位医生确定其他与这位医生有关医生的值班时间for(i=1;i<=n;i++)// 寻找条件中有等于号的，确定该位医生的值班时间，并通过该位医生确定其他与这位医生有关医生的值班时间{if(a[i][2]=='='){ka=a[i][3]-'0';s[ka]=a[i][1];node=a[i][1];a[i][0]='1';// 把已确定时间的条件标记为 '1', 避免再次确定位置（避免重复搜索该条件）func(node,ka);// 调用函数，确定与该医生有关系的医生的值班时间}}考虑有些条件没有等于号，且还未确定值班时间的医生，通过假设该医生的位置，同时确定与该医生有关的医生值班时间for(i=1;i<=n;i++)// 考虑有些条件没有等于号，且还未确定值班时间的医生，通过假设该医生的位置，同时确定与该医生有关的医生值班时间{if(a[i][0]=='0')// 判断是否被标记过{node=a[i][1];s[20]=node;// 假设该医生的时间是在 20ka=20;//记录该医生的位置func(node,ka);// 同过函数，确定与该医生有关的医生与该医生的相对位置}}星期一到星期五是否都有医生值班for(i=1;i<=7;i++)//判断星期一到星期五是否都有医生值班if(s[i]=='0'){aa=i;flag=1;// 如果哪一天没人值班，记下那一天的时间并把flag 标记为1;break;}通过假设的位置，填充到数组的相应位置if(flag==1)// 通过假设的位置，填充到数组的相应位置{for(i=10;i<=29;i++)if(s[i]!='0'){ab=i;break;}for(i=aa;i<=7;i++){if(s[i]=='0')s[i]=s[ab-aa+i];}}输出医生值班的顺序表for(i=1;i<=7;i++)// 输出医生值班的顺序表printf("%c",s[i]);putchar(10);// 换行实现用已知医生及位置确定与其相关的医生的位置voidfunc(charnode,intka)// 实现用已知医生及位置确定与其相关的医生的位置{charnode1,ka1,kb1;intj;for(j=1;j<=n;j++){if(a[j][0]!='1')// 判断是否已确定位置的条件{if(a[j][1]==node||a[j][3]==node)// 判断是否与已知的医生有关的条件{a[j][0]='1';// 把该条件标记为'1', 避免再次使用确定该条件中还未确定位置的另一位医生的位置if(a[j][1]!=node){if(a[j][2]=='<')kb1=a[j][4]-'0';elsekb1=-(a[j][4]-'0');s[ka+kb1]=a[j][1];node1=a[j][1];ka1=ka+kb1;func(node1,ka1);//把该医生作为已知位置的医生来确定其他与这医生有关的医生}else{if(a[j][2]=='<')kb1=-(a[j][4]-'0');elsekb1=(a[j][4]-'0');s[ka+kb1]=a[j][3];node1=a[j][3];ka1=ka+kb1;func(node1,ka1);//把该医生作为已知位置的医生来确定其他与这医生有关的医生}}}}}三、测试用例测试用例1：输入：7A<C1D<E1E>B2B>G4F<B1F>C1F=4输出：EDBFCAG测试用例2：输入：6A>B1B>C1C>D1D>E1E>F1F>G1输出：ABCDEFG测试用例3：输入：7B>D2D=3A>D1C<A2E<A5G=6F>G1输出：BADCFGE测试用例4：输入：6A>B1C<B1C>D1D>E1E>F1G=7输出：ABCDEFG测试用例5：输入：6A>B1C<B1C>D1D>E1E>F1G=1输出：GABCDEF测试用例6：输入：7A<C1D<E1E>B3B>G3F>B1F>C2F=3输出：EDFBCAG测试用例7：输入：8A>B1D<C1B>E3E<C2E=5F<E1G<D3G=7输出：ABCDEFG⋯四、总结介绍程序的完成情况，有待改进之处，以及有何收获、体会等。我觉得我完成的速度和情况还算不错， 当然刚开始的时候考虑的方面有限， 只考虑到买个医生必须都出现， 而且必需直接或间接知道两两医生的相对位置， 虽然这就是题目的要求的内容，但作为一个编程的爱好者， 我自然加入了一些个人的想法，如：不能直接知道两两医生的相对位置，但可以估测其他医生的位置，且具有唯一真值，如：输入：6A>B1C<B1C>D1D>E1E>F1G=7输出：ABCDEFG只知道g的位置和a到f的相对位置，那么a到f只能在星期一到星期六的位置，因此得出星期一到星期日的值班安排。我还是有一些想到的bug，但还是没想到解决办法，这也是这程序的不完美之处，如：5A>C2C>D1D>G3G=7E>F1这时的答案应为：ABCDEFG收获：在编程时，但我的到我要的预期效果，我会感到很高兴。#include<stdio.h>chars[30],a[20][10];//用来存放值班顺序及题目该给的条件intn;voidfunc(charnode,intka)// 实现用已知医生及位置确定与其相关的医生的位置{charnode1,ka1,kb1;intj;for(j=1;j<=n;j++){if(a[j][0]!='1')// 判断是否已确定位置的条件{if(a[j][1]==node||a[j][3]==node)// 判断是否与已知的医生有关的条件{a[j][0]='1';// 把该条件标记为'1', 避免再次使用确定该条件中还未确定位置的另一位医生的位置if(a[j][1]!=node){if(a[j][2]=='<')kb1=a[j][4]-'0';elsekb1=-(a[j][4]-'0');s[ka+kb1]=a[j][1];node1=a[j][1];ka1=ka+kb1;func(node1,ka1);// 把该医生作为已知位置的医生来确定其他与这医生有关的医生}else{if(a[j][2]=='<')kb1=-(a[j][4]-'0');elsekb1=(a[j][4]-'0');s[ka+kb1]=a[j][3];node1=a[j][3];ka1=ka+kb1;func(node1,ka1);//把该医生作为已知位置的医生来确定其他与这医生有关的医生}}}}}intmain(){inti,ka,aa,ab,flag=0;charnode;while(scanf("%d",&n)!=EOF){getchar();for(i=0;i<=29;i++)// 初始化用来存放顺序的数组为 '0's[i]='0';for(i=1;i<=n;i++)// 存放测试数据的条件及标记这些条件{a[i][0]='0';scanf("%s",&a[i][1]);}for(i=1;i<=n;i++)//寻找条件中有等于号的，确定该位医生的值班时间，并通过该位医生确定其他与这位医生有关医生的值班时间{if(a[i][2]=='='){ka=a[i][3]-'0';s[ka]=a[i][1];node=a[i][1];a[i][0]='1';// 把已确定时间的条件标记为 '1', 避免再次确定位置（避免重复搜索该条件）func(node,ka);// 调用函数，确定与该医生有关系的医生的值班时间}}for(i=1;i<=n;i++)//考虑有些条件没有等于号，且还未确定值班时间的医生，通过假设该医生的位置，同时确定与该医生有关的医生值班时间{if(a[i][0]=='0')// 判断是否被标记过{node=a[i][1];s[20]=node;// 假设该医生的时间是在 20ka=20;//记录该医生的位置func(node,ka);// 同过函数，确定与该医生有关的医生与该医生的相对位置}}flag=0;//flag 标记为0；for(i=1;i<=7;i++)// 判断星期一到星期五是否都有医生值班if(s[i]=='0'){aa=i;flag=1;//