计算机解智力题一道
一辆车从甲地到乙地,甲乙两地相距1000公里, 这辆车最多可装载500升油,但是每走一公里耗油一升.很明显，车是不能直接从甲地开到乙地的，所以要在甲乙两地之间放置储油罐，储油罐存放的油由这辆车来运送，问:放置多少个储油罐，分别放在哪，使得从甲地到乙地用油最少，最少是多少?
ps:比较难，期待高手:)
[解决办法]
想想程序应该是用递归的方式解,还没想好怎么写
解答如下
0----------------500--------------1000
A-----B-----C-----D-----E-----F-----G
a-> b-> c b有1/3桶
a-> b-> a b有2/3桶
a-> b加满-> c-> b加上1/3-> a c有1/3桶
a-> b-> c b有1/3桶
a-> b-> a b有2/3桶
a-> b加满-> c-> b加上1/3-> a c有2/3桶
a-> b-> c b有1/3桶
a-> b-> a b有2/3桶
a-> b加满-> c-> b加上1/3-> a c有1桶
a-> b-> c b有1/3桶
a-> b-> a b有2/3桶
a-> b加满-> c-> b加上1/3-> a c有4/3桶
a-> c加满-> d-> c加上2/3桶-> a d有1/3桶
a-> b-> c b有1/3桶
a-> b-> a b有2/3桶
a-> b加满-> c-> b加上1/3-> a c有1/3桶
a-> b-> c b有1/3桶
a-> b-> a b有2/3桶
a-> b加满-> c-> b加上1/3-> a c有2/3桶
a-> b-> c b有1/3桶
a-> b-> a b有2/3桶
a-> b加满-> c-> b加上1/3-> a c有1桶
a-> b-> c b有1/3桶
a-> b-> a b有2/3桶
a-> b加满-> c-> b加上1/3-> a c有4/3桶
a-> c加满-> d-> c加上2/3桶-> a d有2/3桶
a-> b-> c b有1/3桶
a-> b-> a b有2/3桶
a-> b加满-> c-> b加上1/3-> a c有1/3桶
a-> b-> c b有1/3桶
a-> b-> a b有2/3桶
a-> b加满-> c-> b加上1/3-> a c有2/3桶
a-> b-> c b有1/3桶
a-> b-> a b有2/3桶
a-> b加满-> c-> b加上1/3-> a c有1桶
a-> b-> c b有1/3桶
a-> b-> a b有2/3桶
a-> b加满-> c-> b加上1/3-> a c有4/3桶
a-> c加满-> d-> c加上2/3桶-> a d有1桶
a-> d加满-> g
[解决办法]
试着做一下:
1.首先题目的意思是想办法让车到达1000公里,那么如果车到500公里处有500升油的话,题目就解决了,因此,将目标一般化为到 <X, Y> ,即车到X公里处有Y升油.
2.那么最终的目标(设为目标一)是 <1000, 0> .然后引申出目标二 <500, 500>
3.现在考虑怎样把500升油运送到500公里处.显然,一次运送是不行的.那么在前若干次运送时,需要再返回.假设出发点和返回点相同,并且希望该点距离起点越近越好.(注意,这个假设能否保证最佳效率,需要数学证明).这样,可以求出它的位置距离500公里处为500/3公里,即从起点开始的1000/3公里.
4.现在求目标三 <1000/3, Yc> 中的Yc,已知 <500, Yb> 中的Yb = 500.
第一次,从1000/3公里处出发,带500升,在500公里处可以放下500/3,并返回,第二次,再从1000/3公里处出发,带500升油.到达500公里处时,车上尚有1000/3,加上已有的500/3,总计500升!所以,已经满足条件了.从1000/3公里处出发2次，Yc = 1000.
5.同理,目标四为 <500/3, Yd> , 目标五为 <0, Ye> .从第四步的推理中可以猜测出目标T的Y '和目标T-1的Y之间的关系为: Y ' = 3Y-500. 其中T> =3. 这很容易证明(注意最后一次不用返回),这里就省略了.
6.根据第五步的公式,可以得出目标四 <500/3, 2500> ,目标五 <0, 7000>
由以上六步,得出这样的结论:
位置(X) 需油量(Y) 最大储油量（储油罐的最大容量）
0 7000 7000
500/3 2500 2000 + 500/3
1000/3 1000 500 + 500/3
500 500 500/3
1000 0 0
注意中间的几步，储油罐的最大容量为Y-1000/3,因为最后一次车达到时总是带了1000/3升油．
综上所述，需要３个储油罐，共计7000升油．但是这不一定是最优答案（需要数学证明它的最优性）．抛砖引玉，期待更好或更完整的答案．
[解决办法]
程序就不写了，说思路吧！最优的算法一定是把所有储油罐里的油都跑干，假设总共要跑M次，第一个储油设置点的位置应当是，500/(2M -1)因为最后一次只是去，不用回来，这样正好能把所有的油用完。现在这个问题就变成了，从第一个储油设置点要用多少次，才能跑到终点，同理，第二个储油设置点的位置距离第一个设置点应当是500/(2M-3)，以此类推，直到加和大于1000km。
简化出来就是：
500 + 500/3 + 500/5 + 500/7 + ...... > 1000，就OK了！
这个程序应当写起来很简单吧！
[解决办法]
从起始点到达终点有：
原点---> i--> i-1--> .....--> 1--> 终点
其中i是蓄油点的最大编号,蓄油点后面的路段长为x[i]，在该路段上的往返次数为n[i].
因为后一个蓄油点的蓄油量肯定要能使前面的消耗要大，所以有：
(n[i]+1)*500/2-n[i]*x[i] > = SUM(n[i-1]*x[i-1])，其中不等式左边为蓄油点i的蓄油量，SUM（）为加有点i后面发生的所有行使的油耗，显然只有蓄油点i后面的蓄油点没有浪费才能使整个行程油耗最小。
其实我们可以在加油点i前面设一个虚的加有点i+1,那么求油耗最少就变成了求(n[i+1]+1)*500/2-n[i+1]*x[i+1]的最小值了。有趣的是可以先求1号加油点的最小值再求2号加油点的最小值，这样从后往前直到求得i+1虚拟加油点的最小值，当虚拟加油点为负数或者0时认定，计算结束。
(n[i+1]+1)*500/2-n[i+1]*x[i+1]---> mix
=> n[+1]---> mix 并且 x[i+1]---> max
注意,往返加有点之间的次数为奇数。显然n的影响大得多，所以力求n[i+1] <= 2i-1最小。
----------------------------------------------
这个题几乎是靠手算的，不可能用3个加有点完成任务。
[解决办法]
|0----|125-----|250-----|375----|500----------------------
在标了一个500数字的地方，意思是说只要这个地方有500升油，那么以后都不用加油了。这个想法绝妙吧，呵呵。
现在，仔细观察0到125这个地方：当车去得时候，耗125，回来的时候也耗125，可在这个地方存油250。所以总体耗油为125×2，同时存储了250。
那么，当在500的时候，必然耗500×2。
375时：1000×2
250时：2000×2
125时：4000×2
所以：总体上耗油为8000
