[算法习题] 1.人、狗、鸡、米过河的问题

Question

Delphi 版面现在革命的气氛洋溢。作为老虫子，率先起起哄。
从一些简单的智力题让大家从中体会到 算法的重要。老题目：《人、狗、鸡、米过河的问题》话说csdn老鸟猛禽要带一条狗、一只鸡、一袋子米过河，
但小船只有猛禽划外，最多只能载一样东西过河，而当猛禽不在场时，狗要吃鸡、鸡要吃米。
请大家告诉猛禽该如何过河?
输入条件
Raptor，DOG, HEN，RICE注：
1.猛禽不是禽，是csdn 中的delphi版的老鸟:)
2.题目可以用pascal, C完成，但必须是控制台程序（Console Application），因为这样便于大家测试；（c我能看得懂，大家呢？）
3.程序逻辑清晰，注释得当；
4.贴出程序之前必须先清晰地阐述算法；
5.建议大家独立思考，不要到网上找现成的答案；
6.第一个给出大家公认的正确答案的，赏100分；
7.给出最有大家认可的最优算法的赏100分；
8.分可以兼得。希望大家捧场。

Answer 1

先运鸡，在运狗，在吧鸡运回，在把米运过去，最后运鸡
if 岸边有狗和鸡 or 有鸡和米 then
   print("危险")
else  print("ok")

Answer 2

做一个矩阵：
             狗     鸡      米
         狗  0      -1      1
         鸡  -1     0       -1 
         米  1      -1      0
-1 表示不可相容，1表示相容   0表示无效；只要矩阵中的数都>=0就可以相容了，如果有<0
的数就不相容。
由于人要划船是必须每次都要走的，所以人就不需要列到矩阵中了
已经过河的一个矩阵A  未过河的一个矩阵B
刚开始A是0*0的，B是3*3的
每次数据处理完就判断A或B是否相容，如果A或B有一个不相容就取走一个与刚才处理完的不同的行和列（为了避免死循环），然后再判断，直到A是3*3的,B是0*0的就可以了。

Answer 3

Raptor and Hen
      |
     \|/
Raptor Return
      |
     \|/
Raptor and Dog
      |
     \|/
Raptor and Hen Return
      |
     \|/
Raptor and Rice
      |
     \|/
Raptor Return
      |
     \|/
Raptor and Hen

Answer 4

补充一下：如果矩阵AB都相容，则再从B中取掉一行一列再进行

Answer 5

首先，建立窗体，增添控件。添加两个ListBox:ListBox1,ListBox2;一个按钮Button：Button1;一个定时器Timer1.procedure TFormMain.FormShow(Sender: TObject);
begin
  listbox1.AddItem('Raptor');
  listbox1.AddItem('Dog');
  listbox1.AddItem('Hen');
  listbox1.AddItem('Rice');
  Timer1.Interval:=1000;
  Timer1.Enabled:=False;end;
procedure TFormMain.Button1Chick(Sender: TObject);
Label Delay;
begin
  Timer1.Enabled:=True;           //先带小鸡鸡过去
  listbox1.Item('Raptor').Delete;
  listbox1.Item('Hen').Delete;
  listbox2.AddItem('Raptor');
  listbox2.AddItem('Hen');
  Delay;  listbox2.Item('Raptor').Delete;     //独自返回
  listbox1.AddItem('Raptor');
  Delay;  listbox1.Item('Raptor').Delete;     //带小狗过去
  listbox1.Item('Dog').Delete; 
  listbox2.AddItem('Raptor');
  listbox2.AddItem('Dog');
  Delay;  listbox2.Item('Raptor').Delete;    //带小鸡鸡返回
  listbox2.Item('Hen').Delete; 
  listbox1.AddItem('Raptor');
  listbox1.AddItem('Hen');
  Delay;  listbox1.Item('Raptor').Delete;    //带大米过去
  listbox1.Item('Rice').Delete; 
  listbox2.AddItem('Raptor');
  listbox2.AddItem('Rice');
  Delay;  listbox1.Item('Raptor').Delete;    //独自返回
  listbox2.AddItem('Raptor');
  Delay;  listbox1.Item('Raptor').Delete;    //带小鸡鸡过去
  listbox1.Item('Hen').Delete; 
  listbox2.AddItem('Raptor');
  listbox2.AddItem('Hen');
  Delay;//////////////////////////////////////////
Delay:
  {延时2秒}
end;

Answer 6

1. Raptor,HEN
2. Raptor,DOG
3. Raptor,HEN(又带过去)
4. Raptor,RICE
5. Raptor,HEN

Answer 7

(*
使用回溯算法～～
先给个初始状态～～
把空手也看成特殊的物品～～
拾个物品向对岸移动～～
如果不成功就回到原来的状态，换下一个物品～～
如果成功就重复上述操作～～
今天不把Raptor累爬下，才怪～～
*){$APPTYPE CONSOLE}program Raptor;type
  TGoods = (gsNone, gsDOG, gsHEN, gsRICE);const
  cGoodsCaption: array[TGoods] of string = ('空手', '狗', '鸡', '米');var
  vGoodsList: array[TGoods] of Boolean; //物品是否在对岸var
  vRaptorPosition: Boolean; //Raptor是否在对岸
  vOldGoods: TGoods; //上一次移动的物品
  vVictory: Boolean; //是否成功
  vStep: string; //输出用的步数procedure Move(mGoods: TGoods; mStep: string);
