农夫过河问题？

sipingal · 发表于 2004-9-23 16:04:49

用C语言编程输出最少步骤的过河方法
有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？

sipingal · 发表于 2004-9-23 16:49:42

自己顶阿？

redinux · 发表于 2004-9-23 17:09:32

船需要农夫来划吗？

greensun · 发表于 2004-9-23 17:53:03

1、农夫带羊过去
2、农夫回来
3、农夫带狼过去（可以选狼或白菜之一）
4、农夫带羊回来
5、农夫带白菜过去（如果3是带白菜过去，那么5就是农夫带狼过去）
6、农夫独自回来
7、农夫带羊过去

怎么编程输出我不知道，因为我根本不懂编程。

希望对你有用

hiweed · 发表于 2004-9-23 18:37:00

最初由 redinux 发表
船需要农夫来划吗？

不用吧？
船让白菜来划好了，哈哈！

sipingal · 发表于 2004-9-23 19:11:01

在无穷多不同的方案中为何选择这个唯一的。(当然是C说明)

hiweed · 发表于 2004-9-23 19:18:02

根本没有无穷多个方案。
只有上述两种方案。
第一步是唯一的：必须先带羊过河。
第二步是可选的：带白菜，或者带狼；这样就出来了两种方案。

hiweed · 发表于 2004-9-23 19:22:40

当然不可行的方案有多个。
那就是任务失败的方案，比如，第一步先带走狼的话，羊会吃了白菜：行动失败。
再比如如果第一步带走的是白菜，那么狼会吃了羊：行动失败。

sipingal · 发表于 2004-9-23 19:33:55

然后可以带或者不带别的东西来来回回
这里有别人Pascal语言的解决方法，我还没搞懂

************************************************************
农夫过河问题
农夫过河问题
有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？
分析：以向量（人，狼，羊，菜）表示状态，其中每个变元可取0或1，取0表示在左岸（出发点），取1表示在右岸，则我们有八个规则：
（0，*，*，*）--->（1，*，*，*）（1）
（0，0，*，*）--->（1，1，*，*）（2）
（0，*，0，*）--->（1，*，1，*）（3）
（0，*，*，0）--->（1，*，*，1）（4）
（1，*，*，*）--->（0，*，*，*）（5）
（1，1，*，*）--->（0，0，*，*）（6）
（1，*，1，*）--->（0，*，0，*）（7）
（1，*，*，1）--->（0，*，*，0）（8）
注：每个*号可以是任意的0或1，但是在每条规则内部，左边和右边的对应*号应取相同值。
将这八个规则存储在一个二维数组rule(8,4)中，易知该数组的内容是：
（1， 0， 0， 0）
（1， 1， 0， 0）
（1， 0， 1， 0）
（1， 0， 0， 1）
（1， 0， 0， 0）
（-1， 0， 0， 0）
（-1，-1， 0， 0）
（-1， 0，-1， 0）
（-1， 0， 0，-1）
初态是：（0，0，0，0），终态是：（1，1，1，1），
非法中间状态有：（0，0，1，1），（0，1，1，0），（0，1，1，1），
（1，1，0，0），（1，0，0，1），（1，0，0，0）。
相应的广度优先搜索算法的PASCAL程序如下：
program farmer(output);
{programmer: Cheng Zhengxian Date: 1995.1}
const rule:array[1..8,1..4] of -1..1=((1,0,0,0),(1,1,0,0),(1,0,1,0),(1,0,0,1),
(-1,0,0,0),(-1,-1,0,0),(-1,0,-1,0),(-1,0,0,-1));
type stype=string[4];
var s:array[1..100] of record
info:stype;
rn:0..8;
father:integer;
end;
ob,mr:stype;
j,closed,open:integer;
procedure op;
var pre1,pre2,k,c:integer;
begin
writeln;writeln;c:=0;
k:=open;pre1:=s[k].father;s[k].father:=0;
repeat
pre2:=s[pre1].father;s[pre1].father:=k;
k:=pre1;pre1:=pre2;
until pre1=0;
k:=1;
repeat
writeln('Step ',c,':',s[k].info:20,s[k].rn:10);
k:=s[k].father;inc(c);
until k=0;
readln;halt;
end;
function extend(var mr:stype):boolean;
var f:boolean;
k,x:integer;
ss:stype;
begin
ss:=s[closed].info;mr:='';f:=true;
for k:=1 to 4 do
begin
x:=ord(ss[k])-ord('0')+rule[j,k];
if (x<0) or (x>1) then f:=false;
mr:=mr+chr(x+ord('0'));
end;
extend:=f;
end;
function passchk:boolean;
var f:boolean;
k:integer;
begin
f:=true;
for k:=1 to 4 do
if ((mr[2]=mr[3])and(mr[2]<>mr[1])) or ((mr[4]=mr[3])and(mr[3]<>mr[1]))
then f:=false;
if f then
for k:=1 to open-1 do
if mr=s[k].info then f:=false;
passchk:=f;
end;
Begin {=========================main program=============================}
ob:='1111';
closed:=0;open:=1;
s[1].info:='0000';s[1].rn:=0;s[1].father:=0;
repeat
j:=0;closed:=closed+1;
repeat
j:=j+1;mr:='';
if extend(mr) and passchk then
begin
open:=open+1;
s[open].info:=mr;s[open].rn:=j;s[open].father:=closed;
if mr=ob then op;
end;
until j=8;
until closed=open;
writeln('No solution!');
End.

复制代码

乱云飞渡 · 发表于 2004-9-23 20:06:24

我在书店见过一本英文的LISP教程，里边有这个问题，反正就是递归呗

		自动登录	找回密码
密码			注册

农夫过河问题？

没人知道吗

问题是这个算法的最优方案选择

可以先带羊过河

浏览过的版块