汽車加油問(wèn)題之貪心算法

　　(一) 問(wèn)題描述

　　一輛汽車加滿油后可以行駛N千米。旅途中有若干個(gè)加油站。指出若要使沿途的加油次數(shù)最少，設(shè)計(jì)一個(gè)有效的算法，指出應(yīng)在那些加油站�？考佑汀�

　　給出N，并以數(shù)組的形式給出加油站的個(gè)數(shù)及相鄰距離，指出若要使沿途的加油次數(shù)最少，設(shè)計(jì)一個(gè)有效的算法，指出應(yīng)在那些加油站停靠加油。要求：算法執(zhí)行的速度越快越好。

　　(二) 問(wèn)題分析(前提行駛前車?yán)锛訚M油)

　　對(duì)于這個(gè)問(wèn)題我們有以下幾種情況：設(shè)加油次數(shù)為k，每個(gè)加油站間距離為a[i];i=0，1，2，3……n

　　1.始點(diǎn)到終點(diǎn)的距離小于N，則加油次數(shù)k=0;

　　2.始點(diǎn)到終點(diǎn)的距離大于N，

　　A 加油站間的距離相等，即a[i]=a[j]=L=N，則加油次數(shù)最少k=n;

　　B 加油站間的距離相等，即a[i]=a[j]=L>N，則不可能到達(dá)終點(diǎn);

　　C 加油站間的距離相等，即a[i]=a[j]=L

　　D 加油站間的距離不相等，即a[i]!=a[j]，則加油次數(shù)k通過(guò)以下算法求解。

　　(三)算法描述

　　貪心算法的基本思想

　　該題目求加油最少次數(shù)，即求最優(yōu)解的問(wèn)題，可分成幾個(gè)步驟，一般來(lái)說(shuō)，每個(gè)步驟的最優(yōu)解不一定是整個(gè)問(wèn)題的最優(yōu)解，然而對(duì)于有些問(wèn)題，局部貪心可以得到全局的最優(yōu)解。貪心算法將問(wèn)題的求解過(guò)程看作是一系列選擇，從問(wèn)題的某一個(gè)初始解出發(fā)，向給定目標(biāo)推進(jìn)。推進(jìn)的每一階段不是依據(jù)某一個(gè)固定的遞推式，而是在每一個(gè)階段都看上去是一個(gè)最優(yōu)的決策(在一定的標(biāo)準(zhǔn)下)。不斷地將問(wèn)題實(shí)例歸納為更小的相似的子問(wèn)題，并期望做出的局部最優(yōu)的選擇產(chǎn)生一個(gè)全局得最優(yōu)解。

　　貪心算法的適用的問(wèn)題

　　貪心算法適用的問(wèn)題必須滿足兩個(gè)屬性：

　　(1) 貪心性質(zhì)：整體的最優(yōu)解可通過(guò)一系列局部最優(yōu)解達(dá)到，并且每次的選擇可以依賴以前做出的選擇，但不能依賴于以后的選擇。

　　(2) 最優(yōu)子結(jié)構(gòu)：?jiǎn)栴}的整體最優(yōu)解包含著它的子問(wèn)題的最優(yōu)解。

　　貪心算法的基本步驟

　　(1) 分解：將原問(wèn)題分解為若干相互獨(dú)立的階段。

　　(2) 解決：對(duì)于每一個(gè)階段求局部的最優(yōu)解。

　　(3) 合并：將各個(gè)階段的解合并為原問(wèn)題的解。

　　2011計(jì)算機(jī)等級(jí)二級(jí)C語(yǔ)言五套模擬試題及答案

　　計(jì)算機(jī)等級(jí)考試二級(jí)C語(yǔ)言歷年真題匯總(2005-2010)

　　2011年計(jì)算機(jī)等級(jí)考試二級(jí)C語(yǔ)言常見問(wèn)題匯總

　　計(jì)算機(jī)等級(jí)考試二級(jí)C語(yǔ)言常見知識(shí)點(diǎn)總結(jié)