delphi.txt

用delphi语言编写实现传教士食人魔过河问题

首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员 

[被屏蔽广告]
 欢迎您:游客 | 退出 | 登录 注册 帮助 
我的帖子我参与的帖子我的空间我的网摘
 
   CSDNCSDN社区Delphi语言基础/算法/系统设计将帖子提前   放进我的网摘   推荐给好友 我要提问 帖子加分 生成帖子 置顶 推荐(加精) 取消推荐(加精) 锁定帖子 移动帖子 取消引用结贴去... 管理菜单 页面风格切换标准风格老版本论坛  传教士食人魔过河问题，程序出不了结果，请高手看看  [已结贴,结贴人:wei_hewei]
  
 加为好友 
发送私信 
在线聊天
wei_hewei 
hewei_1984 
等级:
 发表于：2008-05-25 13:42:54 楼主 
如题 
源码如下： 
unit Unit1; 

interface 

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

type 
  Tgrave = class(TForm) 
    Button1: TButton; 
    procedure Button1Click(Sender: TObject); 
    procedure FormClose(Sender: TObject; var Action: TCloseAction); 

  private 
    { Private declarations } 
    openTable: TObjectQueue; 
    closeTable: TObjectList; 
  public 
    { Public declarations } 
    {constructor create(owner:Tcomponent);override; 
    destructor Destroy; override; } 
    procedure initialize(); 
    procedure finish(); 
    procedure extend(obj:TObject); 
    procedure serviceExtend(m:integer;o:integer;obj:TObject); 
    function search:Boolean; 
    {扩展的结点可能在closeTable或者openTable里已经有了，这些结点不应在进行扩展} 
    function duplicateFind(obj:Tobject):Boolean; 

  end; 

  Tposition = (leftshore,rightshore); 

  Toperator = (Boat_0_0,Boat_0_1,Boat_0_2,Boat_1_0,Boat_2_0,Boat_1_1,Boat_2_2); 
              {Boat_0_0为赋给初使点的，以保持一致性 
                第一位代表传教士数，第二位代表食人魔数 
                Boat_2_2为循环时跳出错误作边界量} 
  Tstate = class(TObject) 
    Missionary:integer; 
    Orge:integer; 
    BoatPosition:Tposition; 
    procedure setValues(m:integer;o:integer;bp:Tposition); 
    function equal(comp:Tstate):Boolean; 
    function equalToValues(m:integer;o:integer;bp:Tposition):Boolean; 
  end; 

  Tnode = class(TObject) 
    state:Tstate; 
    father:Tnode; 

    procedure setValues(m:integer;o:integer; 
                        bp:Tposition;fath:Tnode); 
  end; 


var 
  grave: Tgrave; 

implementation 

{$R *.dfm} 

{ constructor Tgrave.create(owner:Tcomponent); 
begin 
    inherited Create(Owner); 
    openTable := TObjectQueue.Create; 
    closeTable := TObjectList.Create; 
end; 

destructor Tgrave.Destroy; 
begin 
  openTable.Free; 
  closeTable.Free; 
  inherited Destroy; 
end; 
} 
procedure Tnode.setValues(m:integer;o:integer; 
                          bp:Tposition;fath:Tnode); 
begin 
    state := Tstate.Create; 
    state.setValues(m,o,bp); 
    father := fath; 

end; 

procedure Tstate.setValues(m:integer; 
                              o:integer;bp:Tposition); 
begin 
    Missionary := m; 
    Orge := o; 
    BoatPosition := bp; 
end; 

function Tstate.equal(comp:Tstate):Boolean; 
begin 
    if((Missionary = comp.Missionary) and 
      (Orge = comp.Orge) and (BoatPosition = comp.BoatPosition)) then 
      begin 
        equal:=True; 
      end 
      else 
        equal:=False; 
end; 

