C语言描述的算法各位大哥给你们复习或练手的时候到了\*^_^*/1) 一辆吉普车穿越1000千米的沙漠.吉普车的总装油量为500加仑,耗油率为1加仑/千米.由于沙漠中没有油库,必须先用这辆车在沙漠中

来源:学生作业帮助网 编辑:作业帮 时间:2024/03/29 22:22:48
C语言描述的算法各位大哥给你们复习或练手的时候到了\*^_^*/1) 一辆吉普车穿越1000千米的沙漠.吉普车的总装油量为500加仑,耗油率为1加仑/千米.由于沙漠中没有油库,必须先用这辆车在沙漠中

C语言描述的算法各位大哥给你们复习或练手的时候到了\*^_^*/1) 一辆吉普车穿越1000千米的沙漠.吉普车的总装油量为500加仑,耗油率为1加仑/千米.由于沙漠中没有油库,必须先用这辆车在沙漠中
C语言描述的算法
各位大哥给你们复习或练手的时候到了\*^_^*/1) 一辆吉普车穿越1000千米的沙漠.吉普车的总装油量为500加仑,耗油率为1加仑/千米.由于沙漠中没有油库,必须先用这辆车在沙漠中建立临时油库.偌吉普车用最少的耗油量穿越沙漠,应在哪些地方建立油库,以及各处存储的油量.2) 在m*n的棋盘中,马只能走日字.马从位置(x,y)初处出发,把棋盘的每一个点都走一次,且只走一次,找处所有路径.

C语言描述的算法各位大哥给你们复习或练手的时候到了\*^_^*/1) 一辆吉普车穿越1000千米的沙漠.吉普车的总装油量为500加仑,耗油率为1加仑/千米.由于沙漠中没有油库,必须先用这辆车在沙漠中

第一题:

设Way[i]——第i个贮油点到终点(i=0)的距离;

oil[i]——第i个贮油点的贮油量;

我们可以用倒推法来解决这个问题.从终点向始点倒推,逐一求出每个贮油点的位置及存油量.

从贮油点i向贮油点i+1倒推的方法是:吉普车在贮油点i和贮油点i+1间往返若干次.吉普车每次返回i+1点时应该正好耗尽500加仑汽油,而每次从i+1点出发时又必须装足500加仑汽油.两点之间的距离必须满足在耗油最少的条件下,使i点贮足i*500加仑汽油的要求(0≦i≦n-1).

第一个贮油点i=1应距终点i=0处500km,且在该点贮藏500加仑汽油,这样才能保证吉普车能由i=1处到达终点i=0处,这就是说

Way[1]=500;oil[1]=500;

为了在i=1处贮藏500加仑汽油,吉普车至少从I=2处开两趟满载油的车至i=1处,所以i=2处至少贮有2*500加仑汽油,即oil[2]=500*2=1000;另外,再加上从i=1返回至i=2处的一趟空载,合计往返3次.三次往返路程的耗油量按最省要求只能为500加仑,即d1,2=500/3km,Way[2]=Way[1]+d1,2=Way[1]+500/3

为了在I=2处贮藏1000加仑汽油,吉普车至少从I=3处开三趟满载油的车至I=2处.所以I=3处至少贮有3*500加仑汽油,即oil[3]=500*3=1500.加上I=2至I=3处的二趟返程空车,合计5次.路途耗油亦应500加仑,即d23=500/5,

Way[3]=Way[2]+d2,3=Way[2]+500/5;