穿越沙漠问题---递推法

一、问题描述

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

二、问题解析

以最少的油耗穿过
油耗要求最少，则意味着该车从起点到达终点时各临时加油点的油量全部使用完毕，没有浪费；在每个加油点加油都需要加满500L,因此可知每个加油点的存储油量都会是500的整数倍。
倒推法进行推导
根据题意，起点油量充足，到达终点时汽油应该刚好使用完，则距终点第一个加油站容量500L,距终点距离500km;则距终第一个加油站油量运送由距终第二个加油站负责，500L汽油需要运送2次(装油量为500L)，则经过两点的距离3次，则距终第二个加油站油量= 路上消耗油量+距终第一个加油站油量；往后依次类推

图示如下：

第一次：V1 = 500L 距B为500KM

第二次：V2 =3 * X+V1= 2 * 500 ==> X = 500/3 KM，距B为 (1+1/3) * 500 KM

第三次：V3 =5 * X+V2 = 3 * 500 ==> X = 100 KM，距B为 (2+1/3)*500 KM

图与上类似，省略咯！

第i次：Vi = (2i-1)Xi + Vi-1 = i * 500 ==> x = (v2 - v1) / (2*i - 1);

三、代码示例

    void acrossDesert() {
        int i = 0;//加油点数量（从终点开始算）
        double  v1 = 0, v2 = 0;//加油点油量
        double d = 0;//距终点距离
        double x = 0;//各加油点之间距离

        double xx = 0;//起点矫正量
        double totalOil = 0;//总油耗

        while (d < 1000) {
            //Vi = (2i-1)Xi + Vi-1 = i * 500（推导公式）

            i++;

            v1 = (i - 1)* 500;//上一个加油点存储油量
            v2 = i * 500;//本加油点存储油量
            x = (v2 - v1) / (2*i - 1);//加油点距离公式
            d += x;//累加至距终点距离
            totalOil += (2 * i - 1)*x;

            if (d > 1000) {//起点固定  进行矫正
                xx = d - 1000;
                d = 1000;
            }
            cout << "距起点"<< (1000-d)<<"公里处为第" <<i << "个临时加油点,油量：" << v2<<endl;
        }

        totalOil -= xx*(2*i-1);//矫正为xx公里，根据推到的公式本应行经（2*i-1）次
        cout << "总耗油量：" << totalOil;

    }

结果：