function Tstate.equalToValues(m:integer;o:integer;bp:Tposition):Boolean; 
begin 
    if((Missionary = m) and 
      (Orge = o) and (BoatPosition = bp)) then 
      begin 
        equalToValues:=True; 
      end 
      else 
        equalToValues:=False; 
end; 


procedure Tgrave.initialize; 
var 
  node:Tnode; 
begin 

    openTable := TObjectQueue.Create; 
    closeTable := TObjectList.Create; 

    node := Tnode.Create; 
    node.setValues(3,3,leftshore,nil); 

    openTable.Push(node); 

end; 

procedure Tgrave.finish; 
begin 
    openTable.Free; 
    closeTable.Free; 
end; 

procedure Tgrave.extend(obj:TObject); 
var 
  node:Tnode; 
  op:Toperator; 
begin 

  node := Tnode(obj); 

  for op := Boat_0_1 to Boat_1_1 do 
  begin 

      case op of 
      Boat_0_1: 
          serviceExtend(0,1,node); 
      Boat_0_2: 
          serviceExtend(0,2,node); 
      Boat_1_0: 
          serviceExtend(1,0,node); 
      Boat_2_0: 
          serviceExtend(2,0,node); 
      Boat_1_1: 
          serviceExtend(1,1,node); 
      end; 

  end;  //for 

  closeTable.Add(node);  {扩展以后加入closeTable} 

end; 

procedure Tgrave.serviceExtend(m:integer;o:integer;obj:TObject); 
var 
  node,extendnode,father:Tnode; 
  bp:Tposition; 
  miss,org:integer; 
  isduplicate:Boolean; 
begin 

  node := Tnode(obj); 
  miss := node.state.Missionary; 
  org := node.state.Orge; 
  bp := node.state.BoatPosition; 
  father := node.father; 

  //isduplicate := false; 

  if( bp = leftshore) then 
  begin 
      {左岸时的操作} 
      miss := miss-m; 
      org := org-o; 
      if( (miss = 3) or (miss=org) or (miss = 0) )then 
      begin 
        extendnode := Tnode.Create; 
        extendnode.setValues(miss,org,rightshore,node); 
        isduplicate := duplicateFind(extendnode); 
        if(node.state.equalToValues(3,3,leftshore))then 
        begin 

          openTable.Push(extendnode); 
        end else if((father.state.equal(extendnode.state) <>True) 
                      and(not isduplicate))then 
        begin    {如果它的祖先结点不是这个状态} 
          openTable.Push(extendnode); 
        end else extendnode.Free; 
      end; 

  end else 
  begin 
    {右岸时的操作} 
      miss := miss+m; 
      org := org+o; 
      if( (miss = 3) or (miss = org) or (miss = 0) )then 
      begin 
        extendnode := Tnode.Create; 
        extendnode.setValues(miss,org,leftshore,node); 

        isduplicate := duplicateFind(extendnode); 

        if(node.state.equalToValues(3,3,leftshore))then 
        begin 

          openTable.Push(extendnode); 
        end else if((father.state.equal(extendnode.state) <>True) 
                      and (not isduplicate))then 
        begin 
          openTable.Push(extendnode); 
        end else extendnode.Free; 

      end; //if 

  end; //end if 

end; 

function Tgrave.duplicateFind(obj:Tobject):Boolean; 
var 
  nodeTemp,node:Tnode; 
  i:integer; 

begin 


  node := Tnode(obj); 
  {对于closeTable来说是TObjectList对象，有标准方面可以访问里面的元素} 
  for i:=0 to (closeTable.Count-1) do 
  begin    {数组元素是以基数0开始的，count为元素数目} 
      nodeTemp := Tnode(closeTable.Items[i]); 
      if(node.state.equal(nodeTemp.state)) then duplicateFind := True; 

  end; 

  duplicateFind := false;{如果没有找到则证明没有重复的扩展过的结点} 
  {  5.25改动,不再对openTable进行搜索 
  对于openTable来说，由于是TObjectQueue对象，没有标准的方面可以访问到元素 
    所示采用如下方法 

    for i:=1 to openTable.Count do 
    begin 
      nodeTemp := Tnode(openTable.Pop); 
      openTable.Push(nodeTemp); 
      if(nodeTemp.state.equal(node.state))then inOpenTable :=true; 
    end; 

    result := inOpenTable; 
    相当于将openTable重新取出压入一遍队列，结果为待设置项inOpenTable} 
  end; 


