飞机加油问题

今天我要介绍的也是一个经典问题,飞机加油问题。这个问题是这样的,每架飞机如果满油可以绕着地球飞半圈,飞机和飞机之间可以相互加油,现在问,如果要使一架飞机能够绕着地球飞一圈,那么最少一共需要多少架飞机?

假设每架飞机都必须从同一机场起飞,并且要返回到起飞的机场。

这个问题的难点在于看似不可能。什么意思呢,如果我们把一圈记为0到1,那么因为满油只能飞半圈,就是说,如果一架飞机要安全返航就只能从0飞到1/4,然后从1/4飞回0,这样已经有半圈行程了,但是题目要求有一架飞机要飞一圈,那么它至少要经过1/4到3/4这个阶段。但是按照我们刚才分析的,如果一台机负责加油的,那么它最多只能到1/4(如果是反方向也只能到3/4点),但是如果到了1/4点,加油机就没有多余的油加给那要飞一圈的机,这就是所谓的不可能。

其实问题还是有解的,细心的读者可能就会发现其中的奥妙。虽然一台加油机只能飞到1/4点,但是如果两台加油机,其中一台不到1/4就返航,那它不用消耗所有的油,它可以把多余的油给继续飞的加油机,那么那台加油机到1/4处就有剩余的油加给要飞一圈的机。

问题的解决方法正是这样,我们把飞机编号,1号机是要完成使命的飞机,其余是加油机。首先,1、2、3号机同时起飞,飞到1/8点,3号机已经消耗了1/4油。3号机把1/4油给1号机,把1/4油给2号机,现在1、2号机满油,3号机剩下1/4油,3号机返航。1、2号飞到1/4处,2号机消耗了1/4油,2号机把1/4油给1号机,剩下1/2油,返航。1号机满油。1号机继续飞到3/4处,剩下的油为0。然后在1号机到3/4处之前,反方向也类似,派出4、5、6号机,4、5号机到3/4时各有3/4油,4、5号机都把1/4油给1号机,那么1、4、5号机都有1/2油,全部安全飞到机场。

Aircraft Fueling

问题就这样解决了,不过还可以更加复杂,比如如果满油不是飞半圈,而是小于半圈,那么能够完成任务吗,呵呵,有机会下次继续讨论。

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s