轩辕春秋文化论坛 » 辕门射虎 » 来转个和箱子有关的题目

打印 | 推荐 | 订阅 | 收藏 | 开通个人空间 | 加入资讯
标题: 来转个和箱子有关的题目, 不难理解，答案难定
性别:未知-离线 kesin

南郡公枢密直学士

Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
资政殿大学士（从一品）
组别 翰林学士
级别 镇东将军
好贴 5
功绩 1036
帖子 4004
编号 2725
注册 2003-11-30
#1
发表于 2004-9-6 00:50 资料 文集 短消息 只看该作者
有一辆车，它的油箱恰好能装满1桶油，且车上恰好可以运载一个油桶。假设一桶油可以让车开一百公里。现在在起点，车的油箱装满了油，另外起点还有100桶油。问，这车最远能离开起点多远？


顶部
性别:未知-离线 空度

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 仁勇校尉
功绩 2
帖子 171
编号 16844
注册 2004-9-1
#2
发表于 2004-9-6 02:02 资料 短消息 只看该作者
按题义我算的结果是500公里
而且汽油也没全用完,有4桶放到了起点处(有去抢的么?)

不过到现实中可能很多:
要是我开,就是1里开不了,没驾照
或无限远不看油多少,看干粮多少,我推  
如果是一个能抗动油桶的长跑冠军开,那就是10000公里  
(恐怖 最后一次要抗着油桶跑9999公里.有这力气还不如推车呢  )
有小偷的话.......难说了


顶部
性别:男-离线 god_wolf

Rank: 4
组别 士兵
级别 牙门将军
功绩 5
帖子 521
编号 6045
注册 2004-3-16
#3
发表于 2004-9-6 02:46 资料 主页 短消息 只看该作者
感觉我的答案有误，再想想。难难难

上面我的答案错了，斑竹帮忙删了吧。谢谢
顶部
性别:男-离线 god_wolf

Rank: 4
组别 士兵
级别 牙门将军
功绩 5
帖子 521
编号 6045
注册 2004-3-16
#4
发表于 2004-9-6 02:59 资料 主页 短消息 只看该作者
这次的一定对
100+100+100/3+100/5+100/7+……+100/2n-1（n=100）求和

通项求和忘了，大汗
顶部
性别:未知-离线 kesin

南郡公枢密直学士

Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
资政殿大学士（从一品）
组别 翰林学士
级别 镇东将军
好贴 5
功绩 1036
帖子 4004
编号 2725
注册 2003-11-30
#5
发表于 2004-9-6 07:56 资料 文集 短消息 只看该作者
这题是我在天涯看见的，还没讨论出个结果，所以我也没有标准答案。也请大家答题时能写出推理过程。

空度兄答题时居然还考虑现实中的其他因素？  
现在限制此汽车为智能汽车，无人驾驶，能自动加油和运送油桶，且行驶区域内完全无人干涉。  

帮wolf兄算了一下结果，求和后是428公里多点。
顶部
性别:男-离线 湘江子龙

赵王枢密使

Rank: 30Rank: 30Rank: 30Rank: 30Rank: 30Rank: 30
组别 诸侯
级别 骠骑将军
好贴 9
功绩 630
帖子 8100
编号 8098
注册 2004-6-4
这个题目最难的地方是可以把油桶搬过去，在半路下下来，但究竟在哪里下，怎么下才能有走最远值，直觉是走一半，但现在还没法证明，可能要列个方程算最大值。当然这个题目还是有个bug,那就是满载和空载耗的油会一样吗？现在当然只能按一样算，不然就更难解了，很有意思个题目。
顶部
性别:男-离线 god_wolf

Rank: 4
组别 士兵
级别 牙门将军
功绩 5
帖子 521
编号 6045
注册 2004-3-16
#7
发表于 2004-9-6 09:19 资料 主页 短消息 只看该作者
不会吧,只有400多,还不如一开始我想的500呢

