mcpro.cpp

人智经典算法的实现

//解决传教士—野人问题的递归程序
#include <iostream>
using namespace std;

int a[2000];
int b[2000];
int c[2000];							//三个数组分别用来存放每一个左岸状态的三个参数
bool f=false;						    //作有解标志
bool ff=true;							//当找到一组解时置false，不再继续寻找
int m[2000];
int  n[2000];							//两个数组用以存放每次船上传教士、野人对应的组合


void  mc(int i,int N,int z)        //定义递归程序，i用来表示第几次用送，N是输入的传教士人数，Z为可能的船上组合数
{
	if(a[i]==0&&b[i]==0)          //递归结束条件，左岸无人
	{
		f=true;                           //置有解标志
		cout<<"一组可能的解如下（以左岸状态给出)："<<endl;
		for(int j=0;j<=i;j++)    
		{
			cout<<"("<<a[j]<<","<<b[j]<<","<<c[j]<<")"<<endl;
		}
		ff=false;                       //不再继续找
		return;
	}
	else
	{
		if(c[i]==1)
		{
			for(int p=0;p<=z;p++)   
			{
			  if(m[p]<=a[i]&&n[p]<=b[i])      
				{
					a[i+1]=a[i]-m[p];
					b[i+1]=b[i]-n[p];
					c[i+1]=0;
					if((a[i+1]==0||(N-a[i+1]==0)||(a[i+1]==b[i+1]&&(N-a[i+1])==(N-b[i+1])))&&(m[p]+n[p]!=0))   //满足题给约束条件，可以这样运送
					{
						bool s=true;
						for(int k=0;k<=i;k++)
						{
							if(a[k]==a[i+1]&&b[k]==b[i+1]&&c[k]==c[i+1])                               //这个状态出现过，不再继续
							 s=false;
						}
						if(s&&ff)
						mc(i+1,N,z);
					}
						a[i+1]=a[i+1]+m[p];          //回溯重置
						b[i+1]=b[i+1]+n[p];
						c[i+1]=1;
				}
			}
		}
		if(c[i]==0)                                         //右岸情形
		{
			for(int p=0;p<=z;p++)
			{
				if(m[p]<=N-a[i]&&n[p]<=N-b[i])
				{
					a[i+1]=a[i]+m[p];
					b[i+1]=b[i]+n[p];
					c[i+1]=1;
					if((a[i+1]==0||(N-a[i+1]==0)||(a[i+1]==b[i+1]&&(N-a[i+1])==(N-b[i+1])))&&(m[p]+n[p]!=0))
					{
						bool s=true;
					    for(int k=0;k<=i;k++)
						{
							if(a[k]==a[i+1]&&b[k]==b[i+1]&&c[k]==c[i+1])
							 s=false;
						}
						if(s&&ff)
						mc(i+1,N,z);
					}
						a[i+1]=a[i+1]-m[p];
						b[i+1]=b[i+1]-n[p];
						c[i+1]=0;
				}
			}
		}
	}
}


int main()
{
    int N,k;
	cout<<"请输入传教士人数:"<<endl;
	cin>>N;
	cout<<"请输入船上的限乘人数:"<<endl;
	cin>>k;
	a[0]=N;
	b[0]=N;
	c[0]=1;


	int count=0;                              //下面的两个循环给出船上所有的允许的传教士野人组合情况
	for(int v=1;v<=k;v++)
	{
		for(int h=0;h<=v;h++)
		{
			if(v+h<=k)
			{
				m[count]=v;
				n[count]=h;
				count++;
			}
		}
	}
	   for(int w=1;w<=k;w++)
		{
			m[count]=0;
			n[count]=w;
			count++;
		}	
	mc(0,N,count-1);
	if(!f)
		cout<<"no solution"<<endl;
	cout<<"请输入一个任意整数以结束程序"<<endl;
	int h;
	cin>>h;
	return 0;
}