Question

C语言描述的算法

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

Answer 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；