作者：SkyJacker 2007.06
内容：OOP 习作
目的：欢迎意见、建议、讨论。
发布：http://bbs.cnpack.org
QQ Group: 130970

1、问题提出：

小夏：
有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，
它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。
编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。

2、解决思路：

    想用面向对象的方法来解决。
    看题目，首先要找出具体的独立的对象来，然后根据其特性封装成类。
是否可以将细木干可以作为一个对象呢？如果将细木干作为一个对象，它需要管理每个节点。
不过我感觉选择木干不是很清晰(也许有人会搞明白，望告知)，因此选择了蚂蚁作为一个独立的对象，同时，因为有多个蚂蚁，蚂蚁之间的运动方向，有时取决于其他蚂蚁的方向，因此，建立一个用于管理蚂蚁的类，来实现具体的运动逻辑控制。　

3、具体实现

有时候想的或说的可能简单，但是具体实现起来也有不少要考虑的东东。
下面是具体实现，仅供参考。

const
  MaxAntNum = 5;
  MaxTreeLen = 27;
  cnPositon = '%d %d %d %d %d';

{ TTreeAnt }

  TTreeAnt = class(TObject)
  {* 蚂蚁类}
  private
    FHeadDirection: Boolean; // 头部方向
    FPosition: Integer; // 位置
    FLifeValueUpperLimit: Integer; // 生命上限
    FLifeValueLowerLimit: Integer; // 生命下限
    FLiving: Boolean; // 活着
    FTurnAroundFlag: Boolean; // 是否要转向
    procedure SetTurnAroundFlag(ATurnAroundFlag: Boolean);  
    procedure SetHeadDirection(AHeadDirection: Boolean);
    procedure SetPosition(APosition: Integer);
    procedure SetLifeValueUpperLimit(ALifeValue: Integer);
    procedure SetLifeValueLowerLimit(ALifeValue: Integer);
  protected

  public
    constructor Create;
    destructor Destroy; override;
    procedure StepIt; // 前进
    procedure TurnAround; // 转向
  published
    property HeadDirection: Boolean  read FHeadDirection write SetHeadDirection;
    property Position: Integer read FPosition write SetPosition;
    property Living: Boolean read FLiving;
    property LifeValueUpperLimit: Integer read FLifeValueUpperLimit write SetLifeValueUpperLimit;
    property LifeValueLowerLimit: Integer read FLifeValueLowerLimit write SetLifeValueLowerLimit;
    property TurnAroundFlag: Boolean read FTurnAroundFlag write SetTurnAroundFlag;
  end;

{ TTreeAntMgr }

  TTreeAntInitRec = record
  { 管理蚂蚁记录结构 }
    HeadDirection: Boolean;
    Position: Integer;
    UpperLimit: Integer;
    LowerLimit: Integer;
  end;

  // 树节点结构
  //TTreeNode = array[1..MaxTreeLen] of Integer;
  TTreeNode = array[-1..MaxTreeLen+1] of Integer; // 防溢出

  TTreeAntMgr = class(TObject)
  {* 蚂蚁管理类}
  private
    FTreeNode: TTreeNode;
    FAntCnt: Integer;
    FAntLivingCnt: Integer; // 存活蚂蚁计数
    FSpeed: Integer; // 速度
    FTimer: TTimer; // 蚂蚁步进定时器
    FTreeAnts: array[0..MaxAntNum-1] of TTreeAnt; // 蚂蚁数组
    FTimeCnt: Integer;
    FRunning: Boolean;
    procedure SetSpeed(ASpeed: Integer);
    procedure SetTreeNodeFlag(APosition: Integer);
    procedure ResetTreeNodeFlag(APosition: Integer);
    function GetPositionAntIdx(APosition: Integer): Integer;
    function IsTurnAround(AntIdx: Integer): Boolean; // 转向判断
    procedure TimerRun(Sender: TObject);
    procedure LogPosition; { 辅助函数 }
  protected

  public
    constructor Create;
    destructor Destroy; override;
    procedure EnterTree(TreeAntInitRec: TTreeAntInitRec);
    procedure Start;
    procedure Stop;
    procedure Init;     
  published
    property Running: Boolean read FRunning;
    property Speed: Integer  read FSpeed write SetSpeed;
  end;

