passriver.c

货郎担问题和野人过河问题

#include<stdio.h>

typedef struct Boat         /// 船结构，即表示船上野蛮人和传教士的个数
{
	int numX;               /// 传教士个数
	int numY;               /// 野蛮人个数
}Boat;

Boat LtoR[3]={{2,0},{0,2},{1,1}};    ///从左岸到右岸时船上装的人的种类，有3种
                                  ///2个野人和0个传教士，0个野人和2个传教士，1个野人和1个传教士
Boat RtoL[2]={{1,0},{0,1}};       ///从右岸回左岸时船上装人的种类，有2种
                                  ///1个野人或1个传教士

int fnPassRiver1(x1,y1,x2,y2);     ///递归函数，表示每次由一个野蛮人驾船从右岸回左岸
int fnPassRiver2(x1,y1,x2,y2);     ///递归函数，表示每次由一个传教士驾船从右岸回左岸

main()
{
	int x1,y1,x2,y2;    
	///  x1左岸野蛮人个数，y1左岸传教士个数；x2右岸野蛮人个数，y2右岸传教士个数
    int k;
    printf("      左岸                  右岸                 船上 \n");
    printf("野蛮人    传教士      野蛮人    传教士    野蛮人     传教士\n");
	
	///三重循环，表示第一次去右岸时，船上人数的种类，即数组LtoR[3]的三种情况
	for(k=0;k<3;k++)        
	{   x1=3,x2=0,y1=3,y2=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    \n\n",x1,y1,x2,y2);
		
		x1-=LtoR[k].numX;              ////第一次去右岸后，岸两边人数变化情况
		y1-=LtoR[k].numY;
		x2+=LtoR[k].numX;
		y2+=LtoR[k].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<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==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        %d\n",x1,y1,x2,y2,3-x1-x2,3-y1-y2);
          getch();
		  
		  ///当一个野人驾船回左岸后带上一个传教士回右岸，调用下一级递归函数
          fnPassRiver1(x1,y1-1,x2+1,y2+1);
		  printf("类型22        \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("类型33        \n  %d         %d          %d        %d           %d        %d\n",x1,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)     /////错误返回上一级递归函数
  {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");
   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        %d\n",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        %d\n",x1,y1,x2,y2,3-x1-x2,3-y1-y2);
          getch();	
          
		  ///当一个传教士驾船回左岸后此传教士下船，同时另外两个野人上船回右岸，调用下一级递归函数
		  fnPassRiver2(x1-2,y1+1,x2+2,y2);
		  printf("类型66        \n  %d         %d          %d        %d        %d        %d\n",x1,y1,x2,y2,3-x1-x2,3-y1-y2);
          getch();
	
		  return 0;	
  }
}