面试题:火车运煤问题

面试题:火车运煤问题

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

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

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

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

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


查看答案

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

 

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

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

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

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

  1. 每次运一千吨,分3次,前2次都到666.66667公里处卸煤,第3次到原先卸下处装上666.66667吨,这时火车上共有1000吨,路程还有333.33333公里。
    很明显,到目的地后还有1000-333.333333=666.666667吨煤。

  2. eagle :每次运一千吨,分3次,前2次都到666.66667公里处卸煤,第3次到原先卸下处装上666.66667吨,这时火车上共有1000吨,路程还有333.33333公里。很明显,到目的地后还有1000-333.333333=666.666667吨煤。

    不好意思,算错了,没有考虑回程。

  3. 1.装1000T,走1KM,用掉1T,卸下998T,留1T回去;回去后再装1000T,走1KM,用掉1T,卸下998T,留1T回去;回去后再装最后1000T,走1KM,用掉1T,这次不用回去;由此可以看出,可以用2+2+1=5T的代价前进1KM;
    2.用上述方法向前走了200KM后,用掉了1000T,现在只剩2000T;
    3.后面仍然按上面的方法,不过这次只需要运2000T,代价也就减少到2+1=3T了,一直这样向前走,直到最后剩下1000T;也就是用1000T来前进,可以前进1000/3=333KM;
    4.此时剩下1000T,共前进了200+333=533KM,还剩下467KM;一次运过去,用掉467T,剩下1000-467=533T;

  4. 没有看别人的答案,最后我是这样解的:
    因为运煤的来回都会有消耗,假设剩余煤量是M,一共有多种可采纳的消耗方式,假设前进x公里
    当2000<M<3000时,5次的方式可以保证把所有的煤地往前运
    当1000<M<2000时,3次的方式可以保证把所有的煤地往前运
    当0<M<1000时,1次的方式可以保把所有的煤尽量地往前运
    所以第1点是(M-2000)/5 = 200,第二个点是1000/3, 最后剩余1000顿煤 和 还需要走(1000 – 200 – 1000/3)公里,200+1000/3也就是剩余煤量

    最后可以有归纳法拓展一下:
    比如3000<M<4000,最开始需要用7次的方式来运,然后5次,3次,1次,
    最多能运(M-3000)/7+1000/5+1000/3
    比如4000<M<5000,最开始需要用9次的方式来运,然后7次,5次,3次,1次,
    最多能运(M-4000)/9 + 1000/7 + 1000/5 + 1000/3

  5. 个人觉得最佳答案是:2/3 * 1000 = 666.67
    用3个火车运 到2/3的位置其中两个把煤全给另外一个.
    因为题目没有给出火车要返回和铁路只有一个条的约束

  6. 哈~~~水题,先运1000吨距出发地250公里的位置,放下500吨,则车上还有250吨,刚好能回到出发地,回到出发地后再运1000吨出发,到距出发地500公里时,放下250吨,则车上还有250吨,回走到距出发地250公里的位置(因刚在这放下了500吨,现在往车上加煤250则可回到出发地)加煤,此时这个位置还有250吨煤,车回到出发地,最后运1000吨煤,到距出发地250公里时加煤剩下的250吨,(车花费了250吨)刚好又是1000吨煤,到距出发地500公里时加煤250吨,车上还有1000吨,走完剩下的500公里花费500吨,则最后送达目的地的是1000-500=500

  7. 最佳是2000/3
    分三批次到1000/6处,再分两批次到1000/6+500处
    最后一次到达目的地

  8. 我想到的也是卸煤,不过没算出最优解。不过为什么空载和满载消耗会是一样呢?这肯定不符合常理啊。

  9. 傻啊,换个火车啊,或者叫买家自己来运!哈哈,看大家解得这么开心,开开玩笑

  10. 初始是3000,运3次,
    第一次消耗1000,到点333
    第二次消耗1000,到点500+333=833
    第三次消耗267,到终点,
    一共运回733顿。

  11. 神奇之光 :
    初始是3000,运3次,
    第一次消耗1000,到点333
    第二次消耗1000,到点500+333=833
    第三次消耗267,到终点,
    一共运回733顿。

    没算回程的消耗,其实思路应该是一致的,
    前两次的耗煤量*2,到最后1000的时候直接拉到终点
    1,1000/6=167
    2, 1000/4=250
    3, 1000-167-250= 583

  12. @神奇之光

    神奇之光 :

    神奇之光 :
    初始是3000,运3次,
    第一次消耗1000,到点333
    第二次消耗1000,到点500+333=833
    第三次消耗267,到终点,
    一共运回733顿。

    没算回程的消耗,其实思路应该是一致的,
    前两次的耗煤量*2,到最后1000的时候直接拉到终点
    1,1000/6=167
    2, 1000/4=250
    3, 1000-167-250= 583

    又漏了,不是双倍消耗,是双倍-1
    1,1000/5=200
    2, 1000/3=333
    3, 结果应该是533

  13. 用数学表达
    1000-x x
    |————————————|————-|
    start 临界点 end

    假设: a、临界点(能一次性运完的点)卸下来的煤的总数为:count
    b、最后能剩余的煤为surplus
    c、分n次到达临界点

    1、(1000-x) * n = 3000 – count
    2、count <= 1000
    3、surplus = count – x

    感觉靠自己主观推断3次运送,并且假设临界点是卸下来的煤是1000,毫无意义。我相信还是用数学公式计算下吧。最好能用程序表达出来

  14. 我的想法是利益最大化
    第一次到1/3处,放下333t,然后第二次运行到这里时,还有1000t
    然后设此点为A点,到达的距离为B点,这个距离为x
    x要满足
    1、留下的煤最多同时火车能回到起点
    2、第三次火车到这里时 正好装满火车上的剩余空间
    1000-(x+333+x) = (x+333)
    x = 111
    第二次火车运行到444处,放下445
    最后一次运行445公里,正好到此处全部装上,最后到达目的地剩余445
    但这个和一般的解法500km还是更多的533解法差距都很大
    但感觉思路还是挺正确的 不知道哪里有问题

  15. 这道题其实高中的线性规划知识就可以解决。
    不难想出火车要走完1000km,最多会经历三个阶段:
    |____________|______________|________________|
    起点 A B C(终点)

    1.从起点开始,分3次把3000吨煤拉到A点,路程为5a;
    2.从A点开始,分2次把剩下的煤拉到B点,路程为3b;
    3.从B点开始,1次把剩下的煤拉到终点,路程为c。

    所有消耗的煤的数量为t = 5a + 3b + c,由于煤的总数是一定的,所以我们要求的也就是t最小。
    目标:min t = 5a + 3b +c
    条件:
    a + b + c =1000
    5a + d + c <= 3000 (来来回回消耗的煤不能大于3000)
    3000 – 5a <= 2000 (到达A点时,煤的数量不能超过2000,否则不可能分两次拉完)
    3000 – 5a – 3b <= 1000 (到达B点时,煤的数量不能超过1000,否则不可能一次拉完)

    看似是三元一次方程组,其实c可以用a b表示 (c = 1000 – a – b)。然后在坐标系中,用高中的线性规划知识即可求出t的最小值以及此时的a、b、c, 然后3000 – t = 533 就是煤最大的运送量。

  16. (上一条有个地方错了,重新贴一下)
    这道题其实高中的线性规划知识就可以解决。
    不难想出火车要走完1000km,最多会经历三个阶段:
    |____________|______________|________________|
    起点 A B C(终点)
    1.从起点开始,分3次把3000吨煤拉到A点,路程为5a;
    2.从A点开始,分2次把剩下的煤拉到B点,路程为3b;
    3.从B点开始,1次把剩下的煤拉到终点,路程为c。
    所有消耗的煤的数量为t = 5a + 3b + c,由于煤的总数是一定的,所以我们要求的也就是t最小。
    目标:min t = 5a + 3b +c
    条件:
    a + b + c =1000
    5a + 3b + c <= 3000 (来来回回消耗的煤不能大于3000)
    3000 – 5a <= 2000 (到达A点时,煤的数量不能超过2000,否则不可能分两次拉完)
    3000 – 5a – 3b <= 1000 (到达B点时,煤的数量不能超过1000,否则不可能一次拉完)
    看似是三元一次方程组,其实c可以用a b表示 (c = 1000 – a – b)。然后在坐标系中,用高中的线性规划知识即可求出t的最小值以及此时的a、b、c, 然后3000 – t = 533 就是煤最大的运送量。

  17. 这个问题,首先要考虑什么情况才是最优情况。依照题意,火车只要活动就会消耗煤,所以每次火车出发时只有满载才是最优情况,并且不能扔掉煤不要。有了这个前提,我们接着往下分析。

    求得最优解的过程肯定要减少火车折返的所消耗的总路程。由于全长1000公里,所以我们肯定需要采用多次中转的方式来运送,中转的过程中随着煤的消耗,折返的次数也会减少,所以我们要尽量减少多次折返时所前进的距离。

    只有一辆火车,每次出发都是满载,那么我们需要3次将煤运送到下一站,在此期间需要折返5次。下一站出发如果要满足最优条件,则此期间需要消耗掉一车或者两车煤,根据第二段的分析,我们应该减少5次折返时所前进的距离,故此次运送需要消耗1车煤。1000/5 = 200公里。依次类推,第二次运送折返3次,需要消耗1车煤,前进距离为1000/3 = 333.33……公里。第三次由于仅剩一车煤,满载前进,出去路途消耗,到达终点剩余煤为1000-(1000-(200+333.33) = 533.3333吨。

  18. 把所有煤运到100公里处,需要三趟,往返5次,消耗500吨,还剩2500,同理运到200公里处剩2000吨,运到300公里处剩1700,400公里处剩1400,500公里处剩1100;还有1100吨煤,500公里路,100吨送人不要了,拉上1000吨到市场还剩500吨

  19. 先解决运500吨过去的方案。考虑路中只设置一个转运点,可以设为距起点x km.则有3000-5x-(1000-x)=500.解得X=375,即在距起始出发点375km处设置一个转运点。同理,要保证火车最后运输煤的量最大,则要分3个转运点运输。为什么这是最优的方案呢?因为分为两个转运点最多能运500吨煤,而分成4个或者4个以上就会增加火车往返的次数,况且只有3000吨煤(如果多一些煤还可以考虑),所以为了保证每次往返只消耗一车煤,则第一个转运点应该设置在1000/5=200 km处,第二个转运点应该设置在200+1000/3=533.33km处,所以最终能运到目的地的煤为1000-(1000-200-1000/3)=533.33吨,取整数为533吨。

  20. maximum [(a+b,a,b)|a<-[200,200.4..400],b<-[0,0.4..500],let p = 2000-5*a-3*b in p<1 && 0<p]

    来点有浮点的

  21. 始发站有3000吨煤,每次只能装1000,所以,将所有的煤运离始发站,火车要走5次同样的路程
    这就意味着,我们将所有的煤向前推动1公里,就要消耗5吨煤
    因为我们要装三次车,每次装1000吨
    问题是我们这次向前推进多少合适
    我们第二次向前推进时,还要装车,也许还会有第三次,直到我们只剩下1000吨煤为止,我们才一直驶向终点站
    那么,这就意味着,我们每次装车都应该装1000吨煤,否则,就是在浪费运力
    所以,我们第一次应该向前推进200公里,这样,我们剩下2000吨,才能保证每次装车可以装1000吨煤,使得运力最大化
    那么我们这次每向前推进1公里,就只要消耗3吨煤
    如此,我们有1000吨煤可以消耗
    也就是说可以向前推进三分之一千米
    这意味着我们要用剩下的1000吨煤跑完最后的(800-1000/3)公里的路程
    那么最后剩下533.3333吨煤

  22. 就这种试题来说,
    最多运到目的地的 ((n-1)/(n+1))*每次可运量, n等于 总的待运量/每次可运量
    就本体来讲 n=3 运到目的地的最大值为(1/2)*1000 = 500

  23. 第一个333公里消耗1000,折返3次,运煤2000
    第二个333公里消耗1000,折返3次,运煤1000
    第三个333公里消耗333,折返1次,运煤667

  24. Fidel :
    这个问题,首先要考虑什么情况才是最优情况。依照题意,火车只要活动就会消耗煤,所以每次火车出发时只有满载才是最优情况,并且不能扔掉煤不要。有了这个前提,我们接着往下分析。
    求得最优解的过程肯定要减少火车折返的所消耗的总路程。由于全长1000公里,所以我们肯定需要采用多次中转的方式来运送,中转的过程中随着煤的消耗,折返的次数也会减少,所以我们要尽量减少多次折返时所前进的距离。
    只有一辆火车,每次出发都是满载,那么我们需要3次将煤运送到下一站,在此期间需要折返5次。下一站出发如果要满足最优条件,则此期间需要消耗掉一车或者两车煤,根据第二段的分析,我们应该减少5次折返时所前进的距离,故此次运送需要消耗1车煤。1000/5 = 200公里。依次类推,第二次运送折返3次,需要消耗1车煤,前进距离为1000/3 = 333.33……公里。第三次由于仅剩一车煤,满载前进,出去路途消耗,到达终点剩余煤为1000-(1000-(200+333.33) = 533.3333吨。

    这个思路最清晰,顶一个!

  25. 因为我们不知道要运多少次才能最节省,说3次的只不过是根据经验判断的而已,如果煤炭数、公里数、运载量分别为a、b、c的话,就无法这样判断了。
    我觉得应该这样来算,假设我们有很多火车,那么用到的火车数就是a/c,有余数的话,需要进位计算,而由于需要返程,我们需要另外的a/c-1辆火车的跟随。
    这样,除最后一次消耗的煤炭量是a/c外,前面每公里消耗的煤炭量就是2*a/c-1,a/c有余数的话,需要进位计算。
    而我们可以根据a/c的数值,进行分段计算,前面每段的距离为c/(2*a/c-1),每段消耗的煤炭数为c。最后一段消耗量为a/c*(b-前面每段的距离)。
    比如本题,开始的时候a/c=3,那么就分3段,消耗的总煤量为1000+1000+1*(1000-1000/(2*3000/1000-1)-1000/(2*2000/1000-1))=2466.667吨,剩余533.333吨。

  26. 天凭 :
    因为我们不知道要运多少次才能最节省,说3次的只不过是根据经验判断的而已,如果煤炭数、公里数、运载量分别为a、b、c的话,就无法这样判断了。
    我觉得应该这样来算,假设我们有很多火车,那么用到的火车数就是a/c,有余数的话,需要进位计算,而由于需要返程,我们需要另外的a/c-1辆火车的跟随。
    这样,除最后一次消耗的煤炭量是a/c外,前面每公里消耗的煤炭量就是2*a/c-1,a/c有余数的话,需要进位计算。
    而我们可以根据a/c的数值,进行分段计算,前面每段的距离为c/(2*a/c-1),每段消耗的煤炭数为c。最后一段消耗量为a/c*(b-前面每段的距离)。
    比如本题,开始的时候a/c=3,那么就分3段,消耗的总煤量为1000+1000+1*(1000-1000/(2*3000/1000-1)-1000/(2*2000/1000-1))=2466.667吨,剩余533.333吨。

    根据上面的分析,写程序计算的话,也就很好设计了。

发表回复

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