汽车加油问题——一道迷惑的面试题

现在的位置: 首页 > 综合 > 正文

RSS

汽车加油问题——一道迷惑的面试题

2013年08月06日 ⁄ 综合 ⁄ 共 3578字 ⁄ 字号小中大 ⁄ 评论关闭

问题

一辆载油500升的汽车从A开往1000公里外的B，已知汽车每公里耗油量为1升，A处有无穷多的油，其他任何地点都没有油，但该车可以在任何地点存放油以备中转，问从A到B最少需要多少油？

分析

这道题目初一看觉得方案太灵活，有点晕，网上所有对此题目的答案千篇一律的是：

题目可归结为求数列 an=500/(2n+1) n=0,1,2,3......的和Sn什么时候大于等于1000,解得n>6

当n=6时，S6=977.57

所以第一个中转点离起始位置距离为1000-977.57=22.43公里

所以第一次中转之前共耗油 22.43*(2*7+1)=336.50升

此后每次中转耗油500升

所以总耗油量为7*500+336.50=3836.50升

看起来很有道理，但是又没有说明为什么？害我抓破脑皮去想：这是为什么？怎么证明的？

不过我们简单推下：3836.50 - 7*(500 - 2*22.43) ＝ 650.52，也就是说第一次中转跑7次会剩下650.52，证明这个答案是错误的！

后来我猜想出一种解释，首先我们需要抓住几个关键点：

1. 运输距离要尽量短，也就是说，我们的方案肯定是先从起点将所有需要的油搬到第一个x公里外的转运点，然后再以此类推，不能来回奔波于多个转运点。

2. 运输效率要尽可能高，也就是说，尽量以最大运输能力去跑——不要因为1、2公升油再跑一趟。

3. 相邻转运点之间跑的次数一定是奇数次。

由此，我们可以倒过来考虑：

1. 车到1000公里外的终点的时候，只需要放0的油在那里，转运次数1，可以求得距离是500；

2. 车到500公里外的转运点的时候，需要放500的油在那里，转运次数3，那么如何保证3次都是运输效率最高的呢？通过保证运运输效率最高，可以求得转运点的距离。上面也是这样求的。

3. 以此类推… 中转次数 1 3 5 7 …

解法一

        /// <summary>
        ///计算在距离x的地方放a的油，跑2n+1次运输效率最高的距离
        /// </summary>
        double Distance(double a, int n)
        {
            return (tankLimit * (n + 1) - a) / (2 * n + 1);
        }//x为距离，a = k(tankLimit - 2x) + 500 – x

        /// <summary>
        /// 在距离x的地方，存放amount的油需要跑的总次数
        /// </summary>
        int Trip(double x, double amount)
        {
            int n = 0;
            while (true)
            {
                var a1 = 2 * n * (tankLimit - 2 * x);//来回运的油量
                var a2 = tankLimit - x;//最后一次运的油量
                var diff = a1 + a2 - amount;
                if (diff >= 0 || -diff <= 0.0001) return 2 * n + 1;//避免计算误差
                n++;
            }
        }

        void Transport()//倒推中转
        {
            int k = 0;
            double a = 0, d = 0;//a是每次中转的总耗油量，d是距离累计

            while (d < 1000)
            {
                var last_a = a;
                var x = Distance(a, 2 * k);
                if (d + x <= 1000)
                {
                    a += (2 * k + 1) * x;
                    k++;
                }
                else
                {
                    x = 1000 - d;
                    a += Trip(x, a) * x;
                }
                d += x;

            Console.WriteLine("a = {0:F} x = {1:F} Trip = {2}", a, x, Trip(x, last_a));
            }
        }

运行程序，可以求得：

a = 500.00 x = 500.00 Trip = 1

a = 1100.00 x = 200.00 Trip = 3

a = 1877.78 x = 155.56 Trip = 5

a = 2751.28 x = 124.79 Trip = 7

a = 2888.89 x = 19.66 Trip = 7

可以看出，如果采用这种运输方法，已经比上面网上流传的答案3836.50升少了很多了。但是，这种1 3 5 7…的运输方法就是最优的么？

解法二

或许我们并不需要1 3 5 7…这样递增这么快，1 3 3 3 5 5 5也可能是很好的方法，因此将程序小改动下：

        double Transport(int factor)
       {
                …
                var lastA = a;
                var x = Distance(a, 2 * k);
                if (x == 0) { k++; continue; }
                if (d + x <= 1000)
                {
                    a += (2 * k + 1) * x;
                    if (cnt++ % factor == 0) k++;
                }
                …

然后去计算factor从1～100的情况下耗油量分别是：

1 2888.88888888889

2 2507.65432098765

3 2376

4 2350.4

5 2340.16

6 2336.064

7 2334.4256

8 2333.77024

9 2333.508096

10 2333.4032384

11 2333.36129536

12 2333.344518144

13 2333.3378072576

14 2333.33512290304

15 2333.33404916122

可以看出，factor >15以后就趋于稳定了。

讨论

由此可以看出，不可以盲目迷信别人的解法（当然包括我现在的解法：）做到这里我们可以猜测，解法二也不能说就是最优了，可能存在一些更加优秀的序列——哈哈，说到这里，大家应该想到，这种问题最适合遗传算法了！我暂时没时间了，如果有兴趣的同学找到更优秀的解法麻烦通知我：）

作者：Silver 原文链接：http://yishan.cc/blogs/gpww/archive/2009/10/28/1-1.aspx

-------------------------------------

《编程之美——微软技术面试心得》源代码下载地址：
http://download.csdn.net/source/1883633或者http://www.broadview.com.cn/06074

另外，请大家帮个忙，来投票吧，看看《编程之美》第1章“游戏之乐——游戏中碰到的题目”大家最喜欢哪个题目，或者大家认为哪个题目最有趣。

在此先谢过大家了^_^ （可以选择以下任何网址参与投票）

CSDN：http://vote.csdn.net/VotePost.aspx?voteid=6419

开心网：http://www.kaixin001.com/~vote/detail.php?vid=6324994&uid=57936198

QQ空间：http://user.qzone.qq.com/80754098/vote/1021116304