野蛮人过河问题算法说明

1、野蛮人过河问题算法说明一 问题说明 有3个传教士和3个野蛮人来到河边，打算乘一只船从左岸渡到右岸。该船的负载能力为2人，在任何时刻如果野蛮人人数超过传教士人数，野蛮人就会把传教士吃掉。他们怎样才能用这条船安全让所有人都渡过河。二 算法说明采用递归算法。因为每次过河都要遵循几个约定，一为两边岸上野蛮人的数量必须大于传教士的数量，二为船上最多只能装两个人，所以采用递归算法不断嵌套循环模拟每次过河的过程，同时加上若干递归中止返回条件，则可以推得过河的方法。三 数据结构船结构：即表示船上野蛮人和传教士的个数 typedef struct Boat int numX; / 传教士个数 int numY;

2、 / 野蛮人个数Boat;从左岸到右岸时船上装的人的种类，有3种，即2个野人和0个传教士，0个野人和2个传教士，1个野人和1个传教士。Boat LtoR3=2,0,0,2,1,1; 从右岸回左岸时船上装的人的种类，有2种，即1个野人或1个传教士Boat RtoL2=1,0,0,1;递归函数1： int fnPassRiver1(x1,y1,x2,y2)表示每次由一个野蛮人驾船从右岸回左岸后，再向右过河的过程递归函数2： int fnPassRiver2(x1,y1,x2,y2)表示每次由一个传教士驾船从右岸回左岸后,再向右过河的过程四 具体算法第一次过河时，有三种情况，即2个野人和0个传教士，

3、0个野人和2个传教士，1个野人和1个传教士，所以在主函数中用参数是k的三重for循环，确定整体过河框架。在接下来的从左向右的过河之前，存在两种可能，即驾船从右边回来的是野蛮人或传教士，因此用两个递归函数fnPassRiver1（）和fnPassRiver2（）分类。函数fnPassRiver1（）和fnPassRiver2（）的内容相似，即先判断递归中止条件，若满足三个条件中的任意一个，都跳出此次循环，回到上一级递归；若不满足，则进入下一级循环，此时改变了函数fnPassRiver1（x1,y1,x2,y2）和fnPassRiver2（x1,y1,x2,y2）中的传递参数x1,y1,x2,y2

4、,改变的依据是数组LtoR3中的三组值。具体的说，在函数fnPassRiver1()中依次进行三个递归调用，即当一个野人驾船回左岸后带上另一个野人回右岸，调用下一级递归函数；当一个野人驾船回左岸后带上一个传教士回右岸，调用下一级递归函数；当一个野人驾船回左岸后此野人下船，同时另外两个传教士上船回右岸，调用下一级递归函数。同理，在函数fnPassRiver2()中依次进行三个递归调用，即当一个传教士驾船回左岸后带上另一个传教士回右岸，调用下一级递归函数；当一个传教士驾船回左岸后带上一个野人回右岸，调用下一级递归函数；当一个传教士驾船回左岸后此传教士下船，同时另外两个野人上船回右岸，调用下一级递归

5、函数。经过不断的递归调用最终实现过河全过程。五 源程序（见下页）源程序#include<stdio.h>typedef struct Boat / 船结构，即表示船上野蛮人和传教士的个数int numX; / 传教士个数int numY; / 野蛮人个数Boat;Boat LtoR3=2,0,0,2,1,1; /从左岸到右岸时船上装的人的种类，有3种 /2个野人和0个传教士，0个野人和2个传教士，1个野人和1个传教士Boat RtoL2=1,0,0,1; /从右岸回左岸时船上装人的种类，有2种 /1个野人或1个传教士int fnPassRiver1(x1,y1,x2,y2); /递

6、归函数，表示每次由一个野蛮人驾船从右岸回左岸int fnPassRiver2(x1,y1,x2,y2); /递归函数，表示每次由一个传教士驾船从右岸回左岸main() int x1,y1,x2,y2; / x1左岸野蛮人个数，y1左岸传教士个数；x2右岸野蛮人个数，y2右岸传教士个数 int k; printf(" 左岸 右岸 船上 n"); printf("野蛮人 传教士 野蛮人 传教士 野蛮人 传教士n");/三重循环，表示第一次去右岸时，船上人数的种类，即数组LtoR3的三种情况for(k=0;k<3;k+) x1=3,x2=0,y1=3,y

