开始我编好程序后发现没有结果,后来想了半天,感觉对题目有一些误解,就是考虑河两岸传教士和野蛮人的人数对比时,如果船当前靠岸的那边应该,不存在人数不平衡导致野蛮人吃传教士的情况。
比如当前从左岸到右岸,如果左岸传教士人数比野蛮人多,那么野蛮人会吃传教士;但是对于右岸,当船到右岸时,如果传教士人数比野蛮人少并不应该当作危险考虑,而是船又从右岸出发向左岸时,剩下右岸的人数比例才作为危险考虑。
如果没有注意以下情况,是没有结果的。下面的代码只得出一个结果,其中有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.