main.cpp

同学做的野人与传教士过河问题的程序 三个野人三个传教士 每次最多过两个人

#include<iostream.h>
#include"INFO.h"
#include"STORE.h" 
const   int   nStoreCount=5;  

// 判断是否有下一个满足条件的渡河方案   
bool   GetNextMove(INFO*  pInfo)   
{   
	// 渡船的优先顺序   
	// 此岸数量多优先，野人优先，彼岸数量少优先，传教士优先。   

	STORE   listStore[nStoreCount];   
	//创建规则
	if(pInfo->nSide==-1)   
	{   
		listStore[0].nSavage=2;   
		listStore[0].nBoanerges=0;   
		listStore[1].nSavage=1;   
		listStore[1].nBoanerges=1;   
		listStore[2].nSavage=0;   
		listStore[2].nBoanerges=2;   
		listStore[3].nSavage=1;   
		listStore[3].nBoanerges=0;   
		listStore[4].nSavage=0;   
		listStore[4].nBoanerges=1;   
	}   
	else 
		if(pInfo->nSide==1)
		{   
			listStore[0].nSavage=0;   
			listStore[0].nBoanerges=1;   
			listStore[1].nSavage=1;   
			listStore[1].nBoanerges=0;   
			listStore[2].nSavage=0;   
			listStore[2].nBoanerges=2;   
			listStore[3].nSavage=1;   
			listStore[3].nBoanerges=1;   
			listStore[4].nSavage=2;   
			listStore[4].nBoanerges=0;   
		}   
		//如果船上的传教士和野人数目为0，istart=0
		int  iStart;   
		if(pInfo->nMoveSavage==0&&pInfo->nMoveBoanerges==0)   
		{   
			iStart=0;   
		}   
	  //促发规则
		else   
		{   
			for(iStart=0;iStart<nStoreCount;iStart++)   
			{   
				if(pInfo->nMoveSavage==listStore[iStart].nSavage&&pInfo->nMoveBoanerges==listStore[iStart].nBoanerges)   
					break;   
			}   
			iStart++;   
		}   
		
		if(iStart<nStoreCount)   
		{   
			int  i;   
			for(i=iStart;i<nStoreCount;i++)   
			{   
				int   nSideSavage=pInfo->nSavage+listStore[i].nSavage*pInfo->nSide;   //此岸野人数目
				int   nSideBoanerges=pInfo->nBoanerges+listStore[i].nBoanerges*pInfo->nSide;   //此岸传教士数目
				int   nBesideSavage=3-nSideSavage;   //彼岸野人数目
				int   nBesideBoanerges=3-nSideBoanerges;   //彼岸传教士数目
				
				//此岸 传教士数量大于等于野人或为零并且
				//彼岸野人的数目小于等于传教士的数目或者等于0
				//并且此岸传教士数目大于0并且彼岸传教士数目大于等于0和彼岸野人数目大于等于0
				if((nSideSavage<=nSideBoanerges||nSideBoanerges==0)&&(nBesideSavage<=nBesideBoanerges||nBesideBoanerges==0)&&nSideSavage>=0 &&nSideBoanerges>=0&&nBesideSavage>=0&&nBesideBoanerges>=0)   
				{   
					// 如果本此解等于上次，放弃   
					if(pInfo->pPrevious!=0)   
					{   
						if(pInfo->pPrevious->nMoveBoanerges==listStore[i].nBoanerges&&pInfo->pPrevious->nMoveSavage==listStore[i].nSavage)   
							continue;   
					}   
					break;   
				}   
			}   
			if(i<nStoreCount)   
			{   
				pInfo->nMoveSavage=listStore[i].nSavage;   
				pInfo->nMoveBoanerges=listStore[i].nBoanerges;   
				return   true;   
			}   
		}   
		
		return   false;   
}   

// 递归函数   
bool   Ship(INFO*   pInfo)   
{   
	if(GetNextMove(pInfo))   
	{   
		INFO*  pNew=new INFO; 
		pNew->nSavage=pInfo->nSavage+pInfo->nMoveSavage*(pInfo->nSide);   //新的野人数目等译野人数目加上（渡河野人乘以船的方向）
		pNew->nBoanerges=pInfo->nBoanerges+pInfo->nMoveBoanerges*(pInfo->nSide);   //新的传教士数目等于传教士数目加上（渡河传教士乘以船的方向）
		pNew->nSide=(pInfo->nSide)*(-1);   //船新的方向
		pNew->pPrevious=pInfo;//  旧的指针
		pNew->pNext=NULL;   
		pNew->nMoveSavage=0;   //船上的野人为0
		pNew->nMoveBoanerges=0;   //船上的传教士为0
		pInfo->pNext=pNew;   
		if(pNew->nSavage==0&&pNew->nBoanerges==0)   
			return   true; // 完成   
		return   Ship(pNew);   		
	}   
	else   
	{   
		INFO*  pPre=pInfo->pPrevious;   
		if(pPre==0)   
			return   false; // 无解   
		delete   pInfo;   
		pPre->pNext=0;   
		return   Ship(pPre);   
	}   
	return   true;   
}  
/*//判断初始化的数据是否合法
bool get_number(int &savage,int &boanerge,int &boat)
{
    int flag=0;
	if(savage>0&&boanger>0&&(boat==-1||boat==1))
	{
		flag=1;
		return true;
	}
	while(flag==0)
	{
	 cout<<"******你输入的数据不合法,请重新输入**********"<<endl;
	 cout<<"****** 船的出使位置只能为1和-1,野人和传教士的数目必须大于0"<<endl;
	 cin>>savage;
	 cin>>boanerge;
	 cin>>boat;
	}
}*/
int  main()   
{   
	INFO *pHead=new INFO;   
/*	int boanerge,boat,savage;
	cout<<"请输入野人和传教士的数目,船的出使位置.<<endl;
    cin>>savage;
	cin>>boanerge;
	cin>>boat;
	//得到初始化的数据和出使数据
	while(get_number(savage,boanerge,boat))
	{*/
	pHead->nSavage=3;   
	pHead->nBoanerges=3boanerge;   
	pHead->nSide=-1;   
	pHead->pPrevious=NULL;   
	pHead->pNext=NULL;   
	pHead->nMoveSavage=0;   
	pHead->nMoveBoanerges=0;
//	}
	if(Ship(pHead))   
	{   
		cout<<"渡河过程如下："<<endl;
		INFO*   pInfo=pHead;   
		while(pInfo->pNext)   
		{   
			cout<<"渡河方向：";
				if(pInfo->nSide==-1)
					cout<<"-->";
				else
					cout<<"<--";
				cout<<"人数:"<<"  "
				<<"野人:"<<pInfo->nMoveSavage<<" "
			
				<<"传教士:"<<pInfo->nMoveBoanerges<<"  "
				<<"此岸野人数："<<pInfo->nSavage<<"  "
				<<"传教士数："<<pInfo->nBoanerges<<endl;
			pInfo=pInfo->pNext;   
		}   
		cout<<"渡河完成。"<<endl;
	}   
	else   
	{   
		cout<<"此题无解！"<<endl;
	}   
    
	// 删除链表   
	while(pHead)   
	{   
		INFO*   pTemp=pHead->pNext;   
		delete   pHead;   
		pHead=pTemp;   
	}   
	pHead=NULL;   
   

	return   0;   
}