一．     问题说明

   有3个传教士和3个野蛮人来到河边，打算乘一只船从左岸渡到右岸。该船的负载能力为2人，在任何时刻如果野蛮人人数超过传教士人数，野蛮人就会把传教士吃掉。他们怎样才能用这条船安全让所有人都渡过河。

二． 算法说明

采用递归算法。因为每次过河都要遵循几个约定，一为两边岸上野蛮人的数量必须大于传教士的数量，二为船上最多只能装两个人，所以采用递归算法不断嵌套循环模拟每次过河的过程，同时加上若干递归中止返回条件，则可以推得过河的方法。

三．     数据结构

船结构：即表示船上野蛮人和传教士的个数

        typedef struct Boat        

{

            int numX;               /// 传教士个数

            int numY;               /// 野蛮人个数

}Boat;

 

从左岸到右岸时船上装的人的种类，有3种，即2个野人和0个传教士，0个野人和2个传教士，1个野人和1个传教士。

Boat LtoR[3]={{2,0},{0,2},{1,1}};

 

从右岸回左岸时船上装的人的种类，有2种，即1个野人或1个传教士

Boat RtoL[2]={{1,0},{0,1}};

 

递归函数1：   int fnPassRiver1(x1,y1,x2,y2)

表示每次由一个野蛮人驾船从右岸回左岸后，再向右过河的过程

 

递归函数2：   int fnPassRiver2(x1,y1,x2,y2)

表示每次由一个传教士驾船从右岸回左岸后,再向右过河的过程

 

四．     具体算法

第一次过河时，有三种情况，即2个野人和0个传教士，0个野人和2个传教士，1个野人和1个传教士，所以在主函数中用参数是k的三重for循环，确定整体过河框架。在接下来的从左向右的过河之前，存在两种可能，即驾船从右边回来的是野蛮人或传教士，因此用两个递归函数fnPassRiver1（）和fnPassRiver2（）分类。

函数fnPassRiver1（）和fnPassRiver2（）的内容相似，即先判断递归中止条件，若满足三个条件中的任意一个，都跳出此次循环，回到上一级递归；若不满足，则进入下一级循环，此时改变了函数fnPassRiver1（x1,y1,x2,y2）和fnPassRiver2（x1,y1,x2,y2）中的传递参数x1,y1,x2,y2,改变的依据是数组LtoR[3]中的三组值。具体的说，在函数fnPassRiver1()中依次进行三个递归调用，即当一个野人驾船回左岸后带上另一个野人回右岸，调用下一级递归函数；当一个野人驾船回左岸后带上一个传教士回右岸，调用下一级递归函数；当一个野人驾船回左岸后此野人下船，同时另外两个传教士上船回右岸，调用下一级递归函数。同理，在函数fnPassRiver2()中依次进行三个递归调用，即当一个传教士驾船回左岸后带上另一个传教士回右岸，调用下一级递归函数；当一个传教士驾船回左岸后带上一个野人回右岸，调用下一级递归函数；当一个传教士驾船回左岸后此传教士下船，同时另外两个野人上船回右岸，调用下一级递归函数。

经过不断的递归调用最终实现过河全过程。

五．     源程序

（见下页）