技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 12个经典的行程问题

12个经典的行程问题

浏览:2309次  出处信息

     无论是小学奥数,还是公务员考试,还是公司的笔试面试题,似乎都少不了行程问题――题目门槛低,人人都能看懂;但思路奇巧,的确会难住不少人。平时看书上网与人聊天和最近与小学奥数打交道的过程中,我收集到很多简单有趣而又颇具启发性的行程问题,在这里整理成一篇文章,和大家一同分享。这些题目都已经非常经典了,绝大多数可能大家都见过;希望这里能有至少一个你没见过的题目,也欢迎大家来信提供更多类似的问题。

     让我们先从一些最经典最经典的问题说起吧。选中空白部分显示答案。

     甲、乙两人分别从相距 100 米的 A 、B 两地出发,相向而行,其中甲的速度是 2 米每秒,乙的速度是 3 米每秒。一只狗从 A 地出发,先以 6 米每秒的速度奔向乙,碰到乙后再掉头冲向甲,碰到甲之后再跑向乙,如此反复,直到甲、乙两人相遇。问在此过程中狗一共跑了多少米?

    这可以说是最经典的行程问题了。不用分析小狗具体跑过哪些路程,只需要注意到甲、乙两人从出发到相遇需要 20 秒,在这 20 秒的时间里小狗一直在跑,因此它跑过的路程就是 120 米。

         说到这个经典问题,故事可就多了。下面引用某个经典的数学家八卦帖子: John von Neumann 曾被问起一个中国小学生都很熟的问题:两个人相向而行,中间一只狗跑来跑去,问两个人相遇后狗走了多少路。诀窍无非是先求出相遇的时间再乘以狗的速度。 Neumann 当然瞬间给出了答案。提问的人失望地说你以前一定听说过这个诀窍吧。 Neumann 惊讶道:“什么诀窍?我就是把狗每次跑的都算出来,然后计算无穷级数・・・・・・”

     某人上午八点从山脚出发,沿山路步行上山,晚上八点到达山顶。不过,他并不是匀速前进的,有时慢,有时快,有时甚至会停下来。第二天,他早晨八点从山顶出发,沿着原路下山,途中也是有时快有时慢,最终在晚上八点到达山脚。试着说明:此人一定在这两天的某个相同的时刻经过了山路上的同一个点。

    这个题目也是经典中的经典了。把这个人两天的行程重叠到一天去,换句话说想像有一个人从山脚走到了山顶,同一天还有另一个人从山顶走到了山脚。这两个人一定会在途中的某个地点相遇。这就说明了,这个人在两天的同一时刻经过了这里。

    

     甲从 A 地前往 B 地,乙从 B 地前往 A 地,两人同时出发,各自匀速地前进,每个人到达目的地后都立即以原速度返回。两人首次在距离 A 地 700 米处相遇,后来又在距离 B 地 400 米处相遇。求 A 、 B 两地间的距离。

    答案: 1700 米。第一次相遇时,甲、乙共同走完一个 AB 的距离;第二次相遇时,甲、乙共同走完三个 AB 的距离。可见,从第一次相遇到第二次相遇的过程花了两个从出发到第一次相遇这么多的时间。既然第一次相遇时甲走了 700 米,说明后来甲又走了 1400 米,因此甲一共走了 2100 米。从中减去 400 米,正好就是 A 、 B 之间的距离了。

     甲、乙、丙三人百米赛跑,每次都是甲胜乙 10 米,乙胜丙 10 米。则甲胜丙多少米?

    答案是 19 米。“乙胜丙 10 米”的意思就是,等乙到了终点处时,丙只到了 90 米处。“甲胜乙 10 米”的意思就是,甲到了终点处时,乙只到了 90 米处,而此时丙应该还在 81 米处。所以甲胜了丙 19 米。

     哥哥弟弟百米赛跑,哥哥赢了弟弟 1 米。第二次,哥哥在起跑线处退后 1 米与弟弟比赛,那么谁会获胜?

    答案是,哥哥还是获胜了。哥哥跑 100 米需要的时间等于弟弟跑 99 米需要的时间。第二次,哥哥在 -1 米处起跑,弟弟在 0 米处起跑,两人将在第 99 米处追平。在剩下的 1 米里,哥哥超过了弟弟并获得胜利。

     如果你上山的速度是 2 米每秒,下山的速度是 6 米每秒(假设上山和下山走的是同一条山路)。那么,你全程的平均速度是多少?

    这是小学行程问题中最容易错的题之一,是小孩子们死活也搞不明白的问题。答案不是 4 米每秒,而是 3 米每秒。不妨假设全程是 S 米,那么上山的时间就是 S/2 ,下山的时间就是 S/6 ,往返的总路程为 2S ,往返的总时间为 S/2 + S/6 ,因而全程的平均速度为 2S/(S/2 + S/6) = 3 。

         其实,我们很容易看出,如果前一半路程的速度为 a ,后一半路程的速度为 b ,那么总的平均速度应该小于 (a + b) / 2 。这是因为,你会把更多的时间花在速度慢的那一半路程上,从而把平均速度拖慢了。事实上,总的平均速度应该是 a 和 b 的调和平均数,即 2 / (1/a + 1/b) ,很容易证明调和平均数总是小于等于算术平均数的。

     接下来的两个问题与流水行船有关。假设顺水时实际船速等于静水中的船速加上水流速度,逆水时实际船速等于静水中的船速减去水流速度。

     船在静水中往返 A 、 B 两地和在流水中往返 A 、 B 两地相比,哪种情况下更快?

    这是一个经典问题了。答案是,船在静水中更快一些。这个问题和前一个问题本质上完全一样。注意船在顺水中的实际速度与在逆水中的实际速度的平均值就是它的静水速度,但由前一个问题的结论,实际的总平均速度会小于这个平均值。因此,船在流水中往返需要的总时间更久。

         考虑一种极端情况可以让问题的答案变得异常显然,颇有一种荒谬的喜剧效果。假设船刚开始在上游。如果水速等于船速的话,它将以原速度的两倍飞速到达折返点。但它永远也回不来了・・・・・・

     船在流水中逆水前进,途中一个救生圈不小心掉入水中,一小时后船员才发现并调头追赶。则追上救生圈所需的时间会大于一个小时,还是小于一个小时,还是等于一个小时?

    这也是一个经典问题了。我曾在初中物理竞赛中见过这个问题,也在《编程之美》上见到过完全相同的问题。答案是等于一个小时。原因很简单:船和救生圈都受到了水流速度的影响,我们就可以直接抛开流水的影响不看了。换句话说,我们若以流水为参照系,一切就都如同没有流水了。我们直接可以想像船在静水当中丢掉了一个救生圈并继续前行一个小时,回去捡救生圈当然也需要一个小时。

         每当有人还是没想通时,我很愿意举这么一个例子。假如有一列匀速疾驰的火车,你在火车车厢里,从车头往车尾方向步行。途中你掉了一个钱包,但继续往前走了一分钟后才发现。显然,你回去捡钱包需要的时间也是一分钟。但是,钱包不是正被火车载着自动地往远方走吗?其实,既然你们都在火车上,自然就可以无视火车了。前面的救生圈问题也是一样的道理。

     下面这个问题也很类似:假设人在传送带上的实际行走速度等于人在平地上的行走速度加上一个传送带的速度。

     你需要从机场的一号航站楼走到二号航站楼。路途分为两段,一段是平地,一段是自动传送带。假设你的步行速度是一定的,因而在传送带上步行的实际速度就是你在平地上的速度加上传送带的速度。如果在整个过程中,你必须花两秒钟的时间停下来做一件事情(比如蹲下来系鞋带),那么为了更快到达目的地,你应该把这两秒钟的时间花在哪里更好?

    这个漂亮的问题出自 Terence Tao 的 Blog (http://terrytao.wordpress.com/2008/12/09/an-airport-inspired-puzzle)。很多人可能会认为,两种方案是一样的吧?然而,真正的答案却是,把这两秒花在传送带上会更快一些。这是因为,传送带能给你提供一些额外的速度,因而你会希望在传送带上停留更久的时间,更充分地利用传送带的好处。因此,如果你必须停下来一会儿的话,你应该在传送带上多停一会儿。

     假设你站在甲、乙两地之间的某个位置,想乘坐出租车到乙地去。你看见一辆空车远远地从甲地驶来,而此时整条路上并没有别人与你争抢空车。我们假定车的行驶速度和人的步行速度都是固定不变的,并且车速大于人速。为了更快地到达目的地,你应该迎着车走过去,还是顺着车的方向往前走一点?

    这是我在打车时想到的一个问题。我喜欢在各种人多的场合下提出这个问题,此时大家的观点往往会立即分为鲜明的两派,并且各有各的道理。有人说,由于车速大于人速,我应该尽可能早地上车,充分利用汽车的速度优势,因此应该迎着空车走上去,提前与车相遇嘛。另一派人则说,为了尽早到达目的地,我应该充分利用时间,马不停蹄地赶往目的地。因此,我应该自己先朝目的地走一段路,再让出租车载他走完剩下的路程。

         其实答案出人意料的简单,两种方案花费的时间显然是一样的。只要站在出租车的角度上想一想,问题就变得很显然了:不管人在哪儿上车,出租车反正都要驶完甲地到乙地的全部路程,因此此人到达乙地的时间总等于出租车驶完全程的时间,加上途中接人上车可能耽误的时间。从省事儿的角度来讲,站在原地不动是最好的方案!

         我曾经把这个有趣的问题搬上了《新知客》杂志 2010 年第 9 期的趣题专栏(http://www.matrix67.com/blog/archives/3677)。不少人都找到了这个题的一个 bug :在某些极端情况下,顺着车的方向往前走可能会更好一些,因为你或许会直接走到终点,而此时出租车根本还没追上你!

     某工厂每天早晨都派小车按时接总工程师上班。有一天,总工程师为了早些到工厂,比平日提前一小时出发步行去工厂。走了一段时间后,遇到来接他的小车才上车继续前进。进入工厂大门后,他发现只比平时早到 10 分钟. 总工程师在路上步行了多长时间才遇到来接他的汽车?设人和汽车都做匀速直线运动。

    据说,这是一道初中物理竞赛题(初中物理有“运动”一章)。答案是 55 分钟。首先,让我们站在车的角度去想(正如前一题那样)。车从工厂出发,到半途中就遇上了总工程师并掉头往回走,结果只比原来早到 10 分钟。这说明,它比原来少走了 10 分钟的车程,这也就是从相遇点到总工程师家再到相遇点的路程。这就说明,从相遇点到总工程师家需要 5 分钟车程。

         现在,让我们把视角重新放回总工程师那里。让我们假设总工程师遇上了来接他的车并坐上去之后,并没有下令汽车立即掉头,而是让车像平日那样继续开到他家再返回工厂,那么他到工厂的时间应该和原来一样。这说明,他提前出发的那一个小时完全浪费了。这一个小时浪费在哪儿了呢?浪费在了他步行到相遇点的过程,以及乘车又回到家的过程。既然乘车又回到家需要 5 分钟,因此步行的时间就是 55 分钟了。

     有一位隐居在深山老林的哲学家。一天,他忘记给家里唯一的时钟上发条了。由于他家里没有电话、电视、网络、收音机等任何能获知时间的设备,因此他彻底不知道现在的时间是多少了。于是,他徒步来到了他朋友家里坐了一会儿,然后又徒步回到自己家中。此时,他便知道了应该怎样重新设定自己的时钟。他是怎么做的?

         很多人的第一想法或许是观察日出日落。在此,我们也假设通过太阳位置判断时间是不可靠的。

    传统意义上说,这个问题不算行程问题。不过,在写这篇文章时,这个问题立即跳入我的脑海,我也就把它放进来了。

         答案:别忘了,他家里的时钟并不是不走了,只是不准了而已。因此,他可以借助自己家里的时钟,判断他此次出行一共花了多久。假设往返所花时间一样,再结合在朋友那儿看到的正确时间,他便能算出应该怎样调整自己的时钟了。

     还有几个不太相关的经典问题这里没有提到,不过你或许会感兴趣:

     汽车穿越沙漠问题:http://en.wikipedia.org/wiki/Jeep_problem

QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1