CnPack Forum - Powered by Discuz! Board

Subject: 蚂蚁过桥 [Print This Page]

Author: skyjacker Time: 2007-6-24 11:44 Subject: 蚂蚁过桥

作者：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 编辑 ]

Image Attachment: 1.jpg (2007-6-24 11:44, 40.57 K) / Download count 464
http://bbs.cnpack.org/attachment.php?aid=320

Image Attachment: 2.jpg (2007-6-24 11:44, 48.56 K) / Download count 441
http://bbs.cnpack.org/attachment.php?aid=321

Attachment: 蚂蚁过桥可执行.rar (2007-6-24 11:51, 210.03 K) / Download count 520
http://bbs.cnpack.org/attachment.php?aid=322

Author: Passion Time: 2007-6-24 12:24

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

Author: skyjacker Time: 2007-6-24 13:16

恩。

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

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

程序假设桥是线段。

Author: zzzl Time: 2007-7-12 21:26

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

Welcome to CnPack Forum (http://bbs.cnpack.org/)