{ TTreeAnt }

constructor TTreeAnt.Create;
begin
  FPosition := 1;
  FHeadDirection := True;
  FLiving := True;
  FTurnAroundFlag := False;
end;

destructor TTreeAnt.Destroy;
begin

end;

procedure TTreeAnt.SetTurnAroundFlag(ATurnAroundFlag: Boolean);
begin
  if FTurnAroundFlag <> ATurnAroundFlag then
    FTurnAroundFlag := ATurnAroundFlag;
end;

procedure TTreeAnt.SetHeadDirection(AHeadDirection: Boolean);
begin
  if FHeadDirection <> AHeadDirection then
    FHeadDirection := AHeadDirection;
end;

procedure TTreeAnt.SetPosition(APosition: Integer);
begin
  if FPosition <> APosition then
    FPosition := APosition;
end;

procedure TTreeAnt.SetLifeValueUpperLimit(ALifeValue: Integer);
begin
  if FLifeValueUpperLimit <> ALifeValue then
    FLifeValueUpperLimit := ALifeValue;
end;

procedure TTreeAnt.SetLifeValueLowerLimit(ALifeValue: Integer);
begin
  if FLifeValueLowerLimit <> ALifeValue then
    FLifeValueLowerLimit := ALifeValue;
end;

procedure TTreeAnt.StepIt();
begin
  if FHeadDirection then
    Inc(FPosition)
  else
    Dec(FPosition);

  if (FPosition > FLifeValueUpperLimit) or (FPosition < FLifeValueLowerLimit) then
    FLiving := False;
end;

procedure TTreeAnt.TurnAround;
begin
  FHeadDirection := not FHeadDirection;
end;

{ TTreeAntMgr }

constructor TTreeAntMgr.Create;
begin
  Init;
  FTimer := TTimer.Create(Application);
  FTimer.Enabled := False;
  SetSpeed(1000);
  FTimer.OnTimer := TimerRun;
end;

destructor TTreeAntMgr.Destroy;
begin
end;

procedure TTreeAntMgr.Init;
var
  I: Integer;
begin
  FAntCnt := 0;
  FTimeCnt := 0;
  FAntLivingCnt := 0;
  FRunning := False;
  for I := Low(FTreeNode) to High(FTreeNode) do
  begin
    FTreeNode[I] := 0;
  end;
end;

procedure TTreeAntMgr.SetTreeNodeFlag(APosition: Integer);
begin
  FTreeNode[APosition] := 1;
end;

procedure TTreeAntMgr.ResetTreeNodeFlag(APosition: Integer);
begin
  FTreeNode[APosition] := 0;
end;

function TTreeAntMgr.GetPositionAntIdx(APosition: Integer): Integer;
var
  I: Integer;
begin
  Result := -1;
  for I := Low(FTreeAnts) to High(FTreeAnts) do
  begin
    if FTreeAnts[I].Position = APosition then
    begin
      Result := I;
      Break;
    end;
  end;
end;

function TTreeAntMgr.IsTurnAround(AntIdx: Integer): Boolean;
var
  bMiddle: Boolean;
  bRight: Boolean;
  bLeft: Boolean;
  Position: Integer;
  NextAntIdx: Integer;
begin
  Result := False;
  bMiddle := FTreeAnts[AntIdx].HeadDirection;
  Position := FTreeAnts[AntIdx].Position;

  if bMiddle then
  begin
    if FTreeNode[Position+2] = 0 then
      Exit;
    NextAntIdx := GetPositionAntIdx(Position+2);
    if NextAntIdx = -1 then Exit;
    bRight := FTreeAnts[NextAntIdx].HeadDirection;
    if not bRight then  // 1 23
    begin
      Result := True;
      Exit;
    end;  
  end
  else
  begin
    if FTreeNode[Position-2] = 0 then
      Exit;
    NextAntIdx := GetPositionAntIdx(Position-2);
    if NextAntIdx = -1 then Exit;
    bLeft := FTreeAnts[NextAntIdx].HeadDirection;
    if bLeft then  // 12 3
    begin
      Result := True;
      Exit;
    end;
  end;
end;

procedure TTreeAntMgr.EnterTree(TreeAntInitRec: TTreeAntInitRec);
begin
  if FAntCnt > High(FTreeAnts) then
    Exit;
  if TreeAntInitRec.Position > High(FTreeNode) then
    Exit;
  FTreeAnts[FAntCnt] := TTreeAnt.Create;
  FTreeAnts[FAntCnt].HeadDirection := TreeAntInitRec.HeadDirection;
  FTreeAnts[FAntCnt].Position := TreeAntInitRec.Position;
  FTreeAnts[FAntCnt].LifeValueUpperLimit := TreeAntInitRec.UpperLimit;
  FTreeAnts[FAntCnt].LifeValueLowerLimit := TreeAntInitRec.LowerLimit;
  //FTreeNode[FTreeAnts[FAntCnt].Position] := 1;
  SetTreeNodeFlag(TreeAntInitRec.Position);
  Inc(FAntCnt);
end;

procedure TTreeAntMgr.Start;
begin
  FTimer.Enabled := True;
  FRunning := True;
end;

procedure TTreeAntMgr.Stop;
begin
  FTimer.Enabled := False;
  FRunning := False;  
end;

procedure TTreeAntMgr.SetSpeed(ASpeed: Integer);
begin
  if FSpeed <> ASpeed then
  begin
    FSpeed := ASpeed;
    FTimer.Interval := FSpeed;
  end;
end;

procedure TTreeAntMgr.TimerRun(Sender: TObject);
var
  I: Integer;
begin
  Inc(FTimeCnt);
  Log('计时：' + IntToStr(FTimeCnt));
  LogPosition;
  FAntLivingCnt := 0;
  for I := Low(FTreeAnts) to High(FTreeAnts) do
  begin
    if FTreeAnts[I].FLiving then
      if FTreeAnts[I].TurnAroundFlag then
      begin
        FTreeAnts[I].TurnAround;
        Log('转向:'+IntToStr(I));
     end;
     FTreeAnts[I].TurnAroundFlag := IsTurnAround(I);
  end;
  for I := Low(FTreeAnts) to High(FTreeAnts) do
  begin
    if not FTreeAnts[I].Living then
    begin
      Inc(FAntLivingCnt);
      if FAntLivingCnt >= FAntCnt then
      begin
        Stop;
        AddTime(0);
        Exit;
      end;
      Continue;
    end;  
    ResetTreeNodeFlag(FTreeAnts[I].Position);
    FTreeAnts[I].StepIt;
    if FTreeAnts[I].Living then
      SetTreeNodeFlag(FTreeAnts[I].Position)
    else
    begin
      Log('离桥:'+IntToStr(I) + ' 时间:' + IntToStr(FTimeCnt));
      AddTime(FTimeCnt);
    end;
  end;
end;

procedure TTreeAntMgr.LogPosition;
var
  P1,P2,P3,P4,P5: Integer;
  H1, H2, H3, H4, H5: Boolean;
begin
  P1 := FTreeAnts[0].Position;
  P2 := FTreeAnts[1].Position;
  P3 := FTreeAnts[2].Position;
  P4 := FTreeAnts[3].Position;
  P5 := FTreeAnts[4].Position;

  H1 := FTreeAnts[0].HeadDirection;
  H2 := FTreeAnts[1].HeadDirection;
  H3 := FTreeAnts[2].HeadDirection;
  H4 := FTreeAnts[3].HeadDirection;
  H5 := FTreeAnts[4].HeadDirection;

  FrmAnt.AntImgPostion([P1, P2, P3, P4, P5], [H1, H2, H3, H4, H5]);
  FrmAnt.LogPosition(Format(cnPositon, [P1, P2, P3, P4, P5]));
end;

4、发布可执行
   
如果你有修改、改进的想法，我很愿意发给你工程源代码。

[ 本帖最后由 skyjacker 于 2007-6-24 11:51 编辑 ]

完全就是模拟运动求结果？

恩。

蚂蚁背上的数字可以辨别，在某一个点相遇后，是否马上转向了。

中间的 TMemo 中的数值最大值就是本次过桥所化费的时间。
因为可设蚂蚁的速度，严格上讲是最大多少步。
如果蚂蚁速度是 1 秒，也就是题目要求的了。

程序假设桥是线段。

晕。。楼主参考下动量守恒定律