渡河问题

sally 发表于 2004-6-5 11:57

渡河问题
 A wolf, a goat and a cabbage are on one bank of a river. A ferryman wants to take them across, but since his boat is small, he can take only one of them at a time. For obvious reasons, neither the wolf and the goat nor the goat and the cabbage can be left unguarded. How is the ferryman going to get them across the river?
 
程序代码：
//以下程序在Win98＋vc6.0运行通过
#include <stdio.h>
#include <stdlib.h>
#define MAX 50
struct state
{
int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸
int m;//所采取的过河方法，(1--4)
}s;
int count=0;
FILE *fp=fopen("c:\\2.txt","w+");
void main()
{
void f1(int ),f2();//f1试探递归
s.man=s.sheep=s.wolf=s.cabbage=0;
s.m=4;
s.man=s.sheep=s.wolf=s.cabbage=0;
f1(1);
//f2();
fclose(fp);
printf("\n");
}
//用m值决定的方法渡河，成功返回1,否则返回0
int move(int top,int m)
{
switch(m)
{
 //人带羊过河
case 1:
 //判断人羊是否在同岸
 if(s.man!=s.sheep)
 return 0;
 s.sheep=s.man=(s.man==1)?0:1;
 s.m=m;//存储过河方法
 break;
case 2:
 if(s.man!=s.wolf)
 return 0;
 s.wolf=s.man=(s.man==1)?0:1;
 s.m=m;//存储过河方法
 break;
case 3:
 if(s.man!=s.cabbage)
 return 0;
 s.cabbage=s.man=(s.man==1)?0:1;
 s.m=m;//存储过河方法
 break;
//人单独过河
case 4:
s.man=(s.man==1)?0:1;
s.m=m;//存储过河方法
 break;
}//switch
return 1;
}//move
//打印过河步骤
void display(int top)
{
int i=0;
fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);
for(i=1;i<=top;i++)
{
 switch(s.m)
 {
 case 1:
 if(s.man==1&&s.man==0)
 fprintf(fp,"人带羊从起始岸过河到目的岸\n");
 else
 fprintf(fp,"人带羊从目的岸过河到起始岸\n");
 break;
 case 2:
 if(s.man==1&&s.man==0)
 fprintf(fp,"人带狼从起始岸过河到目的岸\n");
 else
 fprintf(fp,"人带狼从目的岸过河到起始岸\n");
 break;
 case 3:
 if(s.man==1&&s.man==0)
 fprintf(fp,"人带菜从起始岸过河到目的岸\n");
 else
 fprintf(fp,"人带菜从目的岸过河到起始岸\n");
 break;
 case 4:
 if(s.man==1&&s.man==0)
 fprintf(fp,"人单独从起始岸过河到目的岸\n");
 else
 fprintf(fp,"人单独从目的岸过河到起始岸\n");
 break;
 }//switch
fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);

 }//for
fprintf(fp,"All ferried successfully!\n");
}//display
//检查两岸合法性已经有无状态与历史重复性
int check(int top)
{
int i;
//检查两岸合法性
if((s.sheep!=s.man&&s.cabbage!=s.man)||
 (s.wolf!=s.man&&s.sheep!=s.man))
 return 0;
//检查历史重复性
for(i=0;i<top;i++)
 if(s.man==s.man&&s.sheep==s.sheep&&s.cabbage==s.cabbage&&s.wolf==s.wolf)
 return 0;
//ok
return 1;
}
void f1(int top)
{
int m;
if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1
{ //对每次状态分别试探4中方案
 for(m=1;m<5;m++)
 {
 //每次方案的实施是在上次结果状态上做的
 s.man=s.man;s.sheep=s.sheep;
 s.cabbage=s.cabbage;s.wolf=s.wolf;
 //用方案m移动，同时检查结果
 if(move(top,m)&&check(top))
 {
 if(s.man&&s.sheep&&s.cabbage&&s.wolf )
 {
 //打印渡河步骤
 display(top);
 //统计方案个数
 count++;
 fprintf(fp,"count=%d----------------------------\n\n",count);
 if(count>1000) exit(1);
 }
 else
 f1(top+1);
 }
 }//for
}//if(top>=0)
}//f1
 
 

void f2()
{
int top=0,i;
//开始时都在起始岸
s.man=s.sheep=s.wolf=s.cabbage=0;
//未开始渡河
 s.m=4;
while(top>=0)
{
 if(check(top))
 {
 if(s.man&&s.sheep&&s.cabbage&&s.wolf )
 {
 //打印渡河步骤
 display(top);
 //统计方案个数
 count++;
 fprintf(fp,"count=%d----------------------------\n\n",count);
 if(count>1000) exit(1);
 //回溯
 while(top>=0&&s.m>=4)
 top--;
 if(top>=0)
 {
 //在上次状态基础上准备做move
 s.man=s.man;s.sheep=s.sheep;
 s.cabbage=s.cabbage;s.wolf=s.wolf;
 i=1;
 while(s.m+i<5&&!move(top,s.m+i))
 i++;
 }
 }
 else
 {
 top++;
 //在上次状态基础上准备做move
 s.man=s.man;s.sheep=s.sheep;
 s.cabbage=s.cabbage;s.wolf=s.wolf;
 i=1;
 while(i<5&&!move(top,i))
 i++;
 }
 }
 else
 {
 //回溯
 while(top>=0&&s.m>=4)
 top--;
 if(top>=0)
 {
 //在上次状态基础上准备做move
 s.man=s.man;s.sheep=s.sheep;
 s.cabbage=s.cabbage;s.wolf=s.wolf;
 i=1;
 while(!move(top,s.m+i))
 i++;
 }
 }
}//while
}//f2
//---------------------------------

sally 发表于 2004-6-5 12:07

也可以转化为图的遍历问题

huashi3483 发表于 2004-6-6 18:58

呵呵，好搭档

lynn324 发表于 2004-12-4 16:19

是用c编的吗?

mnpfc 发表于 2009-8-15 06:56

呵呵，看过了

页: [1]

数学建模社区-数学中国's Archiver

渡河问题