| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 765 人关注过本帖
标题:[讨论]据说是微软的一道面试题:飞机加油
只看楼主 加入收藏
dragonfly
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:1024
专家分:0
注 册:2006-3-20
收藏
 问题点数:0 回复次数:7 
[讨论]据说是微软的一道面试题:飞机加油
已知:
每个飞机只有一个油箱,
飞机之间可以相互加油(注意是相互,没有加油机)
一箱油可供一架飞机绕地球飞半圈,

问题:
为使至少一架飞机绕地球一圈回到起飞时的飞机场,至少需要出动几架飞机?(所有飞机从同一机场起飞,而且必须安全返回机场,不允许中途降落,中间没有飞机场)
搜索更多相关主题的帖子: 飞机场 机场 地球 
2006-08-04 18:18
无理取闹
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:53
帖 子:4264
专家分:0
注 册:2006-7-26
收藏
得分:0 
我算4架
飞到4分之1,其中两架把油给另两架,这样另两架油又满了
飞到2分之1,其中一架把油给另一架,那架油满了,可以飞全球

win32汇编
病毒 加密
目前兴趣所在
2006-08-04 18:42
无理取闹
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:53
帖 子:4264
专家分:0
注 册:2006-7-26
收藏
得分:0 
对不?

win32汇编
病毒 加密
目前兴趣所在
2006-08-04 18:42
chenjin145
Rank: 1
等 级:禁止访问
帖 子:3922
专家分:0
注 册:2006-7-12
收藏
得分:0 
以下是引用韩峰在2006-8-4 18:42:25的发言:
我算4架
飞到4分之1,其中两架把油给另两架,这样另两架油又满了
飞到2分之1,其中一架把油给另一架,那架油满了,可以飞全球

錯得離譜


[url=javascript:alert(1);] [div]fdgfdgfdg\" on\"[/div] [/url]
2006-08-05 11:38
chenjin145
Rank: 1
等 级:禁止访问
帖 子:3922
专家分:0
注 册:2006-7-12
收藏
得分:2 

我也算出4架
設路程為1 每架飛機0.5 完成任務的飛機為A
倆架跟A一起到0.25
倆架分別給A 0.125的油 A又有0.5 倆架都只余下0.125 返回
此時一架飛到0.125接返回的倆架 分別給倆架0.125 自己也只剩下0.125 然後三架一起返回

此時A有0.5的油可以飛到0.75處 正好油用完

倆架飛機從反方向飛0.25的距離到0.75處去接A(地球是圓的)
同上加油

則A安全返回機場


[url=javascript:alert(1);] [div]fdgfdgfdg\" on\"[/div] [/url]
2006-08-05 12:11
chenjin145
Rank: 1
等 级:禁止访问
帖 子:3922
专家分:0
注 册:2006-7-12
收藏
得分:0 
樓主有沒正確答案
正確否

[url=javascript:alert(1);] [div]fdgfdgfdg\" on\"[/div] [/url]
2006-08-05 12:14
dragonfly
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:1024
专家分:0
注 册:2006-3-20
收藏
得分:0 
不好意思,我只有题没有答案
但我觉着chenjin145的分析应该是对的,好像应该是5架吧,问的是一共出动多少架呵呵

2006-08-05 23:22
xiaohuli120
Rank: 1
等 级:新手上路
帖 子:106
专家分:0
注 册:2006-4-10
收藏
得分:0 

从同一地点出发的相同型号的飞机,可是每架飞机装满油只能饶地球非半周,飞机之间可以加油,加完油飞机必须回到起点。问至少要多少架次,才能满足有一架绕地球一周。

答案:5架次。一般的解法可以分如下两个部分:

(1) 直线飞行

一架飞机载满油飞行距离为1,n架飞机最远能飞多远?在不是兜圈没有迎头接应的情况,这问题就是n架飞机能飞多远?存在的极值问题是不要重复飞行,比如两架飞机同时给一架飞机加油且同时飞回来可认为是重复,或者换句话说,离出发点越远,在飞的飞机就越少,这个极值条件是显然的,因为n架飞机带的油是一定的,如重复,则浪费的油就越多。比如最后肯定是只有一架飞机全程飞行,注意“全程”两个字,也就是不要重复的极值条件。如果是两架飞机的话,肯定是一架给另一架加满油,并使剩下的油刚好能回去,就说第二架飞机带的油耗在3倍于从出发到加油的路程上,有三架飞机第三架带的油耗在5倍于从出发到其加油的路程上,所以n架飞机最远能飞行的距离为s=1+1/3+…+1/(2n+1)这个级数是发散的,所以理论上只要飞机足够多最终可以使一架飞机飞到无穷远,当然实际上不可能一架飞机在飞行1/(2n+1)时间内同时给n-1个飞机加油。

(2) 可以迎头接应加油

一架飞机载满油飞行距离为1/2,最少几架飞机能飞行距离1?也是根据不要重复飞行的极值条件,得出最远处肯定是只有一架飞机飞行,这样得出由1/2处对称两边1/4肯定是一架飞机飞行,用上面的公式即可知道一边至少需要两架飞机支持,(1/3+1/5)/2>1/4(左边除以2是一架飞机飞行距离1/2),但是有一点点剩余,所以想象为一个滑轮(中间一个飞机是个绳子,两边两架飞机是个棒)的话,可以滑动一点距离,就说加油地点可以在一定距离内变动(很容易算出来每架飞机地点和加油数量,等等)

baidu无敌!


2006-08-06 07:58
快速回复:[讨论]据说是微软的一道面试题:飞机加油
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.027136 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved