day2基礎(chǔ)算法-曹利國-noip培訓(xùn)

根底算法策略長沙市第一中學(xué)曹利國算法效率的評價

算法的評估

有時求解同一個問題常常有多種可用的算法，在一定的條件下當(dāng)然要選擇使用好的算法。用什么方法評估算法的好壞呢？通常使用算法復(fù)雜性這一概念來評估算法。

算法評價

算法執(zhí)行時間需通過依據(jù)該算法編制的程序在計算機上運行時所消耗的時間來度量。而度量一個程序的執(zhí)行時間通常有兩種方法：

事后統(tǒng)計的方法

事前分析估算的方法

算法評價

一個用高級程序語言編寫的程序在計算機上運行時所消耗的時間取決于以下因素： ① 依據(jù)的算法選用何種策略； ② 問題的規(guī)模.例如求100以內(nèi)還是1000以內(nèi)的素數(shù)； ③ 書寫程序的語言.對于同一個算法,實現(xiàn)語言的級別越高,執(zhí)行效率就越低； ④ 編譯程序所產(chǎn)生的機器代碼的質(zhì)量； ⑤ 機器執(zhí)行指令的速度。算法評價

一個算法是由控制結(jié)構(gòu)〔順序、分支和循環(huán)三種〕和原操作〔指固有數(shù)據(jù)類型的操作〕構(gòu)成的，那么算法時間取決于兩者的綜合效果。為了便于比較同一問題的不同算法，通常的做法是，從算法中選取一種對于所研究的問題〔或算法類型〕來說是根本運算的原操作，以該根本操作重復(fù)執(zhí)行的次數(shù)作為算法的時間度量。算法評價

一般情況下，算法中根本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f〔n〕，算法的時間量度記作T〔n〕=O〔f〔n〕〕它表示問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f〔n〕的增長率相同，稱作算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度。算法評價

例如：在以下三個程序段中， ① x:=x+1 ② fori:=1tondox:=x+1; ③ forj:=1tondo fork:=1tondox:=x+1含根本操作“x增1”的語句x:=x+1的頻度分別為1，n和n2，那么這三個程序段的時間復(fù)雜度分別為O〔1〕，O〔n〕，O〔n2〕，分別稱為常量階、線性階和平方階。算法評價

算法還可能呈現(xiàn)的時間復(fù)雜度有：對數(shù)階O〔logn〕，指數(shù)階O〔2n〕等。在n很大時,不同數(shù)量級時間復(fù)雜度顯然有O〔1〕<O〔logn〕<O〔n〕<O〔nlogn〕<O〔n2〕<O〔n3〕<O〔2n〕，可以看出，在算法設(shè)計時，我們應(yīng)該盡可能選用多項式階O(nk)的算法，而不希望用指數(shù)階的算法。算法評價

由于算法的時間復(fù)雜度考慮的只是對于問題規(guī)模n的增長率，那么在難以計算根本操作執(zhí)行次數(shù)(或語句頻度)的情況下，只需求出它關(guān)于n的增長率或階即可。 例如，在以下程序段中： fori:=2tondo forj:=2toi-1dox:=x+1語句x:=x+1執(zhí)行次數(shù)關(guān)于n的增長率為n2，它是語句頻度表達式(n-1)(n-2)/2中增長最快的一項。算法評價

類似于算法的時間復(fù)雜度，以空間復(fù)雜度作為算法所需存儲空間的量度，記作 S(n)=O(f(n))其中n為問題的規(guī)模(或大小)。一個上機執(zhí)行的程序除了需要存儲空間來存放本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對數(shù)據(jù)進行操作的工作單元和存儲一些為實現(xiàn)計算所需信息的輔助空間。算法評價

評價一個數(shù)學(xué)模型有以下幾個原那么：1.時間復(fù)雜度一個好的算法一般效率比較高。在競賽中，試題常常會做一些算法運行時間上的限制。這就要求我們所建立的數(shù)學(xué)模型對應(yīng)算法的效率一定要符合要求。這也是最重要的一個原那么。算法評價

2.空間復(fù)雜度出于計算機自身的限制，程序在運行時一般只被提供有限的內(nèi)存空間。這也就要求我們建立模型時顧及到這一點。但對于模型對應(yīng)的算法來說，并不是要求空間越低越好，只要不超過內(nèi)存限制就可以了。

算法評價

3.編程復(fù)雜度相對而言，“編程復(fù)雜度”的要求要略低一些。但是在競賽中，如果建立的算法實現(xiàn)起來十分繁瑣，自然不利于比賽。所以，在建立模型時〔特別是在競賽中〕這點也要納入考慮之中。算法評價

一道題目可能對應(yīng)幾種不同思想的模型，就要根據(jù)評價模型的標(biāo)準(zhǔn)來衡量一下，確定一個模型作為分析方向。這時的評價標(biāo)準(zhǔn)除了上述的時間、空間、編程復(fù)雜度三個標(biāo)準(zhǔn)外，還要加上一個思維的復(fù)雜度。

算法評價

所謂思維的復(fù)雜度，是指思考所消耗的時間和精力。如果我們確定了一個模型作為分析的方向〔沒有考慮思維復(fù)雜度〕，從問題原型到該數(shù)學(xué)模型的建模過程卻十分復(fù)雜，導(dǎo)致思維消耗時間長，精力多，那自然是不合算的?？偟膩碚f，對于多種數(shù)學(xué)模型的選擇，我們遵循“邊分析，邊選擇”的原那么。影響算法效率的因素問題的算法模型的建立問題的數(shù)據(jù)結(jié)構(gòu)選擇第一局部枚舉策略枚舉策略的根本思想枚舉法，又稱窮舉法，指在一個有窮的可能的解的集合中，一一枚舉出集合中的每一個元素，用題目給定的檢驗條件來判斷該元素是否符合條件，假設(shè)滿足條件，那么該元素即為問題的一個解；否那么，該元素就不是該問題的解。枚舉策略的根本思想枚舉方法也是一種搜索算法，即對問題的所有可能解的狀態(tài)集合進行一次掃描或遍歷。在具體的程序?qū)崿F(xiàn)過程中，可以通過循環(huán)和條件判斷語句來完成。枚舉法常用于解決“是否存在”或“有多少種可能”等類型的問題。例如，求解不定方程的問題就可以采用列舉法。

雖然枚舉法本質(zhì)上屬于搜索策略，但是它與回溯法有所不同。因為適用枚舉法求解的問題必須滿足兩個條件：

⑴可預(yù)先確定每個狀態(tài)的元素個數(shù)n；⑵狀態(tài)元素a1，a2，…，an的可能值為一個連續(xù)的值域。設(shè)

ai1—狀態(tài)元素ai的最小值；aik—狀態(tài)元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ankfora1←a11toa1kdofoa2←a21toa2kdo……forai←ai1toaikdo……foran←an1toankdoif狀態(tài)(a1，…，ai，…，an)滿足檢驗條件then輸出問題的解；枚舉策略的根本思想枚舉法的特點是算法比較簡單，在用枚舉法設(shè)計算法時，重點注意優(yōu)化，減少運算工作量。將與問題有關(guān)的知識條理化、完備化、系統(tǒng)化，從中找出規(guī)律，減少枚舉量。枚舉方法的優(yōu)化枚舉算法的時間復(fù)雜度：狀態(tài)總數(shù)*單個狀態(tài)的耗時主要優(yōu)化方法：⑴減少狀態(tài)總數(shù)⑵降低單個狀態(tài)的考察代價優(yōu)化過程從以下幾個方面考慮：⑴枚舉對象的選?、泼杜e方法確實定⑶采用局部枚舉或引進其他算法巧妙填數(shù)將1～9這九個數(shù)字填入九個空格中。每一橫行的三個數(shù)字組成一個三位數(shù)。如果要使第二行的三位數(shù)是第一行的兩倍,第三行的三位數(shù)是第一行的三倍,應(yīng)怎樣填數(shù)。如圖192384576分析此題目有9個格子，要求填數(shù)，如果不考慮問題給出的條件，共有9！=362880種方案，在這些方案中符合問題條件的即為解。因此可以采用枚舉法。但仔細(xì)分析問題，顯然第一行的數(shù)不會超過400，實際上只要確定第一行的數(shù)就可以根據(jù)條件算出其他兩行的數(shù)了。這樣僅需枚舉400次。算式設(shè)有以下的算式：208-------------□□)□□□□□□-------------□□□□□□-------------1要求：求出□中的數(shù)字，并打印出完整的算式。枚舉方法的優(yōu)化【分析】此題找不到很好的方法，于是考慮枚舉法。此題中，待填數(shù)字的空格共有14個，每個格子中都可填0..9這10個數(shù)字。假設(shè)對14個格子都進行0..9十個數(shù)字逐一枚舉，枚舉量是1014，不可能在指定的時間內(nèi)得出結(jié)果。優(yōu)化方法：減少枚舉量，找出適當(dāng)?shù)脑剡M行枚舉。枚舉方法的優(yōu)化由數(shù)學(xué)知識知道，在除法中只要知道被除數(shù)、除數(shù)、商和余數(shù)中的任意三局部就可以求得第四局部。此題商和余數(shù)，只要知道被除數(shù)或除數(shù)，整個算式也就確定下來了。而被除數(shù)和除數(shù)，分別是4位數(shù)和2位數(shù)。我們只需枚舉除數(shù)。枚舉量降為102=100，這個時間復(fù)雜度是完全可以承受的。方格填數(shù)方格填數(shù)問題。如下圖形狀的八個方格中填入1-8這八個數(shù)字，使得相鄰的和對角線上的數(shù)字之差不為1，編程求解所有的填法方案和總數(shù)。B1B2B3B4B5B6B7

