面试题:火车运煤问题
这个可能是一个比较经典的智力题了,和以前的那个《赛马问题》很相似,其题目如下:
你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?
这道题一开始看上去好像是无解的,因为你的火车每一公里就要消耗一吨煤,而到目的地有1000公里,而火车最多只能装1000吨媒。如果你的火车可以全部装下,到目的地也会被全部烧光,一丁点也不剩。所以,很多人的第一反应都是觉得这个不太可能。
如果你一开始就觉得不太可能的话,这是很正常的。不过我不知道你还会不会继续思考下去,如果你不想思考下去了,那么我很为你担忧,因为你可能并不是一个不善于思考的人,而是一个畏难的人,还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。
我一开始也觉得不可能,后来想了一想,想到一个解法可以最多运送500吨煤到市场,方法如下:(希望你先自己想一想再查看这个答案)
【查看答案】
好像这样很不错的了,不过还有更好的方法能运更多的媒过去。你知道这个方法吗?可以提示的是,就是以上述这个方法的思路。我先暂时不把答案放上来,你可以自己想想。过两天我把答案放上来。
更新(2011年4月17日):大家都很聪明,533是应该是最优解,大家用了很多种方法阐述了这一过程,我最初的想法和朋友xPacificCoolShell的一致!很高兴看到有更为科学的解法,受教了。另外,还有一些朋友提出火车不能随时随地调头的实际情况,非常不错,所以,以后这题不能用火车运煤了,可能是用马运草更好一点了。;)
本博客所有文章均镜像自酷壳(Coolshell.cn),所有内容版权归原作者所有。