狼羊白菜實(shí)驗(yàn)報(bào)告

南京郵電大學(xué)通達(dá)學(xué)院程序設(shè)計(jì)(上機(jī))匯報(bào)題目:R004M,P005H專業(yè)網(wǎng)絡(luò)工程學(xué)生姓名班級(jí)學(xué)號(hào)指導(dǎo)教師日期評(píng)分細(xì)則評(píng)分項(xiàng)優(yōu)異良好中等及格不及格恪守機(jī)房規(guī)章制度上機(jī)表現(xiàn)學(xué)習(xí)態(tài)度基礎(chǔ)知識(shí)水平程序設(shè)計(jì)能力課題功效實(shí)現(xiàn)情況算法設(shè)計(jì)合理性用戶界面友好性匯報(bào)書寫認(rèn)真程度匯報(bào)內(nèi)容完整性文字表示清楚程度問題回答準(zhǔn)確性評(píng)分等級(jí)教師署名：年月日備注注：評(píng)分等級(jí)分為五種：優(yōu)異、良好、中等、及格、不及格狼羊白菜過河程序試驗(yàn)匯報(bào)問題描述一個(gè)人帶著一只羊，一條狼和一顆白菜想過河，假設(shè)他每次只能帶一只羊，或者一條狼，或者一顆白菜過河，并限定人不在場時(shí)，狼和羊，或羊和白菜不能單獨(dú)在一起，試編寫程序求出他帶一只羊，一條狼和一顆白菜過河方法。結(jié)構(gòu)圖過河過河農(nóng)夫選擇相斥共存程序運(yùn)行輸出結(jié)果三、結(jié)構(gòu)設(shè)計(jì)1、狼和羊、羊和白菜不能單獨(dú)在一起，包括對(duì)象較多，而且運(yùn)算步驟方法較為復(fù)雜，要用程序語言實(shí)現(xiàn)，需要將詳細(xì)實(shí)例數(shù)字化。針對(duì)實(shí)現(xiàn)整個(gè)過程需要多步，不一樣時(shí)驟中各個(gè)事物所處位置不一樣情況，可定義一個(gè)二維數(shù)組或者結(jié)構(gòu)體來實(shí)現(xiàn)對(duì)四個(gè)對(duì)象狼、羊、白菜和一個(gè)人表示。對(duì)于岸兩側(cè)能夠用0或者1來表示，以實(shí)現(xiàn)在程序設(shè)計(jì)中簡便性。對(duì)狼羊白菜過河步驟，沒有次序約束，所以需要給各個(gè)事物依次進(jìn)行編號(hào)，然后依次嘗試，若成功，進(jìn)行下一步，使用循環(huán)或者遞歸算法進(jìn)行程序程序使用遞歸算法，為了方便將各個(gè)實(shí)例數(shù)字化。定義二維數(shù)組inta[M][4]存放每一步中各個(gè)對(duì)象所處位置，用0-3分別表示二維數(shù)組一維下標(biāo)。詳細(xì)對(duì)應(yīng)為：wolf-0goat-1cabbage-2people-3將本岸和對(duì)岸數(shù)字化，其對(duì)應(yīng)為：本（東）岸-0對(duì)（西）岸-1詳細(xì)對(duì)應(yīng)實(shí)例比如在第3步之后狼在本岸，羊在對(duì)岸，白菜在本岸，農(nóng)夫在對(duì)岸，則其存放結(jié)果為：a[3][0]a[3][1]a[3][2]a[3][3]0101最初存放狀態(tài)為：a[0][0]a[0][1]a[0][2]a[0][3]0000成功渡河之后，二維數(shù)組存放應(yīng)為：a[istep][0]a[istep][1]a[istep][2]a[istep][3]1111所以a[iStep][0]+a[iStep][1]+a[iStep][2]+a[iStep][3]==4。題目要求狼和羊、羊和白菜不能在一起，即出現(xiàn)以下情況：a[iStep][1]!=a[iStep][3]&&(a[iStep][2]==a[iStep][1]||a[iStep][0]==a[iStep][1])則出現(xiàn)錯(cuò)誤，應(yīng)返回操作。遞歸開始結(jié)束a[0][0]=0,a[0][1]=0,a[0][2]=0,a[0][3]=0遞歸開始結(jié)束a[0][0]=0,a[0][1]=0,a[0][2]=0,a[0][3]=0同時(shí)定義一維數(shù)組b[M]來存放每一步中人是怎樣過河。設(shè)計(jì)程序中實(shí)現(xiàn)遞歸操作部分關(guān)鍵程序?yàn)椋篺or(i=-1;i<=2;i++){b[iStep]=i;memcpy(a[iStep+1],a[iStep],16);a[iStep+1][3]=1-a[iStep+1][3];if(i==-1){search(iStep+1);}elseif(a[iStep][i]==a[iStep][3]){a[iStep+1][i]=a[iStep+1][3];search(iStep+1);}}每次循環(huán)從-1到2依次代表渡河時(shí)為一人、帶狼、帶羊、帶白菜經(jīng)過，利用語句“b[iStep]=i”分別統(tǒng)計(jì)每一步中渡河方式，“a[iStep+1][i]=a[iStep+1][3]”即利用賦值方式使狼或羊或白菜與人一同到對(duì)岸或者回到本岸。若渡河成功，則依次輸出渡河方式?！癷<=2”即為操作限制，當(dāng)若i=2時(shí)仍無符合條件方式，則渡河失敗。在遞歸過程中每進(jìn)行一步都需要判斷是否需要繼續(xù)進(jìn)行此次操作，詳細(xì)判斷為：（1）若該步驟能使各值均為1，則渡河成功，輸出結(jié)果。if(a[iStep][0]+a[iStep][1]+a[iStep][2]+a[iStep][3]==4){……return}（2）若該步與以前步驟相同，返回操作。if(memcmp(a[i],a[iStep],16)==0){return;}（3）若羊和人不在一塊而狼和羊或者羊和白菜在一塊，則返回操作。if(a[iStep][1]!=a[iStep][3]&&(a[iStep][2]==a[iStep][1]||a[iStep][0]==a[iStep][1])){return;}四、處理流程圖：search（iStep）search（iStep）人狼羊白菜在本岸人狼羊白菜在本岸輸出處理方案Y輸出處理方案YN狼羊白菜單獨(dú)在一起？狼羊白菜單獨(dú)在一起？Yreturnreturn此狀態(tài)態(tài)與前面相同？結(jié)束search(istep+1)i++i<=2?i=-1N此狀態(tài)態(tài)與前面相同？結(jié)束search(istep+1)i++i<=2?i=-1YNNY源程序#include<stdio.h>#include<stdlib.h>#include<string.h>#defineM10inta[M][4];intb[M];char*name[]={"","andwolf","andgoat","andcabbage"};voidsearch(intiStep){inti;if(a[iStep][0]+a[iStep][1]+a[iStep][2]+a[iStep][3]==4){for(i=0;i<=iStep;i++){printf("本岸:");if(a[i][0]==0)printf("wolf");if(a[i][1]==0)printf("goat");if(a[i][2]==0)printf("cabbage");if(a[i][3]==0)printf("people");if(a[i][0]&&a[i][1]&&a[i][2]&&a[i][3])printf("none");printf("");printf("對(duì)岸:");if(a[i][0]==1)printf("wolf");if(a[i][1]==1)printf("goat");if(a[i][2]==1)printf("cabbage");if(a[i][3]==1)printf("people");if(!(a[i][0]||a[i][1]||a[i][2]||a[i][3]))printf("none");printf("\n\n\n");if(i<iStep)printf("the%dtime\n",i+1);if(i>0&&i<iStep){if(a[i][3]==0){printf("------>people");printf("%s\n",name[b[i]+1]);}else{printf("<-----people");printf("%s\n",name[b[i]+1]);}}}printf("\n\n\n\n");return;}for(i=0;i<iStep;i++){if(memcmp(a[i],a[iStep],20)==0){return;}}if(a[iStep][1]!=a[iStep][3]&&(a[iStep][2]==a[iStep][1]||a[iStep][0]==a[iStep][1])){return;}for(i=-1;i<=2;i++){b[iStep]=i;memcpy(a[iStep+1],a[iStep],sizeof(a[iStep+1]));a[iStep+1][3]=1-a[iStep+1][3];if(i==-1){search(iStep+1);}elseif(a[iStep][i]==a[iStep][3]){a[iStep+1][i]=a[iStep+1][3];search(iStep+1);}}}intmain(){printf（"\n\n人過河問題處理方案以下：\n\n\n");search(0);return0;}程序測(cè)試統(tǒng)計(jì)第一次：WolfgoatcabbbagepeoplenoneThe1timeWolfcabbagegoatpeopleThe2timeWolfcabbagepeoplegoatThe3timeCabbagewolfgoatpeopleThe4timeGoatcabbagepeoplewolfThe5timeGoatwolfcabbagepeople...............第二次:WolfgoatcabbbagepeoplenoneThe1timeWolfcabbagegoatpeopleThe2time<------peopleWolfcabbagepeoplegoatThe3time-------->peopleandwolfCabbagewolfgoatpeopleThe4time<-------peopleandgoatGoatcabbagepeoplewolfThe5time------>peopleandcabbageGoatwolfcabbagepeopleThe6time<-------peopleandgoatWolfgoatpeoplecabbageThe7time-------->peopleandwolfGoatwolfcabbagepeopleThe8time<-------peopleGoatpeoplewolfcabbageThe9time--------->peopleandgoatNonewolfgoatcabbagepeoplePressanykeytocontinue第三次：本岸：Wolfgoatcabbbagepeople對(duì)岸：noneThe1time本岸：Wolfcabbage對(duì)岸：goatpeopleThe2time<------people本岸：Wolfcabbagepeople對(duì)岸：goatThe3time-------->peopleandwolf本岸：Cabbage對(duì)岸：wolfgoatpeopleThe4time<-------peopleandgoat本岸：Goatcabbagepeople對(duì)岸：wolfThe5time------>peopleandcabbage本岸：Goat對(duì)岸：wolfcabbagepeopleThe6time<-------peopleandgoat本岸：Wolfgoatpeople對(duì)岸：cabbageThe7time-------->peopleandwolf本岸：Goat對(duì)岸：wolfcabbagepeopleThe8time<-------people本岸：Goatpeople對(duì)岸：wolfcabbageThe9time--------->peopleandgoat本岸：None對(duì)岸：wolfgoatcabbagepeoplePressanykeytocontinue第四次：人過河問題處理方案以下：本岸：Wolfgoatcabbbagepeople對(duì)岸：noneThe1time本岸：Wolfcabbage對(duì)岸：goatpeopleThe2time<------people本岸：Wolfcabbagepeople對(duì)岸：goatThe3time-------->peopleandwolf本岸：Cabbage對(duì)岸：wolfgoatpeopleThe4time<-------peopleandgoat本岸：Goatcabbagepeople對(duì)岸：wolfThe5time------>peopleandcabbage本岸：Goat對(duì)岸：wolfcabbagepeopleThe6time<------people本岸：Goatpeople對(duì)岸：wolfcabbageThe7time-------->peopleandgoat本岸：None對(duì)岸：wolfgoatcabbagepeople本岸：Wolfgoatcabbbagepeople對(duì)岸：noneThe1time本岸：Wolfcabbage對(duì)岸：goatpeopleThe2time<------people本岸：Wolfcabbagepeople對(duì)岸：goatThe3time-------->peopleandcabbage本岸：wolf對(duì)岸：goatcabbagepeopleThe4time<-------peopleandgoat本岸：wolfgoatpeople對(duì)岸：cabbagaeThe5time------>peopleandwolf本岸：Goat對(duì)岸：wolfcabbagepeopleThe6time<------people本岸：Goatpeople對(duì)岸：wolfcabbageThe7time-------->peopleandgoat本岸：None對(duì)岸：wolfgoatcabbage