#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