B8【分析】將1至8填入到B1至B8中，總共有8?。?0320種填法。該問題的枚舉總量為8！個。由于B3和B6這兩個方格與其相鄰的格子共有6個，放入這兩個格子中的數(shù)，必須和六個數(shù)不連續(xù)，這樣的兩個數(shù)只有1和8。B1，B3，B6，B8這四個格子中僅僅有兩種可能放法，即：2，8，1，7和7，1，8，2。挖掘出這一隱含條件之后，B2，B4，B5，B7四個格子中的數(shù)就只能從3，4，5，6這四個數(shù)中進行選擇，整個問題的枚舉總量將變得只有2＊4?。?8種，從而大大地減少了枚舉量，提高枚舉效率。枚舉方法的優(yōu)化枚舉算法的應(yīng)用二進制數(shù)的分類假設(shè)將一個正整數(shù)轉(zhuǎn)化為二進制數(shù)后，0的個數(shù)多于1的個數(shù)的這類數(shù)稱為A類數(shù)，否那么稱為B類數(shù)。例如：〔13〕10=〔1101〕2，13為B類數(shù)；〔10〕10=〔1010〕210為B類數(shù)；〔24〕10=〔11000〕224為A類數(shù)；程序要求：求出1～1000之中〔包括1與1000〕，全部A、B兩類數(shù)的個數(shù)?！痉治觥看祟}是一道統(tǒng)計類題目。解決統(tǒng)計問題的一個常用方法是枚舉法：逐一枚舉所有情況，同時進行統(tǒng)計，枚舉結(jié)束時，統(tǒng)計也完成，得到結(jié)果。具體對此題而言，采用枚舉法的正確性與可行性是顯然的，而此題的數(shù)據(jù)規(guī)模又僅為1～1000，所以采用逐一枚舉方法進行統(tǒng)計的時間復(fù)雜度是完全可以接受的。枚舉算法的應(yīng)用01統(tǒng)計將問題的數(shù)據(jù)規(guī)模擴充到求1到m〔m<=1030〕中A類數(shù)的個數(shù)。分析此題是統(tǒng)計問題，但使用1~m的循環(huán)來逐個判斷顯然耗時過多，對于m較大時無法在規(guī)定的時間內(nèi)出解。所以我們希望通過分類統(tǒng)計的方法，進一步抽象問題，得到可行的算法:根據(jù)二進制數(shù)的前綴來分類是合理的，既沒有重復(fù)也沒有遺漏。當(dāng)m的二進制數(shù)長度為n時，最多有2n種類型，即2〔log2m+1〕種，比窮舉m種類型有了很大進步。設(shè)m=(112)10=(1110000)2，求1~m的A類數(shù)個數(shù)。可以將112個數(shù)分為以下幾類：數(shù)字形式為(111xxxx)2這一類數(shù)只有1個，即(1110000)2，是A類數(shù)數(shù)字形式為(110xxxx)2設(shè)4個填數(shù)位置填0的個數(shù)為S0，填1的個數(shù)為S1，那么S0+S1+3=7,假設(shè)為A類數(shù)，那么S0+1>S1+2,可以取S0=4S1=0；S0=3S1=1.這一類數(shù)中的A類數(shù)個數(shù)：(44)+(34)數(shù)字形式為(10xxxxx)2設(shè)5個填數(shù)位置填0的個數(shù)為S0，填1的個數(shù)為S1，那么S0+S1+2=7假設(shè)為A類數(shù)，那么S0+1>S1+1,可以取S0=5S1=0；S0=4S1=1；S0=3S1=2.這一類數(shù)中的A類數(shù)個數(shù)：(55)+(45)+(35)數(shù)字形式為(0xxxxxx)2這一類數(shù)字的分析與前幾類略有不同，因為前幾類二進制數(shù)的位數(shù)都是7，而這一類數(shù)還需對位數(shù)進行討論：〔1〕1位數(shù)，即(1)2，不是A類數(shù)〔2〕2位數(shù)，即(1x)2，(10)2和(11)2都不是A類數(shù)〔3〕3位數(shù)，即(1xx)2，A類數(shù)個數(shù)為(22)=1〔4〕4位數(shù)，即(1xxx)2，A類數(shù)個數(shù)為(33)=1〔5〕5位數(shù)，即(1xxxx)2，A類數(shù)個數(shù)為(44)+(34)=5〔6〕6位數(shù)，即(1xxxxx)2，A類數(shù)個數(shù)為(55)+(45)=6最后的答案是1+5+16+(1+1+5+6)=35圓桌騎士〔IOI試題〕在一個8*8的棋盤上，有一個國王和假設(shè)干個武士。其中，國王走一字步，騎士走馬步。假設(shè)國王與騎士相會在同一點上，國王可以選擇讓騎士背他走。求一個點，使所有的騎士和國王相距在這個點上的所走的步數(shù)最少。枚舉對象確實定【分析】此題可從3個方面考慮：分治、枚舉、數(shù)學(xué)方法。由于無法將這個問題劃分為各自獨立的小問題來解決，分治顯然是不行的。又因武士和國王位置的不固定性和其走法的差異，推導(dǎo)不出一個數(shù)學(xué)公式。因此考慮使用枚舉，需要枚舉的三個要點：1、最后的會聚點。2、國王與背他的騎士的會聚點。3、國王與背他的騎士。枚舉算法的應(yīng)用國王最多只會與一個騎士結(jié)合，因為騎士的最終目標(biāo)也是最終會聚點，一旦國王與某個騎士集合后，即馬上可與其結(jié)合，剩下的只需要將所有的騎士集合就可以了。更沒有必要在中途中有將國王托付給其他的騎士。這樣我們估算一下時間為O〔8*8*8*8*63〕=O〔36*10^4〕，完全可以承受。另外，我們需要預(yù)先將2點之間走馬字步的距離計算出來?？梢允褂肍loyd或是Bfs。枚舉算法的應(yīng)用算法流程：dis[x1，y1，x2，y2]--〔x1，y1〕〔x2，y2〕之間的距離。ForI：=1to8do{枚舉集合點}Forj：=1to8dobeginAll：=所有騎士到這一點的和；Best:=min(best,all+國王到會聚點的步數(shù))Forx：=1to8do{枚舉武士國王的相會點}Fory：=1to8dobeginForkk：=1tokdo{枚舉與國王結(jié)合的武士}Ifdis[knight[kk].x,knight[kk].y,x,y]<minthenbegin Min:=dis[knight[kk].x,knight[kk].y,x,y]; Mink:=k;End;End；Now:=all-mink武士走到集合點的距離+mink武士走到會聚點的距離+國王走到會聚點的距離+從會聚點到集合點的距離； Best：=min〔best，now〕End；局部枚舉例題：求第一、第二、第三最短路問題局部枚舉例題：新年好重慶城里有n個車站，m條雙向公路連接其中的某些車站。每兩個車站最多用一條公路直接相連，從任何一個車站出發(fā)都可以經(jīng)過一條或多條公路到達其他車站，但不同的路徑需要花費的時間可能不同。在一條路上花費的時間等于路徑上所有公路需要的時間之和。佳佳的家在車站1，他有五個親戚，分別住在車站a,b,c,d,e。過年了，他需要從自己的家出發(fā)，拜訪每個親戚〔順序任意〕，給他們送去節(jié)日的祝福。怎樣走，才需要最少的時間？分析這一題中的邊數(shù)遠小于n2，所以復(fù)雜度也只有nlogn+m算法框架是：〔1〕用5次最短路，計算出6個點兩兩之間的距離〔2〕枚舉5個結(jié)點的全排列，找到一個使得總路程長度最短的方案。第二局部遞推策略遞推的概念與根本思想給定一個數(shù)的序列H0,H1,…,Hn,…假設(shè)存在整數(shù)n0，使當(dāng)n>n0時,可以用等號(或大于號、小于號)將Hn與其前面的某些項Hi(0<i<n)聯(lián)系起來，這樣的式子就叫做遞推關(guān)系。解決遞推問題的一般步驟

