一、問題描述

??一輛吉普車來到1000km寬的沙漠邊沿。吉普車的耗油量為1L／km，總裝油量為500L。顯然，吉普車必須用自身油箱中的油在沙漠中設幾個臨時 加油點，否則是通不過沙漠的。假設在沙漠邊沿有充足的汽油可供使用，那么吉普車應在哪些地方、建多大的臨的加油點，才能以最少的油耗穿過這塊沙漠?

二.問題分析

1.為使油量消耗最少：每次出發的時候，汽車的裝油量必須裝滿，所以每一個加油點的存油量都是汽車總裝油量500L的整數倍，即500k

2.從終點倒推考慮：如果從開始點考慮的話，由于很難確定它的第一個加油點的位置，所以我們從終點出發，因為要使油耗最少，所以最后一個加油站設置的位置在距離終點500km的位置，這樣最后一次剛好走完整個沙漠。

圖示如下：

第一次： c1?= 500L（指的是c1至少要存儲500L） 距B為500KM

?

現在我們知道了倒數第一個加油點的位置，該加油點必須存儲500L的油量(即k的值為1)，要從倒數第二個加油點傳送500L油量給倒數第一個加油點，至少要傳送兩次才行（因為汽車往返要耗油，每次不能直接傳500L），假設倒數第二個加油點到倒數第一個加油點的距離為Xkm,傳送兩次，汽車從倒數第二個加油點傳油到倒數第一個加油點需要行走3倍的x距離（即3xkm），車子耗油量也是3x L，由于還要傳送500L油，所以倒數第二個加油點的存油至少500+3X L,又由于每一個加油點的存量必須是500的k倍且要保證汽車油耗最少，所以取k=2，即倒數第二個加油點的存油為1000L,所以500+3x=500*2,可以得出X=500/3 km

倒數第二個加油點到倒數第一個加油點的距離為x=500/3 ，圖示如下：

第二次：c2 =3 * X+c1= 2 * 500 ==> X = 500/3，距B為 (1+1/3) * 500 KM

現在計算倒數第三個加油點到倒數第二個加油點的距離，跟上面求解步驟一樣，假設倒數第三個加油點到倒數第二個加油點的距離為Xkm，要從倒數第三個加油點傳送1000L油量給倒數第二個加油點，至少要傳三次才行，汽車從倒數第三個加油點傳油到倒數第二個加油點需要行走5倍的x距離（即5xkm），車子耗油量也是5x L，由于還要傳送1000L油，所以倒數第三個加油點的存油至少1000+5X L，所以k=3，即1000+5x=500*3，所以倒數第三個加油點到倒數第二個加油點的距離為x=500/5?，倒數第三個加油點到倒數第一個加油點的距離為x=500/5，以此類推

?

第i次：ci?= (2i-1)xi+ Ci-1?= i * 500 ==> x = (Ci-Ci-1) / (2*i - 1)=500 / (2*i - 1);

三. c語言源碼

#include <stdio.h> int main() {double dis = 500,oil=500; //油量和距離終點的距離int k = 1; //初始倍數為1//因為不確定循環次數，又至少做一次，所以我們用do_whiledo{printf("儲油點%d：距離出發點%.2lf,",k,1000-dis); //距離開始點的距離 printf("儲油量%d\n",(int)oil);k = k+1; //倍數dis = dis +500.00/(2*k-1); //dis是距離終點的距離oil = 500*k; //為倒數第一個加油點以及每個加油點的儲油量}while(dis<1000);printf("儲油點%d：距離出發點%d,儲油量%.2lf L\n",k,0,oil);// 由于總距離超過了1000km,需要重新計算第一個加油點到出發點的距離，從而得出開始點的實際的儲油量dis=dis-500.00/(2*k-1); //減去最后一次汽車的距離，得出前n-1個加油點需要的總量// 計算總耗油量=前k-1個加油點需要的油量+第一個加油點到出發點的距離（即油量）oil = 500.00*(k-1)+(1000-dis)*(2*k-1);printf("\n計算實際需要出發點的儲油量:\n");printf("儲油點%d：距離出發點%d,儲油量%.2lf L\n",k,0,oil);return 0; }

運行結果：

?

總結

以上是生活随笔為你收集整理的汽车穿越沙漠的算法问题（反推法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。