汽車加油問題試驗報告

1、一、實驗名稱 ：用貪心算法解決汽車加油次數(shù)最少問題。二、實驗?zāi)康模阂惠v汽車加滿油后 ,可行使 n 千米。旅途中有若干個加油站。 若要使沿途加油次數(shù)最少，設(shè)計一個有效算法，對于給定的n和k個加油 站位置，指出應(yīng)在哪些加油站?？考佑筒拍苁辜佑痛螖?shù)最少。輸入數(shù)據(jù) 中，第一行有 2 個正整數(shù)，分別表示汽車加滿油后可行駛 n 千米，且旅 途中有 k 個加油站。接下來的 1 行中，有 k+1 個整數(shù)，表示第 k 個加油 站與第 k-1 個加油站之間的距離。第 0 個加油站表示出發(fā)地，汽車已加 滿油。第 k+1 個加油站表示目的地。輸出為最少的加油次數(shù)，如果無法 到達(dá)目的地，則輸出“ No Solution

2、 ”。實驗提示：把兩加油站的距離放在數(shù)組中， a1.k 表示從起始位置開始跑， 經(jīng) 過k個加油站，ai表示第i 1個加油站到第i個加油站的距離。汽車 在運行的過程中如果能跑到下一個站則不加油，否則要加油。輸入數(shù)據(jù)示例7 71 2 3 4 5 1 6 6輸出數(shù)據(jù)4三、使用的策略：貪心算法、回溯算法等。四、實驗內(nèi)容：（一）問題描述一輛汽車加滿油后可以行駛 N千米。旅途中有若干個加油站。指出若要使沿 途的加油次數(shù)最少，設(shè)計一個有效的算法，指出應(yīng)在那些加油站?？考佑?。給出N，并以數(shù)組的形式給出加油站的個數(shù)及相鄰距離，指出若要使沿途的加0 1 2油次數(shù)最少，設(shè)計一個有效的算法，指出應(yīng)在那些加油站?？考佑?/p>

3、。要求：算法執(zhí) 行的速度越快越好。（二）問題分析（前提行駛前車?yán)锛訚M油）對于這個問題我們有以下幾種情況：設(shè)加油次數(shù)為k,每個加油站間距離為 ai;i=0 , 1 , 2 , 3n1始點到終點的距離小于N,則加油次數(shù)k=0 ；2始點到終點的距離大于 N ,i=aj=L=N，則加油次數(shù)最少 k=n ;i=aj=L>N，則不可能到達(dá)終點;i=aj=L<N，則加油次數(shù) k= n/N（n%N=O）i! =aj，則加油次數(shù) k通過以下算法求A力啪站間的距離相等，即aB力啪站間的距離相等，即aC力啪站間的距離相等，即a或 k=n/N+1（n%N ! =0）;D力啪站間的距離不相等，即 解。（三）

4、算法描述1.貪心算法解決方案貪心算法的基本思想該題目求加油最少次數(shù)，即求最優(yōu)解的問題，可分成幾個步驟，一般來說，每 個步驟的最優(yōu)解不一定是整個問題的最優(yōu)解，然而對于有些問題，局部貪心可以得到全局的最優(yōu)解。貪心算法將問題的求解過程看作是一系列選擇，從問題的某一個初始解出發(fā)，向給定目標(biāo)推進(jìn)。推進(jìn)的每一階段不是依據(jù)某一個固定的遞推式，而是在每一個階段都看上去是一個最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。不斷地將問題實 例歸納為更小的相似的子問題，并期望做出的局部最優(yōu)的選擇產(chǎn)生一個全局得最優(yōu) 解。貪心算法的適用的問題貪心算法適用的問題必須滿足兩個屬性：（1）貪心性質(zhì)：整體的最優(yōu)解可通過一系列局部最優(yōu)解達(dá)到，并且

