churchman.cpp

hws01:野人和传教士问题 hws02:用Romberg外推法求积分近似值 hws03:八数码问题 hws04:模拟退火算法 hws05:遗传算法解决旅行商问题

#include <iostream>
#include <vector>
using namespace std;
int N,k;                                  //N和k分别表示传教士（野人）数和船最大载人数
bool goal=false;                     //设置目标，赋初值false表示还没有找到结果
void path(int m,int n,int l);              //解路径函数，用来输出状态集
bool samestate(int m,int n,int l);//判断是不是有相同状态
struct state{                          //定义状态集
	int c,w,b;                          //定义c(churchman),w(wild),b(boat)分别表示传教士，野人和船的状态
	bool operator==(state& s) //重载==函数，为后来去除重复状态准备
	{
		if(this->c==s.c&&this->w==s.w&&this->b==s.b)
			return true;
		else 
			return false;
	}
};
vector<state> v;                   //定义容器存放状态

void path(int m,int n,int l)      //通过递归实现函数求解
{
	if(m==0&&n==0&&l==0){//递归结束条件
		goal=true;
		for(vector<state>::iterator i=v.begin();i!=v.end();i++)
	    {
		    cout<<'('<<i->c<<','<<i->w<<','<<i->b<<')'<<endl;
	    }
	} 
	else if(goal==false&&l==1)      //船在左岸的情况
	{
		for(int i=0;i<=k;i++)           //船上传教士数目
			for(int j=0;i+j<=k;j++)   //船上野人数目
			{
				if(i==0&&j==0)continue;     //船不载人不能走
				else if(i!=0&&i<j) break;            //野人数大于传教士人数
				else if(samestate(m-i,n-j,0)==true)
				{
				    state st;
					st.c=m-i;st.w=n-j;st.b=0;  
					v.push_back(st);             //保存状态
					path(m-i,n-j,0);               //递归调用
					v.pop_back();
				}	
				else continue;
			}
	}
else if(goal==false&&l==0)                //船在右岸的情况
	{
		for(int i=0;i<=k;i++)               //船上传教士数目
			for(int j=0;i+j<=k;j++)       //船上野人数目
			{
				if(i==0&&j==0)continue;     //船不载人不能走
				if(i!=0&&i<j) break;            //野人数大于传教士人数
				else if(samestate(m+i,n+j,1)==true)
				{
				    state st;
					st.c=m+i;st.w=n+j;st.b=1;
					v.push_back(st);
					path(m+i,n+j,1);        //递归
					v.pop_back();
				}	
				else continue;
			}
	}
}
bool samestate(int m,int n,int l)
{ //野人和传教士初始人数相等，因此状态集里传教士和野人在每一侧人数必须相等或者传教士在一起
	if((m<=N&&m>=0&&n<=N&&n>=0)&&(m==N||m==0||m==n))
	{
    state s2;
	s2.c=m;s2.w=n;s2.b=l;	
	for(vector<state>::iterator i=v.begin();i!=v.end();i++)
	{
		if(*i==s2)return false;	             
	}
	return true;
	}
	else return false;
}

int main()
{
	cout<<"请输入传教士与野人数N:"<<endl;
	cin>>N;
	cout<<"请输入船最大载人数k:"<<endl;
	cin>>k;
	state s1;
	s1.c=N;s1.w=N;s1.b=1;
	v.push_back(s1);
	path(N,N,1);                                        //初始函数
	if(goal==false)                                    //没找到结果                                   
	{
		cout<<"no solution"<<endl;
	}	
	return 0;
}