建立遞推關(guān)系式確定邊界條件遞推求解

遞推的形式順推法和倒推法遞推的應(yīng)用分類

一般遞推問題組合計數(shù)類問題一類博弈問題的求解動態(tài)規(guī)劃問題的遞推關(guān)系遞推的應(yīng)用〔一般遞推問題〕例題1:Hanoi塔問題.Hanoi塔由n個大小不同的圓盤和三根木柱a,b,c組成。開始時，這n個圓盤由大到小依次套在a柱上，如圖1所示。要求把a柱上n個圓盤按下述規(guī)那么移到c柱上：(1)一次只能移一個圓盤；(2)圓盤只能在三個柱上存放；(3)在移動過程中，不允許大盤壓小盤。問將這n個盤子從a柱移動到c柱上，總計需要移動多少個盤次？abc

圖1遞推的應(yīng)用〔一般遞推問題〕例題1:Hanoi塔問題.Hanoi塔由n個大小不同的圓盤和三根木柱a,b,c組成。開始時，這n個圓盤由大到小依次套在a柱上，如圖1所示。要求把a柱上n個圓盤按下述規(guī)那么移到c柱上：(1)一次只能移一個圓盤；(2)圓盤只能在三個柱上存放；(3)在移動過程中，不允許大盤壓小盤。問將這n個盤子從a柱移動到c柱上，總計需要移動多少個盤次？abc

圖1分析設(shè)hn為n個盤子從a柱移到c柱所需移動的盤次。顯然，當(dāng)n=1時，只需把a柱上的盤子直接移動到c柱就可以了，故h1=1。當(dāng)n=2時，先將a柱上面的小盤子移動到b柱上去；然后將大盤子從a柱移到c柱；最后，將b柱上的小盤子移到c柱上，共記3個盤次，故h2=3。以此類推，當(dāng)a柱上有n(n>=2)個盤子時，總是先借助c柱把上面的n-1個盤子移動到b柱上，然后把a柱最下面的盤子移動到c柱上；再借助a柱把b柱上的n-1個盤子移動到c柱上；總共移動hn-1+1+hn-1個盤次?！鄅n=2hn-1+1

邊界條件：h1=1遞推的應(yīng)用〔一般遞推問題〕例2：實數(shù)數(shù)列一個實數(shù)數(shù)列共有n項，ai=(ai-1-ai+1)/2+d，(1<i<n)(n<60)鍵盤輸入n，d，a1，an，m，輸出am。輸入數(shù)據(jù)均不需判錯。分析根據(jù)公式ai=(ai-1-ai+1)/2+d變形得，ai+1=ai-1-2ai+2d，因此該數(shù)列的通項公式為：ai=ai-2-2ai-1+2d，a1，如果能求出a2，這樣就可以根據(jù)公式遞推求出am∵ai=ai-2-2ai-1+2d……(1) =ai-2-2〔ai-3-2ai-2+2d〕+2d=-2ai-3+5〔ai-4-2ai-3+2d〕-2d=5ai-4-12ai-3+8d……

一直迭代下去，直到最后，可以建立ai和a1與a2的關(guān)系式。分析設(shè)ai=Pia2+Qid+Ria1，我們來尋求Pi,Qi,Ri的變化規(guī)律?！遖i=ai-2-2ai-1+2d∴ai=Pi-2a2+Qi-2d+Ri-2a1-2〔Pi-1a2+Qi-1d+Ri-1a1〕+2d=(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1∴Pi=Pi-2-2Pi-1 ……② Qi=Qi-2-2Qi-1+2 ……③ Ri=Ri-2-2Ri-1 ……④顯然，P1=0Q1=0R1=1〔i=1〕 P2=1Q2=0R2=0 〔i=2〕將初值P1Q1R1和P2Q2R2代入②③④可以求出PnQnRn∵an=Pna2+Qnd+Rna1∴a2=(an-Qnd+Rna1)/Pn然后根據(jù)公式①遞推求出am，問題解決。改進算法但仔細(xì)分析，上述算法有一個明顯的缺陷：在求由于在求a2要運用除法，因此會存在實數(shù)誤差，這個誤差在以后遞推求am的過程又不斷的擴大。在實際中，當(dāng)m超過30時，求出的am就明顯偏離正確值。顯然，這種算法雖簡單但不可靠。為了減少誤差，我們可設(shè)計如下算法：∵ai=Pia2+Qid+Ria1 =Pi-1a3+Qi-1d+Ri-1a2 =Pi-2a4+Qi-2d+Ri-2a3……=Pi-2+kak+Qi-2+kd+Ri-2+kak-1∴an=Pn-k+2ak+Qn-k+2d+Rn-k+2ak-1ak=(an-Qn-k+2d+Rn-k+2ak-1)/Pn-k+2……⑤根據(jù)公式⑤，可以順推a2、a3、…、aM。雖然仍然存在實數(shù)誤差，但由于Pn-k+2遞減，因此最后得出的am要比直接利用公式①精確得多。遞推的應(yīng)用〔一般遞推問題〕例題：貯油點。一輛重型卡車欲穿過1000公里的沙漠，卡車耗汽油為1升/公里，卡車總載油能力為500公升。顯然卡車裝一次油是過不了沙漠的。因此司機必須設(shè)法在沿途建立假設(shè)干個貯油點，使卡車能順利穿過沙漠。試問司機如怎樣建立這些貯油點？每一貯油點應(yīng)存儲多少汽油，才能使卡車以消耗最少汽油的代價通過沙漠？編程計算及打印建立的貯油點序號，各貯油點距沙漠邊沿出發(fā)的距離以及存油量。格式如下：No.Distance(k.m.)Oil(litre)1××××2××××……………分析設(shè)Way[i]——第i個貯油點到終點〔i=0〕的距離；oil[i]——第i個貯油點的貯油量；我們可以用倒推法來解決這個問題。從終點向始點倒推，逐一求出每個貯油點的位置及存油量。從貯油點i向貯油點i+1倒推的方法是：卡車在貯油點i和貯油點i+1間往返假設(shè)干次。卡車每次返回i+1點時應(yīng)該正好耗盡500公升汽油，而每次從i+1點出發(fā)時又必須裝足500公升汽油。兩點之間的距離必須滿足在耗油最少的條件下，使i點貯足i*500公升汽油的要求〔0≦i≦n-1〕。倒推第一步第一個貯油點i=1應(yīng)距終點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次。路途耗油亦應(yīng)500公升，即d23=500/5，Way[3]=Way[2]+d2,3=Way[2]+500/5；倒推第k步……為了在i=k處貯藏k*500公升汽油，卡車至少從i=k+1處開k趟滿載車至i=k處，即oil[k+1]=(k+1)*500=oil[k]+500，加上從i=k返回i=k+1的k-1趟返程空間，合計2k-1次。這2k-1次總耗油量按最省要求為500公升，即dk,k+1=500/(2k-1)Way[k+1]=Way[k]+dk,k+1=Way[k]+500/(2k-1)；i=n的情形i=n至始點的距離為1000-Way[n],oil[n]=500*n。為了在i=n處取得n*500公升汽油，卡車至少從始點開n+1次滿載車至I=n，加上從I=n返回始點的n趟返程空車，合計2n+1次，2n+1趟的總耗油量應(yīng)正好為〔1000-Way[n]〕*(2n+1)，即始點藏油為oil[n]+(1000-Way[n])*(2n+1)。遞推的應(yīng)用〔組合計數(shù)〕Catalan數(shù)定義：一個凸n邊形通過不相交于n邊形內(nèi)部的對角線把n邊形拆分成假設(shè)干三角形的不同拆分?jǐn)?shù)。分析設(shè)Cn表示凸n邊形的拆分方案總數(shù)。由題目中的要求可知一個凸n邊形的任意一條邊都必然是一個三角形的一條邊，邊P1Pn也不例外，再根據(jù)“不在同一直線上的三點可以確定一個三角形”，只要在P2，P3，……，Pn-1點中找一個點Pk(1<k<n)，與P1、Pn共同構(gòu)成一個三角形的三個頂點，就將n邊形分成了三個不相交的局部(如圖3所示)，我們分別稱之為區(qū)域①、區(qū)域②、區(qū)域③，其中區(qū)域③必定是一個三角形，區(qū)域①是一個凸k邊形，區(qū)域②是一個凸n-k+1邊形。P1Pn①②③圖3P2P3PkPn--1分析區(qū)域①的拆分方案總數(shù)是Ck，區(qū)域②的拆分方案數(shù)為Cn-k+1，故包含△P1PkPn的n邊形的拆分方案數(shù)為CkCn-k+1種，而Pk可以是P2，P3，……，Pn-1種任一點，根據(jù)加法原理，凸n邊形的三角拆分方案總數(shù)為，同時考慮到計算的方便，約定邊界條件C2=1。