7、2=0; switch(k) case 0 : printf("-第一次两个野蛮人先过河-n"); break; case 1 : printf("n-第二次两个传教士先过河-n"); break; case 2 : printf("n-第三次一个野蛮人和一个传教士一起过河-n"); break; default: break;printf(" %d %d %d %d nn",x1,y1,x2,y2);x1-=LtoRk.numX; /第一次去右岸后，岸两边人数变化情况y1-=LtoRk.numY;x2+=LtoR

8、k.numX;y2+=LtoRk.numY; fnPassRiver1(x1,y1,x2,y2); /调用递归函数过河fnPassRiver2(x1,y1,x2,y2); /调用递归函数过河int fnPassRiver1(xx1,yy1,xx2,yy2) /表示每次由一个野蛮人驾船从右岸回左岸后，再向右过河的过程 int x1,y1,x2,y2; int i,j; 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

9、<0|x1>3|y1>3|x2>3|y2>3) /错误返回上一级递归函数 printf("wrong! 错误类型：理论上的人数出现负数 ，搜索过程错误n"); return 0; else if(x1>y1)&&y1!=0)|(x2>y2)&&y2!=0) /错误返回上一级递归函数 printf("wrong! 错误类型：野蛮人的个数大于传教士的个数n"); return 0; else if(x1=0&&y1=0&&x2=3&&y2

10、=3) /成功返回上一级递归函数 printf("seccessful! 过河成功n"); return 0; else x2-=1; / 一个野蛮人驾船回左岸，则右岸野蛮人个数减一 y2-=0; / 右岸传教士个数不变 / 此时人在船上，左岸人数，即x1,y1暂时不作调整 if(x2<0|y2<0) return 0; /当一个野人驾船回左岸后带上另一个野人回右岸，调用下一级递归函数 fnPassRiver1(x1-1,y1,x2+2,y2); printf("类型11 n %d %d %d %d %d %dn",x1,y1,x2,y2,3

11、-x1-x2,3-y1-y2); getch(); /当一个野人驾船回左岸后带上一个传教士回右岸，调用下一级递归函数 fnPassRiver1(x1,y1-1,x2+1,y2+1); printf("类型22 n %d %d %d %d %d %dn",x1,y1,x2,y2,3-x1-x2,3-y1-y2); getch(); /当一个野人驾船回左岸后此野人下船，同时另外两个传教士上船回右岸，调用下一级递归函数 fnPassRiver1(x1+1,y1-2,x2,y2+2); printf("类型33 n %d %d %d %d %d %dn",x1,

12、y1,x2,y2,3-x1-x2,3-y1-y2); getch(); return 0; int fnPassRiver2(xx1,yy1,xx2,yy2) /表示每次由一个传教士驾船从右岸回左岸后,再向右过河的过程 int x1,y1,x2,y2; int i,j; 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) /错误返回上一级递归

13、函数 printf("wrong! 错误类型：理论上的人数出现负数 ，搜索过程错误n"); return 0; else if(x1>y1)&&y1!=0)|(x2>y2)&&y2!=0) /错误返回上一级递归函数 printf("wrong! 错误类型：野蛮人的个数大于传教士的个数n"); return 0; else if(x1=0&&y1=0&&x2=3&&y2=3) /成功返回上一级递归函数 printf("seccessful! 过河成功n&q

14、uot;); return 0; else x2-=0; / 一个传教士驾船回左岸，则右岸传教士个数减一 y2-=1; / 右岸野蛮人个数不变 / 此时人在船上，左岸人数，即x1,y1暂时不作调整 if(x2<0|y2<0) return 0; /当一个传教士驾船回左岸后带上另一个传教士回右岸，调用下一级递归函数 fnPassRiver2(x1,y1-1,x2,y2+2); printf("类型44 n %d %d %d %d %d %dn",x1,y1,x2,y2,3-x1-x2,3-y1-y2); getch(); /当一个传教士驾船回左岸后带上一个野人回右岸，调用下一级递归函数 fnPassRiver2(x1-1,y1,x2+1,y2+1); printf("类型55 n %d %d %d %d %d %dn",x1,y1,