work1.cpp

野人与传教士问题的求解程序

/******************************************************************************************
**--------------File Info------------------------------------------------------------------
** File name:			AI_work1.cp
** Last modified Date:  2008-10-16
** Last Version:		1.0
** Descriptions:		传教士与野人过河问题求解程序
** Input ：				N  ---  传教士与野人个数均为N
                        k  ---  渡船每次至多k人乘坐	
** Output：             有解输出状态序列
                        无解输出“no solution”
*******************************************************************************************/

#include <stdio.h>
#include <iostream.h>
#include <math.h>
#define Stk_deep 30
  
int x[Stk_deep],y[Stk_deep],x_boat[10],y_boat[10];
int Boat_Flag=0,Step_Num=1;
/*
x,y为未渡河的传教士与野人的数目；x_boat,y_boat表示渡船上传教士与野人的数目
Boat_flag表示渡船所处的位置：0 -- 此岸    1--彼岸
Step_num 为渡船摆渡次数
*/


/*****************************************************************************
** 函数名称 ：NextOpr(int boat_flag,int step_num,int opr_index)
** 函数功能 ：计算下一步渡船操作后 x,y的状态 
** 入口参数 ：
              Step_num   --操作次数，即数组x，y的索引
			  Opr_index  --渡船上传教士与野人人数配备的索引值
** 出口参数 ：无
******************************************************************************/
void NextOpr(int step_num,int opr_index)
{
	if(step_num%2)    //船在此岸，摆渡向彼岸
	{
		x[step_num+1]=x[step_num]-x_boat[opr_index];
		y[step_num+1]=y[step_num]-y_boat[opr_index];
		Boat_Flag=1;   //船状态置1
	}
	else               //船在彼岸，摆渡向此岸
	{
		x[step_num+1]=x[step_num]+x_boat[opr_index];
		y[step_num+1]=y[step_num]+y_boat[opr_index];
		Boat_Flag=0;   //船状态置0
	}
}
/*****************************************************************************
** 函数名称 ：Judge(int p,int q)
** 函数功能 ：判断状态是否符合规则集，是否重复 
** 入口参数 ：p --传教士人数
              q --野人人数
** 出口参数 ：0 --错误
              1 --正确
******************************************************************************/
int Judge(int p,int q)
{
	int Status,j;
	if (p<0 || p>x[1] || q<0 || q>y[1]|| p!=0 && q>p|| x[1]-p!=0 && (y[1]-q)>(x[1]-p) )
		Status = 0;           //不在规则集范围内
	else
	{
		for (j=Step_Num-1;j>0;j-=2)   //j每次减2是因为状态与船在哪岸有关
			if(p==x[j]&&q==y[j])
			{
				Status = 0;   //出现状态重复
				break;
			}
		if(j<=0)
			Status=1;     //满足规则集的条件
	}
	return Status;
}

/*****************************************************************************
** 函数名称 ：main(void)
** 函数功能 ： 
** 入口参数 ：无
** 出口参数 ：
******************************************************************************/
void main()
{
	int i,j,k,RECORD[Stk_deep],Bk_flag=1; //RECORD采用的决策的序号，Bk_flag为是否回溯的标记
	x_boat[1]=2; y_boat[1]=0;   /* 给决策编号并赋值 */
    x_boat[2]=0; y_boat[2]=2;
    x_boat[3]=1; y_boat[3]=0;
    x_boat[4]=0; y_boat[4]=1;
    x_boat[5]=1; y_boat[5]=1;
	cout<<"输入传教士与野人的数目N:";
	cout<<"\n";
	cin>>x[1];
	y[1]=x[1];
	cout<<"输入渡船限坐人数k:";
	cout<<"\n";
	cin>>k;
	while(Bk_flag)
	{
		for (i=1;i<=5;i++)         //遍历各种决策情况
		{
			NextOpr(Step_Num,i);  // 计算下一状态
			if(Judge(x[Step_Num+1],y[Step_Num+1]))
			{
				RECORD[Step_Num]=i;  //记录采用到的决策序号
				if(x[Step_Num+1]==0 && y[Step_Num+1]==0)    //如果完成，输出结果
				{
					printf("初始值     传教士:   %d      野人: %d\n",x[1],y[1]); /* 输出结果 */
					for(j=1;j<=Step_Num;j++)
					{printf("第%d次操作            %d            %d\n",j,x[j+1],y[j+1]);}
					Bk_flag=0;     //结束回溯算法
					break;
				}
				else
				{
					Step_Num++;    //递归次数增加
					break;         //遍历结束，计算下一步状态
				}
			}
			else              //若新状态不允许或者重复，进入DeadEnd
			{
				while(i==5)   //本步决策已经遍历
				{
					if(Step_Num==1)     //初始即DeadEnd了，无解
					{
						cout<<"no solution\n";
						Bk_flag=0;
						break;
					}
					else
					{
						Step_Num--;    //回溯一步
						i=RECORD[Step_Num];
					}
				}
				if(Bk_flag)
					continue;
				else
					break;
			}

				
		}
	}
}