P1Pn①②③圖4P2P3PkPn--1分析=C(2n,n)/(n+1)具體實現(xiàn)時，假設(shè)直接用上述公式計算，對數(shù)字的精度要求較高?？蓪⑵浠癁檫f推式再進行遞推計算，并且注意類型的定義要用comp型。

Catalan數(shù)的應(yīng)用〔局部和序列〕n個+1，n個-1構(gòu)成2n項a1,a2,a3,a4,,,,,,a2n

其局部和滿足

a1+a2+......ak(k=1,2,3,...2n)>=0的數(shù)列個數(shù)。Catalan數(shù)的應(yīng)用〔加括號〕序列a1a2..ak的元素順序保持不變，按不同結(jié)合方式插入合法圓括號對的方案數(shù)。

n=4

(a((bc)d))

(a(b(cd)))

((ab)(cd))

(((ab)c)d)

((a(bc))d)一個操作數(shù)序列，從1，2，一直到n，棧A的深度大于n。現(xiàn)在可以進行兩種操作：1．將一個數(shù)，從操作數(shù)列的頭端移至棧的頭端〔對應(yīng)棧的push操作〕2．將一個數(shù)，從棧的頭端移至輸出序列的尾端〔對應(yīng)棧的pop操作〕。使用這兩種操作，由一個操作數(shù)序列就可以得到一系列的輸出序列，下表為由123生成序列231的過程。步驟0123456操作數(shù)序列1232333

棧

1211311

輸出序列

2223231Catalan數(shù)的應(yīng)用〔棧NOIp2003〕結(jié)合定義我們很容易能發(fā)現(xiàn)：如果進?？闯?，出?？闯?，在任何一位上累計的“0”的個數(shù)不大于累計的“1”的個數(shù)，因為必須在棧里有數(shù)的情況下才能向外彈數(shù)。原題轉(zhuǎn)化為——n個1和n個0組成一個2n位的二進制數(shù)，要求從左到右掃描，“0”的累計數(shù)不大于“1”的累計數(shù)，求滿足條件的數(shù)有多少。任務(wù)：你的程序?qū)o定的n，計算并輸出由操作數(shù)序列1，2，……，n經(jīng)過操作可能得到的輸出序列總數(shù)。分析n個數(shù)，分別為1~n，排成一個長度為n的排列。假設(shè)每一個數(shù)的位置都與數(shù)的本身不相等，那么稱這個排列是一個錯排。例如，n=3，那么錯排有231、312。編寫程序，求n的錯排個數(shù)。錯排問題〔經(jīng)典問題〕遞推的應(yīng)用〔組合計數(shù)〕我們設(shè)k個元素的錯位全排列的個數(shù)記做：W(k)。四個元素的錯位排列W(4)我們用窮舉法可以找到如下9個：

(4，3，2，1)(3，4，1，2)(2，1，4，3)

(4，1，2，3)(3，4，2，1)(3，1，4，2)

(4，3，1，2)(2，4，1，3)(2，3，4，1)它們有什么規(guī)律呢？分析通過反復(fù)的試驗，我們發(fā)現(xiàn)事實上有兩種方式產(chǎn)生錯位排列：

A.將k與(1，2，…，k－1)的某一個數(shù)互換，其他k－2個數(shù)進行錯排，這樣可以得到(k－1)×W(k-2)個錯位排列。

B.另一局部是將前k－1個元素的每一個錯位排列〔有W(k-1)個〕中的每一個數(shù)與k互換，這樣可以得到剩下的(k－1)×W(k-1)個錯位排列。根據(jù)加法原理，我們得到求錯位排列的遞推公式W(k):W(k)=(k–1)*[W(k–1)+W(k–2)]分析例題3：走直線棋問題。有如下所示的一個編號為１到ｎ的方格：

現(xiàn)由計算機和人進行人機對奕，從１到ｎ，每次可以走ｋ個方格，其中ｋ為集ｓ={a1,a2,a3,....am}中的元素(m<=4)，規(guī)定誰最先走到第n格為勝，試設(shè)計一個人機對奕方案，摸擬整個游戲過程的情況并力求計算機盡量不敗。遞推的應(yīng)用〔博弈問題〕12345……N-1N題設(shè)條件：假設(shè)誰先走到第N格誰將獲勝，例如，假設(shè)S={1,2}，從第N格往前倒推，那么走到第N-1格或第N-2格的一方必敗，而走到第N-3格者必定獲勝，因此在N，S確定后，棋格中每個方格的勝、負(fù)或和態(tài)〔雙方都不能到達第N格〕都是可以事先確定的。將目標(biāo)格置為必勝態(tài)，由后往前倒推每一格的勝負(fù)狀態(tài)，規(guī)定在自己所處的當(dāng)前格后，假設(shè)對方無論走到哪兒都必定失敗，那么當(dāng)前格為勝態(tài)，假設(shè)走后有任一格為勝格，那么當(dāng)前格為輸態(tài)，否那么為和態(tài)。分析設(shè)1表示必勝態(tài)，-1表示必敗態(tài)，0表示和態(tài)或表示無法到達的棋格。例如，設(shè)N＝10，S＝{1,2}，那么可確定其每個棋格的狀態(tài)如下所示：而N＝10，S＝{2,3}時，其每格的狀態(tài)將會如下所示：有了棋格的狀態(tài)圖后，程序應(yīng)能判斷讓誰先走，計算機選擇必勝策略或雙方和〔雙方均不能到達目標(biāo)格〕的策略下棋，這樣就能保證計算機盡可能不敗。分析1-1-11-1-11-1-110-1-1010-1-101在一個n×m的方格中，m為奇數(shù)，放置有n×m個數(shù)，如圖,方格中間的下方有一人，此人可按照五個方向前進但不能越出方格,見右以下圖。人每走過一個方格必須取此方格中的數(shù)。要求找到一條從底到頂?shù)穆窂?，使其?shù)相加之和為最大。輸出和的最大值。1643126034-56700260-1-236853400-27-17407-560-1341242人

