Java开发网 - 一道面试算法题，大家有兴趣研究一下……

Topic: 一道面试算法题，大家有兴趣研究一下……

1.一道面试算法题，大家有兴趣研究一下……

Posted by: jasonhero
Posted on: 2006-05-10 10:14

一些飞机从基地起飞，要让其中有一架飞机绕地球飞一圈后回到基地，但一架飞机上满油后只能绕地球半圈，不过飞机之间可以互相传油，飞机不能坠毁，没油的飞机只能返回基地，飞机在基地可以加油，
问：要让一架飞机绕地球飞一圈至少需要多少架飞机？

2.Re:一道面试算法题，大家有兴趣研究一下…… [Re: jasonhero]	Copy to clipboard
Posted by: Skybus Posted on: 2006-05-10 10:21 微软的经典题目，下面链接中有答案： http://quitgame.cnblogs.com/archive/2005/11/06/270178.html

3.Re:一道面试算法题，大家有兴趣研究一下…… [Re: jasonhero]	Copy to clipboard
Posted by: BIGBUG Posted on: 2006-05-11 17:42 5

4.Re:一道面试算法题，大家有兴趣研究一下…… [Re: jasonhero]	Copy to clipboard
Posted by: fosterdaredream Posted on: 2006-05-14 15:04 5架

5.Re:一道面试算法题，大家有兴趣研究一下…… [Re: jasonhero]	Copy to clipboard
Posted by: jasonhero Posted on: 2006-05-14 17:46 谁能把解决过程详细的写出来啊？

6.Re:一道面试算法题，大家有兴趣研究一下…… [Re: jasonhero]	Copy to clipboard
Posted by: zqswork Posted on: 2006-05-28 11:28 6

7.Re:一道面试算法题，大家有兴趣研究一下…… [Re: jasonhero]	Copy to clipboard
Posted by: suntao19830709 Posted on: 2006-07-27 10:32 传油的时间是否忽略不计

8.Re:一道面试算法题，大家有兴趣研究一下…… [Re: jasonhero]	Copy to clipboard
Posted by: InTheTerRan Posted on: 2006-07-27 13:23 2架够了吧？

9.Re:一道面试算法题，大家有兴趣研究一下…… [Re: jasonhero]	Copy to clipboard
Posted by: zhb Posted on: 2006-08-06 14:47 飞不到的吧.....感觉最多那一架飞到接近3/4 挂掉...........

10.Re:一道面试算法题，大家有兴趣研究一下…… [Re: jasonhero]

Copy to clipboard

Posted by: guru
Posted on: 2006-08-16 01:20

包括绕地球飞一圈那架一共6架即可。

方案如下：

1. 两架飞机伴随环球的那架飞机一起起飞，飞至1/4圈处各为环球飞机加1/8圈的油，然后返航。此时，环球的飞机加满了飞行1/2圈所需的油，返航的飞机各剩1/8圈的油。

2. 两架飞机返航时再起飞一架飞机并在1/8圈处为返航的两架飞机各加1/8的油。这样这三架飞机都有1/8圈的油，刚好可以返回机场。

3. 环球的飞机独立飞行，并在其飞至1/2圈的时候安排一架飞机反方向起飞，两架飞机将在3/4圈处汇合，反方向起飞的飞机为环球飞行的飞机加1/8圈的油，这样飞行中的两架飞机各有1/8圈的油飞至7/8圈处。

4. 在上面两架飞机加油的时候再安排反方向起飞一架飞机在7/8圈处接应这两架飞机并为它们各加1/8圈的油，这样飞行的三架飞机均有1/8圈的油完成整个航行。

11.Re:一道面试算法题，大家有兴趣研究一下…… [Re: jasonhero]	Copy to clipboard
Posted by: floater Posted on: 2006-08-16 03:37 3

12.Re:一道面试算法题，大家有兴趣研究一下…… [Re: jasonhero]	Copy to clipboard
Posted by: nothing Posted on: 2006-08-16 12:40 出题不严谨，一架就可以了。落到地面上加油就行了。 :-<

13.Re:一道面试算法题，大家有兴趣研究一下…… [Re: nothing]

Copy to clipboard

Posted by: zcjl
Posted on: 2006-08-16 14:33

3架飞机，分别命名为A、B、C
其中，A主要负责环球飞行，B、C负责空中传油
假设：环球飞行旅程总长下面简称“航程”，飞机油箱容量为4个单位

过程如下：
1、ABC从基地满油起飞
2、航程1/8处，ABC各耗油1个单位，C分别传油1个单位给AB然后返回，AB在满油状态下继续前进
3、航程2/8处，C抵达基地待命，AB各耗油1个单位，B传油1个单位给A然后返回，A在满油状态下继续前进
4、航程4/8处，B抵达基地，满油反方向起飞，A耗油2个单位，还剩2个单位油，继续前进
5、航程6/8处，AB汇合，A油耗尽，B耗油2个单位，B传油1个单位给A然后转向与A一同朝基地飞行，C从基地满油迎着AB起飞
6、航程7/8处，AB与C汇合，AB油耗尽，C耗油1个单位，C分别传油1个单位给AB，然后ABC一同朝基地飞行
7、ABC抵达基地，A环球一周

上面的过程基本能满足要求，当然，前提是飞机之间传油的时间消耗忽略不计，飞机油耗尽时不会立即坠毁等等

14.Re:一道面试算法题，大家有兴趣研究一下…… [Re: jasonhero]	Copy to clipboard
Posted by: floater Posted on: 2006-08-16 21:23 very precise