2011年計算機等級考試二級C輔導實例編程(2)

　　汽車加油問題之貪心算法

　　(一) 問題描述

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

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

　　(二) 問題分析(前提行駛前車里加滿油)

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

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

　　2.始點到終點的距離大于N，

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

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

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

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

　　(三)算法描述

　　貪心算法的基本思想

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

　　貪心算法的適用的問題

　　貪心算法適用的問題必須滿足兩個屬性：

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

　　(2) 最優(yōu)子結構：問題的整體最優(yōu)解包含著它的子問題的最優(yōu)解。

　　貪心算法的基本步驟

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

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

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

　　2011計算機等級二級C語言五套模擬試題及答案

　　計算機等級考試二級C語言歷年真題匯總(2005-2010)

　　2011年計算機等級考試二級C語言常見問題匯總

　　計算機等級考試二級C語言常見知識點總結