回复 3楼 御坂美琴
好的，不过我的程序好像有点大啊
要是有时间就看看，多谢了
我把大概思想在程序中注释了
#include<stdio.h>
#include<iostream>
typedef struct man{
//野人和传教士的分布有三状况，河左边、河右边、船上。定义一个结构体，用于存放 河左边、河右边、船上 的野人和传教士的数目
int left_wild;
int left_church;
int boat_wild;
int boat_church;
int right_wild;
int right_church;
bool useful;
//没用的，不用管
struct man *next;
struct man *back;
man()
{
left_wild=0;
left_church=0;
boat_wild=0;
boat_church=0;
right_wild=0;
right_church=0;
useful=false;
next=NULL;
back=NULL;
}
man(int lw,int lc,int bw,int bc,int rw,int rc,bool use,struct man *n=NULL,struct man *ba=NULL)
{
left_wild=lw;
left_church=lc;
boat_wild=bw;
boat_church=bc;
right_wild=rw;
right_church=rc;
useful=use;
next=n;
back=ba;
}
}Manstate;
bool is_next(Manstate *obj)
//这是确定找出的一个状态是不是满足要求（野人>传教士）
{
if(obj->boat_church>0 || obj->boat_wild>0)
{
if(obj->left_church>=0 && obj->left_wild>=0 && obj->right_church>=0 && obj->right_wild>=0)
if(obj->left_church >= obj->left_wild || obj->left_church==0)
if(obj->right_church >= obj->right_wild || obj->right_church==0)
if(obj->boat_church >= obj->boat_wild || obj->boat_church==0)
if((obj->left_wild+obj->boat_wild <= obj->left_church+obj->boat_church || (obj->left_church+obj->boat_church==0)) && (obj->right_wild+obj->boat_wild <= obj->right_church+obj->boat_church || obj->right_church+obj->boat_church==0))
return true;
}
else if(obj->boat_church==0 && obj->boat_wild==0 && obj->left_church==0 && obj->left_wild==0)
return true;
return false;
}
bool copynode(Manstate *obj,Manstate *source)
//这儿是复制结构体里面的数据
{
obj->boat_church=source->boat_church;
obj->boat_wild=source->boat_wild;
obj->left_church=source->left_church;
obj->left_wild=source->left_wild;
obj->right_church=source->right_church;
obj->right_wild=source->right_wild;
obj->useful=source->useful;
obj->next=source->next;
obj->back=source->back;
return true;
}
bool check(Manstate *obj,Manstate *source)
//这是判断两个结构体里的数据（不算指针）是不是相同
{
if(obj->boat_church!=source->boat_church)
return false;
if(obj->boat_wild!=source->boat_wild)
return false;
if(obj->left_church!=source->left_church)
return false;
if(obj->left_wild!=source->left_wild)
return false;
if(obj->right_church!=source->right_church)
return false;
if(obj->right_wild!=source->right_wild)
return false;
return true;
}
void acrossriver(Manstate *obj,int num)
//传入一个刚开始的野人和传教士分布的结构体，再进行扩展，寻找下一种情况，直到全过河为止
{
int i=0,j=0;
bool flag=false;
Manstate *now,*tail,*previous;
tail=obj;
previous=obj;
while(tail->left_church>0 || tail->left_wild>0)
//这儿是寻找从
左岸
上船的各种情况
{
now=new Manstate();
for(i=num;i>=0;i--)
{
for(j=num-i;j>=0;j--)
{
copynode(now,tail);
now->left_wild-=i;
now->left_church-=j;
now->boat_church+=j;
now->boat_wild+=i;
if(is_next(now))
{
if(tail->back && !check(now,tail->back))
//判断符合条件并且和前一种运输状况不同
{
tail->next=now;
now->back=tail;
tail=tail->next;
flag=true;
break;
}
else if(!tail->back)
//如果刚开始就直接连在链表末尾，（下同）
{
tail->next=now;
now->back=tail;
tail=tail->next;
flag=true;
break;
}
}
}
if(flag)
{
flag=false;
break;
}
}
if(tail->left_church==0 && tail->left_wild==0)
//如果左岸全没人了，跳出这层循环
{
now=new Manstate();
copynode(now,tail);
now->right_church+=now->boat_church;
now->right_wild+=now->boat_wild;
now->boat_church=0;
now->boat_wild=0;
tail->next=now;
now->back=tail;
tail=tail->next;
break;
}
now=new Manstate();
copynode(now,tail);
now->right_church+=now->boat_church;
//把船上的人都放到右岸，形成一个节点
now->right_wild+=now->boat_wild;
now->boat_church=0;
now->boat_wild=0;
tail->next=now;
now->back=tail;
tail=tail->next;
now=new Manstate();
for(i=0;i<=num;i++)
//寻找从右岸上船的各种情况
{
for(j=0;j<=num-i;j++)
{
copynode(now,tail);
now->right_church-=i;
now->right_wild-=j;
now->boat_church+=i;
now->boat_wild+=j;
if(is_next(now))
{
if(tail->back && !check(now,tail->back))
//判断符合条件并且和前一种状况不同
{
tail->next=now;
now->back=tail;
tail=tail->next;
flag=true;
break;
}
else if(!tail->back)
{
tail->next=now;
now->back=tail;
tail=tail->next;
flag=true;
break;
}
}
}
if(flag)
{
flag=false;
break;
}
}
now=new Manstate();
//把船上的人都放到右岸，形成一个节点
copynode(now,tail);
now->left_church+=now->boat_church;
now->left_wild+=now->boat_wild;
now->boat_church=0;
now->boat_wild=0;
tail->next=now;
now->back=tail;
tail=tail->next;
}
//下面的是输出
tail=obj;
printf("%dc %dw ------ %dc %dw ------ %dc %dw\n",tail->left_church,tail->left_wild,tail->boat_church,tail->boat_wild,tail->right_church,tail->right_wild);
tail=tail->next;
flag=true;
int count=0;
while(tail)
{
count++;
if(flag)
{
if(count%2==0)
flag=!flag;
printf("%dc %dw ----> %dc %dw ----> %dc %dw\n",tail->left_church,tail->left_wild,tail->boat_church,tail->boat_wild,tail->right_church,tail->right_wild);
}
else
{
if(count%2==0)
flag=!flag;
printf("%dc %dw <---- %dc %dw <---- %dc %dw\n",tail->left_church,tail->left_wild,tail->boat_church,tail->boat_wild,tail->right_church,tail->right_wild);
}
tail=tail->next;
}
}
void main()
{
Manstate initman;
int num;
printf("input the number of wildman or churchman:");
scanf("%d",&initman.left_wild);
initman.left_church=initman.left_wild;
printf("input the number of once across by boat:");
scanf("%d",&num);
acrossriver(&initman,num);
//
printf("%d
%d
%d\n",initman.left_wild,initman.left_church,num);
system("pause");
}
