谜题求解（关于算法）

只看该作者 · 2009-7-16 19:33

有4个人打算过桥，他们都在桥的某一端。我们有17分钟让他们全部到达桥的另一头。时间是晚上，他们只有一只手电筒。最多只能有两人同时过桥，并且必须携带手电筒。必须步行将手电筒带来带去，即扔来扔去是不行的。每个人走路的速度是不同的：甲过桥要1分钟，乙要2分钟，丙要5分钟，丁要10分钟。两个人一起走的速度等于其中较慢的人的速度。例如，如果让甲和丁一起过桥，当他们到达桥的另一端的时候，已经耗尽10分钟了。如果再由丁带回手电筒，一共20分钟就过去了，这样，任务就以失败告终。试问，何种方案可以完成任务？

1万 · 2009-7-17 08:21

最省时间的是由甲来回带手电筒，并且需两人同时过三回桥，这样最少需要19分钟，不考虑来回送手电筒就得17分钟，哪个计算机也算不出来，出题人没用脑子
其实这个题可以先这样考虑：
无论怎样，至少需要甲乙丙丁单独过桥的时间相加，这样就得18分钟了

只看该作者 · 2009-7-17 08:36

1万 · 2009-7-17 08:40

2万 · 2009-7-17 08:42

很简单，甲分别背着后面的三个人走就是了。。。

只看该作者 · 2009-7-17 08:46

因为自己想不通所以才在这边问，如果没有意义人家为什么要出这样的题目？
虽然可能没解，但如果是像二楼说的那样，那不是人人都想得到，就真的没有讨论的意义了。如果说是三楼那位说的答案在那个“某”字上，是否有钻题目的空子的嫌疑啊

楼上的更强悍

只看该作者 · 2009-7-17 11:33

桥左                                    桥右                     时间

甲(1)，乙(2)，丙(5)，丁(10)             --                         0

丙(5)，丁(10)                           甲(1)，乙(2)               2

甲(1)，丙(5)，丁(10)                    乙(2)                      3

甲(1)                                   乙(2),丙(5)，丁(10)        13

甲(1),乙(2)                             丙(5)，丁(10)              15

--                                      甲(1),乙(2),丙(5)，丁(10)  17

====
第一步后甲返回带回电筒，第三步后乙返回带回电筒。
总共 17 分钟。

只看该作者 · 2009-7-17 11:47

结构，函数，数组，递归，做好了，C基本过关了。

2万 · 2009-7-17 12:38

2楼是不动脑筋的典型（自以为动过了，然后停止思维）

1万 · 2009-7-17 12:56

a1,b2,c5,d10  ----- 开始,          sum = 0!
      c5,d10 ------> a1,b2,        sum = 2;
   a1,c5,d10 <------ b2,           sum = 3;
          a1 ------> b2,c5,d10,    sum = 13;
      a1 ,b2 ------> c5,d10,       sum = 15;
             ------> a1,b2,c5,d10, sum = 17;

只看该作者 · 2009-7-17 19:20

没想到答案其实这么简单，之前自己想的时候思维定势了，一直认为由甲带回手电筒是最节省时间的，只要一分钟，忘了说丙和丁一起过桥会比丙丁分开节省了5分钟，思维还是最重要的啊。

1万 · 2009-7-17 20:33

只看该作者 · 2009-7-19 01:05

但是要有限制条件，否则会进入死循环，比如甲过去，甲又回来了，甲又过去了，甲又回来了。

比较明显的限制条件就是，必须两个人过去，一个人回来。直到全过完。

递归调用看起来比较合适。

谜题求解（关于算法）

相关下载

相关帖子

这个题无解

他们都在桥的“某”一端,答案在这个“某”上？

这样出题有意义吗？

~~

这是我在一本算法书上看到的

很简单呀

题目的关键为在答案，而是在意编程方法。

关键是思想（智慧），能想到丙和丁一起过桥即为胜利

简单:

受启发了

gusto不简单呀

此题解法当然是穷举或递归

核心会员奖章

坚毅之洋流

十世金身

技术奇才奖章

终身成就奖章

技术领袖奖章

七世轮回

无冕之王奖章

沉静之湖泊