数学研发论坛

 找回密码
 欢迎注册
查看: 2973|回复: 12

[擂台] 飞机加油的最佳策略设计

[复制链接]
发表于 2009-12-19 02:42:30 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
背景描述:

数轴的$0$点是飞机场,可容纳任意多架飞机。

飞机的油箱容量是$1$,装满油可以飞行$1$个单位距离。

所有飞机的飞行速度是一样的,每个单位时间飞行$1$个单位距离。

除了飞机场,飞机不能在任何地方停留,但可以在任何地方转向。

当两架飞机位于同一地点的时候,其中一架飞机可以把一部分油加给另一架飞机。

飞机一旦把油用尽就会坠毁,除非把油用尽的时候刚好到达飞机场或者有另一架飞机为他加油。

飞机的起飞、降落、加油、转向动作都是一瞬间完成的,只有飞行是需要时间的。

任务描述:

任务$1$:远航任务
--------------------
该任务有$2$个版本。

任务$1.1$:最多使用$n$程油,令$1$架飞机飞到尽可能远的地方并坠毁。

任务$1.2$:最多出动$m$架飞机($m=1,2,3,...$),在其余的$(m-1)$架辅助飞机都不坠毁的前提下,令$1$架飞机飞到尽可能远的地方并坠毁。
--------------------

任务$2$:返航任务
--------------------
该任务也有$2$个版本。

任务$2.1$:最多使用$n$程油,令$1$架飞机飞到尽可能远的地方并安全返航。

任务$2.2$:最多出动$m$架飞机($m=1,2,3,...$),所有的飞机都不得坠毁,令$1$架飞机飞到尽可能远的地方并安全返航。
--------------------

任务$3$:环球飞行任务
--------------------
所有的飞机都不得坠毁,令$1$架飞机环球飞行$1$圈后回到出发点。
--------------------

由于微软按照任务$3$的设定出了一道面试题:

http://blog.csdn.net/miracle_ma/article/details/42109457

因此该问题被广泛传播。

但是环球飞行任务可以通过任务$1$解决,做法如下:

假设绕地球飞行一圈需要$s$程油,那么我们只需令$1$架飞机远航至$(s+1)/2$程即可。

只要反向出动相同架次的辅助飞机,使用对称的操作即可把远航至$(s+1)/2$程的那架飞机从反方向救回。

因此只需讨论任务$1$和任务$2$即可。

摆擂目的:

飞机加油问题虽然与汽车跑路问题相似,但两者的难度并不是同一个档次的,前者至今仍未得到精确解。

这类问题有清晰的背景和简单的假设,易理解,可视,可操作,具有趣味性。

希望通过摆擂攻擂的方式,收集到大量案例的精确解,找到精确解的一般规律,从而彻底解决飞机加油问题。

同时也希望这类问题最终都能做成解谜类游戏,通过破解谜题让人感受到数学的魅力。

攻擂规则:

所有看过此贴的人都可以参与。

下载这个附件,解压后就可以玩这个游戏了:

p0.zip (16.2 KB, 下载次数: 24)

评分

参与人数 1贡献 +2 收起 理由
数学星空 + 2 在娱乐中理解数学,让数学变得更有趣..

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-19 08:23:46 | 显示全部楼层
呵,KeyTo9_Fans在编程方面的确有更深的研究嘛,你这种做法值得大家学习哟,可以让更多的人参与游戏又增长了数学知识...
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-20 20:25:13 | 显示全部楼层
估计这类问题可能需要不断编程、不断修正数学模型才能逼近最优解,
有些难度,适合作为一个长期的擂台节目。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-21 08:36:44 | 显示全部楼层
细想起来
很麻烦
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-21 17:08:49 | 显示全部楼层
问题1:
考虑两驾,一驾可以在1/3处将另一驾加满,然后自己安全返回,于是
任务需要轰炸机在坐标1是满油的,此时需要另一个在坐标1将他加满
即在坐标1有两驾2/3油
这两驾是在坐标2/3处被另两驾加满的于是,需要4驾在坐标2/3处2/3油
8驾在坐标1/3处2/3油
另外,还需接回坐标1处空油的一驾,即需要坐标1处2/3油的一驾,共同返回坐标2/3,这需要4驾
然后需要接回坐标2/3处的2驾空油的,这需要另外的坐标2/3处2驾2/3油,即4驾0处满油
然后,需要接回坐标1/3处的4驾空油的,这是额外4驾
总共:8+4+4+4=20驾
乱七八糟,不知错了没
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-21 18:00:27 | 显示全部楼层
不需要所有飞机同时起飞的。可以部分飞机迟一些起飞,去接其他没有油的飞机,问题复杂在这里
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-22 01:41:19 | 显示全部楼层
5#说的是这个方案吗?

p.gif

貌似一共出动14架,每架1箱油就可以了。

为什么是20架呢?

和上述方案有什么差别?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-22 09:45:12 | 显示全部楼层
7# KeyTo9_Fans

哦,我就是想这个意思,只不过总是算错
你这个图有意思,咋画的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-22 17:29:35 | 显示全部楼层
没有在操作平台上跑一遍吗?如果跑通了就不大可能出错了。

拿gif工具一帧一帧画的。

除了第一帧,后面的直接复制粘贴,然后做点小改动。

共有116帧,做了两个小时。

不过这样做效率太低了。

所以我考虑在1楼的操作平台里添加一个功能,自动生成gif动画。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-3 11:37:48 | 显示全部楼层
哦,一开始觉得很简单,轻易得出共需8架飞机8个油的结论。后来发现不对了。
关键是飞机一经起飞,就必须在天上飞,不停耗油。需要把握好时间呢。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-3-19 16:04 , Processed in 0.059935 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表