过河问题:传教士与野人 ( 积分: 10 )

  • 主题发起人 主题发起人 adamlee
  • 开始时间 开始时间
A

adamlee

Unregistered / Unconfirmed
GUEST, unregistred user!
传教士与野人

又一个过河问题:
三个传教士与三个野人要从河的左岸渡到右岸,刚好左岸有一只小船,一次最多只能坐两人,在任何时候,河的两岸,如果野人的数量多于传教士的数量,那么野人的恶习会复发,传教士会被吃掉!请编程找出所有可能的成功渡河方案,所谓成功,是指六个人都能成功渡河!

谢谢参与擂台赛:http://www.delphipages.cn/dispbbs.asp?boardID=21&ID=676&page=1

Delphi中文技术论坛
http://www.delphipages.cn
专用群组号:15345852 欢迎加入!
 
传教士与野人

又一个过河问题:
三个传教士与三个野人要从河的左岸渡到右岸,刚好左岸有一只小船,一次最多只能坐两人,在任何时候,河的两岸,如果野人的数量多于传教士的数量,那么野人的恶习会复发,传教士会被吃掉!请编程找出所有可能的成功渡河方案,所谓成功,是指六个人都能成功渡河!

谢谢参与擂台赛:http://www.delphipages.cn/dispbbs.asp?boardID=21&ID=676&page=1

Delphi中文技术论坛
http://www.delphipages.cn
专用群组号:15345852 欢迎加入!
 
程序是编好了,可不知道是编错了还是题目确实无解,查了半了。
program Project2;

{$APPTYPE CONSOLE}

uses
SysUtils;

type
TNode = record
a, b: Integer;
d1, d2: Integer
end;

var
Stack: array [1..100] of TNode;
Top: Integer;
NewNode: TNode;

function Double(const Node: TNode): Boolean;
var
i: Integer;
begin
for i:=1 to Top do
if (Stack.a=Node.a) and (Stack.b=Node.b) then
begin
Result:=True;
Exit
end;
Result:=False
end;

procedure Print;
var
i: Integer;
begin
for i:=1 to Top do
WriteLn('(', Stack.a, ', ', Stack.b, ') (', Stack.d1, ', ',
Stack.d2, ')');
WriteLn('(', NewNode.a, ', ', NewNode.b, ') (', 3-NewNode.a, ', ',
NewNode.b, ')')
end;

begin
Top:=1;
Stack[Top].a:=3;
Stack[Top].b:=3;
Stack[Top].d1:=0;
Stack[Top].d2:=0;

while Top>0 do
begin
while (Stack[Top].d1<=2) and (Stack[Top].d2<=2) do
begin
Inc(Stack[Top].d2);
if Stack[Top].d2>2 then
begin
Inc(Stack[Top].d1);
Stack[Top].d2:=0
end;
if (Stack[Top].d1+Stack[Top].d2)<=2 then
begin
if (Top mod 2)=1 then
begin
NewNode.a:=Stack[Top].a-Stack[Top].d1;
NewNode.b:=Stack[Top].b-Stack[Top].d2
end
else
begin
NewNode.a:=Stack[Top].a+Stack[Top].d1;
NewNode.b:=Stack[Top].b+Stack[Top].d2
end;
if (NewNode.a in [0..3]) and (NewNode.b in [0..3]) then
if (NewNode.a>=NewNode.b) or (NewNode.a=0) then
if (NewNode.a<=NewNode.b) or (NewNode.a=3) then
if not Double(NewNode) then
if (NewNode.a=0) and (NewNode.b=0) then
Print
else
begin
Inc(Top);
Stack[Top]:=NewNode;
Stack[Top].d1:=0;
Stack[Top].d2:=0;
end
end
end;
Dec(Top)
end;
ReadLn
end.
 
开始我编好程序后发现没有结果,后来想了半天,感觉对题目有一些误解,就是考虑河两岸传教士和野蛮人的人数对比时,如果船当前靠岸的那边应该,不存在人数不平衡导致野蛮人吃传教士的情况。

比如当前从左岸到右岸,如果左岸传教士人数比野蛮人多,那么野蛮人会吃传教士;但是对于右岸,当船到右岸时,如果传教士人数比野蛮人少并不应该当作危险考虑,而是船又从右岸出发向左岸时,剩下右岸的人数比例才作为危险考虑。

如果没有注意以下情况,是没有结果的。下面的代码只得出一个结果,其中有2处被注释的地方就是针对以上情况的。

unit Unit1;

interface

uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls;

type
TForm1 = class(TForm)
Button1: TButton;
Memo1: TMemo;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject);
var count:integer;
s:string;
ProcArr:array[0..500, 0..1, 0..1] of integer;
ManArr:array[0..500,0..1] of integer;
BoatArr:array[0..500] of boolean;

procedure Go(iStep:integer
bLeft:boolean);
var i,j,k:integer;
begin
//当前状态与之前状态有重复
if iStep>2 then
begin
for k:=0 to iStep-2 do
if (ProcArr[k,0,0]=ProcArr[iStep-1,0,0]) and
(ProcArr[k,0,1]=ProcArr[iStep-1,0,1]) and
(BoatArr[k]=BoatArr[iStep-1]) then
exit;
end;

//全部过河
if (ProcArr[iStep-1,1,0]=3) and
(ProcArr[iStep-1,1,1]=3) then
begin
inc(count);
s:='['+IntToStr(Count)+']'+#13;
s:=s+'-------左岸--------------------------右岸-------'+#13;
s:=s+'--传教士:野蛮人------------------传教士:野蛮人--'+#13;
s:=s+' 3 : 3 ------------------ 0 : 0'+#13;
for k:=1 to iStep-1 do
if BoatArr[k] then
s:=s+format(' %d : %d --[%d:%d]->--------- %d : %d'+#13,[ProcArr[k,0,0],ProcArr[k,0,1],ManArr[k,0],ManArr[k,1],ProcArr[k,1,0]-ManArr[k,0],ProcArr[k,1,1]-ManArr[k,1]])
else
s:=s+format(' %d : %d ----------<-[%d:%d]- %d : %d'+#13,[ProcArr[k,0,0]-ManArr[k,0],ProcArr[k,0,1]-ManArr[k,1],ManArr[k,0],ManArr[k,1],ProcArr[k,1,0],ProcArr[k,1,1]]);
Memo1.Lines.Text:=Memo1.Lines.Text+s+#13+#13;
exit;
end;

for i:=0 to 2 do //传教士人数
for j:=0 to 2-i do //野蛮人人数
if i+j>0 then
begin
if bLeft then
begin //从左边
if (ProcArr[iStep-1,0,0]>=i) and //传教士人数足够
(ProcArr[iStep-1,0,1]>=j) and //野蛮人人数足够
(ProcArr[iStep-1,0,0]-i>=ProcArr[iStep-1,0,1]-j) //如果执行当前方案:左岸传教士人数大于等于野蛮人人数
//不考虑这种情况 (ProcArr[iStep-1,1,0]+i>=ProcArr[iStep-1,1,1]+j) //如果执行当前方案:右岸传教士人数大于等于野蛮人人数
then
begin
ProcArr[iStep,0,0]:=ProcArr[iStep-1,0,0]-i;
ProcArr[iStep,0,1]:=ProcArr[iStep-1,0,1]-j;
ProcArr[iStep,1,0]:=ProcArr[iStep-1,1,0]+i;
ProcArr[iStep,1,1]:=ProcArr[iStep-1,1,1]+j;
ManArr[iStep,0]:=i;
ManArr[iStep,1]:=j;
BoatArr[iStep]:=bLeft;
Go(iStep+1, not(bLeft));
end;
end
else
begin //从右边
if (ProcArr[iStep-1,1,0]>=i) and //传教士人数足够
(ProcArr[iStep-1,1,1]>=j) and //野蛮人人数足够
(ProcArr[iStep-1,1,0]-i>=ProcArr[iStep-1,1,1]-j) //如果执行当前方案:右岸传教士人数大于等于野蛮人人数
//不考虑这种情况 (ProcArr[iStep-1,0,0]+i>=ProcArr[iStep-1,0,1]+j) //如果执行当前方案:左岸传教士人数大于等于野蛮人人数
then
begin
ProcArr[iStep,1,0]:=ProcArr[iStep-1,1,0]-i;
ProcArr[iStep,1,1]:=ProcArr[iStep-1,1,1]-j;
ProcArr[iStep,0,0]:=ProcArr[iStep-1,0,0]+i;
ProcArr[iStep,0,1]:=ProcArr[iStep-1,0,1]+j;
ManArr[iStep,0]:=i;
ManArr[iStep,1]:=j;
BoatArr[iStep]:=bLeft;
Go(iStep+1, not(bLeft));
end;
end;
end;
end


begin
count:=0;

//第一步状态
ProcArr[0,0,0]:=3
//左岸:传教士3人
ProcArr[0,0,1]:=3
//左岸:野蛮人3人
ProcArr[0,1,0]:=0
//右岸:传教士0人
ProcArr[0,1,1]:=0
//右岸:野蛮人0人
BoatArr[0]:=false
//左岸

Go(1,true);
end;

end.
 
晕死,严格按照题意就是无解丫。
 
你们想好没有?真的无解么?其实,不但有解,还不只一种,传教士与野人是可以相等的,只是不能某一边野人数量比传教士多。
请到我的论坛:http://www.delphipages.cn擂台赛区参赛!
谢谢参与!
 
to 楼主:给一个解,也好让我检查程序的错误.
 
呵呵,发现问题了.在Double函数里加一句话
if (i mod 2)=((Top+1) mod 2) then
 
改过如下,4个解
program Project2;

{$APPTYPE CONSOLE}

type
TNode = record
a, b: Integer;
d1, d2: Integer
end;

var
Stack: array [1..100] of TNode;
Top: Integer;
NewNode: TNode;

function Double(const Node: TNode): Boolean;
var
i: Integer;
begin
for i:=1 to Top do
if (Stack.a=Node.a) and (Stack.b=Node.b) then
if (i mod 2)=((Top+1) mod 2) then
begin
Result:=True;
Exit
end;
Result:=False
end;

procedure Print;
{$J+}
const
Count: Integer = 0;
{$J-}
var
i: Integer;
begin
Inc(Count);
WriteLn(Count);
for i:=1 to Top do
WriteLn('(', Stack.a, ', ', Stack.b, ') (', 3-Stack.a, ', ',
3-Stack.b, ')');
WriteLn('(', NewNode.a, ', ', NewNode.b, ') (', 3-NewNode.a, ', ',
NewNode.b, ')')
end;

begin
Top:=1;
Stack[Top].a:=3;
Stack[Top].b:=3;
Stack[Top].d1:=0;
Stack[Top].d2:=0;

while Top>0 do
begin
while (Stack[Top].d1<=2) and (Stack[Top].d2<=2) do
begin
Inc(Stack[Top].d2);
if Stack[Top].d2>2 then
begin
Inc(Stack[Top].d1);
Stack[Top].d2:=0
end;
if (Stack[Top].d1+Stack[Top].d2)<=2 then
begin
if (Top mod 2)=1 then
begin
NewNode.a:=Stack[Top].a-Stack[Top].d1;
NewNode.b:=Stack[Top].b-Stack[Top].d2
end
else
begin
NewNode.a:=Stack[Top].a+Stack[Top].d1;
NewNode.b:=Stack[Top].b+Stack[Top].d2
end;
if (NewNode.a in [0..3]) and (NewNode.b in [0..3]) then
if (NewNode.a>=NewNode.b) or (NewNode.a=0) then
if (NewNode.a<=NewNode.b) or (NewNode.a=3) then
if not Double(NewNode) then
if (NewNode.a=0) and (NewNode.b=0) then
Print
else
begin
Inc(Top);
Stack[Top]:=NewNode;
Stack[Top].d1:=0;
Stack[Top].d2:=0;
end
end
end;
Dec(Top)
end;
ReadLn
end.
 
第一次:野人、传教士各一个渡河,野人划回来 左岸:野人2传教士2 右岸:传教士1
第二次:野人载一个野人过河,野人划回来 左岸:野人1传教士2 右岸:传教士1野人1
第三次:野人载一个传教士过河,野人划回来 左岸:野人1传教士1右岸:传教士2野人1
第四次:野人载一个传教士/野人过河,野人划回来 左岸:野人1/0传教士0/1右岸:传教士2/3野人1/2
第五次:不用说了,剩下那个
我觉得关键在于谁划船才能保持数量平衡
 
请到我的论坛:
http://www.delphipages.cn
擂台赛区参赛!
谢谢参与!
 
四个解是对的,不过,在这里不算数,必须上我的论坛擂台赛区提交源代码,才算参赛!谢谢配合!
 
晕,搂主就是想宣传自己的论坛着
 
我觉的youngwind所说不对,
第一次:野人、传教士各一个渡河,野人划回来 左岸:野人2传教士2 右岸:传教士1(野人回到右岸后,有三个野人,这不就把传教士给吃了,其余类同)
 
你在这里当然算不上参赛了,我说的没错啊,没错,我是宣传我的论坛,这也有错么?
谢谢。
 
这是人工智能中的问题吧,
如果用推理语言解决可能更简单。
 
恩,AI的书中就有这个题,当时我们就做过好多遍了,用树推理。还有什么九宫图之类的,都是经典问题
 
还不用上升到AI的高度,只要是软件专业的学生,最初都会在《离散数学》里学到,然后在〈数据结构〉里复习,然后在〈程序设计方法〉中再次复习,最后才会在〈人工智能〉里再三复习。
 
专业还是专业呀,对我来说,真是可望而不可及,我是学文科的,这些于我,是~!@#$%^&amp;*()*&amp;^%$#@!~

Delphi是我的业余爱好。
 

Similar threads

S
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
D
回复
0
查看
1K
DelphiTeacher的专栏
D
D
回复
0
查看
1K
DelphiTeacher的专栏
D
后退
顶部