oil.cpp

微软加油题的几种算法 原题 . 一道关于飞机加油的问题

// oil.cpp : Defines the entry point for the console application.
//
/*
问题介绍：
每个飞机只有一个油箱，飞机之间可以相互加油（注意是相互，没有加油机），一箱油可供一架飞机绕地球飞半圈。
问：为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？  
（所有飞机从同一机场起飞，而且必须都安全返回机场，不允许中途降落，中间没有飞机场）   

解题思路：
递归方案。设最终有一架能飞完全一圈，而一架最多装油半圈，故它需
要补充半圈油。羊毛出在羊身上，我们来找那头羊好了，嘻嘻。这半圈油当然
出在别的飞机身上，而别的飞机又抽别别的飞机。。。递归终止条件：当某一架飞
机被抽完其它飞机“仅仅所需的油”后，它还能安全飞回基地。递归结束。
具体细节:
一架飞机在1/4全程点上如能满油(即得到1/4的补充量)，它就能飞回。因为3/4点同样可补到1/4的量（注意地球是圆的,可两边补）。 那么1/4全程点时它可抽其它飞机的,然后它可飞回了，但然后其它飞机飞不回怎么办呢？再用解决刚才那"飞全程飞机的方法"来解决其它飞机，递归下去...直到有飞机被人抽后还能够油飞回基地。(注意每次补充量只需它总的补充量的一半就行哦) 
*/

#include "stdafx.h"
#include "oil.h"

void fly(double journey, double oil)
{
    if ( journey-oil>0 )
    {
        count++;
        fly(journey-oil, Max-0.5*(journey-oil));
    }
}

int main()
{
    printf("从同一地点出发的相同型号的飞机，可是每架飞机装满油\n");
    printf("只能绕地球飞半周，飞机之间可以加油，加完油的飞机必\n");
    printf("须回到起点。问至少要多少架次，才能满足有一架绕地球一周。\n");
    count++;
    fly(2,1);
    printf("答案：飞机共 %d架\n", count);
	return 0;
}