123..c

人工智能元陈旭下载（传教士与野人的过河问题

#include<iostream>
using namespace std;
int Right_Balance;//右岸的传教士与野人的平衡情况
int count=0;//可能的渡河方法数
struct Load{
 int Passenger;
 int Shipman;
};
Load Notes[5];//应该走5趟
int main(){
 void Travel(int n);
 void Init();//初始化各参数
 Init();
 Travel(0);
 cout<<"可能的渡河方法为:"<<count<<endl;
    return 0;
}

void Init(){
 Right_Balance=0;
 for(int i=0;i<5;i++){
  Notes[i].Passenger=0;
  Notes[i].Shipman=0;
 }
}

void Travel(int n){
 if(n==5){//输出
  for(int i=0;i<5;i++){
   cout<<"第"<<i+1<<"趟:"<<endl;
            cout<<"划船者为:";
            if(Notes[i].Shipman==-1)cout<<"野人";
   else cout<<"传教士";
   cout<<endl;
   cout<<"到左岸者为:";
            if(Notes[i].Passenger==-1)cout<<"野人";
   else cout<<"传教士";
   if(i==4){
    if(Notes[i].Shipman==-1)cout<<" 野人";
    else cout<<" 传教士";
   }
   cout<<endl;
  }
  cout<<"*******************"<<endl;
  count++;
  return ;
 }
 else{//从右岸中选出两个人来渡河
  if(n==0){//第一趟,至少要有一个野人上船
   Right_Balance+=2;//两个野人上船
   Notes[n].Passenger=-1;
   Notes[n].Shipman=-1;
   Travel(n+1);
            //一个传教士一个野人上船,两种情况
   Right_Balance=0;
            Notes[n].Passenger=-1;//野人先过
   Notes[n].Shipman=1;
   Travel(n+1);

   Right_Balance=0;//传道士先过
   Notes[n].Passenger=1;
   Notes[n].Shipman=-1;
   Travel(n+1);
            
  }
  else{
   if(Right_Balance>0){ //传教士较多,此时船上的只能是野人
                Right_Balance--;//选择一个传教士并且作为乘客
    Notes[n].Passenger=1;
    Notes[n].Shipman=-1;
    Travel(n+1);
    
   }
   else{
                Right_Balance++;//必须选择一个野人
    if(Notes[n-1].Shipman==-1){//船上的为野人
     Notes[n].Passenger=-1;
     Notes[n].Shipman=-1;
     Travel(n+1);
    }
    else{//船上的为传道士
                    Notes[n].Passenger=1;
     Notes[n].Shipman=-1;
        Travel(n+1);
    }
   }
  }
 }
}