标题: 来转个和箱子有关的题目 [打印本页]
作者:
kesin 时间: 2004-9-6 00:50
有一辆车，它的油箱恰好能装满1桶油，且车上恰好可以运载一个油桶。假设一桶油可以让车开一百公里。现在在起点，车的油箱装满了油，另外起点还有100桶油。问，这车最远能离开起点多远？
作者:
空度 时间: 2004-9-6 02:02
按题义我算的结果是500公里
而且汽油也没全用完,有4桶放到了起点处(有去抢的么?)
不过到现实中可能很多:
要是我开,就是1里开不了,没驾照
或无限远不看油多少,看干粮多少,我推
如果是一个能抗动油桶的长跑冠军开,那就是10000公里
(恐怖 最后一次要抗着油桶跑9999公里.有这力气还不如推车呢 )
有小偷的话.......难说了
作者:
god_wolf 时间: 2004-9-6 02:46
感觉我的答案有误，再想想。难难难
上面我的答案错了，斑竹帮忙删了吧。谢谢
作者:
god_wolf 时间: 2004-9-6 02:59
这次的一定对
100+100+100/3+100/5+100/7+……+100/2n-1（n=100）求和
通项求和忘了，大汗
作者:
kesin 时间: 2004-9-6 07:56
这题是我在天涯看见的，还没讨论出个结果，所以我也没有标准答案。也请大家答题时能写出推理过程。
空度兄答题时居然还考虑现实中的其他因素？
现在限制此汽车为智能汽车，无人驾驶，能自动加油和运送油桶，且行驶区域内完全无人干涉。
帮wolf兄算了一下结果，求和后是428公里多点。
作者:
湘江子龙 时间: 2004-9-6 08:19
这个题目最难的地方是可以把油桶搬过去，在半路下下来，但究竟在哪里下，怎么下才能有走最远值，直觉是走一半，但现在还没法证明，可能要列个方程算最大值。当然这个题目还是有个bug,那就是满载和空载耗的油会一样吗？现在当然只能按一样算，不然就更难解了，很有意思个题目。
作者:
god_wolf 时间: 2004-9-6 09:19
不会吧,只有400多,还不如一开始我想的500呢
和的同项是什么?望指教
作者:
god_wolf 时间: 2004-9-6 09:26
我是这么考虑的,2桶是能直接运的,所以能有200公里,3桶是运道100/3处,这样费1桶油能把两桶运到100/3+200,4桶是100/5+100/3+200,依次类推,所以我觉得我的算法没错,应该是大于500的,怎么会只有400多呢?
作者:
kesin 时间: 2004-9-6 09:27
2+1/3+1/5+1/7...+1/197+1/199＝4.28，用一个简单的循环程序算的。
作者:
湘江子龙 时间: 2004-9-6 09:52
应该是可心那个是对的。
作者:
英布之勇 时间: 2004-9-6 09:55
湘江子龙的答案似乎只是理想值……
若开始车装满油，起点64桶~~运油32桶后，耗油31桶，车在50米处，油箱半满，起点还有一桶油~~这时无论回不回去装那桶油，往下一个50米处的时候车都是半满状态。
这样32桶油+半满的车，更加保证不了后面的发展……
作者:
周瑜 时间: 2004-9-6 10:17
看了楼下god_wolf的方法，又想出一种新方法：
公里 油
050.00 50.5
050.51 50.0
100.51 25.5
101.53 25.0
103.65 24.0
153.65 12.5
155.83 12.0
205.83 06.5
210.37 06.0
260.37 03.5
270.37 03.0
303.71 02.0
503.71
晕原来车上装满了油，也就是相当于101桶，看来还能多走一些：
公里 油
000.503 100
050.503 50.5
051.008 50.0
101.008 25.5
102.028 25.0
104.156 24.0
154.156 12.5
156.330 12.0
206.330 06.5
210.875 06.0
260.875 03.5
310.875 02.0
510.875
作者:
god_wolf 时间: 2004-9-6 10:33
子龙兄的方法我想过,不过会有油浪费,而且最远能到500(就是在50公里处放油).
但是在50公里处放下却不是最佳值,这个值是随油桶数变化的.如果有3桶,最加就是在100/3处,如放在50公里处,只能跑200,因为有一桶是来回浪费了.
作者:
kesin 时间: 2004-9-6 12:42
天涯讨论出的最远值有510多，但也不能确认这就是最大，具体我还没仔细看，大家先考虑考虑。
作者:
god_wolf 时间: 2004-9-6 13:22
原帖由周瑜于2004-09-06, 10:17:21发表
看了楼下god_wolf的方法，又想出一种新方法：
公里 油
050.00 50.5
050.51 50.0
100.51 25.5
101.53 25.0
103.65 24.0
153.65 12.5
155.83 12.0
205.83 06.5
210.37 06.0
260.37 03.5
270.37 03.0
303.71 02.0
503.71
兄台高见,帮我破除了500的瓶颈.看来如何分配还要好好研究
安兄台走法,6桶时直接用50公里的,因为此时n=4,用50公里的能走300,所以你的方法应该最远是510.37,不过之前是否是最优还要看看
作者:
god_wolf 时间: 2004-9-6 14:04
关键是合时用折半,合时用1/2n-1。假设出始是6桶则正好最远是50*2+200=300，所以到6桶就直接加300就行了
作者:
周瑜 时间: 2004-9-6 15:51
想了一下，6桶油走300公里应该是这样的，不知道对不对：
6桶走50公里，得3.5桶。然后卸下车上半桶，用一桶运一桶再走50公里，回程，再用半桶运一桶走50公里。此时已走100公里，还剩2桶。
作者:
god_wolf 时间: 2004-9-6 16:44
原帖由周瑜于2004-09-06, 15:51:32发表
想了一下，6桶油走300公里应该是这样的，不知道对不对：
6桶走50公里，得3.5桶。然后卸下车上半桶，用一桶运一桶再走50公里，回程，再用半桶运一桶走50公里。此时已走100公里，还剩2桶。
我也是这样想的。最后是2桶，之前就要有3.5桶，要有3.5,之前要有6,依次类推11.5, 22, 43.5, 86, 171.5,也就是说86桶就能到500,171.5就能到550.
作者:
周瑜 时间: 2004-9-6 22:17
选用若干中继点，可以把这道题拆为若干步骤，每一步开始时有(n+m)个桶，用n个桶送m个桶，其中n<[m]，([]为向下取整)。
先计算理论值，因为n<[m]，计算结果一定不多于50公里。
假设n和m均为0.5的整数倍，那么需要跑2[m]-1个单程，耗油共n桶，也就是用n桶能送m桶的距离为：100n/(2[m]-1)公里。
证明，该理论值一定能达到。
例1：
5桶油，用2桶送3桶，能送40公里，方法：
第一次，装1桶，载1桶，送出40公里，放下1桶，返回，剩0.2桶。
第二次，装1桶，载1桶，送出40公里，放下1桶，返回，剩0.2桶。
第三次，装0.4桶，载1桶，送出40公里，放下1桶。
例2：
5.5桶油，用2桶送3.5桶，能送40公里，方法：
第一次，装1桶，载1桶，送出40公里，放下1桶，返回，剩0.2桶。
第二次，装1桶，载1桶，送出40公里，放下1桶，返回，剩0.2桶。
第三次，装0.9桶，载1桶，送出40公里，放下1桶，剩0.5桶。
例3：
5桶油，用1.5桶送3.5桶，能送30公里，方法：
第一次，装1桶，载1桶，送出30公里，放下1桶，返回，剩0.4桶。
第二次，装1桶，载1桶，送出30公里，放下1桶，返回，剩0.4桶。
第三次，装0.8桶，载1桶，送出30公里，放下1桶，剩0.5桶。
建立函数f(x)和g(n,m)，f(x)为x桶油能走的距离，g(n,m)为n桶油送m桶油能走的距离。
那么函数f(x)的初始值
f(2)=200
递推关系
n= 0.5 to [x/2]
m= x - n
f(x) = max { g(n,m)+f(m) }
也就是在0.5到[x/2]中任意选择一个n，剩下的作为m，计算出n送m的距离再加上f(m)作为这个n值的最终距离。然后比较所有的n值的最终距离，取最大的一个最终距离为f(x)。
计算出f(x)之后，就可以再算f(x+0.5)直到f(100)。
代码略，以下是输出结果：
f(101.0)=511.83 49.5
f(51.5)=462.82 25.5
f(26.0)=412.82 12.5
f(13.5)=362.82 6.0
f( 7.5)=316.67 3.5
f( 4.0)=266.67 1.5
f( 2.5)=216.67 0.5
翻译一下：
公里 油
000.00 101.
049.01 51.5
099.01 26.0
149.01 13.5
195.16 07.5
245.16 04.0
295.16 02.5
311.83 02.0
511.83
作者:
kesin 时间: 2004-9-6 23:13
周瑜的算法应该是比较完善了。
作者:
god_wolf 时间: 2004-9-7 00:57
不错,不错.
作者:
重阳 时间: 2004-9-7 13:12
这个题目还真不是一般的难。
周瑜的程序计算出的结果是相当好了，但其中假设n和m均为0.5的整数倍，而没有证明，应该还只是一个近似的结果。
考虑了一下5桶油（含车内的）的情况，如果按此假设，最多可走280公里，但如先用1.4桶油，结果可走281.33公里。
估计这个问题没有什么好的算法，不同的油数计算起来差别相当大。
作者:
空度 时间: 2004-9-7 22:10
149.01 13.5
195.16 07.5
周瑜的这步算法为什么不是
149.01 13.5
199.01 07.0
作者:
周瑜 时间: 2004-9-7 23:18
原帖由空度于2004-09-07, 22:10:18发表
149.01 13.5
195.16 07.5
周瑜的这步算法为什么不是
149.01 13.5
199.01 07.0
这是程序输出的结果，自动选择总路程最大值。
计算f(13.5)时，比较g(6,7.5)+f(7.5)和g(6.5,7)+f(7)以及其他一切分法的最大值。
g(6,7.5)=600/13=46.18
f(7.5)=316.67
g(6,7.5)+f(7.5)=362.82
g(6.5,7)=650/13=50
f(7)=309.52
g(6.5,7)+f(7)=359.52
明显前一个计算结果大的多。
作者:
god_wolf 时间: 2004-9-8 01:01
这题难就难在只能靠比较得出最大。要是谁能用数学方法证明如何取最佳就好了。
| 欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |