本文由抱雪(hugsnow)原创，转载请注明来源 http://www.luoxf.net/
设有m个传教士和m个野人来到河边，打算乘一只船从右岸渡到左岸去。该船最大负载能力为n人，在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去呢？
C++代码:
1 #include <stdio.h>
2 #include <vector>
3 #include <algorithm>
4 #include <iostream>
5
6 using namespace std;
7 bool ok(int a,int b);
8 bool guoqu(int a,int b,vector < int > c);
9 bool guolai(int a,int b,vector < int > c);
10 const int ren=5;
11 const int sheep=3;
12
13 int main(int argc, char **argv)
14 {
15 vector < int > v;
16 v.push_back(ren*110+1);
17 guoqu(ren,ren,v);
18 system("pause");
19 return 0;
20 }
21 bool guoqu(int a,int b,vector < int > c){
22 //if(a==0&&b==0)
23 // return true;
24 for(int i=0;i<=a;i++)
25 for(int j=0;j<=b;j++)
26 if(i+j>0&&i+j<=sheep){
27 int a1,b1,a2,b2,d;
28 a1=a-i;
29 b1=b-j;
30 a2=ren-a1;
31 b2=ren-b1;
32 d=a1*100+b1*10+0;
33 if(find(c.begin(),c.end(),d)==c.end()&&ok(a1,b1)){
34 c.push_back(d);
35 if(guolai(a2,b2,c)){
36 cout<<"运"<<i<<"牧师和"<<j<<"野人过去,"
37 <<"这边"<<a1<<b1<<",那边"<<a2<<b2<<endl;
38 return true;
39 }
40 }
41 }
42 return false;
43 }
44 bool guolai(int a,int b,vector < int > c){
45 if(a==ren&&b==ren)
46 return true;
47 for(int i=0;i<=a;i++)
48 for(int j=0;j<=b;j++)
49 if(i+j>0&&i+j<=sheep){
50 int a1,b1,a2,b2,a3,b3,d;
51 a1=a-i;
52 b1=b-j;
53 a2=ren-a1;
54 b2=ren-b1;
55 d=a2*100+b2*10+1;
56 if(find(c.begin(),c.end(),d)==c.end()&&ok(a2,b2)){
57 c.push_back(d);
58 if(guoqu(a2,b2,c)){
59 cout<<"运"<<i<<"牧师和"<<j<<"野人过来,"
60 <<"这边"<<a2<<b2<<",那边"<<a1<<b1<<endl;
61 return true;
62 }
63 }
64 }
65 return false;
66 }
67
68 bool ok(int a,int b){
69 return a==ren||a==0||a==b;
70 }