面试题:火车运煤问题

面试题:火车运煤问题

这个可能是一个比较经典的智力题了,和以前的那个《赛马问题》很相似,其题目如下:

你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?

这道题一开始看上去好像是无解的,因为你的火车每一公里就要消耗一吨煤,而到目的地有1000公里,而火车最多只能装1000吨媒。如果你的火车可以全部装下,到目的地也会被全部烧光,一丁点也不剩。所以,很多人的第一反应都是觉得这个不太可能。

如果你一开始就觉得不太可能的话,这是很正常的。不过我不知道你还会不会继续思考下去,如果你不想思考下去了,那么我很为你担忧,因为你可能并不是一个不善于思考的人,而是一个畏难的人,还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。

我一开始也觉得不可能,后来想了一想,想到一个解法可以最多运送500吨煤到市场,方法如下:(希望你先自己想一想再查看这个答案


查看答案

好像这样很不错的了,不过还有更好的方法能运更多的媒过去。你知道这个方法吗?可以提示的是,就是以上述这个方法的思路。我先暂时不把答案放上来,你可以自己想想。过两天我把答案放上来。

 

更新(2011年4月17日):大家都很聪明,533是应该是最优解,大家用了很多种方法阐述了这一过程,我最初的想法和朋友xPacificCoolShell的一致!很高兴看到有更为科学的解法,受教了。另外,还有一些朋友提出火车不能随时随地调头的实际情况,非常不错,所以,以后这题不能用火车运煤了,可能是用马运草更好一点了。;)

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

好烂啊有点差凑合看看还不错很精彩 (51 人打了分,平均分: 4.45 )
Loading...