var
  I, J: TGoods;
begin
  if vVictory then Exit; //已经成功
  vRaptorPosition := not vRaptorPosition; //移动Raptor
  vGoodsList[mGoods] := not vGoodsList[mGoods]; //移动物品
  J := vOldGoods; //保存历史以便恢复
  vOldGoods := mGoods; //记录上次移动的物品
  
  ///////Begin 判断是否成功
  if vRaptorPosition and vGoodsList[gsDOG] and
    vGoodsList[gsHEN] and vGoodsList[gsRICE] then begin
    vStep := mStep;
    vVictory := True;
    Exit;
  end;
  ///////End 判断是否成功  ///////Begin 判断是否合法
  if not ((vGoodsList[gsHEN] = vGoodsList[gsRICE]) and
    (vRaptorPosition <> vGoodsList[gsRICE])) and //米没被吃
    not ((vGoodsList[gsDOG] = vGoodsList[gsHEN]) and
    (vRaptorPosition <> vGoodsList[gsHEN])) then //鸡没被吃
    for I := Low(I) to High(I) do
      if vOldGoods <> I then Move(I, mStep + '>>' + cGoodsCaption[I]);
  ///////End 判断鸡是否被吃  ///////Begin 还原
  vRaptorPosition := not vRaptorPosition; //移动Raptor
  vGoodsList[mGoods] := not vGoodsList[mGoods]; //移动物品
  vOldGoods := J;
  ///////End 还原
end;procedure Init;
begin
  FillChar(vGoodsList, SizeOf(vGoodsList), 0);
  vRaptorPosition := False;
  vVictory := False;
  vOldGoods := gsNone;
  vStep := '无法移动';
end;procedure Calc;
var
  I: TGoods;
begin
  for I := Low(I) to High(I) do
    if vOldGoods <> I then Move(I, cGoodsCaption[I]);
end;procedure Print;
begin
  Write(vStep);
  Readln;
end;begin
  Init;
  Calc;
  Print;
end.

Answer 8

伴水来凑热闹了;) 欢迎。to richlife(多采人生)
我说了，要控制台程序，不要用VCL.gencan(无敌)  的思路比较有意思，关注一下。

Answer 9

///////Begin 判断是否合法
  if ((vRaptorPosition = vGoodsList[mGoods]) or (mGoods = gsNone)) and //除空手外必须和移动的物品在一边     <<<<<<<<<<<<<<<<<<忘加了一个判断，巧合结果也是一样的
    not ((vGoodsList[gsHEN] = vGoodsList[gsRICE]) and
    (vRaptorPosition <> vGoodsList[gsRICE])) and //米没被吃
    not ((vGoodsList[gsDOG] = vGoodsList[gsHEN]) and
    (vRaptorPosition <> vGoodsList[gsHEN])) then //鸡没被吃
    for I := Low(I) to High(I) do
      if vOldGoods <> I then Move(I, mStep + '>>' + cGoodsCaption[I]);
  ///////End 判断鸡是否被吃
--------鸡
狗、米
鸡、人--------空
狗、米、人
鸡--------狗
米
鸡、狗、人--------鸡
鸡、米、人
狗--------米
鸡
狗、米、人
--------空
鸡、人
狗、米--------鸡
狗、米、鸡、人

Answer 10

大家都傻了吗
两种方案，保证最后一个是鸡就行了狗->米->鸡米->狗->鸡

Answer 11

首先批判伴水判断什么鸡是否被吃？多此一举再强烈谴责 forgetter狗->米->鸡   //把狗带过去，鸡就把米吃了米->狗->鸡  //把米带过去，狗就把鸡吃了
先扣100分再说

Answer 12

强烈建议
forgetter先捐出100分再说

Answer 13

forgetter() 米->狗->鸡
~~~~~~~~~~
着方案行吗？呵呵

Answer 14

KAO, 这种题目上小学就做过了，怎么现在还做错？

Answer 15

forgetter() 
说明小学教育有问题呀！教育抓得不够。

Answer 16

强烈建议
forgetter先捐出100分再说

Answer 17

如果只是针对这个问题的话
Go('猛鸟','鸡');
Back('猛鸟');
Go('猛鸟','狗');
Back('猛鸟','鸡');
Go('猛鸟','米');
Back('猛鸟');
Go('猛鸟','鸡');这样行吗？嘿嘿

Answer 18