和的同项是什么?望指教
顶部
性别:男-离线 god_wolf

Rank: 4
组别 士兵
级别 牙门将军
功绩 5
帖子 521
编号 6045
注册 2004-3-16
#8
发表于 2004-9-6 09:26 资料 主页 短消息 只看该作者
我是这么考虑的,2桶是能直接运的,所以能有200公里,3桶是运道100/3处,这样费1桶油能把两桶运到100/3+200,4桶是100/5+100/3+200,依次类推,所以我觉得我的算法没错,应该是大于500的,怎么会只有400多呢?
顶部
性别:未知-离线 kesin

南郡公枢密直学士

Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
资政殿大学士（从一品）
组别 翰林学士
级别 镇东将军
好贴 5
功绩 1036
帖子 4004
编号 2725
注册 2003-11-30
#9
发表于 2004-9-6 09:27 资料 文集 短消息 只看该作者
2+1/3+1/5+1/7...+1/197+1/199＝4.28，用一个简单的循环程序算的。
顶部
性别:男-离线 湘江子龙

赵王枢密使

Rank: 30Rank: 30Rank: 30Rank: 30Rank: 30Rank: 30
组别 诸侯
级别 骠骑将军
好贴 9
功绩 630
帖子 8100
编号 8098
注册 2004-6-4
应该是可心那个是对的。
顶部
性别:未知-离线 英布之勇

Rank: 5Rank: 5
组别 士兵
级别 讨逆将军
功绩 6
帖子 630
编号 6578
注册 2004-4-7
#11
发表于 2004-9-6 09:55 资料 短消息 只看该作者
湘江子龙的答案似乎只是理想值……

若开始车装满油，起点64桶~~运油32桶后，耗油31桶，车在50米处，油箱半满，起点还有一桶油~~这时无论回不回去装那桶油，往下一个50米处的时候车都是半满状态。

这样32桶油+半满的车，更加保证不了后面的发展……
顶部
性别:男-离线 周瑜

栎阳侯谏议大夫
★

Rank: 16
组别 翰林学士
级别 征西将军
好贴 10
功绩 943
帖子 4716
编号 1808
注册 2003-11-3
家族 瓦岗寨
#12
发表于 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

Rank: 4
组别 士兵
级别 牙门将军
功绩 5
帖子 521
编号 6045
注册 2004-3-16
#13
发表于 2004-9-6 10:33 资料 主页 短消息 只看该作者
子龙兄的方法我想过,不过会有油浪费,而且最远能到500(就是在50公里处放油).

但是在50公里处放下却不是最佳值,这个值是随油桶数变化的.如果有3桶,最加就是在100/3处,如放在50公里处,只能跑200,因为有一桶是来回浪费了.
顶部
性别:未知-离线 kesin

南郡公枢密直学士

Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
资政殿大学士（从一品）
组别 翰林学士
级别 镇东将军
好贴 5
功绩 1036
帖子 4004
编号 2725
注册 2003-11-30
#14
发表于 2004-9-6 12:42 资料 文集 短消息 只看该作者
天涯讨论出的最远值有510多，但也不能确认这就是最大，具体我还没仔细看，大家先考虑考虑。
顶部
性别:男-离线 god_wolf

Rank: 4
组别 士兵
级别 牙门将军
功绩 5
帖子 521
编号 6045
注册 2004-3-16
#15
发表于 2004-9-6 13:22 资料 主页 短消息 只看该作者


QUOTE:
原帖由周瑜于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

Rank: 4
组别 士兵
级别 牙门将军
功绩 5
帖子 521
编号 6045
注册 2004-3-16
#16
发表于 2004-9-6 14:04 资料 主页 短消息 只看该作者
关键是合时用折半,合时用1/2n-1。假设出始是6桶则正好最远是50*2+200=300，所以到6桶就直接加300就行了
顶部
性别:男-离线 周瑜

栎阳侯谏议大夫
★

