野蠻人過河問題算法說明及程序

--6-一．問題說明

傳教士與野人問題算法及程序說明

0810504班33個(gè)野蠻人來到河邊，打算乘一只船從左岸渡到右岸。該船的負(fù)載力量為2才能用這條船安全讓全部人都渡過河。二．算法說明的過程，同時(shí)加上假設(shè)干遞歸中止返回條件，則可以推得過河的方法。三．?dāng)?shù)據(jù)構(gòu)造船構(gòu)造：即表示船上野蠻人和傳教士的個(gè)數(shù)typedefstructBoat{intnumX; ///傳教士個(gè)數(shù)intnumY; ///野蠻人個(gè)數(shù)}Boat;從左岸到右岸時(shí)船上裝的人的種類，有32002個(gè)傳教士，11BoatLtoR[3]={{2,0},{0,2},{1,1}};從右岸回左岸時(shí)船上裝的人的種類，有211BoatRtoL[2]={{1,0},{0,1}};遞歸函數(shù)1： intfnPassRiver1(x1,y1,x2,y2)表示每次由一個(gè)野蠻人駕船從右岸回左岸后，再向右過河的過程遞歸函數(shù)2： intfnPassRiver2(x1,y1,x2,y2)表示每次由一個(gè)傳教士駕船從右岸回左岸后,再向右過河的過程四．具體算法200211k的三重for用兩個(gè)遞歸函數(shù)fnPassRiver1〔〕和fnPassRiver2〔〕分類。函數(shù)fnPassRiver1〔〕和fnPassRiver2〔〕的內(nèi)容相像，即先遞歸中推斷止條件，假設(shè)循環(huán)，此時(shí)轉(zhuǎn)變了函數(shù)fnPassRiver1〔x1,y1,x2,y2〕和fnPassRiver2〔x1,y1,x2,y2〕中的傳遞參數(shù)x1,y1,x2,y2,轉(zhuǎn)變的依據(jù)是數(shù)組LtoR[3]中的三組值。具體的說，在函數(shù)fnPassRiver1級遞歸函數(shù)。同理，在函數(shù)fnPassRiver2中依次進(jìn)展三個(gè)遞歸調(diào)用，即當(dāng)一個(gè)傳教士駕另外兩個(gè)野人上船回右岸，調(diào)用下一級遞歸函數(shù)。經(jīng)過不斷的遞歸調(diào)用最終實(shí)現(xiàn)過河全過程。五．源程序#include<stdio.h>typedefstructBoat *船構(gòu)造，即表示船上野蠻人和傳教士的個(gè)數(shù)*{intnumX; *傳教士個(gè)數(shù)*intnumY; *野蠻人個(gè)數(shù)*}Boat;BoatLtoR[3]={{2,0},{0,2},{1,1}}; *從左岸到右岸時(shí)船上裝的人的種類，有3種**2個(gè)野人和0個(gè)傳教士，0個(gè)野人和2個(gè)傳教士，1個(gè)野人和1個(gè)傳教士*BoatRtoL[2]={{1,0},{0,1}}; *從右岸回左岸時(shí)船上裝人的種類，有2種**1個(gè)野人或1個(gè)傳教士*intfnPassRiver1(xx1,yy1,xx2,yy2)**{intx1,y1,x2,y2; *x1左岸野蠻人個(gè)數(shù)，y1左岸傳教士個(gè)數(shù)；x2右岸野蠻人個(gè)數(shù)，y2右岸傳教士個(gè)數(shù)*x1=xx1,y1=yy1,x2=xx2,y2=yy2;printf(“%d %d %d %d\n“,x1,y1,x2,y2);getch;if(x1<0||y1<0||x2<0||y2<0||x1>3||y1>3||x2>3||y2>3)*錯(cuò)誤返回上一級遞歸函數(shù)*{printf(“wrong!!!\nThewrongtype:thenumberis negativeintheory,searchingprocessiswrong\n“); **return0;}elseif(((x1>y1)&&y1!=0)||((x2>y2)&&y2!=0)){printf(“wrong!!!\nThewrongtype:thenumberofbarbariansisgreaterthan thenumberofmissionaries\n“); *錯(cuò)誤類型：野蠻人的個(gè)數(shù)大于傳教士的個(gè)數(shù)*return0;}elseif(x1==0&&y1==0&&x2==3&&y2==3) *成功返回上一級遞歸函數(shù)*{printf(“seccessful!!!\nSuccessfullypassingtheriver\n“); 過河成功*return0;}else{x2-=1; *一個(gè)野蠻人駕船回左岸，則右岸野蠻人個(gè)數(shù)減一*y2-=0; *右岸傳教士個(gè)數(shù)不變,此時(shí)人在船上，左岸人數(shù)，即x1,y1臨時(shí)不作調(diào)整*if(x2<0||y2<0) return0;**fnPassRiver1(x1-1,y1,x2+2,y2);printf(“TYPE11\n%d%d %d %d %d %d\n“,x1,y1,x2,y2,3-x1-x2,3-y1-y2);getch; **fnPassRiver1(x1,y1-1,x2+1,y2+1);printf(“TYPE22\n%d %d %d %d %d %d\n“,x1,y1,x2,y2,3-x1-x2,3-y1-y2);getch;**fnPassRiver1(x1+1,y1-2,x2,y2+2);printf(“TYPE33\n%d %d %d %d %d %d\n“,x1,y1,x2,y2,3-x1-x2,3-y1-y2);getch;return0;}}intfnPassRiver2(xx1,yy1,xx2,yy2) *表示每次由一個(gè)傳教士駕船從右岸回左岸后,再向右過河的過程*{intx1,y1,x2,y2;x1=xx1,y1=yy1,x2=xx2,y2=yy2;printf(“%d %d %d %d\n“,x1,y1,x2,y2);getch;if(x1<0||y1<0||x2<0||y2<0||x1>3||y1>3||x2>3||y2>3)*錯(cuò)誤返回上一級遞歸函數(shù)*{printf(“wrong!!!\nThewrongtype:thenumberisnegativeintheory,searchingprocessiswrongn“);**return0;}elseif(((x1>y1)&&y1!=0)||((x2>y2)&&y2!=0)) *錯(cuò)誤返回上一級遞歸函數(shù)*{printf(“wrong!!!\nThewrongtype:thenumberofbarbariansisgreaterthanthenumberofmissionaries\n“); *錯(cuò)誤類型：野蠻人的個(gè)數(shù)大于傳教士的個(gè)數(shù)*return0;}elseif(x1==0&&y1==0&&x2==3&&y2==3) **{printf(“seccessful!!!\nSuccessfullypassingtheriver\n“);過河成功*return0;}else{x2-=0;*一個(gè)傳教士駕船回左岸，則右岸傳教士個(gè)數(shù)減一*y2-=1;*右岸野蠻人個(gè)數(shù)不變,此時(shí)人在船上，左岸人數(shù)，即x1,y1臨時(shí)不作調(diào)整*if(x2<0||y2<0)return0;fnPassRiver2(x1,y1-1,x2,y2+2);*當(dāng)一個(gè)傳教士駕船回左岸后帶上另一個(gè)傳教士回右岸，調(diào)用下一級遞歸函*printf(“TYPE44\n%d %d %d %d %d %d\n“,x1,y1,x2,y2,3-x1-x2,3-y1-y2);getch;*當(dāng)一個(gè)傳教士駕船回左岸后帶上一個(gè)野人回右岸，調(diào)用下一級遞歸函*fnPassRiver2(x1-1,y1,x2+1,y2+1);printf(“TYPE55\n%d %d %d %d %d %d\n“,x1,y1,x2,y2,3-x1-x2,3-y1-y2);getch;**fnPassRiver2(x1-2,y1+1,x2+2,y2);printf(“TYPE66\n%d %d %d %d %d %d\n“,x1,y1,x2,y2,3-x1-x2,3-y1-y2);getch;return0;}}main{intx1,y1,x2,y2;intk;printf(“Left Right Boat\n“);printf(“BarbariansMissionariesBarbariansMissionariesBarbariansMissionaries\n“);for(k=0;k<3;k++){ x1=3,x2=0,y1=3,y2=0;switch(k){case0:printf(“\n------First,twobarbarianscrosstheriverfirst \n“);break;case1:printf(“\n------Secondly,twoMissionariescrosstheriver \n“);break;case2:printf(“\n------Thirdly,abarbarianscrosstheriverwithamissionary \n“);break;default:break;}printf(“%d %d %d %d\