mc.cpp

一个自己写的传教士与野人问题程序。程序结构比较清楚。完全安装人工智能的里面的结构编写的。

#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
/*
	定义三元组：（m, c, b） 
	其中： 0 <= m <=3，表示传教士在河左岸的人数。
	　　　 0<= c <=3，表示野人在河左岸的认输。
	　　　 b=1，表示船在左岸，b=0，表示船在右岸。
	2，规则集 
	按每次渡河的人数分别写出每一个规则，
	共 (1 1)、(1 0)、(0 1)、(0,2),(2,0)3种渡河的可能（其中(x y)
	表示x个传教士和y个野人上船渡河），因此共有10个规则

	（从左岸到右岸、右岸到左岸各3个）。
	规则集如下： 
	r1：IF (m, c, 1) THEN (m-1, c-1, 0)
	r2：IF (m, c, 1) THEN (m-1, c, 0) 
	r3：IF (m, c, 1) THEN (m, c-1, 0)
	r4：IF (m, c, 1) THEN (m, c-2, 0)
	r5：IF (m, c, 1) THEN (m-2, c, 0)
	r4：IF (m, c, 0) THEN (m+1, c+1, 1)
	r5：IF (m, c, 0) THEN (m+1, c, 1)
	r6：IF (m, c, 0) THEN (m, c+1, 1) 
	r6：IF (m, c, 0) THEN (m, c+2, 1) 
	r6：IF (m, c, 0) THEN (m+2, c, 1) 
	3，初始状态：(3, 3, 1)
	4，结束状态：(0, 0, 0) 
*/
typedef struct _State
{
	int m;  // 表示传教士在河左岸的人数
	int c;  // 表示野人在河左岸的认输
	int b;  // b=1，表示船在左岸，b=0，表示船在右岸
}State;
typedef struct _Rule
{
	int m;
	int c;
}Rule;
Rule rule[5] = {{1,1}, {1,0}, {0,1}, {2,0}, {0,2}};  // 规则集
void OutResult(const vector<int>& ruleSet, const vector< State >& StateSet, const int index)
{  
	cout <<"   " << "初始状态" << "         " << "(" << 3 << "," << 3 << ")";
	cout << "         " << "(" << 0 << "," << 0 << ")" << "    " << "left" << endl;

	for(int i = 0; i <= index; i ++)
	{
		cout << i +1 << "  ";
		if( i % 2 == 0 )
			cout << "L-to-R" << "(" << rule[ ruleSet[i] ].m 
			     << "," << rule[ ruleSet[i] ].c << ")";
		else 
			cout << "R-to-L" << "(" << rule[ ruleSet[i] ].m 
			     << "," << rule[ ruleSet[i] ].c << ")";
		cout << "      (" << StateSet[i].m << "," << StateSet[i].c << ")";
		cout << "         (" << 3-StateSet[i].m << "," << 3-StateSet[i].c << ")";
		if( StateSet[i].b == 1 )
			cout << "    " << "left " << endl;
		else 
			cout << "    " << "right " << endl;


	}
}
bool IsExist(const vector< State >& StateSet, const State& state, const int index)
{
	if( state.m == 3 && state.c == 3 && state.b == 1) return true;
	for(int i = 0; i <= index; i ++)
		if(StateSet[i].m == state.m && StateSet[i].c == state.c && StateSet[i].b == state.b)
			return true;
	return false;

}
bool SearchRule(vector<int>& ruleSet, 
				vector< State >& StateSet, int index,
				State NowState)
{
	if(NowState.b == 0 && NowState.c == 0 && NowState.m == 0) // 达到最终状态
	{
		OutResult(ruleSet, StateSet, index);
		return true;
	}

	int iSize = ruleSet.size();
	if( iSize <= index )
	{
		cout << "full" << endl;
		return false;
	}

	State state;
	for(int i = 0; i < 5; i ++)
	{
		state = NowState;
		if( NowState.b == 1 ) // 船在左岸
		{
			state.m -= rule[i].m;
			state.c -= rule[i].c;
			if( state.m < 0 || state.c < 0 ) continue;

			// state为安全状态
			if( state.m == state.c ||  state.m == 3 || state.m == 0 )
			{
				state.b = 0;
				if( IsExist(StateSet, state, index) ) continue;

				ruleSet[ index + 1 ] = i;
				StateSet[ index + 1 ] = state;
		//		if( SearchRule( ruleSet, StateSet, index+1, state) ) return true;
				SearchRule(ruleSet, StateSet, index+1, state);
			}
				
		}
		else  // 在右岸
		{
			state.m += rule[i].m;
			state.c += rule[i].c;
			
			if( state.m > 3 || state.c > 3 ) continue;
			
			if( state.m == state.c ||  state.m == 3 || state.m == 0 )
			{
				state.b = 1;
				if( IsExist(StateSet, state, index) ) continue;

				ruleSet[ index + 1 ] = i;
				StateSet[ index + 1 ] = state;
			//	if( SearchRule(ruleSet, StateSet, index+1, state) ) return true;
				
				SearchRule(ruleSet, StateSet, index+1, state);
			}	
		}
	}
	return false;
}
int main()
{
	State InitState = {3, 3, 1};  // 初始状态
	
	vector< int > ruleSet;          // 存放摆渡规则
	vector< State > StateSet;    // 存放状态
	ruleSet.resize( 10000 );
	StateSet.resize( 10000 );
	cout << "假设初始状态，野人、传教士和船都在左岸" << endl;
	cout << "   摆渡规则" << "     " << "左岸(m,c)" << "     " << "右岸(m,c)"
		 << " " << "船的状态" << endl;
	SearchRule(ruleSet, StateSet, -1, InitState);

	cout << "结果说明：" << endl;
	cout << "L-to-R(2,0)  (1,1)   (2,2)   right" << endl;
	cout << "表示从左岸向右岸运2个传教士和一个野人，然后左岸传教" << endl;
	cout << "士和野人为(1,1), 右岸为(2,2), 船到右岸" << endl;
	cout << endl;
	cout << "姓名：李志博" << endl;
	cout << "学好：" << endl;
	cout << "专业：" << endl;
	getchar();
	return 1;

}