function Tgrave.search:Boolean; 
var 
  node:Tnode; 
begin 

  grave.initialize; 
  while (openTable.Count <>0) do 
  begin 
      node := Tnode(openTable.Pop); 
      if(node.state.equalToValues(3,3,rightshore))then    {目标状态} 
      begin 
        closeTable.Add(node); 
        result := True; {如果找到，则closeTable的最后一个ITEM为目标节点,返回true} 
      end else 
      extend(node); {否则扩展} 

  end; 
  result := False;  {若没有可扩展的节点了，而且没有找到目标节点，则返回fasle} 
end; 

procedure Tgrave.Button1Click(Sender: TObject); 
var 
  cando:Boolean; 
begin 
  grave.initialize; 
  cando := grave.search; 
  if cando then 
  begin 
    showmessage('可以搜索到'); 
  end else 
  begin 
    showmessage('不可以找到'); 
  end; 

end; 

procedure Tgrave.FormClose(Sender: TObject; var Action: TCloseAction); 
begin 
    grave.finish; 
end; 

end. 
 






 
问题点数：20 回复次数：3 显示所有回复显示星级回复显示楼主回复 修改 删除 举报 引用 回复   
 

[被屏蔽广告]
 加为好友 
发送私信 
在线聊天
 ssdldq 
月夜倩影 
等级:
 发表于：2008-05-25 13:51:381楼 得分:10 
有三个传教士和三个野人过河，只有一条能装下两个人的船，无论何时何地，如果野人的人数大于教士的人数，那么教士就会被吃掉. 你能不能找出一种安全的渡河方法呢? 
----以上为问题的描述，以上代码运行没有结果．．． 
 
修改 删除 举报 引用 回复   
 
 加为好友 
发送私信 
在线聊天
 ssdldq 
月夜倩影 
等级:
 发表于：2008-05-25 19:46:392楼 得分:10 
函数返回出了问题．在需要返回的地方Exit; 
 
修改 删除 举报 引用 回复   
 
 加为好友 
发送私信 
在线聊天
 wei_hewei 
hewei_1984 
等级:
 发表于：2008-05-25 19:50:483楼 得分:0 
函数返回时要exit；另外这一段node := Tnode(openTable.Pop); 
      if(node.state.equalToValues(3,3,rightshore))then    {目标状态} 
      begin 
        closeTable.Add(node); 
        result := True; {如果找到，则closeTable的最后一个ITEM为目标节点,返回true} 
      end else 
      extend(node); {否则扩展} 

的node.state.equltovalues(0,0,rightshore)就可以了 
还有就是 (miss = 3) or (miss = org) or (miss = 0)这个条件得加上对miss和orge的取值范围限定 
 
修改 删除 举报 引用 回复   
 

将帖子提前   放进我的网摘   推荐给好友 我要提问 帖子加分 结贴去... 管理菜单 页面风格切换标准风格老版本论坛  


--------------------------------------------------------------------------------
网站简介－广告服务－网站地图－帮助－联系方式－诚聘英才－English－ 问题报告
北京创新乐知广告有限公司 版权所有 京 ICP 证 070598 号
世纪乐知(北京)网络技术有限公司 提供技术支持
Copyright ? 2000-2008, CSDN.NET, All Rights Reserved
--------------------------------------------------------------------------------

  
      
 abc推荐给好友 
 

         
         
         
  

close