遞推的應(yīng)用〔動態(tài)規(guī)劃中的遞推例4：方格取數(shù)分析我們用坐標(biāo)(x,y)唯一確定一個點，其中(m,n)表示圖的右上角，而人的出發(fā)點是，受人前進方向的限制，能直接到達點(x,y)的點只有(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)。到點(x,y)的路徑中和最大的路徑必然要從(m/2,0)到(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)的幾條路徑中產(chǎn)生，既然要求最優(yōu)方案，當(dāng)然要挑一條和最大的路徑，關(guān)系式如下：Fx,y=Max{Fx+2,y-1,Fx+1,y-1,Fx,y-1,Fx-1,y-1,Fx-2,y-1}+Numx,y，其中Numx,y表示(x,y)點上的數(shù)字。邊界條件為：動態(tài)規(guī)劃與遞推的關(guān)系上題實質(zhì)上是采用動態(tài)規(guī)劃來求解,那么與遞推動態(tài)規(guī)劃之間到底是什么關(guān)系呢？我們不妨畫個圖(如以下圖)。而通常人們理解的遞推關(guān)系就是一般遞推關(guān)系，故認(rèn)為動態(tài)規(guī)劃與遞推關(guān)系是兩個各自獨立的個體。動態(tài)規(guī)劃一般遞推關(guān)系遞推關(guān)系動態(tài)規(guī)劃與遞推的關(guān)系1、一般遞推邊界條件很明顯,動態(tài)規(guī)劃邊界條件比較隱蔽,容易被無視2、一般遞推數(shù)學(xué)性較強,動態(tài)規(guī)劃數(shù)學(xué)性相對較弱3、一般遞推一般不劃分階段,動態(tài)規(guī)劃一般有較為明顯的階段第三局部遞歸一個函數(shù)、過程、概念或數(shù)學(xué)結(jié)構(gòu)，如果在其定義或說明內(nèi)部又直接或間接地出現(xiàn)有其本身的引用，那么稱它們是遞歸的或者是遞歸定義的。在程序設(shè)計中，過程或函數(shù)直接或者間接調(diào)用自己，就被稱為遞歸調(diào)用。遞歸的概念與根本思想遞歸過程是借助于一個遞歸工作棧來實現(xiàn)的問題向一極推進，這一過程叫做遞推；而問題逐一解決，最后回到原問題，這一過程叫做回歸。遞歸的過程正是由遞推和回歸兩個過程組成。遞歸的概念與根本思想用遞歸算法求n!定義：函數(shù)fact(n)=n! fact(n-1)=(n-1)! 那么有 fact(n)=nfact(n-1) fact(1)=184下面畫出了調(diào)用和返回的遞歸示意圖遞歸的概念與根本思想遞歸實現(xiàn)的代價是巨大的棧空間的消耗，那是因為過程每向前遞推一次，程序?qū)⒈緦拥膶嵲谧兞俊仓祬⒑妥儏ⅰ场⒕植孔兞繕?gòu)成一個“工作記錄”壓入工作棧的棧頂，只有退出該層遞歸時，才將這一工作記錄從棧頂彈出釋放局部空間。由此可以想到，減少每個“工作記錄”的大小便可節(jié)省局部空間。例如某些變參可以轉(zhuǎn)換為全局變量，某些值參可以省略以及過程內(nèi)部的精簡。遞歸的概念與根本思想例如：求a[1..n]的最大者。有如下過程：Procedurefindmax(i:integer;varmax:integer);varj:integer;beginmax:=a[i];ifi=nthenexitelsebeginfindmax(i+1,j);ifj>maxthenmax:=j;end;end;

遞歸的概念與根本思想起始狀態(tài)就是調(diào)用findmax(1,max),而像上述過程中的變參max完全可以省略。將上述方法修改可得下面的算法：Procedurefindmax(i:integer);beginifi=nthenexitelsebeginfindmax(i+1);ifa[i]>maxthenmax:=a[i];end;end;

遞歸的概念與根本思想起始狀態(tài)就是調(diào)用findmax(1)，max為全局變量，同時還減少了一個局部變量的使用。盡管這只是一個很簡單的例子，在本例中不做精簡，程序也還是能通過，但它精簡的原那么對其它使用遞歸的程序而言卻是同樣適用的。特別是在遞歸過程出現(xiàn)堆棧溢出情況時就應(yīng)該考慮這一問題。遞歸的概念與根本思想采用遞歸方法編寫的問題解決程序具有結(jié)構(gòu)清晰，可讀性強等優(yōu)點，且遞歸算法的設(shè)計比非遞歸算法的設(shè)計往往要容易一些，所以當(dāng)問題本身是遞歸定義的，或者問題所涉及到的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的，或者是問題的解決方法是遞歸形式的時候，往往采用遞歸算法來解決。遞歸的應(yīng)用解決搜索問題處理遞歸定義或解決方法為遞歸方式的問題實現(xiàn)分治思想用于輸出動態(tài)規(guī)劃的中間過程遞歸的應(yīng)用〔搜索樹〕樹結(jié)構(gòu)是由遞歸定義的。因此，在解決與樹有關(guān)的問題時，常常可以采用遞歸的方法。因為搜索產(chǎn)生的節(jié)點成樹狀結(jié)構(gòu)，所以可以用遞歸方法解決。這類例子很多，如“N后”問題，哈密頓回路，圖的可著色性等等。遞歸的應(yīng)用例題：鋼板分割問題。設(shè)有一塊正方形的鋼板，現(xiàn)需將它分成n個小正方形。例如，當(dāng)：n=2不可能有解。n=3不可能有解。n=4 可分成4個小正方形鋼板。n=5不可能有解。n=6即一個大的加五個小的。n=7即三個較大的加四個小的。n=8 即一個大的加七個小的。問題為任給n，求出分成n個小正方形的方法。遞歸的應(yīng)用【分析】經(jīng)過分析就可以得出：〔1〕按n=4的方法將1個小正方形分成4個，那么增加了3個正方形?！?〕以n=6為根底，由〔1〕可以得出n=9，12，15，。〔3〕以n=7為根底，由〔1〕可以得出n=10，13，16，。〔4〕以n=8為根底，由〔1〕可以得出n=11，14，17，。由此可以得出如下的遞歸算法：遞歸的應(yīng)用proceduredevide(i:integer);Beginifn>8thenbegin

分解成四小塊；對于其中一塊devide(n-3)endelsecasenof6:按n=6分割；

7:按n=7分割；

8:按n=8分割；

end;End;遞歸的應(yīng)用〔實現(xiàn)分治思想〕不難發(fā)現(xiàn)，在各種時間復(fù)雜度為nlogn排序方法中，大都采用了遞歸的形式。因為無論是分治合并排序，還是堆排序、快速排序，都存在有分治的思想。只要分開處理，就可以采用遞歸。其實進行分治，也是一個建樹的過程。遞歸的應(yīng)用〔例題分析〕例題2：剔除多余括號鍵盤輸入一個含有括號的四那么運算表達式，可能含有多余的括號，編程整理該表達式，去掉所有多余括號，原表達式中所有變量和運算符相對位置保持不變，并保持原表達式等價。分析： 首先考慮人處理這個問題的方法，就是依靠符號來判斷是否可以去括號。括號的前后，以及括號內(nèi)的符號，都需要考慮。因此，可以按照人的處理方法，從最外層處理起，一層一層的去掉括號，這便是分治的思想。而由于每次分治的處理過程根本相同，用遞歸最為適宜。遞歸的應(yīng)用〔例題分析〕在遞歸過程中，對于正在處理的表達式s，如果s本身最外層就是多余括號，那么去括號，并處理括號內(nèi)的表達式〔遞歸調(diào)用〕；否那么，可沿該表達式中的最低級運算符p，將其拆為兩個表達式，分別進行處理〔遞歸調(diào)用〕，并獲得左右兩表達式中的最低級運算符c1,c2，通過與p的比較，確定是否應(yīng)添加括號。遞歸的終止條件為：s是變量。遞歸的應(yīng)用〔例題分析〕例如，處理表達式‘((a+b)*f)-(i/j)’,過程如下：

‘((a+b)*f)-(i/j)’,‘-’

‘((a+b)*f),’*’‘(i/j),’/’

‘(a+b)*f),’*’

‘i/j’,’/’

‘(a+b)’,’+’ ‘f’,’‘

‘i’,’‘ ‘j’,’‘

‘a(chǎn)+b’,’+’

‘a(chǎn)’,’‘‘b’,’‘

最后得出結(jié)果：‘(a+b)*f-i/j’。遞歸的應(yīng)用〔輸出動態(tài)規(guī)劃的中間過程〕動態(tài)規(guī)劃對空間要求較高，假設(shè)要保存中間過程用于輸出，那么可能要增加一倍的空間需求。此時，如果采用遞歸輸出，就完全不需要浪費這珍貴的空間。例題：最正確航線問題你在加拿大航空公司組織的一次競賽中獲獎，獎品是一張免費機票，可在加拿大旅行，從最西的一個城市出發(fā)，單方向從西向東經(jīng)假設(shè)干城市到達最后一個城市〔必須到達最東的城市〕，然后在單方向從東向西飛回起點〔可途徑假設(shè)干城市〕。除起點城市外，任何城市只能訪問一次。起點城市被訪問兩次：出發(fā)一次，返回一次。除指定的航線外，不允許乘其他航線，也不允許使用其他交通工具。求解的問題是：給定城市表列及兩城市之間的直通航線，請找出一條旅行航線，在滿足上述限制條件下，使訪問的城市盡可能多。例題分析：最正確航線問題

對這一問題，我們采用了動態(tài)規(guī)劃的方法。假設(shè)城市已按從西到東編號，數(shù)組dist[i,j]表示城市i到城市n,再到城市j的所有可行方案中，最多能夠訪問的城市數(shù)目。逆推關(guān)系式為：dist[n,n]=1;dist[i,j]=dist[j,i];dist[i,j]=max(dist[i,k])+1;(j<i,j<k<=n,且存在航線k─j)

