思考

题目

农民把3000斤萝卜送到1000公里外去卖,骆驼最高载重1000斤,而骆驼每走一公里就要吃掉一斤萝卜,问农民最多可以卖掉多少斤萝卜?

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

如果一开始就觉得不太可能的话，这是很正常的。我一开始也觉得不可能，思考下去，后来想到一个解法可以运送500斤萝卜到市场
方法如下:

• 1、装1000斤萝卜，走250公里，扔下500斤回去
• 2、装1000斤萝卜，走250公里，拿起250斤萝卜，走到500公里处，扔下500斤回去
• 3、装1000斤萝卜，走到500公里处，装上500斤走到目的地**
  于是有了500斤运到市场

好像很不错了，不过还有更好的方法能运更多萝卜。

解答:

抽象解答使用递推公式:

f(1) = 1  
f(2) = f(1) + 1/3  
f(3) = f(2) + 1/5  
…  
f(n) = f(n-1) + 1/(2*n+1)  

通项公式: f(n) = Σ(1/(2*i)+1) (1 <= i <=n)

题目对应是能走的最远距离减去已知的距离，即 (f(3) – 1) * 1000 = 533

就是说最多可以运533斤萝卜
具体如下：

• 1、装1000斤萝卜，走200公里，扔下600斤回去
• 2、装1000斤萝卜，走200公里，装200斤，再走333公里，扔下334斤，往回走
• 3、走到200公里处，装上200斤，回去，此时200公里处还剩200斤
• 4、装1000斤萝卜，走至200公里处，装200斤，走至533公里处，装334斤，走到终点，剩533斤

这是之前遇到的一个面试题