传教士与野人渡河问题 源程序及报告

设有若干个传教士和若干个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。怎样才能安全的将所有人都渡过河去？

#include 
#include 
using namespace std;

struct PAS{
	int Nm_leftNm_rightNc_leftNc_right;//传教士、野人左右岸人数
	int Nm_lrNc_lr; //从左岸到右岸的传教士、野人人数
	int Nm_rlNc_rl;//从右岸到左岸的传教士、野人人数
	struct PAS *father*children; 
}pas;

struct PAS *first*last;
int num;//第N轮
int store[100][2]; //储存左岸传教士、野人的人数

void init（int Nmint Nc）   //定义初始状态
{
	num=0;
	first= last=（struct PAS*）malloc（sizeof（pas））;
	first->Nm_left=Nm;
	first->Nc_left=Nc;
	first->children=NULL;
	first->father=NULL;
	first->Nc_lr=first->Nc_rl=first->Nc_right=first->Nm_lr=first->Nm_rl=first->Nm_right=0;
}

int store_or（int sint c） //判断是否已经储存过
{ 
	for（int i=0;i		if（s==store[i][0]&&c==store[i][1]）
			return 1;
	return 0;
}

int ways[5][2]={{20}{11}{02}{10}{01}};//渡河方案

int pass_river（int t）
{
	int tNm_left tNc_lefttNm_righttNc_right ; // 左岸、右岸的传教士、野人人数 
	int Nm_lrNc_lr ; // 从左岸到右岸的传教士、野人人数 
	int Nm_rlNc_rl ; // 从左岸到右岸的传教士、野人人数 
	struct PAS *temp;
	temp = （struct PAS*） malloc （sizeof（pas））;
	if（temp==NULL）
	{
		cout<<“内存不足溢出!“<		exit（0）;
	}
	for（int i=0;i<5;i++）   //左岸到右岸
	{
		Nm_lr=ways[i][0];
		Nc_lr=ways[i][1];
		tNm_left = last -> Nm_left; 
		tNc_left = last -> Nc_left;
		tNm_right = last -> Nm_right;  
		tNc_right = last -> Nc_right;

		if （（Nm_lr <=  tNm_left）&&（Nc_lr <=  tNc_left） ）
		{
			tNm_left = tNm_left - Nm_lr;
			tNc_left = tNc_left - Nc_lr;
			tNm_right = tNm_right + Nm_lr;
			tNc_right = tNc_right + Nc_lr;

			if（（tNm_left ==  0） && （tNc_left ==  0））// 成功过河
			{ 
				temp -> father = last;       
				temp -> children = NULL;
				temp -> Nm_left = 0;
				temp -> Nc_left = 0;
				temp -> Nm_right = tNm_right;
				temp -> Nc_right = tNc_right;
				temp -> Nm_lr = Nm_lr;
				temp -> Nc_lr = Nc_lr;
				temp -> Nm_rl = 0;
				temp -> Nc_rl = 0;

				if（first==last）
					first -> children = temp;
				else last-> children = temp;
				last = temp;
				return 1;
			}   
			else if （（tNm_left - tNc_left）*tNm_left >= 0&&（tNm_right - tNc_right）*tNm_right >= 0） // 传教士人数不能少于野人人数
			{
				int bNm_right  bNc_rightbNm_left  bNc_left;
				for（int i=4;i!=0;i--）   //从右岸到左岸
				{
					Nm_rl=ways[i][0];
					Nc_rl=ways[i][1];
					if（Nc_lr==Nc_rl&&Nm_lr==Nm_rl）;	//跳过来去人数一样的情况				
					else if （（Nc_rl <= tNc_right） && （Nm_rl <= tNm_right））
					{
						bNm_right = tNm_right - Nm_rl;
						bNc_right = tNc_right - Nc_rl;
						bNm_left = tNm_left + Nm_rl; 
						bNc_left = tNc_left + Nc_rl;

						if（store_or（bNm_leftbNc_left））;  //该路已经试过
						else if （（bNm_right - bNc_right） * bNm_right >= 0&&（bNm_left - bNc_left） * bNm_left >= 0）//传教士人数必须大于野人人数
						{                                    
							temp = （struct PAS*） malloc （sizeof（pas））;
							temp -> father = last;     
							temp -> children = NULL;	
							temp -> Nm_right = bNm_right;
							temp -> Nc_right = bNc_right;
							temp -> Nm_left = bNm_left;
							temp -> Nc_left = bNc_le

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       5543  2011-04-26 14:06  传教士与野人渡河问题\yyp.cpp

     文件      41984  2011-04-26 14:06  传教士与野人渡河问题\yyp.exe

     文件     171819  2011-07-05 10:01  传教士与野人渡河问题\实验报告.docx

     目录          0  2011-07-05 10:01  传教士与野人渡河问题

----------- ---------  ---------- -----  ----

               219346                    4