如果要記錄中間過程，就必須再開辟一個二維數(shù)組，就會導(dǎo)致程序可完成的數(shù)據(jù)規(guī)模降低。而采用遞歸求出路徑后再輸出，編程并未增加多少難度，而可處理的數(shù)據(jù)量卻大大增加了。求路徑的過程完全按照倒推的方法，利用dist數(shù)組得出往返的路線。。第四局部貪心方法貪心方法的根本思想貪心是一種解題策略，也是一種解題思想使用貪心方法需要注意局部最優(yōu)與全局最優(yōu)的關(guān)系，選擇當(dāng)前狀態(tài)的局部最優(yōu)并不一定能推導(dǎo)出問題的全局最優(yōu)利用貪心策略解題，需要解決兩個問題：該題是否適合于用貪心策略求解如何選擇貪心標(biāo)準(zhǔn)，以得到問題的最優(yōu)解

適用于貪心策略求解的問題的特點

適用于貪心策略求解的問題必須具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，但并不是所有具有最優(yōu)子結(jié)構(gòu)的問題都可以用貪心策略求解。因為貪心往往是盲目的，需要使用更理性的方法——動態(tài)規(guī)劃〔例如“0-1背包問題”與“局部背包問題”〕貪心方法的應(yīng)用例題1：節(jié)點網(wǎng)絡(luò)?，F(xiàn)有一個N！個節(jié)點的網(wǎng)絡(luò)，每個節(jié)點的編號都是編號〔A1A2A3…AN〕序列的一個置換。對于任意兩個節(jié)點S和T，如果T的編號是由S編號的首位與除首位外的編號中任一位交換所得，那么S和T之間有一條邊，求從給定節(jié)點S走到節(jié)點〔A1A2A3…AN〕所需經(jīng)過的最少邊數(shù)。其中，n≤100。貪心方法的應(yīng)用例如n=3的情況：(A1A2A3)(A1A3A2)(A2A3A1)(A2A1A3)(A3A1A2)(A3A2A1)貪心方法的應(yīng)用【分析】從題意外表上看，此題是一個求最短路徑的問題，但題設(shè)中的N≤100，也就是說圖中最多有100！個節(jié)點，采用二維關(guān)系的圖結(jié)構(gòu)根本無法存貯這眾多的狀態(tài)。通過問題的本質(zhì)分析，可以將問題轉(zhuǎn)化為一個序列的最優(yōu)轉(zhuǎn)化問題。貪心方法的應(yīng)用采用貪心策略：每次讓一個節(jié)點歸位或為下一步工作做準(zhǔn)備。其具體步驟為：假設(shè)序列中第一個點為Ax(x≠1)，那么將第一個點和第x個點交換。這便完成了讓一個點歸位的工作；假設(shè)第一個是A1，那么任找一個編號與位置不相符的點，并與之交換。這樣下一步便可讓交換到1號位置的點歸位。貪心方法的應(yīng)用(A3A4A1A2)(A1A4A3A2)第一個點A1已歸位，但第二個點為A4≠A2，將第2個點A4與A1交換第一個點為A3≠A1，將第3個點A1與A3交換(A4A1A3A2)第一個點為A4≠A1，將第4個點A2與A4交換(A2A1A3A4)第一個點為A2≠A1，將第2個點A1與A2交換(A1A2A3A4)已經(jīng)符合要求了一共經(jīng)過4步完成。下面看一個n=4，初始序列為(A3A4A1A2)的推演過程：例題2排序問題排序是計算機科學(xué)中一個常見任務(wù)。有一種特殊的排序，最多只有3個關(guān)鍵字。例如，試圖對這次競爭的獎牌榜排序時，就只有3個關(guān)鍵字，所有的金牌獲得者在最前面，隨后是獲銀牌者，最后是銅牌獲得者。此題中用1,2,3分別表示3個關(guān)鍵字，需將它們按升序排列。排序是通過一系列對換操作實現(xiàn)的。一次操作可以交換兩個數(shù)的位置。子任務(wù)A請寫一個程序，對于一個給定的只含有關(guān)鍵字的序列，計算最少需要幾次對換操作就可以將其按升序排列。子任務(wù)B輸出一種最少次數(shù)的對換方案。分析如果要我們自己來手算的話，勢必會先找到一對數(shù)，使其交換位置后正好都回到應(yīng)該在的位置，例如數(shù)串111232333，我們發(fā)現(xiàn)第5位上的3與第6位上的2正好反過來了。把它們交換就可以得到排序后的數(shù)串。又因為這樣的一次交換使兩個數(shù)回到正確的位置，這說明這次交換已經(jīng)發(fā)揮了它的最大成效，一定不是多余的，雖然是要求最少的交換次數(shù)也絕不能少了這樣的交換。到這里我們發(fā)現(xiàn)這道題可以用貪心法來做。不斷地尋找這樣的一對數(shù)，直至找不到為止。但是注意，還有一種更加普遍的情況我們沒有考慮，也就是雖然存在錯位了的數(shù)，但是找不到互換位置可以符合以上要求的兩個數(shù)。例如：113221332中，第3位上的3，第6位上的1，第9位上的2，都是錯位的，但不管取他們?nèi)齻€中的哪兩個交換，通通都不能使兩個數(shù)都?xì)w原位。這個時候，我們只好放棄一個，只保證一個數(shù)可以歸原位，于是交換1與2，數(shù)串變成113222331，這時再交換3與1，就用兩次交換對該數(shù)列排完了序。問題變形給定N個不同的正整數(shù)，每次只能交換兩個相鄰的數(shù)，如何一住校的交換次數(shù)使得其變成升序？貪心方法的應(yīng)用〔貪心標(biāo)準(zhǔn)〕例題：d-規(guī)那么問題。對任意給定的m(m∈N+)和n(n∈N+)，滿足m<n，構(gòu)造一初始集合：P={x|m≤x≤n,x∈N+}(m,n≤100)現(xiàn)定義一種d規(guī)那么如下：假設(shè)存在a∈P，且存在K∈N+,K>1，使得Ka∈P，那么修改P為：P=P-{y|y=sa,s∈N+}，并稱該d規(guī)那么具有分值a?，F(xiàn)要求編制一個程序，對輸入的m,n值，構(gòu)造相應(yīng)的初始集合P，對P每應(yīng)用一次d規(guī)那么就累加其相應(yīng)的分值，求能得到最大累加分值的d規(guī)那么序列，輸出每次使用d規(guī)那么時的分值和集合p的變化過程。貪心方法的應(yīng)用【分析】初看這一問題，很容易想到用貪心策略來求解，即選擇集合中最大的可以刪除的數(shù)開始刪起，直到不能再刪除為止，而且通過一些簡單的例子來驗證，這一貪心標(biāo)準(zhǔn)似乎也是正確的，例如，當(dāng)m=3，n=10時，集合P＝{3,…,10}，運用上述“貪心標(biāo)準(zhǔn)”可以得到這一問題的正確的最優(yōu)解d=5＋4＋3＝12，即其d-規(guī)那么過程如下：1.a=5P={3,4,6,7,8,9} d=52.a=4P={3,6,7,9} d=5+4=93.a=3p={7} d=5+4+3=12貪心方法的應(yīng)用但是，如果再仔細(xì)地分析一個例子，當(dāng)m=3，n＝18時，如果還是使用上述“貪心標(biāo)準(zhǔn)”，那么得到問題的d-規(guī)那么總分為d=35，其d-規(guī)那么序列為〔9,8,7,6,5〕，而實際上可以得到最大d-規(guī)那么總分為d＝38，其對應(yīng)的d-規(guī)那么序列為〔9,8,7,6,3,5〕。為什么會出現(xiàn)這樣的反例呢？這是因為，問題中要使得d-規(guī)那么總分d值越大，不光是要求每一個d分值越大越好，也要求取得的d分值越多越好。因此，此題不能采用純粹的貪心策略求解。貪心方法的應(yīng)用【改進】將原算法根底上進行改進。下面給出新的算法：建立集合P={m..n}從ndiv2到m每數(shù)構(gòu)造一個集合c[i]，包含該數(shù)在P中的所有倍數(shù)〔不包括i本身〕從ndiv2起找到第一個元素個數(shù)最少但又不為空的集合c[i]在d分值中加上i把i及c[i]集合從P集中刪除，更新所有構(gòu)造集合的元素檢查所有構(gòu)造集合，假設(shè)還有非空集合，那么繼續(xù)3步驟，否那么打印、結(jié)束貪心方法的應(yīng)用下面看m=3,n=18時的推演過程：初始P={3..18}找到i=9,c[i]={18},P={3..8,10..17}找到i=8,c[i]={16},P={3..7,10..15,17}找到i=7,c[i]={14},P={3..6,10..13,15,17}找到i=6,c[i]={12},P={3..5,10,11,13,15,17}找到i=3,c[i]={15},P={4,5,10,11,13,17}找到i=5,c[i]={10},P={4,11,13,17}到此所有構(gòu)造集合全部為空，d=9+8+7+6+3+5=38例題分析：田忌賽馬問題中國古代的歷史故事“田忌賽馬”是為大家所熟知的。話說齊王和田忌又要賽馬了，他們各派出N匹馬，每場比賽，輸?shù)囊环綄⒁o贏的一方200兩黃金，如果是平局的話，雙方都不必拿出錢?，F(xiàn)在每匹馬的速度值是固定而且的，而齊王出馬也不管田忌的出馬順序。請問田忌該如何安排自己的馬去對抗齊王的馬，才能贏取最多的錢？正整數(shù)n(n<=2000)，表示雙方馬的數(shù)量。分析不妨用貪心思想來分析一下問題。因為田忌掌握有比賽的“主動權(quán)”，他總是根據(jù)齊王所出的馬來分配自己的馬，所以這里不妨認(rèn)為齊王的出馬順序是按馬的速度從高到低出的。由這樣的假設(shè)，我們歸納出如下貪心策略：1、如果田忌剩下的馬中最強的馬都贏不了齊王剩下的最強的馬，那么應(yīng)該用最差的一匹馬去輸給齊王最強的馬。2、如果田忌剩下的馬中最強的馬可以贏齊王剩下的最強的馬，那就用這匹馬去贏齊王剩下的最強的馬。

3、如果田忌剩下的馬中最強的馬和齊王剩下的最強的馬打平的話，可以選擇打平或者用最差的馬輸?shù)舯荣?。光是打平的話，如果齊王馬的速度分別是123，田忌馬的速度也是123，每次選擇打平的話，田忌一分錢也得不到，而如果選擇先用速度為1的馬輸給速度為3的馬的話，可以贏得200兩黃金。光是輸?shù)舻脑?，如果齊王馬的速度分別是13，田忌馬的速度分別是23，田忌一勝一負(fù)，仍然一分錢也拿不到。而如果先用速度為3的馬去打平的話，可以贏得200兩黃金。

通過上述的三種貪心策略，我們可以發(fā)現(xiàn)，如果齊王的馬是按速度排序之后，從高到低被派出的話，田忌一定是將他馬按速度排序之后，從兩頭取馬去和齊王的馬比賽。有了這個信息之后，動態(tài)規(guī)劃的模型也就出來了！Dp求解設(shè)f[i,j]表示齊王按從強到弱的順序出馬和田忌進行了i場比賽之后，從“頭”取了j匹較強的馬，從“尾”取了i-j匹較弱的馬，所能夠得到的最大盈利。狀態(tài)轉(zhuǎn)移方程如下：F[I,j]=max{f[i-1,j]+g[n-(i-j)+1,i],f[i-1,j-1]+g[j,i]}其中g(shù)[i,j]表示田忌的馬和齊王的馬分別按照由強到弱的順序排序之后，田忌的第i匹馬和齊王的第j匹馬賽跑所能取得的盈利，勝為200，輸為－200，平為0。貪心方法的應(yīng)用〔貪心標(biāo)準(zhǔn)證明〕例題：射擊競賽射擊的目標(biāo)是一個由RC(2≤R≤C≤1000)個小方格組成的矩形網(wǎng)格。每一列恰有2個白色的小方格和R-2個黑色的小方格。行從頂至底編號為1~R，列從左至右編號為1~C。射擊者可射擊C次。在連續(xù)的C次射擊中，假設(shè)每列恰好有一個白色的方格被射中，且不存在無白色方格被射中的行，這樣的射擊才是正確的。如果存在正確的射擊方法，那么要求找到它。貪心方法的應(yīng)用射擊的選擇有2C種，符合要求的卻很少。要解決問題，還需從正確的射擊方法的特征入手。貪心方法的應(yīng)用【方法一】網(wǎng)絡(luò)流算法我們將表示列的點編號為1到C，表示行的點編號為C+1到C+R，如果一個白色方格處在第i行第j列，那么從點j向點C+i連一條弧，弧的容量為1。再增設(shè)一個源點S，從點S往點1到C間各連一條弧，弧的容量為1，又設(shè)一個匯點T，從點C+1到點C+R向匯點T連一條弧，弧的容量為1，那么從源點S到匯點T求最大流，求出的最大流量即為最多可以射擊到的行數(shù)。各條流的路線那么描述了具體的射擊方案?？梢钥闯觯绻镁W(wǎng)絡(luò)流求出的最大流量比R小，那么問題無解，否那么我們可以先根據(jù)網(wǎng)絡(luò)流的結(jié)果求出該二分圖的具體匹配方案。貪心方法的應(yīng)用紅色的連線流量為1藍色的連線流量為0選擇的射擊格即為：(1,3),(2,1),(3,2),(4,4)S21432143T列:行:源:匯:貪心方法的應(yīng)用網(wǎng)絡(luò)流算法經(jīng)過優(yōu)化，時間復(fù)雜度可以到達O(C(n+4C+4R))上述網(wǎng)絡(luò)流算法雖然可以通過全部數(shù)據(jù)，但編程復(fù)雜度很高，而且極易出錯，一不小心就會因為一個小錯誤影響整個程序。貪心方法的應(yīng)用【方法二】貪心方法統(tǒng)計所有行包含的白格數(shù)從還沒有射擊格的行中選出一個白格數(shù)最少的檢查所選的行假設(shè)所選行的白格數(shù)為0，那么輸出無解；否那么從所選行的白格中任選一個作為射擊格，并將與該格同列的另一個白格所處行的白格數(shù)減1返回到第2步，直到所有的行都有射擊格。假設(shè)還有列沒有選射擊格，那么在該列任選一白格作為射擊格即可貪心方法的應(yīng)用上面的貪心方法非常高效：時間復(fù)雜度為O(R

C)，如果在程序中使用堆優(yōu)化，時間復(fù)雜度將降為O(R

log2C)?？臻g復(fù)雜度是線性的，而且非常容易實現(xiàn)。現(xiàn)在關(guān)鍵的問題就是——如何證明它的正確性？貪心方法的應(yīng)用【證明】用h[i]表示第i行的白格數(shù)。如果最開始的時候：min{h[i]}=0:第i行已經(jīng)沒有方法找到可作為射擊格的白格，那么問題只能無解。min{h[i]}=1:那么第i行的這一個白格必須要作為射擊格，否那么將因第i行沒有射擊格而造成問題無解。min{h[i]}≥2:那么在這一行任選一個白格，頂多只會造成剩余行中有一行h值為1，再處理那一行，最多也只會再造成剩余行中有一行h值為1，如此往復(fù)，將保持h值為1的行數(shù)不超過1行，最后最壞的情況也是造成最后一行的h值為1，繼續(xù)下去所有行就都已選取了射擊格了。因此，如果原問題有解，該貪心方法一定能找到一種正確的方案。由此可以證明，此貪心方法是正確的。例題分析買彩票(tickt.exe)電視里面正放著“抽百萬大獎，贏幸福生活”的宣傳廣告，bird看后也想去試試手氣，當(dāng)然，作為經(jīng)濟學(xué)院的高材生，他可不屑只是單純的去碰運氣。經(jīng)過他的一番分析，發(fā)現(xiàn)，商家在彩票里面做了手腳，使得每個抽獎點的中獎概率不是完全一樣的，而且隨著時間的變化而變化，不過這種變化是有規(guī)律的。

