面试题:火车运煤问题

面试题:火车运煤问题

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

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

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

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

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


查看答案

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

 

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

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

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

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

  1. 我不同意你的这些方法。你的所有方案前提是可以背着煤走而可以不用火车,这么一说最好的方案是背着1000吨煤直接到目的地。

  2. 我想了下能运500吨的方法:先从矿区运1000吨开始走,走到250公里的地方下500吨煤下来,还有250吨煤在车上,然后回矿区;再运1000吨开始从矿区走,到250公里的时候把上次下下来的煤运上250吨上来,这时候车上1000吨,继续走到500公里的时候车上还有750吨煤,下500吨下来回矿区,走到250公里时没有煤了,把还剩的250吨煤上上来继续回矿区;这时候还剩下的煤就是500公里那500吨,矿区1000吨,火车在矿区,这样火车从矿区运1000吨开始走,到500公里的时候把那500吨上上来车上有1000吨了,再到集市的时候还剩下500吨煤

  3. 其实计算机一直是用这种中间件的方式发展、解决问题的。
    一开始就想到这个问题的答案了,呵呵~

  4. 实在无解了才偷看答案——老大,你条件里没说能半道把煤卸下来啊,潜规则啊!
    拜托把这条件补上吧~~~

    1. 哦,我以为这个潜规则你可以思考或推理出来的。半道把煤卸下往返几次是这题有解的方法之一啊。;-) 当然,在面试过程中,如果面试者想不出来这个潜规则,一般都应该提示的,因为面试时间有限。这里,大家都有时间去想,应该能推理出这个潜规则的。

      推理不出“潜规则”的朋友应该也不必怀疑自己,这完全是中国教育的问题——把我们教得很死板地不会思考了。哎……

  5. 我是这样想的:火车运行时,最好让他满载,起始点记为A
    第一步,分三次把煤运送到中间点B
    第二步,分两次把煤运送到中间点C
    第三步,把煤运送到目的地D
    第一步:5*(AB) = 1000;解得AB=200
    第二步:3*BC = 1000;解得BC=333.
    第三步:AB+BC+CD=1000;解得CD=467
    因此,做多运送533吨煤到目的地

  6. 我想的方法比较土。。

    先运1000吨至400公里处,卸下200吨,返回
    继续运1000吨至400公里处,卸下200吨,返回
    继续运1000吨至400公里处,卸下600吨。运1000吨至1000公里处,卸下400吨

    。。只运了400吨。-____-!

  7. 我想到的解法和9楼一样
    先假设路程是1,每次运的煤也是1.
    第一次:开到1/5处,卸下3/5的煤,回来;

    第二次:开到1/5处,装上1/5的煤,再往前开1/3,到达8/15处,卸下1/3的煤,掉头回到1/5处,正好没煤,装上1/5的煤,回来;

    第三次:开到1/5处,装上1/5的煤,再往前开1/3,到达8/15处,装上1/3的煤,到终点.

    最后一次消耗掉了1,路上装上了8/15,所以最后运到时还剩8/15.
    不知道这样是不是最优?

  8. @Thkfly
    这个解不错,可能是最优的了。
    但是有个问题在于,我们怎么知道需要分”三次运到B,两次到C,一次到D”?

  9. @Mine
    因为共有3000吨,一次运1000吨,所以第一次要三次,
    第二次,因为已经消耗了1000吨,只剩2000吨了,所有2次,
    左右只有1000吨了,所以一次
    我的理解是这样

  10. @Thkfly
    这个是正确的最优解。
    假定从A到B需要2m+1次,距离为x,那么运过去消耗(2m+1)x的煤。一开始的时候必须(m+1)>=3才可以把煤运完,而且空载是没有哦效率的,所以(m+1)<4.
    所以m=2,而m=1是,所剩煤为2000,m=0时,所剩煤为1000.由m值可以得到距离x,和9楼一样。
    同时,在m不变的情况下,可以任意分段,比如m=2是,可以把煤运到50处,然后在运到100处,然后再运到200处,由于m都是等于2,所以到200时,总会剩下2000煤。
    所以实际上解有无群多,只要让煤在200,533的地方重新聚集就行了。

  11. 假设车只能装载、卸下整数吨数的煤,可以用动态规划
    f[n][d]: 车离终点距离d,有n吨的煤需要运送时最多可以送到终点的吨数
    f[n][0]=n
    f[n][d]=max{f[n-times*k][d-k]}
    times=ceil(n/1000)*2-1, k \in [1,floor(n/times)]
    复杂度O(nd^2)
    有点大材小用了……

  12. 我是这么想的:
    当煤量在(2000,3000]时,需要运送三次;
    当煤量在(1000,2000]时,需要运送两次;
    当煤量在[0,1000]时,需要运送一次。
    那么,我们只需要设置两个中点站,分别使总剩余煤量为2000,1000。
    这么一算,第一段距离为200m,第二段距离为2000/3m,第三段距离为1000-(200 + (2000/3))m
    理论最大值为1600/3吨。

  13. 【每一公里需要耗一吨煤】?不管运多少煤,消耗速度都一样?
    空车返回,消耗速度?
    中途卸煤,下次再装,要不要开销?

  14. 刚开始我也想到用中途放下返回的问题,但是如何达到最优值,陷入困难。
    经过思考,我的解题思路是这样的:首先,要获得最大值,必须在最远的中间”补给点”放下等同其路程的煤作为补给。所以接下来要做的就是,如何让2000吨煤放到最远的地方,同时留下“补给煤”。因为条件限制,所以只能分两次达成上面的目标,第一个补给点,他要消耗的是他路程的5倍的煤,因为他自己消耗两次,第二次送煤的消耗两次,最后一次直达终点的要消耗一次。所以他要在1/5的地方放下,第一个点已经提供补给,所以第二点要补给3次,他自己两次,最后直达的一次。所以是在200+333的地方放下333.所以最后到达的,应该是200+333 = 533. 总数是其他值也可以推导出来了
    编程的例子就是:

    int sum = 3000;
    int load_num = 1000;

    int result = 0;
    int time = sum / load_num – 1;
    for (int i = time; i > 0 ; –i) {
    result += load_num / ((i*2) + 1);
    }

  15. @Thkfly 的应该是最优解

    我一开始的的思路,算出来是416吨,说出来和大家分享一下:

    整个过程分为三段路程:
    第一段从起点开始,煤每前进1公里,需要消耗6吨煤(运3次,每次1个来回),1000/6=166
    第二段从166公里开始,此时还有煤3000-166*6=2004,由于2004-2000=4,此时再运3次不合算,因此在166公里,会舍弃4吨煤,以2000吨记。煤每前进1公里,需要消耗4吨煤(运2次,每次1个来回),1000/4=250
    第三段从416公里开始(166+250),此时还有煤2000-1000=1000

    此时到终点的时候,应该还有煤416吨

    我考虑的是煤堆前进的成本,显然这一步一步前进造成了额外的浪费啊

  16. 非常非常有意思的题目!
    最开始还以为是无解的,然后试着算了一下发现居然有希望

    路程分三段,
    第一段要来回5次,耗煤系数为5,
    第二段的系数为3,
    第三段的系数为1,

    然后稍微计算一下就有结果了

  17. 还有就是我用firefox4 怎么点查看答案闪了一下就没有了。。

    跳转到javascript: document.getElementById(‘answer’).style.display = ”;这个页面了

    1. 这是我的失误,只测试了Chrome,没有测试FF和IE。原来a href=”javascript:”中在FF和IE中不能有语句,只能有function。Chrome下则没有这个限制。真是万恶的Web编程啊。

  18. 刚在GReader里面看到,算出来533,点开一看评论,大家都解出来了嘛。

    关键就是让火车第二次开得尽量远,并且火车第三次到了第二次所在位置时能正好补满。这就要求火车第一次开得尽量近,省煤。

  19. 1000是基本刻度,解题精髓在于消耗多余的煤把煤移动到一个离终点更近的距离,最后一次运上1000吨然后从这个地方直达终点,还能剩下的就是你能运达的煤。
    煤越多需要搬运的次数越多,次数越多消耗就越多。
    要运送到相对较近的距离对煤的消耗量为(2n + 1)*Step,Step为一次行进的步长,n=(总煤量 – 1) / 1000,
    根据这个公式,
    当煤量为2000~3000时,你的运送成本是5*Step
    1000~2000时为3*Step,
    小于等于1000时为1*Step,

    所以第一次选择行进200公里,消耗的煤为5 × 200 = 1000,剩余2000
    第二次选择行进333公里,消耗的煤为3 × 333 = 999 =~ 1000,剩余1000
    此时一共行进了533公里,还剩下1000吨煤,最后到达终点还剩533吨

    其实次数是无所谓的,关键是把握消耗的数量级。

    此题具备高中数学知识就够解了,我发现算法其实很多时候要求的数学知识并不是非常精深,很复杂的数学问题的解也许是一个很简单的方程。
    思考大于知识。

  20. 1000是基本刻度,解题精髓在于消耗多余的煤把煤移动到一个离终点更近的距离,最后一次运上1000吨然后从这个地方直达终点,还能剩下的就是你能运达的煤。
    煤越多需要搬运的次数越多,次数越多消耗就越多。
    要运送到相对较近的距离对煤的消耗量为(2n + 1)*Step,Step为一次行进的步长,n=(总煤量 – 1) / 1000,
    根据这个公式,
    当煤量为2000~3000时,你的运送成本是5*Step
    1000~2000时为3*Step,
    小于等于1000时为1*Step,
    所以第一次选择行进200公里,消耗的煤为5 × 200 = 1000,剩余2000(2000~3000)
    第二次选择行进333公里,消耗的煤为3 × 333 = 999 =~ 1000,剩余1000(1000~2000)
    此时一共行进了533公里,还剩下1000吨煤,最后到达终点还剩533吨(1000内)

    其实次数是无所谓的,关键是把握消耗的数量级。看把第二个刻度分解了
    第一次选择行进200公里,消耗的煤为5 × 200 = 1000,剩余2000(2000~3000)
    第二次选择行进200公里,消耗的煤为3 × 200 = 600,剩余1400(1000~2000)
    第三次选择行进100公里,消耗的煤为3 × 100 = 300, 剩余1100(1000~2000)
    第四次选择行进33公里,消耗3×33=99~=100,剩余1000(1000~2000)
    此时一共行进了533公里,还剩下1000吨煤,最后到达终点还剩533吨(1000内)

    此题具备高中数学知识就够解了,我发现算法其实很多时候要求的数学知识并不是非常精深,很复杂的数学问题的解也许是一个很简单的方程。
    思考大于知识。

  21. 问题在于,你半路扔下的煤等你下次去还会在那里么?早就被人捡走了吧

  22. 先运到200米处,三趟使得那里有600*3。
    然后运到500米处,运两次,这时可以带这900走完最后500米,这样终点有四百。

    这是一个近似问题我觉得,作为程序员思路是使得最后一处拥有1000的数尽量靠近终点,而在这处前地上都没有煤了,是一个近似问题,对1000做剖分,剖分越细集合越大,解越精确,最值难说。

  23. 顶13楼的,不是说其他的版本不好,只是这个版本火车回头的次数最少,也最易于理解.
    3000吨煤,毫无疑问最少的运输次数为3次,第一次时,其实就是为后两次运输的补给作准备,假设其行走最远距离为x,则它本身的来回2x,加上第二次在这段距离上的来回2x,再加上最后一次的来(没有回)x,5x=1000,即x=200.
    第二次时,由于之前的200距离无需考虑煤的消耗,所以在200的基础上,假设其继续走了y,即它自己在y上的来回2y加上第三次的来(同样没有回)y,3y=1000,即y=1000/3.
    第三次时火车尽管往前开,遇到煤再补给上就ok了.

  24. 我有个不靠谱的想法,在这道题里,我们可以把关键视为如何使火车的运载效率最大化的问题,成本是运行过程中消耗的媒量,而收获则是运送到目的地的媒量。这样效率可以简化为 运载量/消耗量。在一次运载过程中,我们在起点都会装载饱和数量的媒,那么,一次运输的运载量其实取决于运载距离的长短。所以我想,如果无限缩短每次的运载距离,是不是可以得到一个比较大的效率?

  25. 昨天没时间回复.

    假设火车一次装满1000T,往前开1Km,卸下998T,剩下1T开回去.所以火车把全部的煤拉到1Km处需要消耗5T.最后一次不需要回去了.结论就是超过2000T的煤需要5T/Km的消耗.这样往前推进,到200Km的地方,还剩2000T煤.

    接下来的一段路,1000T到2000T之间的煤,需要3T/Km的消耗.到达下一个点(还剩1000T)的点,是多远呢? 1000T/3T=333.33Km

    最后,车子在533.33Km的地方还剩1000T煤,满载到达终点,还剩533.33T

    看样子要用到微积分,但是数学从来没及格过,所以将就看吧.

  26. 哈,我的思路并不好,由于在运输过程中,在每一小段的起点媒量都是递减的,因此必定有一趟车无法满载的情况,因而也就无法计量其效率。正确的分析方法应该是:对于一段任何长度的距离,运输的成果 = 起点的媒量 – 运载过程消耗的媒量。耗媒取决火车行驶的路程,因而关键则在于减少运输的次数。如果要分X次运输,则耗媒 = (2 * X – 1) * 距离。如果能找到几个分点,使到第一个分点时,耗媒量恰等于1000吨,则在接下来的一段路程中只需运载X-1次。所以btpot的解法是最好的。

发表回复

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