小学的题大学的解法

本题节选自《C/C++程序员面试指南》一书

面试题7：飞机绕地球环行问题

已知每架飞机有一个油箱，飞机之间可以相互加油，一整油箱的油可以供一架飞机绕地球飞行半圈。为使至少一架飞机绕地球一圈回到飞机起飞的机场，至少需要使用几架飞机，飞行几个架次？

所有飞机从同一飞机场起飞，而且必须安全返回机场，不允许中途降落，一架飞机起飞一次算作一架次，加油时间可以忽略。

1．所涉及的知识点

· 作图法

· 计算法

2．分析问题

借助于图形解决问题的方法就是图形法。根据问题中已知的条件，采用适当的方法画出图形，有助于问题的解决。有些问题，在没画图之前，会觉得无从下手，画了图后就一目了然了。

对于本题只是用脑子去想象来解决这道题是件很复杂的事，如果借助于图形来解决就简单多了。在此假设地球的长度为1，根据题意可知一油箱的油可以让一架飞机绕地球持续飞行1/2。现假设飞机起飞地点为x，如图12.9所示。

图12.9 飞机环行地球示意图

根据条件可推知，只用一架飞机肯定是无法完成任务的。当用两架飞机时，两架飞机的油量刚好够一架飞机绕地球一圈，无论怎么补充也完成不了航行任务。所以至少有三架飞机，设为飞机A，飞机B和飞机C。整个飞行过程如下：

（1）三架飞机同时从飞机场x同向起飞。如图12.10所示。

（2）到1/8时A、B和C的可持航油量都为3/8，此时C将油量的1/8给B，另外1/8的油量给A后，A和B的剩余可持航油量1/2，C剩余1/8的可持航油量正好足够返航。A、B继续飞行，C返航，如图12.11所示。

图12.10 三架飞机同时逆时针起航图12.11 C返航

（3）到达1/4处时A和B的可持航油量都为3/8，C已返回机场。此时B将1/8的油量给A，A的可持航油量为1/2，B的可持航油量为1/4恰好可以安全返航，此时A继续绕地球飞行，B返航，如图12.12所示。

（4）当A到达1/2处时，A的可持航油量为1/4，此时A继续绕地球飞行。B已经到达机场，B加满油顺时针起飞，如图12.13所示。

图12.12 B返航图12.13 B顺时针起航

（5）A和B在3/4处相遇，此时A的可持航油量为0，B的可持航油量为1/4，B将1/8的可持航油量分给A后，A、B的油量相等，都为1/8。A和B同时逆时针飞行，C此时在机场装满油顺时针起飞。如图12.14所示。

（6）A、B和C相遇在7/8处，此时A和B的油量为0，C的油量为1/4，C将1/8的可持航油量分给A，再将1/8的可持航油量分给B后，三者的油量相同，都恰好够飞回机场。三架飞机逆时针向机场飞行，如图12.15所示。

图12.14 C顺时针起航，B逆时针返航图12.15 C逆时针返航

（7）三架飞机同时安全返回机场，飞机A成功绕地球飞行一圈。

共用了三架飞机，A起飞一次，B起飞两次，C起飞两次。所以共用了三架飞机，5个航次。

根据观察可以发现后1/2的飞行情况是前1/2的反序。所以在分析完前1/2时，就已经可以算出总共需要的飞机架次。

3．答案

共用了三架飞机，5个航次。

事实上，许多问题都要运用几种不同的方法才能解决。所谓综合法，就是综合各种方法（包括前述各种方法以外的方法）去解决某些问题。所以不要只是简单地硬套方法，应该了解各种方法的技巧，随机应变。

书名：C/C++程序员面试指南

作者：杨国祥等编著

ISBN 978-7-121-10359-9

出版日期：2010年3月出版

定价：49.00元

宣传语

从企业面试的角度来梳理C/C++程序员的技术功底

以技术经理的眼光来审视对C/C++编程知识的掌握

内容简介

C、C++语言是IT行业的主流编程语言，也是很多程序员必备的软件基本功，是软件开发行业招聘考查的重点。本书以流行的面试题讲解为主要内容，介绍了C、C++语言基本概念，包括保留字、字符串、指针和引用、结构体、库函数等各个方面的基础知识，介绍了面向对象编程基本概念，包括如何实现继承、多态和封装等。还介绍了排序算法及数据结构的实现，包括链表、堆栈、队列和树。此外，本书开始用两章篇幅详细介绍了中英文面试的注意事项、常见问题及程序员的职业规划等软件工程师的常识。最后四章详细讲解了现在流行的智力测试题。

本书的特点是在详细介绍C、C++面试中常见技术问题的同时，还详细讲解了智力测试的基本方法及数学能力、推理能力和反应能力的常见测试题。本书适合正在找工作的应届毕业生，也适合想要换工作而基础知识不扎实或不熟悉智力测试的老程序员。

购买地址：当当网卓越网中国互动出版网

同类书推荐：.NET程序员面试指南(含光盘1张) Java程序员面试指南

本书详细信息：http://www.broadview.com.cn/10359

更多图书信息：www.broadview.com.cn

想即时获取更多图书及活动资讯，赶快加入博文视点读者俱乐部吧！