對于第I個抽獎點，最開始的中獎概率是百萬分之Pi，以后每抽一張彩票后都要重新排隊，花費的時間是T分鐘，每抽一次減少的概率為Di。由于可憐的bird還有一大堆的作業(yè)沒做，他只能抽出H個小時去買彩票。由于抽獎地點都在一路公共汽車的線路上，所以怕麻煩的bird決定按車站順序抽獎。當(dāng)然，bird可以從任意一站開始抽獎，對于經(jīng)過的抽獎點可以買彩票，也可以不買。假設(shè)從第I個抽獎點到第I+1個抽獎點需要做Ci分鐘的汽車。Bird希望能在有限的H個小時內(nèi)獲得最好的運氣——即抽獎的概率和最大。輸入：第一行為一個整數(shù)n，表示抽獎點的個數(shù)，1<=n<=200第二行是兩個整數(shù)H和T，1<=H<=10，1<=T<=60。接下來的n行，每行3個整數(shù)，分別是Pi，Di，Ci〔Cn=0〕。1<=Pi<=10000，Di<=Pi，1<=Ci<=600。輸出：一個整數(shù)，抽獎概率和的最大值。樣例數(shù)據(jù)input.txtoutput.txt2500120200100103002000樣例說明：首先，bird從1號開始抽獎，花費20分鐘，得到概率200，然后坐車到2號，花費10分鐘，再花20分鐘得到概率300，概率和是500，花費50分鐘。此題最初可能想到用搜索，不過如果仔細(xì)分析題目會發(fā)現(xiàn)其實用貪心就可以解了。雖然中獎的概率會不斷變化，但概率只和在該抽獎地點的抽獎次數(shù)有關(guān)，和抽獎的總次數(shù)以及時間無關(guān)。所以，我們可以枚舉起始S和終點T的抽獎地點，那么在路上花費的時間可以求出，那么在這個范圍內(nèi)的抽獎，可以看作bird能瞬間轉(zhuǎn)移，那么我們只需將此范圍內(nèi)的抽獎概率排序，取前假設(shè)干個，使得花費的時間不超過時限。很容易證明，這種方法是最優(yōu)的。此題的貪心關(guān)鍵是要先確定一個范圍，然后針對具體的范圍貪心。貪心法的隱秘性還是比較強的。例題分析〔駱駝商隊〕有N個城市，編號為1……N。在一些城市之間有路可通，有路就有商隊。但是在不同的城市之間經(jīng)商所得的收益不同，在下面的這個N=4的例子中，在城市1和城市2之間進行一次交易可以獲得40枚金幣，在城市2和3之間交易一次可以獲得50枚金幣，規(guī)定在任意兩個城市之間，這樣的交易只能進行一次。給出這個大陸的地圖和每兩個城市之間的貿(mào)易值〔如果這兩個城市之間有路可通的話〕，你需要指揮你的N支商隊進行一次經(jīng)商，使得這N支商隊在這次經(jīng)商中獲得的總收益最大。注意：你的每支商隊只能進行一次交易，即它們只能從它們所在的城市到達一個相鄰的城市。當(dāng)然，它們也可以不進行任何交易。分析此題轉(zhuǎn)化成模型就是：在一個無向圖中，對于每個點，取一條和它相關(guān)聯(lián)的邊〔如果這樣的邊存在的話〕，使得取出來的所有邊的權(quán)和最大。首先，如果這個圖是不連通的，那么它的各個連通分量之間是沒有任何聯(lián)系的。對這些連通分量中的問題可以分別獨立地解決，合并起來就是整個問題的解。所以我們在下面的討論中假定圖是連通的。直觀地考慮，如果圖中存在度為1的點，那么就把這一點上的唯一的一條邊分配給這個點〔將某條邊“分配”給某個點的含義是：將這條邊作為和這一點相關(guān)聯(lián)的邊取出來，同時這一點就失效了，因為和它相關(guān)聯(lián)的其他邊都不能再取了〕。如果不存在這樣的點，那么此時有兩種情況：一種是邊數(shù)等于點數(shù)，那么這個圖就是一個環(huán)，這時可以取出圖中所有的邊；一種是邊數(shù)大于點數(shù)，那么就可以把這個圖中權(quán)最小的一條邊直接刪去，因為這條邊“顯然”不會被取到的。貪心算法〔用于連通圖〕：1、如果圖中只有一個點，直接結(jié)束算法。2、如果圖中存在度為1的點，執(zhí)行3；否那么轉(zhuǎn)4。3、任意找一個度為1的點v，將v上的唯一一條邊分配給它。轉(zhuǎn)2。4、如果圖中的邊數(shù)等于點數(shù)，執(zhí)行5；否那么轉(zhuǎn)6。5、設(shè)圖中的點數(shù)〔也就是邊數(shù)〕為n。任取一條邊e1，將它分配給它的兩個端點中的任意一個v1；然后將v1上的另一條邊e2分配給e2的另一個端點v2；將v2上的另一條邊e3分配給e3的另一個端點v3；……如此重復(fù)直到將en分配給vn，即圖中所有的邊都已分配，結(jié)束算法。6、將圖中權(quán)最小的邊不分配而直接刪去。如果此時圖仍然連通，那么轉(zhuǎn)2；否那么對這個圖的兩個連通分量分別執(zhí)行本算法貪心方法的推廣貪心與其它算法結(jié)合搜索的最優(yōu)化剪枝〔生日蛋糕〕優(yōu)化動態(tài)規(guī)劃〔Peter的快餐店〕貪心方法與解題策略最優(yōu)方法不一定是最好方法想不到最優(yōu)解法就用較優(yōu)解法貪心與其它算法結(jié)合例題：Peter的快餐店〔貪心與動態(tài)規(guī)劃〕Peter最近在R市新開了一家快餐店。該快餐店準(zhǔn)備推出一種套餐，每套由A個漢堡、B個薯條和C個飲料組成。為了提高產(chǎn)量，Peter引進了N條生產(chǎn)線。所有生產(chǎn)線都可以生產(chǎn)漢堡、薯條和飲料，由于每條生產(chǎn)線一天能工作的時間是有限的、不同的，而漢堡、薯條和飲料的單位生產(chǎn)時間又不同，Peter需要知道，怎樣安排才能是一天中生產(chǎn)的套餐量最大。假設(shè)一天中漢堡、薯條和飲料的產(chǎn)量均不超過100個，且生產(chǎn)線總數(shù)小于等于10。貪心與其它算法結(jié)合【分析】用p1、p2、p3分別表示漢堡、薯條和飲料的單位生產(chǎn)時間，t[i]表示第i條生產(chǎn)線每天的生產(chǎn)時間，p[i,j,k]表示用前i條生產(chǎn)線生產(chǎn)j個漢堡、k個薯條的情況下，最多能生產(chǎn)的飲料數(shù)，r[i,j,k]表示用第i條生產(chǎn)線生產(chǎn)j個漢堡、k個薯條的情況下，最多能生產(chǎn)的飲料數(shù)，那么p[i,j,k]=max{p[i-1,j1,k1]+r[i,j-j1,k-k1]}((j-j1)p1+(k-k1)p2<t[i])通過對該算法的時間復(fù)雜度分析，最壞的情況下時間復(fù)雜度將到達109，是相當(dāng)費時的。貪心與其它算法結(jié)合現(xiàn)在參加貪心方法，用貪心方法作預(yù)處理：首先計算出一天生產(chǎn)套數(shù)的上限值：min{100divA,100divB,100divC}接著，用貪心方法計算出這N條生產(chǎn)線可以生產(chǎn)的套數(shù)，并與上限比較，大于或等于那么輸出上限值并退出，否那么再調(diào)用動態(tài)規(guī)劃。因為貪心方法的代價很低，這里甚至可以使用屢次貪心標(biāo)準(zhǔn)不同的貪心方法，取其最大值。在運行動態(tài)規(guī)劃的過程中，也可以每完成一階段工作便與上限值進行比較，將貪心思想充分融入到動態(tài)規(guī)劃過程中，這樣以來，便可望在動態(tài)規(guī)劃完成前提前結(jié)束程序。貪心方法小結(jié)貪心作為一種解題思路，雖然有時無法證明它的正確性，但在無法找到其他算法的時候，不失為一種好方法。并且，貪心與其他算法的結(jié)合，可以對其他算法起到優(yōu)化作用。第四局部分治策略分治思想分治(divide-and-conquer)就是“分而治之”的意思，其實質(zhì)就是將原問題分成n個規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題；然后遞歸地解這些子問題，最后合并其結(jié)果就得到原問題的解。其三個步驟如下；分解(Divide)：將原問題分成一系列子問題。解決(Conquer)：遞歸地解各子問題。假設(shè)子問題足夠小，那么可直接求解。合并(combine)；將子問題的結(jié)果合并成原問題的解。分治思想如果在將規(guī)模為n的問題分成k個不同子集合的情況下，能得到k個不同的可分別求解的子問題，其中1＜k＜=n，而且在求出了這些子問題的解之后，還可找到適當(dāng)?shù)姆椒ò阉鼈兒喜⒊烧麄€問題的解，那么，具備上述特性的問題可考慮使用分治策略設(shè)計求解。這種設(shè)計求解的思想就是將整個問題分成假設(shè)干個小問題后分而治之。分治思想問題S問題S問題SS的解問題S1……問題S2問題Si問題Sn……S1的解……S2的解Si的解Sn的解……問題的分解子集解的合并子問題求解分治思想由分治法所得到的子問題與原問題具有相同的類型。如果得到的子問題相對來說還太大，那么可反復(fù)使用分治策略將這些子問題分成更小的同類型子問題，直至產(chǎn)生