数值算法/人工智能

开发平台：
Visual C++

895.cpp：源码内容
							#include <IOSTREAM>    
#include <VECTOR>    
#include <STDIO.H> 
#include<fstream.h>   
ofstream   r_out("传教士和野人过河.txt",ios::in||ios::app);   //文件流 ，用来输出结果
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; 
int ms;
int k;
int r; 
Rule rule[1000];  // 规则集 
class MoveGroup 
{
public:
    Rule move[500]; //算符集
	int numMove; //可用算符的总数
	MoveGroup(){}
    int Group(int MAX_ON_BOAT) {    //利用构造器求算符集
		int m, c, i = 0;
		for (m = 0; m <=MAX_ON_BOAT; m++)
			for (c = 0; c <= MAX_ON_BOAT; c++){
				if (c==0 && m!=0) {
					move[i].m=m;
					move[i].c=0;
					i++;
				}
				else if (m==0 && c!=0) {
					move[i].m=0;
					move[i].c=c;
					i++;
				}
				else if (m!=0&&c!=0&&m+c<=MAX_ON_BOAT&& m>=c) {
					move[i].m = m;
					move[i].c = c;
					i++;
				}
				numMove = i;
			}return numMove;
	}
};
long int d=1;  
void OutResult(const vector<int>& ruleSet, const vector< State >& StateSet, const int index)   
{   r_out <<"第"<<d<<"种方案：" <<endl; 
r_out <<"   " << "初始状态" << "         " << "(" << ms << "," << ms << ")";   
r_out << "         " << "(" << 0 << "," << 0 << ")" << "    " << "left" << endl;   
for(int i = 0; i <= index; i ++)   
{   
	r_out << i +1 << "  ";   
	if( i % 2 == 0 )   
		r_out << "L-to-R" << "(" << rule[ ruleSet[i] ].m    
		<< "," << rule[ ruleSet[i] ].c << ")";   
	else    
		r_out << "R-to-L" << "(" << rule[ ruleSet[i] ].m    
		<< "," << rule[ ruleSet[i] ].c << ")";   
	r_out << "      (" << StateSet[i].m << "," << StateSet[i].c << ")";   
	r_out << "         (" << ms-StateSet[i].m << "," <<ms-StateSet[i].c << ")";   
	if( StateSet[i].b == 1 )   
		r_out << "    " << "left " << endl;   
	else    
		r_out << "    " << "right " << endl;   
	
	
} 
d++;
}   
bool IsExist(const vector< State >& StateSet, const State& state, const int index)   
{   
    if( state.m == ms && state.c == ms && 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 )   
    {   
        r_out << "full" << endl;   
        return false;   
    }   
	
    State state;   
    for(int i = 0; i < r; 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 == ms || 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 > ms || state.c >ms) continue;   
			
            if( state.m == state.c ||  state.m == ms || 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;   
} 
bool IsExist2(int m,int n)
{
	if(m<=0)
		return false;
	else if(m<6)
	{
		if(n>=m/2+1)
			return true;
		else
			return false;
	}
	else
	{
		if(n>=4)
			return true;
		else
			return false;
	}
}  
int main()   
{   r_out<<"输入人数m,和船的载重量k："<<endl;
std::cout<<"输入人数m,和船的载重量k："<<endl;
std::cin>>ms>>k;
r_out<<"传教士和野人数各为："<<ms<<" 船的载重量： "<<k<<endl;
if(IsExist2(ms,k)==1)
{
	MoveGroup p;
	r=p.Group (k);
	for(int i=0;i<r;i++)
		rule[i]=p.move[i];
    State InitState = {ms,ms, 1};  // 初始状态    
	
    vector< int > ruleSet;          // 存放摆渡规则在规则集中的序号    
    vector< State > StateSet;    // 存放状态    
    ruleSet.resize( 10000 );   
    StateSet.resize( 10000 );   
    r_out << "假设初始状态，野人、传教士和船都在左岸" << endl;   
    r_out << "   摆渡规则" << "     " << "左岸(m,c)" << "     " << "右岸(m,c)"   
		<< " " << "船的状态" << endl;   
    SearchRule(ruleSet, StateSet, -1, InitState);   
	
    r_out << "结果说明：" << endl;   
    r_out << "L-to-R(2,0)  (1,1)   (2,2)   right" << endl;   
    r_out << "表示从左岸向右岸运2个传教士和一个野人，然后左岸传教" << endl;   
    r_out << "士和野人为(1,1), 右岸为(2,2), 船到右岸" << endl;   
    r_out << endl;   
    r_out << "姓名：汪潮" << endl;   
    r_out << "学号：0705030121" << endl;   
    r_out << "专业：智能科学与技术" << endl; 
}
else
{
   r_out<<"不可能事件："<<endl;
}
getchar();   
return 1;   
}   

						