首页 > 技术文章 > 猴子搬香蕉问题

chengwb 原文

题目:一只猴子有100个香蕉,把香蕉搬到50米之外的家里,每次最多拿50个香蕉,每走一米要吃掉一个香蕉,最后家里能剩下几个香蕉。

答案:

很多人的方案:猴子先搬50根,走17米,在回来搬50根走到17米处,回来后再搬剩下的49根走完33米,最后得到16根!

但是其实可以剩下17根。

注意条件:每走一米要吃掉一个香蕉,那如果只走了0.9米就不用吃。

猴子先搬50根,走16.9米,在回来搬50根走到16.9米处,回来后再搬剩下的50根走完33.1米,最后得到17根!
分解:
1.先搬50根走到16.9米处,消耗了16个香蕉,返回到0米处需要带上17根香蕉吃(之前吃了16个后又走了0.9米,加上要走的16.9米=17.8米),此时就在16.9米处剩下17根香蕉;
2.接着搬第二次50根,走到16.9米处,消耗了17个香蕉(之前吃了香蕉后多走了0.8米,加上要走的16.9米=17.7米),第二次搬的50个还剩余33个香蕉;
3.两次下来在16.9米处总共还有50根香蕉,走完剩下的33.1米,消耗33个香蕉,最后得到17根香蕉。


为什么在16.9米(在16.6667到17米之间都可以),是为了最后可以直接搬50个走向家里,16.9的路程走三次=50.7米,加上最后走的33.1米 = 83.8米 0.8米没有达到1米,猴子不需要吃香蕉

 

思考过程:

题中说了猴子每次最多只能拿50个,所以每次取香蕉要拿到50个才是最好的,100个可以拿两次;

如果拿了50个香蕉直接走到家,则家里剩余0个,起点剩余50个,这时猴子不能返回到起点了,因为没有香蕉吃了。所以第一次拿了50个应该找一个中间点停留,然后回起点拿剩下的50个香蕉;

那应该怎么选中间点呢?前面说了每次拿要拿50个才是最优的,所以需要找一个点使得搬两次50个香蕉后能剩下50个香蕉,即搬两次50的香蕉到中间点吃了50个香蕉还剩50个。

假设中间点距离起点距离为x米,搬两次50的香蕉走了3x米

则有100-3x = 50解的x=16.6667米

注意题中是每走1米就吃一个香蕉,我们现在走16米的话就只消耗了16个香蕉,放下18个香蕉,带上16个香蕉返回起点再消耗16个香蕉,取剩下的50个香蕉走到16米剩下34个香蕉,这样还剩下34+18个香蕉=52,猴子没法一次拿完。

16米为中间点会多余两个香蕉,所以需要把这两个香蕉消耗掉,需要在往返途中多走2米但是不到3米的路程才行,这样有设比16米多走y米,则2=<3y<3  可得 0.66667 <=y<1,加上前面的16米即16.6667<=x<17

即只要中间点距离起点为

16.6667<=x<17

 范围的距离都可以使得中间点的剩余个数为50个,拿着剩下的50个香蕉走  50 -x米,

-17 < -x <=16.6667

33 < 50-x <= 33.3333

所以最后50个香蕉走完大于33米小于34米的路程到家,只需要吃33个香蕉,还剩17个香蕉。

作者:不曾潇洒
出处:http://www.cnblogs.com/chengwb
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

推荐阅读