穿越沙漠问题求解


问题描述

一辆吉普车来到1000km宽的沙漠边沿。吉普车的耗油量为1L/km,最大装油量为500L。显然,吉普车必须用自身油箱中的油在沙漠中设几个临时加油点,否则是通不过沙漠的。假设在沙漠边沿有充足的汽油可供使用,那么吉普车应在哪些地方、建多大的临的加油点,才能以最少的油耗穿过这块沙漠?给出每个加油点的位置及该加油点的存油量。

问题分析

  1. 吉普车最大装油量为500L,显然一次不够穿过沙漠
  2. 正推基本不可能,我们可以尝试倒退法:最后一个加油站我们记为1号加油站,要使耗油量最小,那么吉普车到这个加油站时刚好耗完油,在这里加满油后直接到达终点,且到达终点刚好耗尽油,即1号加油站有500L油
  3. 要使1号加油站有500L油,就要从2号往1号送油。一次显然不能使1号500L(吉普车最大才能装500L,路上还要消耗一部分),所以要在每两个加油站之间来回跑,且至少跑三次(2->1, 1->2, 2->1)
  4. 要使耗油量最小,那么就要使每次从一个加油站出发时,正好加满油;每次回到这个加油站时,正好耗尽油。因此可以推出,每个加油站的存油量应为500的整数倍(500,1000,1500,…)
  5. 2号加油站到1号加油站,设距离为dis,那么至少走三个dis,且要保证耗油最少,来回只能用500L,并且保证最终1号有500L,可以得出dis=500/3
  6. 同理,3号到2号,要保证2号有1000L,那么dis=500/5
  7. 推理可知,$dis=500/(2\times n-1)$
  8. 不断迭代,可以求出各个加油站距离终点的距离以及存油量。最后一个(正推的第一个)可能在起点之前。

代码

#include <stdio.h>

void output(int n, float dis, int oil)
{
    printf("%d, %.2f, %d\n", n, dis, oil);
}

void cross(float distance)
{
    float dis = 500;
    int oil = 500, n = 1;
    while (dis < distance)
    {
        output(n, dis, oil);
        n += 1;
        oil = 500 * n;
        dis += 500.0 / (2 * n - 1);
    }
    dis = distance - (dis - 500.0 / (2 * n - 1));
    oil = oil - 500 + dis * (2 * n - 1);
    output(n, dis, oil);
}

int main()
{
    float distance;
    printf("Input distance: ");
    scanf("%f", &distance);
    cross(distance);

    return 0;
}

文章作者: 恰醋
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 恰醋 !
评论
  目录