綜合編程實驗報告-值班安排祥解

“程序設(shè)計（Ⅱ）”綜合編程實驗報告（2012 -2013 學(xué)年第2 學(xué)期）實驗項目名稱： 值班安排一、實驗內(nèi)容與要求醫(yī)院有A、B、C、D、E、F、G7位大夫，在一星期內(nèi)（星期一至星期天）每人要輪流值班一天，如果已知：（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。編寫程序，根據(jù)輸入的條件，輸出星期一至星期天的值班人員。輸入數(shù)據(jù)時，先輸入一個整數(shù)n，再輸入n組條件，要求能夠根據(jù)輸入的條件確定唯一的值班表，且輸入的n組條件中能夠直接或間接得到任意兩位大夫的關(guān)聯(lián)關(guān)系，例如上面的條件 (2)直接顯示了 D與E間的關(guān)系，而通過條件（ 1）、6）、（5）可以間接得到A與B的關(guān)系。條件的輸入格式有2種：格式1：編號比較運算符編號天數(shù)其中比較運算符有2種：>或<，分別表示“早”或“晚”例如：A<C1表示：A大夫比C大夫晚1天值班格式2：編號=數(shù)值例如：F=4 表示：F大夫在星期四值班輸入輸出示例7A<C1D<E1E>B2B>G4F<B1F>C1F=4EDBFCAG二、系統(tǒng)設(shè)計1、解題思路通過尋找有等號的條件，確定其醫(yī)生的位置，然后把這個醫(yī)生及其位置作為已知的結(jié)點，尋找與該醫(yī)生有關(guān)的條件，確定另一位醫(yī)生的位置，并把該位醫(yī)生作為結(jié)點，繼續(xù)尋找，以此遞歸。2、數(shù)據(jù)結(jié)構(gòu)描述可以定義一個二維字符數(shù)組保存條件數(shù)據(jù)，大小為10*20，但從a[1]開始存放，以便與輸入數(shù)據(jù)（位置值）匹配，另外用a[][0]來標(biāo)記條件，還有定義為全局變量，因為函數(shù)里要用到。3、程序框架結(jié)構(gòu)定義全局字符數(shù)組 s[30]來存放排好序的醫(yī)生的位置。定義voidfunc(charnode,intka) ；4、關(guān)鍵算法描述（1）初始化用來存放順序的數(shù)組為 '0'for(i=0;i<=29;i++)// 初始化用來存放順序的數(shù)組為 '0's[i]='0';（2）存放測試數(shù)據(jù)的條件及標(biāo)記這些條件for(i=1;i<=n;i++)// 存放測試數(shù)據(jù)的條件及標(biāo)記這些條件{a[i][0]='0';scanf("%s",&a[i][1]);}（3）尋找條件中有等于號的，確定該位醫(yī)生的值班時間，并通過該位醫(yī)生確定其他與這位醫(yī)生有關(guān)醫(yī)生的值班時間for(i=1;i<=n;i++)// 尋找條件中有等于號的，確定該位醫(yī)生的值班時間，并通過該位醫(yī)生確定其他與這位醫(yī)生有關(guān)醫(yī)生的值班時間{if(a[i][2]=='='){ka=a[i][3]-'0';s[ka]=a[i][1];node=a[i][1];a[i][0]='1';// 把已確定時間的條件標(biāo)記為 '1', 避免再次確定位置（避免重復(fù)搜索該條件）func(node,ka);// 調(diào)用函數(shù)，確定與該醫(yī)生有關(guān)系的醫(yī)生的值班時間}}考慮有些條件沒有等于號，且還未確定值班時間的醫(yī)生，通過假設(shè)該醫(yī)生的位置，同時確定與該醫(yī)生有關(guān)的醫(yī)生值班時間for(i=1;i<=n;i++)// 考慮有些條件沒有等于號，且還未確定值班時間的醫(yī)生，通過假設(shè)該醫(yī)生的位置，同時確定與該醫(yī)生有關(guān)的醫(yī)生值班時間{if(a[i][0]=='0')// 判斷是否被標(biāo)記過{node=a[i][1];s[20]=node;// 假設(shè)該醫(yī)生的時間是在 20ka=20;//記錄該醫(yī)生的位置func(node,ka);// 同過函數(shù)，確定與該醫(yī)生有關(guān)的醫(yī)生與該醫(yī)生的相對位置}}星期一到星期五是否都有醫(yī)生值班for(i=1;i<=7;i++)//判斷星期一到星期五是否都有醫(yī)生值班if(s[i]=='0'){aa=i;flag=1;// 如果哪一天沒人值班，記下那一天的時間并把flag 標(biāo)記為1;break;}通過假設(shè)的位置，填充到數(shù)組的相應(yīng)位置if(flag==1)// 通過假設(shè)的位置，填充到數(shù)組的相應(yīng)位置{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];}}輸出醫(yī)生值班的順序表for(i=1;i<=7;i++)// 輸出醫(yī)生值班的順序表printf("%c",s[i]);putchar(10);// 換行實現(xiàn)用已知醫(yī)生及位置確定與其相關(guān)的醫(yī)生的位置voidfunc(charnode,intka)// 實現(xiàn)用已知醫(yī)生及位置確定與其相關(guān)的醫(yī)生的位置{charnode1,ka1,kb1;intj;for(j=1;j<=n;j++){if(a[j][0]!='1')// 判斷是否已確定位置的條件{if(a[j][1]==node||a[j][3]==node)// 判斷是否與已知的醫(yī)生有關(guān)的條件{a[j][0]='1';// 把該條件標(biāo)記為'1', 避免再次使用確定該條件中還未確定位置的另一位醫(yī)生的位置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);//把該醫(yī)生作為已知位置的醫(yī)生來確定其他與這醫(yī)生有關(guān)的醫(yī)生}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);//把該醫(yī)生作為已知位置的醫(yī)生來確定其他與這醫(yī)生有關(guān)的醫(yī)生}}}}}三、測試用例測試用例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?四、總結(jié)介紹程序的完成情況，有待改進(jìn)之處，以及有何收獲、體會等。我覺得我完成的速度和情況還算不錯， 當(dāng)然剛開始的時候考慮的方面有限， 只考慮到買個醫(yī)生必須都出現(xiàn)， 而且必需直接或間接知道兩兩醫(yī)生的相對位置， 雖然這就是題目的要求的內(nèi)容，但作為一個編程的愛好者， 我自然加入了一些個人的想法，如：不能直接知道兩兩醫(yī)生的相對位置，但可以估測其他醫(yī)生的位置，且具有唯一真值，如：輸入：6A>B1C<B1C>D1D>E1E>F1G=7輸出：ABCDEFG只知道g的位置和a到f的相對位置，那么a到f只能在星期一到星期六的位置，因此得出星期一到星期日的值班安排。我還是有一些想到的bug，但還是沒想到解決辦法，這也是這程序的不完美之處，如：5A>C2C>D1D>G3G=7E>F1這時的答案應(yīng)為：ABCDEFG收獲：在編程時，但我的到我要的預(yù)期效果，我會感到很高興。#include<stdio.h>chars[30],a[20][10];//用來存放值班順序及題目該給的條件intn;voidfunc(charnode,intka)// 實現(xiàn)用已知醫(yī)生及位置確定與其相關(guān)的醫(yī)生的位置{charnode1,ka1,kb1;intj;for(j=1;j<=n;j++){if(a[j][0]!='1')// 判斷是否已確定位置的條件{if(a[j][1]==node||a[j][3]==node)// 判斷是否與已知的醫(yī)生有關(guān)的條件{a[j][0]='1';// 把該條件標(biāo)記為'1', 避免再次使用確定該條件中還未確定位置的另一位醫(yī)生的位置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);// 把該醫(yī)生作為已知位置的醫(yī)生來確定其他與這醫(yī)生有關(guān)的醫(yī)生}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);//把該醫(yī)生作為已知位置的醫(yī)生來確定其他與這醫(yī)生有關(guān)的醫(yī)生}}}}}intmain(){inti,ka,aa,ab,flag=0;charnode;while(scanf("%d",&n)!=EOF){getchar();for(i=0;i<=29;i++)// 初始化用來存放順序的數(shù)組為 '0's[i]='0';for(i=1;i<=n;i++)// 存放測試數(shù)據(jù)的條件及標(biāo)記這些條件{a[i][0]='0';scanf("%s",&a[i][1]);}for(i=1;i<=n;i++)//尋找條件中有等于號的，確定該位醫(yī)生的值班時間，并通過該位醫(yī)生確定其他與這位醫(yī)生有關(guān)醫(yī)生的值班時間{if(a[i][2]=='='){ka=a[i][3]-'0';s[ka]=a[i][1];node=a[i][1];a[i][0]='1';// 把已確定時間的條件標(biāo)記為 '1', 避免再次確定位置（避免重復(fù)搜索該條件）func(node,ka);// 調(diào)用函數(shù)，確定與該醫(yī)生有關(guān)系的醫(yī)生的值班時間}}for(i=1;i<=n;i++)//考慮有些條件沒有等于號，且還未確定值班時間的醫(yī)生，通過假設(shè)該醫(yī)生的位置，同時確定與該醫(yī)生有關(guān)的醫(yī)生值班時間{if(a[i][0]=='0')// 判斷是否被標(biāo)記過{node=a[i][1];s[20]=node;// 假設(shè)該醫(yī)生的時間是在 20ka=20;//記錄該醫(yī)生的位置func(node,ka);// 同過函數(shù)，確定與該醫(yī)生有關(guān)的醫(yī)生與該醫(yī)生的相對位置}}flag=0;//flag 標(biāo)記為0；for(i=1;i<=7;i++)// 判斷星期一到星期五是否都有醫(yī)生值班if(s[i]=='0'){aa=i;flag=1;//