作者:年少不轻易谈情 | 来源:互联网 | 2023-08-17 18:05
详细问题描述如下:有一辆吉普车要穿越一个沙漠,路程是1000KM,但是这辆车最高只能携带500L的油(1L油跑1KM)。由于沙漠中没有加油站,于是先要用这辆车在沙漠中建立临时加油站。
详细问题描述如下:
有一辆吉普车要穿越一个沙漠,路程是1000KM,但是这辆车最高只能携带500L的油(1L油跑1KM)。由于沙漠中没有加油站,于是先要用这辆车在沙漠中建立临时加油站。
请问,要在什么地方建立临时加油站?每个临时加油站要存多少油才能使吉普车穿越沙漠“所消耗的油最少”?最少消耗多少L油?
如何用C语言程序实现?
敬请前辈给出“解题思路”以及“源码”~谢谢~ :)
10 个解决方案
最后到终点肯定是刚到终点的时候油就没有了
那么在离终点500KM远的地方有一个加油站
考虑这个加油站,到达这个加油站的时候车上剩的油 + 这个加油站里的油 = 500L
再前面一个加油站 到这个加油站的时候车上剩的油 + 这个加油站里的油 - 这个加油站到上面加油站的路程 = 到下一个加油站剩的油
...
第一个加油站 车上油为0 加油站里的油为无穷大
还有条件 就是第二个加油站里的油量 = 500 - 第一个加油站的距离 * 2 > 0
第三个加油站里的油量 = 500 + 第二个加油站里的油量- 第三个加油站到第一个加油站的距离*2 > 0
再分析一下就OK
http://topic.csdn.net/t/20030304/17/1490855.html
吉普车穿越沙漠问题
一、问题
一辆吉普车来到1000km宽的沙漠边沿。吉普车的耗油量为1L/km,总装油量为500L。显然,吉普车必须用自身油箱中的油在沙漠中设几个临时加油点,否则是通不过沙漠的。假设在沙漠边沿有充足的汽油可供使用,那么吉普车应在哪些地方、建多大的临的加油点,才能以最少的油耗穿过这块沙漠?
二、问题分析
本题是一个极值问题,要求具有最小的油耗。因此,它的解是唯一的。吉普车在沙漠中建临时油库,是逐步向前推进的,即建好一个油库后,再建下一个油库。为使油耗最小应做到:
(1)每次吉普车出发时都应满载,放下一部分油再返回时,油恰好用完,并且把下一 个油库建好后这个油库中的油恰好用完。所以每个点的油库中的油都应是吉普车装油量的整数倍(因为出发时满载),即500Xk(k为正整数),并且每个点的存油量为下一个点的存油量及吉普车为建立下个油库在两点之间往返的油耗之和 (下一个油库建成,前一个油库中的油恰好用完)。
(2)吉普车为建立下一个油库运油次数应最少。
用递推法解这个题,可由一个点的存油量推出相邻的另一个点的存油量及两点之 间的距离。但正推是不可能的,因为第一个点的存油量及其距A的距离尚无法确定。但是可推得最后一个点Cl的存油量应为500L,它与B相距为500km,这样吉普车从Cl到达B恰好跑一趟B。递推必须由已知的初始条件开始。为此本题应使用倒推法。图2-7为这一倒推过程的示意图。图中A为起始点,B为终点,C1,
C1,…,Cn分别为倒数第1,2,…,n个临时油库点。
由于B点无需储油,吉普车只须从Cl到达B即可,所以C1点的存油量应为500L,C1到B的距离为500km。为向Cl送500L油,吉普车最少要满载出发两次(若一趟,因途中要耗油而不可能),往返共三程(应为奇数)。考虑最少油耗,C:点应存油2'500L。由此可得如下关系:
v2=3*x2+500=2*500
x2=500/3
C:距B的路程为:
d2=dl+x2=500+500/3=(1+1/3)*500
为向C:送1000L油,吉普车最少要满载出发3次,往返共5趟。考虑最少油耗,C,点应存油3*500L。由此可得:
v3=5*x3+v2=3*500
x3=500/5
d3=d2+x3=(1+1/3+1/5)*500
同理可知,对倒数第i个点有:
Vi=(2*i-1)Xi+Vi-1=i*500 —
Xi=500/(2*i—1) :
Di=di-1+xi=(1+1/3+1/5+…1/(2*i-1))*500
递推到di≥1000时结束。当di≥1000时,Ci-1就是倒数最后一个油库点。它距A的距离为1000—di-l。
感谢7楼 lights_joy 前辈的详细赐教~ :)