【摘要】

      吃豆子过桥,今天遇到的一个智力题。呵呵 以后有时间就总结一下类似的智力小题不仅仅为了解决智力小题而是为了学习解决思路,扩展自己的思路!

【主题】

• 小题描述
• 解决思路
• 扩展思路 

【内容】

1. 小题描述

      豆子过桥问题描述如下：

      一个桥，长80米，一个人过桥，走一米必须吃颗豆子，每次只能最多带60颗。桥这头有无数的豆子，过桥人可以将豆子放在桥上，请问过桥人要想过桥至少要吃多少豆子？

2. 解决思路

2.1 利用不等式来优化

a.从题目可以看出，一趟当然不行，若折回一趟，且设这一趟从出发点到折回点的距离为x，则有如下不等式

(1) 2x <= 60             ；第一趟来回必须要有豆子剩余

(2) x + 60 >= 80       ；必须能过桥

(3) 2x + 80 <= 120   ；两趟之内过桥

最后得到 x = 20

2.2 通过逆向分析

这里要看到关键的几个特点：

(1) 从第n趟折回点到第n+1趟折回点之间的路程，无论什么时候经过这段都只能消耗第n+1趟的豆子，否则第n+1趟的折回是无效的；

(2)若总共走了n趟，第i-1趟到第i趟之间距离为ai，则ai这个距离被走的次数为2(n-1+1)-1，即要尽量让在前面的距离短，而i越大，则ai的距离要越长，即去极大值；

在这两个特点的情况下再来分析，那么最后一次的距离应该为60，倒数第二次要走三次，则应该为20。

3. 扩展思路

      如果桥为81需要多少个豆？

      主要思路就是把80为一个整体,就是分为两种，分前1米和后80米 和前80米和后1米

3.1 不等式优化

      若需要折回两趟，则假设第一趟从出发点到折回点的距离为x，第一趟折回点到第二趟折回点距离为y，则问题化为如下

(1) 2x <= 60

(2) x + y + 60 >= 81

(3) 2x + (2x + 2y) + 81 <= 60*3

(4) 2x + (2x + 2y) + (x + y) <= 60*2 ；第三趟的豆子不能在前两趟的路程上消费掉，可以无视(3)

(5) 2x + 2x + x <= 60                        ；从出发点到第一趟折回点的豆子只能消耗第一趟的豆子，否则第一趟折回没有意义

(6) 2y + y <= 60                     ；从第一趟折回点到第二趟折回点的路程只能消耗第二趟的豆子，否则第二趟折回没有意义

最后需要求z = 2x + (2x + 2y) + 81 的最小整数解

解得最优值 x = 1， y = 20， z(x,y)min = 125

3.2 通过逆向分析

这里要看到关键的几个特点：

(1) 从第n趟折回点到第n+1趟折回点之间的路程，无论什么时候经过这段都只能消耗第n+1趟的豆子，否则第n+1趟的折回是无效的；

(2)若总共走了n趟，第i-1趟到第i趟之间距离为ai，则ai这个距离被走的次数为2(n-1+1)-1，即要尽量让在前面的距离短，而i越大，则ai的距离要越长，即去极大值；

在这两个特点的情况下再来分析，那么最后一次的距离应该为60，倒数第二次要走三次，则应该为20，同理倒数第三次的距离为60/5，第四次为60/7……但实际上桥长81，倒数第二次走过之后剩下的距离只有1，故倒数第三次距离选为1即可。这时在来算，则总共消耗的距离为60+20×3+1×5=125。

同理倒数第三次的距离为60/5，第四次为60/7……但实际上桥长81，倒数第二次走过之后剩下的距离只有1，故倒数第三次距离选为1即可。这时在来算，则总共消耗的距离为60+20×3+1×5=125。 

【结束】

自我总结：

• 对于问题要学会分析,逆向思维很重要，有时间能解决很多问题。多思考做一个会思考的人！

参考资料：

• 百度
• 吃豆子过桥

【介绍】

Breeze 喜爱互联网 现在只是一个码农正在努力 一个小螺丝钉但不甘心做一个小螺丝钉

在新的一年里加油!!!

Email、MSN、UC … …:wfwq2008@gmail.com

http://blog.sina.com.cn/breeze104

北京·2011-02-17·晚上