[算法习题] 1.人、狗、鸡、米过河的问题
Delphi 版面现在革命的气氛洋溢。作为老虫子，率先起起哄。
从一些简单的智力题让大家从中体会到 算法的重要。
老题目：《人、狗、鸡、米过河的问题》
话说csdn老鸟猛禽要带一条狗、一只鸡、一袋子米过河，
但小船只有猛禽划外，最多只能载一样东西过河，而当猛禽不在场时，狗要吃鸡、鸡要吃米。
请大家告诉猛禽该如何过河?
输入条件
Raptor，DOG, HEN，RICE
注：
1.猛禽不是禽，是csdn 中的delphi版的老鸟:)
2.题目可以用pascal, C完成，但必须是控制台程序（Console Application），因为这样便于大家测试；（c我能看得懂，大家呢？）
3.程序逻辑清晰，注释得当；
4.贴出程序之前必须先清晰地阐述算法；
5.建议大家独立思考，不要到网上找现成的答案；
6.第一个给出大家公认的正确答案的，赏100分；
7.给出最有大家认可的最优算法的赏100分；
8.分可以兼得。
希望大家捧场。
问题点数：200、回复次数：60Top
1 楼outer2000（天外流星）回复于 2003-12-16 17:42:58 得分 0
气氛不够热烈啊，我来UP；Top
2 楼pazee（耙子)(今年过年不收礼，收礼只收尿不湿）回复于 2003-12-16 17:49:34 得分 0
是呀:(
好像没人感兴趣。明天再没人就结了帖子:(Top
3 楼wave_f（小浪花）回复于 2003-12-16 17:51:19 得分 0
老问题了,嘿嘿Top
4 楼zgxly2002（zgxly2002）回复于 2003-12-16 17:51:27 得分 0
upTop
5 楼flyforlove（吾将远去）回复于 2003-12-16 17:52:18 得分 0
这个过程太简单了，换个复杂点的吧，
大象，小象，
大虎，小虎，
大狮，小狮，
过河，只有一条船，
限制条件：
1，船一次载重，两个大的，或者，三个小的
2，如果没有大的陪伴，小的会被其他大的吃掉。
3，大的都会划船，小的只有小象会。
求过河程序。
Top
6 楼pazee（耙子)(今年过年不收礼，收礼只收尿不湿）回复于 2003-12-16 17:56:10 得分 0
题目简单吗？我这都不会呀！呵呵。
看看大家算法如何写。
你这个题目我可以把他最为第二个帖子的，别急。Top
7 楼wangchangchun521gx（wangchangchun）回复于 2003-12-16 17:57:17 得分 0
先运鸡，在运狗，在吧鸡运回，在把米运过去，最后运鸡
if 岸边有狗和鸡 or 有鸡和米 then
print("危险")
else print("ok")
Top
8 楼pazee（耙子)(今年过年不收礼，收礼只收尿不湿）回复于 2003-12-16 18:02:44 得分 0
楼上的，这也叫算法？
我脑袋也能想明白，问题是让你写出来。Top
9 楼hbqinlei（漫步者）回复于 2003-12-16 18:06:26 得分 0
学习一下...Top
10 楼gencan（无敌）回复于 2003-12-16 18:22:45 得分 30
做一个矩阵：
狗 鸡 米
狗 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的就可以了。
Top
11 楼richlife（多采人生）回复于 2003-12-16 18:26:55 得分 0
Raptor and Hen
|
\|/
Raptor Return
|
\|/
Raptor and Dog
|
\|/
Raptor and Hen Return
|
\|/
Raptor and Rice
|
\|/
Raptor Return
|
\|/
Raptor and Hen
Top
12 楼gencan（无敌）回复于 2003-12-16 18:33:28 得分 0
补充一下：如果矩阵AB都相容，则再从B中取掉一行一列再进行Top
13 楼toyjoy（异根）回复于 2003-12-16 18:35:12 得分 0
这类问题可以用人工智能中的建模思想
具体的方法我也忘了，^ō^
好像是先确定限制条件，就是题目中的 狗要吃鸡、鸡要吃米
然后将一去一来两个过程看成是两个函数，带入参数后可以得到很多等式
最后就可以根据这些等式很容易的列出所有的结果
具体的方法大家看看相关参考书吧，呵呵Top
14 楼richlife（多采人生）回复于 2003-12-16 18:39:17 得分 0
首先，建立窗体，增添控件。添加两个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;Top
15 楼Flarezhao（蓝舍）回复于 2003-12-16 18:49:59 得分 0
upTop
16 楼tglong（Dragon）回复于 2003-12-16 18:51:21 得分 0
1. Raptor,HEN
2. Raptor,DOG
3. Raptor,HEN(又带过去)
4. Raptor,RICE
5. Raptor,HENTop
17 楼wjpop3（海崴）回复于 2003-12-16 18:59:34 得分 0
学习一下Top
18 楼whitetiger8（键盘未敲坏，基本功未练成）回复于 2003-12-16 19:16:41 得分 0
太费脑了。Top
19 楼zswangII（伴水清清)(一贴不灌，何以灌天下？）回复于 2003-12-16 19:17:15 得分 100
(*
使用回溯算法～～
先给个初始状态～～
把空手也看成特殊的物品～～
拾个物品向对岸移动～～
如果不成功就回到原来的状态，换下一个物品～～
如果成功就重复上述操作～～
今天不把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.
Top
20 楼liushiboy（绯村）回复于 2003-12-16 19:22:01 得分 40
这是一个关于图论的问题
把一岸上的合法状态全部列出来,然后在相邻状态之间连线
起始状态为(1,1,1,1),
而且求的最终结果为(0,0,0,0)
这样就变成了求两点之间最短路径的算法.
简单吧!
具体的自己试试吧,,,要去上政治课了..PS:科学共产主义
Top
21 楼liushiboy（绯村）回复于 2003-12-16 19:22:26 得分 0
错了,是要上科学社会主义!Top
22 楼xiaocuo_zrf（小错——淫雄所贱略同）回复于 2003-12-16 19:29:06 得分 0
用最短路径算法就可以实现
Top
23 楼pazee（耙子)(今年过年不收礼，收礼只收尿不湿）回复于 2003-12-16 19:51:27 得分 0
伴水来凑热闹了;) 欢迎。
to richlife(多采人生)
我说了，要控制台程序，不要用VCL.
gencan(无敌) 的思路比较有意思，关注一下。Top
24 楼zswangII（伴水清清)(一贴不灌，何以灌天下？）回复于 2003-12-16 19:58:08 得分 0
///////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 判断鸡是否被吃
--------鸡
狗、米
鸡、人
--------空
狗、米、人
鸡
--------狗
米
鸡、狗、人
--------鸡
鸡、米、人
狗
--------米
鸡
狗、米、人
--------空
鸡、人
狗、米
--------鸡
狗、米、鸡、人Top
25 楼pazee（耙子)(今年过年不收礼，收礼只收尿不湿）回复于 2003-12-16 20:04:28 得分 0
伴水的界面越来越人性化了。还能改成啥样？
给咱做个动画的行不？ :0Top
26 楼forgetter（csdn第一人渣）回复于 2003-12-16 20:22:56 得分 0
大家都傻了吗
两种方案，保证最后一个是鸡就行了
狗->米->鸡
米->狗->鸡
Top
27 楼hkbarton（→Beginner←）回复于 2003-12-16 20:34:38 得分 0
哈哈，不错，不错Top
28 楼ekin（风语者）回复于 2003-12-16 21:49:21 得分 0
凑热闹Top
29 楼myling（不理你）回复于 2003-12-16 22:10:31 得分 0
很简单呀
猛鸟先带鸡过去，自己回来
再带狗过去，把鸡带回来
再带米过去，自己回来
再带鸡过去就行了
算法嘛
真要写动画吗？哈哈Top
30 楼xiaoqiang123（xiaoqiang）回复于 2003-12-16 22:13:07 得分 0
高手云集啊，呵呵，看热闹了！！Top
31 楼forgetter（csdn第一人渣）回复于 2003-12-16 22:18:19 得分 0
阿德你傻了啊，直路不走走弯路，不要把问题复杂化Top
32 楼myling（不理你）回复于 2003-12-16 22:18:50 得分 0
首先批判伴水
判断什么鸡是否被吃？多此一举
再强烈谴责 forgetter
狗->米->鸡 //把狗带过去，鸡就把米吃了
米->狗->鸡 //把米带过去，狗就把鸡吃了
先扣100分再说
Top
33 楼myling（不理你）回复于 2003-12-16 22:19:43 得分 0
哈哈，还说我呢？
我晚上多喝了几杯
还比你清醒呢Top
34 楼myling（不理你）回复于 2003-12-16 22:22:15 得分 0
强烈建议
forgetter先捐出100分再说Top
35 楼pazee（耙子)(今年过年不收礼，收礼只收尿不湿）回复于 2003-12-16 22:23:09 得分 0
forgetter()
米->狗->鸡
~~~~~~~~~~
着方案行吗？呵呵Top
36 楼forgetter（csdn第一人渣）回复于 2003-12-16 22:25:20 得分 0
KAO, 这种题目上小学就做过了，怎么现在还做错？Top
37 楼myling（不理你）回复于 2003-12-16 22:26:18 得分 0
哈哈，说明你小学没毕业Top
38 楼pazee（耙子)(今年过年不收礼，收礼只收尿不湿）回复于 2003-12-16 22:39:55 得分 0
forgetter()
说明小学教育有问题呀！教育抓得不够。Top
39 楼myling（不理你）回复于 2003-12-16 22:42:56 得分 0
强烈建议
forgetter先捐出100分再说
Top
40 楼pazee（耙子)(今年过年不收礼，收礼只收尿不湿）回复于 2003-12-16 22:44:25 得分 0
他能捐200的，100太少了。Top
41 楼forgetter（csdn第一人渣）回复于 2003-12-16 23:48:04 得分 0
妈的，拿老子开心，今天面子丢大了Top
42 楼myling（不理你）回复于 2003-12-16 23:51:16 得分 0
哈哈哈哈
今天是真爽呀
我得意的笑我得意的笑Top
43 楼forgetter（csdn第一人渣）回复于 2003-12-17 00:23:25 得分 0
AD你有种写个程序出来，从现在开始计时，看谁狠，敢不敢！Top
44 楼myling（不理你）回复于 2003-12-17 00:27:44 得分 0
有种你加我呀？哈哈哈
我得意的笑我得意的笑Top
45 楼myling（不理你）回复于 2003-12-17 00:36:40 得分 0
如果只是针对这个问题的话
Go('猛鸟','鸡');
Back('猛鸟');
Go('猛鸟','狗');
Back('猛鸟','鸡');
Go('猛鸟','米');
Back('猛鸟');
Go('猛鸟','鸡');
这样行吗？
嘿嘿Top
46 楼myling（不理你）回复于 2003-12-17 00:40:30 得分 0
伴水已经写的很好了
俺自问写不过他
嘿嘿，就不浪费时间了Top
47 楼pazee（耙子)(今年过年不收礼，收礼只收尿不湿）回复于 2003-12-17 01:01:00 得分 0
伴水用的是回溯，用别的大家写一个Top
48 楼forgetter（csdn第一人渣）回复于 2003-12-17 01:31:45 得分 30
妈的，老子被你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;
Top
49 楼pazee（耙子)(今年过年不收礼，收礼只收尿不湿）回复于 2003-12-17 01:39:22 得分 0
forgetter()
你居然能把程序写成这样！！！！！！！
我服了，有点像那个不同水平的高手写"hello world"的例子。
这程序不完整呀！
我去睡觉了，明天接着看，Top
50 楼forgetter（csdn第一人渣）回复于 2003-12-17 08:52:10 得分 0
死AD，臭AD，烂AD，让我今天迟到10分钟Top
51 楼littlevoice（这个冬天不太冷）回复于 2003-12-17 11:14:24 得分 0
我觉得绯村的思路才是最正确的，上学时图论老师就提出过用最短路径的想法来解决这个问题，无奈当时习惯copy作业，都没仔细思考
现在正在思考ing。。。。。
应该往这方向想才对Top
52 楼pazee（耙子)(今年过年不收礼，收礼只收尿不湿）回复于 2003-12-17 12:15:08 得分 0
绯村 的思路是正确的，建模比较对，不过我以前写的和伴水的一样，因为它好理解。Top
53 楼gencan（无敌）回复于 2003-12-17 14:25:25 得分 0
怎么没人用我的思路呀！我认为我的是最简单的！！！！！！！！！！！！！！！！！Top
54 楼myling（不理你）回复于 2003-12-17 14:46:00 得分 0
forgetter()
你只是迟到10分钟
我昨晚喝的滥醉，还跟你折腾到半夜
今天上午旷工半天！！
我睡到12:30
:(Top
55 楼Shiyl（云淡风清 卷舒自在）回复于 2003-12-17 15:22:30 得分 0
好强！Top
56 楼1nsc（在线网）回复于 2003-12-17 15:36:19 得分 0
在绿盟论坛上http://www.0mai.com/bbs/down_default.asp 有这问题的说明
http://www.0mai.com/bbs上有说明
我的OICQ：9199333
Top
57 楼pazee（耙子)(今年过年不收礼，收礼只收尿不湿）回复于 2003-12-17 15:46:09 得分 0
gencan(无敌)
你自己写一个完整的呀！Top
58 楼gencan（无敌）回复于 2003-12-17 17:31:20 得分 0
哈哈：
你说的是算法，为什么非要完整的。
其实搞软件重在思想，为什么非要代码不行呢？Top
59 楼gencan（无敌）回复于 2003-12-17 17:32:03 得分 0
我认为我的思路是最好的，不信你好好想想！！！！！Top
60 楼liaoqingpeng（棋快一步）回复于 2003-12-20 22:45:55 得分 0
upTop
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
