请选择 进入手机版 | 继续访问电脑版

五彩数学

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 309|回复: 5

过桥问题

[复制链接]

34

主题

200

帖子

680

积分

版主

Rank: 7Rank: 7Rank: 7

积分
680
发表于 2016-5-4 12:38:42 | 显示全部楼层 |阅读模式
在漆黑的夜里,四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,四个人一共只带了一只手电筒,而桥窄得只够让两个人同时通过。如果各自单独过桥的话,四人所需要的时间分别是1258分钟;而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是,你如何设计一个方案,让用的时间最少。

设这四个人叫做A,B,C,D,他们所需要的时间分别是1,2,5,8分钟。

第一步:A和B过桥,花费2分钟。

第二步:A回来,花费1分钟。

第三步:C和D过桥,花费8分钟。

第四步:B回来,花费2分钟。

第五步:A和B过桥,花费2分钟。

这样只要花费2+1+8+2+2=15分钟,下面再来考虑如何用程序来解决这类问题,在写程序之前还有个细节要考虑下,比如A,B,C,D四个人所需要的时间分别是1,8,9,10分钟。

方案一

第一步:A和B过桥,花费8分钟。

第二步:A回来,花费1分钟。

第三步:C和D过桥,花费10分钟。

第四步:B回来,花费8分钟。

第五步:A和B过桥,花费8分钟。

一共要8+1+10+8+8=35分钟。

方案二

第一步:A和B过桥,花费8分钟。

第二步:A回来,花费1分钟。

第三步:A和C过桥,花费9分钟。

第四步:A回来,花费1分钟。

第五步:A和D过桥,花费10分钟。

一共要8+1+9+1+10=29分钟。

因此可以得出更加细化的解决方案——要么是最快者将最慢的2个送过桥,要么是最快的2个将最慢的2个送过桥。即将过桥的人按其过桥的时间从小到大排列,设为A,B,…… Y,Z。其中A和B是最快的二个,Y和Z是最慢的二个。那么就有二种方案:

方案一 最快者将最慢的2个送过桥

第一步:A和Z过桥,花费Z分钟。

第二步:A回来,花费A分钟。

第三步:A和Y过桥,花费Y分钟。

第四步:A回来,花费A分钟。

这四步后总人数就减小2个,花费时间为A + A + Y + Z分钟。

方案二 最快的2个将最慢的2个送过桥

第一步:A和B过桥,花费B分钟。

第二步:A回来,花费A分钟。

第三步:Y和Z过桥,花费Z分钟。

第四步:B回来,花费B分钟。

这四步后总人数同样减小2个,花费时间为A + B + B + Z分钟。

这样,每次比较一下这二种方案就能将总人数减小2。然后我们再考虑一些边界情况:

有三个人过桥设为A,B,C(已经排好序,下同)。应该花费A + B + C分钟。

有二个人过桥设为A,B。那么肯定是花费B分钟。

有一个人过桥设为A。肯定花费A分钟。


回复

使用道具 举报

13

主题

225

帖子

671

积分

智慧侠客

Rank: 4

积分
671
发表于 2016-5-8 18:00:56 | 显示全部楼层
哦!我明白了!
回复 支持 反对

使用道具 举报

5

主题

99

帖子

276

积分

英雄少年

Rank: 3Rank: 3

积分
276
发表于 2016-7-11 14:15:19 | 显示全部楼层
我明白了。
回复

使用道具 举报

2

主题

83

帖子

229

积分

英雄少年

Rank: 3Rank: 3

积分
229
发表于 2016-8-9 09:16:42 | 显示全部楼层
我明白了。
回复

使用道具 举报

12

主题

133

帖子

391

积分

版主

Rank: 7Rank: 7Rank: 7

积分
391
发表于 2016-8-24 12:45:08 | 显示全部楼层
我知道了。
回复

使用道具 举报

2

主题

83

帖子

229

积分

英雄少年

Rank: 3Rank: 3

积分
229
发表于 2016-9-6 19:19:19 | 显示全部楼层
我明白了。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表