5.值班安排C语言程序报告

“程序设计（Ⅱ）”综合编程实验报告（2011–2012学年第2学期）实验项目名称：值班安排学生姓名：钱雪峰专业班级：计算1103学号：31101178一、实验内容与要求医院有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种：或，分别表示“早”或“晚”例如：AC1表示：A大夫比C大夫晚1天值班格式2：编号=数值例如：F=4表示：F大夫在星期四值班输入输出示例7AC1DE1EB2BG4FB1FC1F=4EDBFCAG7CB1DC1ED1GE1AG1FA1FB6BCDEGAF6AB3CF1DC5GA2EB4BC1BCFAEGD6AB1CA1DC1ED1BG5F=1FBACDEG二、系统设计1、解题思路分三种情况讨论1、带有“=”的情况：这类情况只需先把确定日期的医生排好，然后通过和已经确定的医生比较来确定其他医生的值班情况，剩下的再和之前确定的医生比较，以此类推2、没有“=”的情况：只需要定义一个一维14长度的数组，然后将第一个医生放入第7个位置，再依次和这位医生比较确定其他医生，剩下的再和之前确定的医生比较，以此类推3、有“=”但其他条件和有“=”的无关联：先按照情况2排好然后将剩下的填入空缺，如果是星期一则放在第一个，星期天则放在最后2、数据结构描述存储条件的数组char[100][5]；第一种情况定义了数组charc[7]来存储给出确定值班日期的医生，用一个一维7长度的数组intp[7]用来存储每个医生值班的时间，并且用一个二维数组来存储每两个医生之间的值班关系；第二种情况定义了一个一维14长度的数组charpi[14]用来存放值班医生从中间开始放，用数组intf[100]来存储下一个和前一字母条件相关联的字幕的位置，用数组intlibai[7]来存储给出确定值班日期的医生；第三种情况则是前两种情况的结合，所以不用再另外定义4、程序框架结构主函数intmain（）子函数intset()用来输出第一种情况的结果；主函数程序流程图：输入所有条件含有“=”条件但此条件中医生和其他条件无关联含有“=”条件且此条件中医生和其他条件有关联不含“=”的条件将含“=”的已确定值班日期医生排入数组，然后找出和这名医生有关联的医生排入值班表，再找出和刚排入值班表的医生有关联的医生排入值班表，以此类推从第一个不是“NULL”的字符开始输出将第一个出现在条件中医生存储在pi[7]然后找出和这名医生有关联的医生排入值班表，再找出和刚排入值班表的医生有关联的医生排入值班表，以此类推，其余的用NULL代替用第三种情况的方法将没有“=”条件的医生排入数组pi中，将含“=”的条件存储在数组libai中其余的用NULL代替，保存一个数据代表在pi中第一个医生之前的值班医生数量，在pi中空出来，依次将pi中NULL的地方填入libai中已确定值班日期的医生调用子函数：按照数组中存储的顺序输出医生值班顺序5、关键算法描述保存所有有关联的医生值班相差的日期，+表示早-表示晚for(i=0;in;i++){a=s[i][0]-'A';b=s[i][2]-'A';if(s[i][1]=='='){p[s[i][0]-'A']=s[i][2]-'1';}elseif(s[i][1]==''){m[b][a]=-(s[i][3]-'0');m[a][b]=-m[b][a];}else{m[a][b]=-(s[i][3]-'0');m[b][a]=-m[a][b];}}没有“=”条件，将打一个医生排在pi[7]的算法pi[7]=s[0][0];f[0]=7;l=1;num=1;while(num=n){for(i=0;in;i++){for(j=0;jn;j++){if(s[j][0]!='0'&&s[j][0]==pi[f[i]]){if(s[j][1]=='')t=s[j][3]-'0';elset=-(s[j][3]-'0');f[l]=f[i]+t;pi[f[l]]=s[j][2];l++;s[j][0]='0';num++;}elseif(s[j][0]!='0'&&s[j][2]==pi[f[i]]){if(s[j][1]=='')t=-(s[j][3]-'0');elset=s[j][3]-'0';f[l]=f[i]+t;pi[f[l]]=s[j][0];l++;s[j][0]='0';num++;}}}将含“=”但与其他条件不相关的医生存入以确定的无“=”的顺序之中for(i=0;i14;i++){if(pi[i]!=NULL){qi=i;break;}}for(i=0;i7;i++){if(libai[i]!=NULL)qi-=1;elsebreak;}k=0;for(i=qi;iqi+7;i++){if(pi[i]==NULL){for(j=k;j7;j++){if(libai[j]!=NULL){printf(%c,libai[j]);k=j;break;}}}elseprintf(%c,pi[i]);}三、测试用例测试用例1：测试用例2：测试用例3：测试用例4：四、总结程序总在不断的改善中先是只考虑了第一种情况，编好之后发现还有第二种情况，这也是最难的情况，方法是借鉴其他类似题目的，但是真真难的确实其中的许多变量，很容易搞混，难以理清。其中第二种情况关键程序可以编写成函数，然后第三种情况可以调用，但由于这是一个比较耗时的事情，在不求完美的情况下就不再改了。由于还有一类以目前水平难以处理的情况，因此在此程序中排除这类情况附录全代码：#includestdio.h#includestring.hstaticintm[7][7];intp[7]={-1,-1,-1,-1,-1,-1,-1};voidset(intmin,intn){inti;for(i=0;in;i++){if(p[i]-1||m[min][i]==0)continue;p[i]=m[min][i]+p[min];set(i,n);}}intmain(){intf[100],l=0,n,i,j,k=0,num=0,a,b,count=0,t,ji=0,qi;chars[100][5],pi[14],c[7],libai[7];scanf(%d,&n);for(i=0;in;i++)scanf(%s,s[i]);for(i=0;i7;i++)libai[i]=NULL;for(i=0;i14;i++)pi[i]=NULL;for(i=0;in;i++){if(s[i][1]=='='){count++;libai[s[i][2]-'1']=s[i][0];c[k++]=s[i][0];}}if(count=1){for(j=0;jn;j++){for(i=0;in;i++){if(s[i][0]==c[j])ji++;elseif(s[i][2]==c[j])ji++;}}if(jicount){for(i=0;in;i++){a=s[i][0]-'A';b=s[i][2]-'A';if(s[i][1]=='='){p[s[i][0]-'A']=s[i][2]-'1';}elseif(s[i][1]==''){m[b][a]=-(s[i][3]-'0');m[a][b]=-m[b][a];}else{m[a][b]=-(s[i][3]-'0');m[b][a]=-m[a][b];}}for(i=0;i7;i++){if(p[i]-1)set(i,7);}for(i=0;i7;i++){for(b=0;b7;b++){if(p[b]==i){putchar(b+'A');}}}puts();}elseif(count==ji){pi[7]=s[0][0];f[0]=7;l=1;num=1;while(num=(n-count)){for(i=0;in;i++){for(j=0;jn;j++){if(s[j][0]!='0'&&s[j][0]==pi[f[i]]&&s[j][1]!='='){if(s[j][1]=='')t=s[j][3]-'0';elset=-(s[j][3]-'0');f[l]=f[i]+t;pi[f[l]]=s[j][2];l++;s[j][0]='0';num++;}elseif(s[j][0]!='0'&&s[j][2]==pi[f[i]]&&s[j][1]!='='){if(s[j][1]=='')t=-(s[j][3]-'0');elset=s[j][3]-'0';f[l]=f[i]+t;pi[f[l]]=s[j][0];l++;s[j][0]='0';num++;}}}}for(i=0;i14;i++){if(pi[i]!=NULL){qi=i;break;}}for(i=0;i7;i++){if(libai[i]!=NULL)qi-=1;elsebreak;}k=0;for(i=qi;iqi+7;i++){if(pi[i]==NULL){for(j=k;j7;j++){if(libai[j]!=NULL){printf(%c,libai[j]);k=j;break;}}}elseprintf(%c,pi[i]);}printf(\n);}}else{pi[7]=s[0][0];f[0]=7;l=1;num=1;while(num=n){for(i=0;in;i++){for(j=0;jn;j++){if(s[j][0]!='0'&&s[j][0]==pi[f[i]]){if(s[j][1]=='')t=s[j][3]-'0';elset=-(s[j][3]-'0');f[l]=f[i]+t;pi[f[l]]=s[j][2];l++;s[j][0]='0';num++;}elseif(s[j][0]!='0'&&s[j][2]==pi[f[i]]){if(s[j][1]=='')t=-(s[j][3]-'0');elset=s[j][3]-'0';f[l]=f[i]+t;pi[f[l]]=s[j][0];l++;s[j][0]='0';num++;}}}}for(i=0;i14;i++){if(pi[i]!=NULL)printf(%c,pi[i]);}printf(\n);}return0;}