妈的，老子被你AD害死了
type
  TADClass = class of TAD;
  TAD = class //为报复AD
  private
    FFoeClassName: string;
  public
    constructor Create(AFoeClassName: string);
    function IsRaptor: Boolean; virtual; abstract;
    function IsFoe(AAD: TAD): Boolean; virtual;
  end;  TADRaptor = class(TAD)
  public
    constructor Create;
    function IsRaptor: Boolean; override;
  end;  TADDog = class(TAD)
  public
    constructor Create;
    function IsRaptor: Boolean; override;
  end;  TADHen = class(TAD)
  public
    constructor Create;
    function IsRaptor: Boolean; override;
  end;  TADRice = class(TAD)
  public
    constructor Create;
    function IsRaptor: Boolean; override;
  end;  TSite = class
  private
    FADList: TList;
  public
    constructor Create;
    destructor Destroy; override;
    function AddAD(AAD: TAD): Boolean;
    function RemoveAD(AAD: TAD): Boolean;
  end;  TBoat = class(TSite)
  private
    function CanMove: Boolean;
  public
    procedure Move;
  end;---------------------------
constructor TAD.Create(AFoeClassName: string);
begin
  FFoeClassName := AFoeClassName;
end;function TAD.IsFoe(AAD: TAD): Boolean;
begin
  Result := AAD.ClassNameIs(FFoeClassName);
end;{ TRaptor }constructor TADRaptor.Create;
begin
  inherited Create('');
end;function TADRaptor.IsRaptor: Boolean;
begin
  Result := True;
end;{ TADDog }constructor TADDog.Create;
begin
  inherited Create('');
end;function TADDog.IsRaptor: Boolean;
begin
  Result := False;
end;{ TADHen }constructor TADHen.Create;
begin
  inherited Create('TADDog');
end;function TADHen.IsRaptor: Boolean;
begin
  Result := False;
end;{ TADRICE }constructor TADRice.Create;
begin
  inherited Create('TADHen');
end;function TADRice.IsRaptor: Boolean;
begin
  Result := False;
end;
{ TSite }
constructor TSite.Create;
begin
  FADList := TObjectList.Create(True);
end;destructor TSite.Destroy;
begin
  FADList.Clear;
  FADList.Free;
end;function TSite.AddAD(AAD: TAD): Boolean;
var
  I: Integer;
begin
  Result := False;  for I := 0  to FADList.Count - 1 do
  begin
    if TAD(FADList[I]).ClassNameIs(AAD.ClassName) then
      raise Exception.Create('已经加入')
    else
      if TAD(FADList[I]).IsRaptor then
      begin
        Result := True;
        Break;
      end
      else if TAD(FADList[I]).IsFoe(AAD) then
        raise Exception.Create('不能加入');
  end;
  if (FADList.Count = 0) or (I = FADList.Count - 1) then
    Result := True;
  if Result then
  begin
    FADList.Add(AAD);
    Result := True;
  end;
end;
function TSite.RemoveAD(AAD: TAD): Boolean;
var
  I, J: Integer;
  iIndex: Integer;
  bHasRaptor: Boolean;  function GetIndex: Integer;
  var
    I: Integer;
  begin
    Result := -1;
    for I := 0 to FADList.Count - 1 do
      if TAD(FADList[I]).ClassNameIs(AAD.ClassName) then
      begin
        Result := I;
        Break;
      end;
  end;begin
  Result := False;
  iIndex := GetIndex;  bHasRaptor := False;
  for I := 0 to FADList.Count - 1 do
  begin
    if I = iIndex then continue;
    if TAD(FADList[I]).IsRaptor then
      bHasRaptor := True;
  end;
  if bHasRaptor then
    Result := True
  else begin
    for I := 0 to FADList.Count - 1 do
    begin
      for J := 0 to FADList.Count - 1 do
      begin
        if (I = J) or (I = iIndex) or (J = iIndex) then continue;
        if TAD(FADList[I]).IsFoe(TAD(FADList[J])) then
          raise Exception.Create('不能退出');
      end;
    end;
  end;  if Result then
    FADList.Remove(AAD);
end;{ TBoat }function TBoat.CanMove: Boolean;
var
  I: Integer;
begin
  Result := True;
  for I := 0 to FADList.Count - 1 do
  begin
    if TAD(FADList[I]).IsRaptor then
    begin
      Result := True;
      Break;
    end;
  end;
  if Result then
    Result := Result and (FADList.Count > 0)
      and (FADList.Count < 4);
end;procedure TBoat.Move;
begin
  if not CanMove then
     raise Exception.Create('不能移动');end;

Answer 19

forgetter() 
你居然能把程序写成这样！！！！！！！
我服了，有点像那个不同水平的高手写"hello world"的例子。这程序不完整呀！我去睡觉了，明天接着看，

Answer 20

死AD，臭AD，烂AD，让我今天迟到10分钟

Answer 21

我觉得绯村的思路才是最正确的，上学时图论老师就提出过用最短路径的想法来解决这个问题，无奈当时习惯copy作业，都没仔细思考
现在正在思考ing。。
应该往这方向想才对

Answer 22

forgetter() 你只是迟到10分钟我昨晚喝的滥醉，还跟你折腾到半夜今天上午旷工半天！！我睡到12:30  :(

Answer 23

在绿盟论坛上http://www.0mai.com/bbs/down_default.asp  有这问题的说明
http://www.0mai.com/bbs上有说明
我的OICQ：9199333

Answer 24

gencan(无敌)
你自己写一个完整的呀！