5、每次的 選擇可以依賴以前做出的選擇，但不能依賴于以后的選擇。（2）最優(yōu)子結(jié)構(gòu)：問題的整體最優(yōu)解包含著它的子問題的最優(yōu)解。貪心算法的基本步驟(1)分解：將原問題分解為若干相互獨立的階段。(2)解決：對于每一個階段求局部的最優(yōu)解。(3)合并：將各個階段的解合并為原問題的解。 問題分析 由于汽車是由始向終點方向開的 , 我們最大的麻煩就是不知道在哪個加油站加 油可以使我們既可以到達(dá)終點又可以使我們加油次數(shù)最少。提出問題是解決的開始.為了著手解決遇到的困難,取得最優(yōu)方案。我們可以假設(shè)不到萬不得已我們不加油， 即除非我們油箱里的油不足以開到下一個加油站， 我 們才加一次油。 在局部找到一個最優(yōu)的解。 卻

6、每加一次油我們可以看作是一個新的 起點， 用相同的遞歸方法進(jìn)行下去。 最終將各個階段的最優(yōu)解合并為原問題的解得 到我們原問題的求解。加油站貪心算法設(shè)計( C )：include<math.h>include<studio.h>int add(int b ,int m,int n) /求一個從 m 到 n 的數(shù)列的和int sb;for(int i=m;i<n;i+) sb+=bi;return sb;int Tanxin(int an, int N) /an 表示加油站的個數(shù)， N 為加滿油能行駛的最遠(yuǎn) 距離int bn;若在ai加油站加油，則 bi為1，否則為0

7、int m=0;if(ai>N) return ERROR;/如果某相鄰的兩個加油站間的距離大于N,則不能到達(dá)終點if(add(ai, 0, n)<N) /如果這段距離小于N,則不需要加油bi=0;return add(bi,0,n);if(ai=aj&&ai=N) /如果每相鄰的兩個加油站間的距離都是N ，則每個加油站都需要加油bi=1;return add(bi,0,n);if(ai=aj&&ai<N) / 如果每相鄰的兩個加油站間的距離相等且都小于Nif( add(ai,m,k) < N && add(ai,m,k+

8、1) > N )bk=1;m+=k;return add(bi,0,n);if(ai!=aj) / 如果每相鄰的兩個加油站間的距離不相等且都小于Nif( add(ai,m,k) < N && add(ai,m,k+1) > N )bk=1;m+=k;return add(bi,0,n);viod main( )int a ;scanf("%d",a);scanf("/n");scanf("/d",&N);Tanxin(a ,0,n);貪心算法正確性證明：貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題

9、的整體最優(yōu)解可以通過一系列局部最優(yōu)的選 擇，即貪心選擇來達(dá)到。對于一個具體的問題，要確定它是否具有貪心性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問題的一個整體最優(yōu)解。該題設(shè)在加滿油后可行駛的 N千米這段路程上任取兩個加油站A、E，且A距離始點比E距離始 點近，則若在E加油不能到達(dá)終點那么在A加油一定不能到達(dá)終點，如圖：由圖知：因為m+N<n+N ,即在B點加油可行駛的路程比在A點加油可行駛的路程要長n-m千米，所以只要終點不在B、C之間且在C的右邊的話，根據(jù)貪心選擇，為使加油次數(shù)最少就會選擇距離加滿油得點遠(yuǎn)一些的加油站去加油，因此，加油次數(shù)最少滿足貪心選擇性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)一個

10、問題大的最優(yōu)解包含著它的子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。由于(b1,b2,bn)是這段路程加油次數(shù)最少的一個滿足貪心選擇 性質(zhì)的最優(yōu)解，則易知若在第一個加油站加油時，b1=1,則(b2,b3,bn)是從a2到an這段路程上加油次數(shù)最少且這段路程上的加油站個數(shù)為 (a2,a3,an)的最優(yōu)解，即每次汽車中剩下的油不能在行駛到下一個加油站 時我們才在這個加油站加一次油，每個過程從加油開始行駛到再次加油滿足貪心且每一次加油后相當(dāng)于與起點具有相同的條件，每個過程都是相同且獨立，也就是說加油次數(shù)最少具有最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心算法時間復(fù)雜度分析由于若想知道該在哪個加油站加油就必須遍歷所有的加油站，且不需要重復(fù)遍歷，所以時間復(fù)雜度為0( n)。五、實驗心得：在貪心算法中，每次做出的選擇僅在當(dāng)前的狀態(tài)下做出的最好的選擇，即局部 最優(yōu)選擇。然后再去解做出這個選擇后產(chǎn)生的相應(yīng)的子問題。