面试题:火车运煤问题》的相关评论

  1. 假设两点A和Z距离3000km。先逆向思维,最后存在离终点最近的一点,此刻剩余煤量最多,为1000t。再正向思维,在(2000t,3000t]范围内,火车往返总共5n次,最少5次;同理在(1000t,2000t]范围内,往返3m次,最少3次;最后1000t需1次。那么肯定存在两个中间点2000t处,1000t处。假设2000t处为B,1000t处为Y,那么AB中间总共消耗1000t,BY之间总共消耗1000t,按往返次数最少可得:5AB=1000t,3BY=1000t,AB+BY+YZ=1000km,1000t-YZ=?

  2. 我的解法可以剩533吨。

    0-533公里内,每次搬一公里。

    第一阶段,0-200公里,每公里去3趟,回2趟,消耗5吨,到第200公里剩2000吨;

    第二阶段,200-533公里,每公里去2趟,回1趟,消耗3吨,到第533公里剩1001吨;

    最后,装上剩下的1000吨(丢掉1吨),直接开往终点,消耗467吨;最后剩533吨。

  3. 使用极限求值,应该可以求到最优点。

    但是,装卸的成本就没考虑啦。作为这样一个煤老板,我觉得这次生意肯定黄了。赔大了。

  4. 第一次载上1000吨煤到200处,卸下600吨,回来,煤耗光
    再次载上1000吨,如上步骤
    第三次将最后的1000吨煤载上,到达200处,此时消耗200吨煤,目前200处煤有2000吨
    载上1000吨煤,开到1000/3+200处,卸下1000-2000/3吨煤,再返回200处,载上剩下的1000吨煤到1000/3+200处,此时总共有1000(1000-2000/3+1000-1000/3)吨煤
    剩下路程为800-1000/3,则最终剩下的煤为200+1000/3约等于533.333…

  5. @coyzjc
    第三次将最后的1000吨煤载上,到达200处,此时消耗200吨煤,目前200处煤有2000吨
    (这里应该是1200吨吧)

  6. 思路:
    1.确定到底要运几次.
    3次.推理过程略去。
    所以包括往返两次和第三次直接到目的地。

    2.确定每次火车的出发和返回的状态和目的:

    2.1第一次出发满载1000,返回不剩煤。设第一次出发到达的地点距离起点x公里,目的:在路上留下头两次往返和第三次经过时足够支持火车走这段x公里的煤,所以5x=1000,x=200
    2.2第二次出发满载1000,返回不剩煤。设第二次出发到达的地点距离起点x+y公里,目的:在路上留下第二次往返和第三次经过时足够支持火车走这段y公里的煤, 所以3y=1000,y约等于333
    2.3第三次出发满载1000,直接到目的地。前200+333公里消耗的煤都补充上了,就是可以带到目的地的煤了,533。

    至于沿途放的煤,每次放的总量确定了,放的方法很多啊。

  7. 不说别的.看第二步:”2 装1000吨煤,走到250公里处,拿起250吨煤继续向前到500公里处,扔下500吨煤,回矿山。此时火车上还有250吨,再加上在250公里处还有250吨煤,所以,火车是可以回矿山的。”
    这个就有问题啊. 首先” 装1000吨煤,走到250公里处 ” 这时车上还有750吨–> “拿起250吨煤” 这时车上有1000吨–>”继续向前到500公里处” 走了250公里,车上又只有750吨了–>”扔下500吨煤,回矿山。此时火车上还有250吨” 这个没错–>”再加上在250公里处还有250吨煤”这个哪来的啊.来的路上不是已经让你拿起了吗?–>”所以,火车是可以回矿山的” 所以,你是回不去的.!!!

  8. 能耗问题,天气问题,装卸货问题,往返时间问题,是我,这单生意我然给你做,这是哪门子智力 ,难怪人说理科生智障的多

  9. 拿1000吨,到200公里点,放下600吨,车上200吨煤。
    返回原点。
    现在车上0吨煤,原点2000吨煤,200公里点600吨煤。

    拿600吨,到200公里点,拿起400吨,车上800吨煤。
    到400公里点,放下400吨,车上200吨煤。
    返回200公里点,拿起200吨,车上200吨煤。
    返回原点。
    现在车上0吨煤,原点1400吨煤,200公里点0吨煤,400公里点400吨煤。

    拿600吨,到200公里点,放下200吨,车上200吨煤。
    返回原点。
    现在车上0吨煤,原点800吨煤,200公里点200吨煤,400公里点400吨煤。

    拿800吨,到200公里点,拿起200吨,车上800吨煤。
    到400公里点,拿起400吨,车上1000吨煤。
    到终点,车上600吨煤。

  10. 到400公里点,拿起400吨,车上1000吨煤。
    到终点,车上600吨煤。—>这。。。1000-600=600?

  11. 阿里里 :
    能耗问题,天气问题,装卸货问题,往返时间问题,是我,这单生意我然给你做,这是哪门子智力 ,难怪人说理科生智障的多

    哈哈

  12. 3000吨煤如果运出的话,火车最多只能装1000吨煤,所以至少需要三次。在经过第一次运输后,在第一个卸载点所剩的媒>=2000,<3000,所以第二次运输的话运输2或3次,如果三次的话最后一次运输<1000,没有达到火车装煤的极限,所以在第一个卸载点最后只剩2000吨煤,此地点应该距原始点(3000-2000)/(2+2+1) =200公里处。剩下距终点还有800公里,火车还不能一次运到。假设下一个卸载点距第一个卸载点y公里,那么在第二个卸载点剩余煤应为(2000-3y)<2000,分析同一个卸载点,第二卸载点应该剩余煤1000吨,2000-3y=1000,y=333.33….。所以到终点剩余最多没煤为1000-(1000-200-333.333)=533.333。

  13. 你们知道什么是火车吗?还可以随意掉头?!铁轨啊!铁轨!!不到站掉不了头的!!我没看答案想了半天啊啊!!原来是掉头这招!!!

  14. 别太在意了。想不到 也不能证明什么。
    此类题的 目的是
    检验你的思维能力如何。碰到问题敢不敢想。楼主也说了。
    纠结就米意思了对吧。

  15. 在这个路程上逻辑设置多个火车站:在每站上都可以放煤取煤,这样就演变为类似编程解汉诺塔的问题了。用图的数据结构+递归就可以解出多少个火车站以及分布是合理的了。

  16. 这道题应该是逆推吧 发表一下我的拙见。
    终点D,中间点C,中间点B,起点A。
    首先为了满足火车运到某个中间点可以卸下一定量的煤并返回,应保证每次运输的距离小于500,这样起点和终点直接至少存在2个中间点。
    为了减少煤的损耗,每次运输时应满载,故在C点应有1000吨煤,而为了让C点有1000吨煤,需要火车从B点到C点走3次(2次去,一次回)。而B点储存的煤应该是1000的2倍,所以从B运到C共损失1000吨煤,BC=1000/3;
    为了使B点储存2000吨煤,需要从A点到B点往返5次(3次去,2次回),A点有3000吨煤,从A到B损失1000吨煤,则AB=1000/5;
    AB=200;BC=333.33333;那么CD=1000-AB-BC=466.6666;
    所以最终剩余1000-CD=533.3333吨煤

  17. 你这个思路一看就有问题的。应该是时刻保持火车最大装载量,可是你一开始就不让火车装满,肯定效率低的@路人

  18. 一公里一公里的向前移动
    在3000 – 2000 时,每向前一公里,需要来回移动5次,故在这个时段每公里耗费5吨煤
    在2000 – 1000 时,每向前一公里,需要来回移动3次,每公里耗费3吨煤
    在1000 – 0 时,每公里1吨煤

    所以结果如下:
    剩下的煤 已经走了的公里数
    3000 : 0
    2000 : (1000/5) = 200
    1001 : 200 + (1000/3) = 533

    最后在走了533公里的时候,火车上还可以有1001吨,但是零下的一吨是带不走的
    所以最后应该是 1000吨 – (1000公里 – 533公里)* 1吨每公里 = 533吨

  19. /**
    * @param m the total weight of coal
    * @param n the capacity of train or the miles count of distance
    * @return the weight of the left coal mine
    */
    public static int resolve(int m, int n){
    int milesLeft = n;
    int capacity = n;
    int coalLeft = m;

    int backAndForthCount = coalLeft / milesLeft + (((coalLeft % milesLeft) > 0) ? 1 : 0 );
    int backAndForthTimes = 2 * backAndForthCount – 1;
    while(backAndForthTimes > 1){
    // 每次向前走一公里耗费的煤
    int costPerMile = backAndForthTimes;
    int milesToBeMoved = n / costPerMile;
    coalLeft -= milesToBeMoved * costPerMile;
    milesLeft -= milesToBeMoved;
    backAndForthCount–;
    backAndForthTimes = 2 * backAndForthCount – 1;
    }
    return capacity – milesLeft;
    }

    public static void main(String[] args) {
    int miles = 3000;
    int capacity = 1000;
    System.out.printf(“there are totally %d ton(s) of coal left”, resolve(miles, capacity));
    }

  20. 应该是533.333吧。
    1、第一次中点站应该下一次为2000t最好,所以为1000=5x,x=200;
    2、第二个中点站应该等下次只剩下1000t的时候最优,1000=3y,y=333.33;
    3、最后剩下的1000直接走完剩下的路,1000-(1000-x-y)。
    最后得533.33.

  21. 类似于小学生条件局限的数学题,首先没有给出空车能耗,最优载重量,以及超过最优载重能耗是正比增长,还是成指数增长,还有看了大概看了楼上的,切不说超过最优是否成能耗指数递增,即使成指数,要最优的话,是最忌空车往返的,还有我认为这题的考点在能耗,满载1000直接去终点不会全耗尽煤的,
    他没给最优载重,题意暗指能耗是成比例增长,忽略车重,1000吨直接到终点还剩是
    1000*(0.999^1000),最后空车往返可不计。
    个人愚见,勿怪

  22. 火车不用掉头,倒着开就好了。火车不是汽车。有调度给搬道岔就好了,不用自己控制方向。呵呵^_^

  23. 设定始发点为A(3000吨),第二个起点为B(2000吨),第三个起点为C(1000吨),终点为D。从B到A火车运行了5次,即消耗1000吨煤也就是运行了1000公里,所以B点应该设在200公里处。从B到C火车运行了3次,即消耗1000吨煤运行了1000公里,所以B到C的距离为1000/3。从C到D的距离为1000-200-1000/3 = 1400/3, 但是C点的煤为1000吨,所以剩余的煤为1000-1400/3 = 1600/3.

  24. 不大明白超过500的是怎么算的,我得出是500,把路程分成4份是500,分成8份,得出的也是500,超过500的是怎么算的呢?

  25. 一辆车一吨煤
    假设有3辆车(刚好装满3000)
    1000/ (3辆(消耗) + 2辆(返程))) = 200公里 (返回两辆),200公里处剩2000吨
    假设有2辆车(刚好装满2000)
    1000 / (2辆(消耗)+ 1辆 (返程)) = 333.333333公里 (返回一辆),533公里处剩1000 吨

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注