Rank: 16
组别 翰林学士
级别 征西将军
好贴 10
功绩 943
帖子 4716
编号 1808
注册 2003-11-3
家族 瓦岗寨
#17
发表于 2004-9-6 15:51 资料 主页 文集 短消息 只看该作者
想了一下，6桶油走300公里应该是这样的，不知道对不对：
6桶走50公里，得3.5桶。然后卸下车上半桶，用一桶运一桶再走50公里，回程，再用半桶运一桶走50公里。此时已走100公里，还剩2桶。
顶部
性别:男-离线 god_wolf

Rank: 4
组别 士兵
级别 牙门将军
功绩 5
帖子 521
编号 6045
注册 2004-3-16
#18
发表于 2004-9-6 16:44 资料 主页 短消息 只看该作者


QUOTE:
原帖由周瑜于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.
顶部
性别:男-离线 周瑜

栎阳侯谏议大夫
★

Rank: 16
组别 翰林学士
级别 征西将军
好贴 10
功绩 943
帖子 4716
编号 1808
注册 2003-11-3
家族 瓦岗寨
#19
发表于 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

南郡公枢密直学士

Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
资政殿大学士（从一品）
组别 翰林学士
级别 镇东将军
好贴 5
功绩 1036
帖子 4004
编号 2725
注册 2003-11-30
#20
发表于 2004-9-6 23:13 资料 文集 短消息 只看该作者
周瑜的算法应该是比较完善了。
顶部
性别:男-离线 god_wolf

Rank: 4
组别 士兵
级别 牙门将军
功绩 5
帖子 521
编号 6045
注册 2004-3-16
#21
发表于 2004-9-7 00:57 资料 主页 短消息 只看该作者
不错,不错.
顶部
性别:男-离线 重阳

高阳侯光禄大夫

Rank: 12Rank: 12Rank: 12
组别 翰林学士
级别 前将军
好贴 2
功绩 585
帖子 1775
编号 50
注册 2003-8-21
#22
发表于 2004-9-7 13:12 资料 主页 文集 短消息 只看该作者
这个题目还真不是一般的难。

周瑜的程序计算出的结果是相当好了，但其中假设n和m均为0.5的整数倍，而没有证明，应该还只是一个近似的结果。
考虑了一下5桶油（含车内的）的情况，如果按此假设，最多可走280公里，但如先用1.4桶油，结果可走281.33公里。

估计这个问题没有什么好的算法，不同的油数计算起来差别相当大。
顶部
性别:未知-离线 空度

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 仁勇校尉
功绩 2
帖子 171
编号 16844
注册 2004-9-1
#23
发表于 2004-9-7 22:10 资料 短消息 只看该作者
149.01 13.5
195.16 07.5

周瑜的这步算法为什么不是

149.01 13.5
199.01 07.0
顶部
性别:男-离线 周瑜

栎阳侯谏议大夫
★

Rank: 16
组别 翰林学士
级别 征西将军
好贴 10
功绩 943
帖子 4716
编号 1808
注册 2003-11-3
家族 瓦岗寨
#24
发表于 2004-9-7 23:18 资料 主页 文集 短消息 只看该作者


QUOTE:
原帖由空度于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

Rank: 4
组别 士兵
级别 牙门将军
功绩 5
帖子 521
编号 6045
注册 2004-3-16
#25
发表于 2004-9-8 01:01 资料 主页 短消息 只看该作者
这题难就难在只能靠比较得出最大。要是谁能用数学方法证明如何取最佳就好了。
顶部

正在浏览此帖的会员 - 共 1 人在线




当前时区 GMT+8, 现在时间是 2024-11-22 01:22
京ICP备2023018092号 轩辕春秋 2003-2023 www.xycq.org.cn

Powered by Discuz! 5.0.0 2001-2006 Comsenz Inc.
Processed in 0.015195 second(s), 10 queries , Gzip enabled
TOP

清除 Cookies - 联系我们 - 轩辕春秋 - Archiver - WAP