第二章

常用算法2.1 遞歸法2.2 分治法2.3 貪心法2.4 搜索法與回溯法【2.1.1 遞歸的概念與基本思想】

遞歸（Recursion）即是一個函數(shù)直接或間接調(diào)用自己本身的過程。使用遞歸時必須符合以下三個條件：

①可將一個問題轉(zhuǎn)化為新問題，而新問題的解決方法仍然與原問題的方法相同，只不過所處理的對象不同而已，即它們只是規(guī)律的遞增和遞減。

②可以通過轉(zhuǎn)化過程使問題回到對原問題的求解。

③必須要有一個明確的遞歸結束條件，否則遞歸會無休止地進行下去。遞歸的思想就是把復雜的問題層層分解成簡單的問題去解決。 我們用幾個經(jīng)典例子說明遞歸的思想。 階乘函數(shù)f（n）=n！按照遞歸的思想可以定義為

f(0)=1, n=0 f(n)=f(n—1)×n, n＞0

對應的遞歸函數(shù)：

intf(intn)

｛

if(n==0) return1；

2.1 遞歸法 else returnf(n—1)*n；

｝ 斐波那契數(shù)列按照遞歸的思想可以定義為：

f(1)=1， n=1 f(2)=1， n=2 f(n)=f(n—1)＋f(n—2), n＞2

對應的遞歸函數(shù)：

intf(intn)

｛

if(n==1) return1；

if(n==2) return1；

else returnf(n—1)+f(n—2)； ｝2.1 遞歸法【2.1.2 遞歸法的應用】【例2.1】計算兩個數(shù)的最大公約數(shù)?！舅惴ǚ治觥课覀冇胓cd（n，m）來表示兩個數(shù)的最大公約數(shù)，那么我們有公式∶gcd（n，m）=gcd（m，n—m）進而我們可以按照遞歸的思想寫出新的公式∶gcd(n,m)=gcd(m,n%m)有了這個公式我們就可以寫出程序了?！驹O計技巧】可以利用?∶表達式來簡化程序?！境绦?qū)崿F(xiàn)】下面是用if語句完成的程序。 /* prog:gcd lang∶c＋＋

*/ #include＜iostream＞ usingnamespacestd； intgcd（inta,intb）2.1 遞歸法

｛

if（b==0）

returna；

else returngcd（b，a%b）；

｝ intmain（）

｛ inta，b；

cin＞＞a＞＞b；

cout＜＜gcd（a，b）＜＜endl；

return0；

｝2.1 遞歸法下面是用？：表達式完成的程序。 /* prog：gcd lang：c＋＋

*/ #include＜iostream＞ usingnamespacestd； intgcd（inta，intb）

｛

returnb==0？a：gcd（b，a%b）；

｝ intmain（）｛ inta，b；

cin＞＞a＞＞b；

cout＜＜gcd（a，b）＜＜endl； return0；

｝2.1 遞歸法

【例2.2】將十進制正整數(shù)n轉(zhuǎn)化為m進制數(shù)。2≤m≤20。

【算法分析】連續(xù)除以m直到商為0，從底向上記錄余數(shù)即可得到結果。 如圖2.1所示，將12轉(zhuǎn)化為2進制數(shù)，（12）10=（1100）2

觀察這個過程，它就是一個遞歸的過程，遞歸的邊界條件是當前數(shù)為0，只需按照上圖的思路設計程序即可。

【設計技巧】需要注意n=0時是特殊情況，需要特殊處理保證程序的正確性。

可以提前存儲代碼，減少程序代碼量。 在遞歸更深層結束后再將這一層對應的余數(shù)加入答案，即回溯時再將這一層的余數(shù)加人答案。

【程序?qū)崿F(xiàn)】 /* prog：進制轉(zhuǎn)換

lang：c＋＋ */ #include＜iostreanm＞

usingnamespacestd；

stringNum[20]；

stringS； voidPreWork（void）

2.1 遞歸法圖2.112轉(zhuǎn)換為2進制數(shù) ｛ for（inti=0；i＜20；i＋＋）Num[i]="." for（inti=0；i＜10；i＋＋Num[i][0]=（char）（′0′＋i）；

for（inti=10；i＜20；i＋＋）Num[i][0]=（char）（′A′＋i—10）； ｝

voidNemberConver（intn，intm） ｛ if（n==0）return；

NumberConver（n/m，m）；

S＋=Num[n%m]； ｝

intmain（） ｛ intn，m；

cin＞＞n＞＞m；

id（n==0）cout＜＜0＜＜endl；

else

｛ PreWork（）；

NumberConver（n，m）；

cout＜＜S＜＜endl； ｝

return0； ｝2.1 遞歸法【2.2.1 分治的概念與基本思想】 分治法是一種很重要的算法。字面上的解釋是“分而治之”，其基本思想就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題，直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。這個技巧是很多高效算法的基礎，如排序算法（快速排序，歸并排序），傅立葉變換（快速傅立葉變換）。 任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模有關。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少。例如，對于n個元素的排序問題，當n=1時，不需任何計算；n=2時，只要作一次比較即可排好順序；n=3時只要作三次比較即可。而當n較大時，問題就不那么容易處理了，要想直接解決一個規(guī)模較大的問題，有時是相當困難的。

分治法的設計思想：將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。

分治策略：對于一個規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設計策略叫做分治法。2.2 分治法 分治法所能解決的問題一般具有以下幾個特征： （1）該問題的規(guī)?？s小到一定的程度就可以容易地解決。 （2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結構性質(zhì)。 （3）利用該問題分解出的子問題的解可以合并為該問題的解。 （4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 上述的第一條特征是絕大多數(shù)問題都可以滿足的，因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加;第二條特征是應用分治法的前提它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應用;第三條特征是關鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動態(tài)規(guī)劃法。第四條特征涉及到分治法的效率，如果各子問題是不獨立的則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態(tài)規(guī)劃法較好。 分治法的基本步驟。 分治法在每一層遞歸上都有三個步驟： （1）分解：將原問題分解為若干個規(guī)模較小、相互獨立并且與原問題形式相同的子問題； （2）解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題； （3）合并：將各個子問題的解合并為原問題的解。 它的一般的算法設計模式如下：

Divide—and—Conquer（P） ①if|P|≤n0；2.2 分治法 ②thenreturn（ADHOC（P））； ③將P分解為較小的子問題P1，P2，…，Pk； ④fori←1tok； ⑤doyi←Divide—and—Conquer（Pi）；

∥遞歸解決Pi ⑥T←MERGE（y1，y2，…，yk）； ∥合并子問題 ⑦return（T）。

其中|P|表示問題P的規(guī)模；n0為一閾值，表示當問題P的規(guī)模不超過n0時，問題已容易直接解出，不必再繼續(xù)分解。ADHOC（P）是該分治法中的基本子算法，用于直接解小規(guī)模的問題P。因此，當P的規(guī)模不超過n0時直接用算法ADHOC（P）求解。算法MERGE（y1，y2，…，yk）是該分治法中的合并子算法，用于將P的子問題P1，P2，…，Pk的相應的解yl，y2，…，yk合并為P的解。

分治法的過程如圖2.2所示。2.2 分治法圖2.2分治法的過程 實際中分治法的應用很廣泛，信息學競賽中有很多經(jīng)典的應用。例如，歸并排序算法、快速排序算法和二分查找算法。下面我們介紹歸并排序算法和二分查找算法來更詳細的解釋分治法。

1.歸并排序算法 歸并排序是一種利用了分治法的排序算法。其可以分為三個步驟： ①將序列分為規(guī)模相等的兩部分。 ②對兩部分分別進行排序。 ③將已經(jīng)排過序的兩部分整合起來得到有序的原序列。 其中②可以繼續(xù)遞歸下去處理，整個遞歸樹只有O（lnn）層，故如果我們能在O（n）時間復雜度內(nèi)完成③，則整個算法時間復雜度為O（nlnn）。 歸并排序非常巧妙的應用了分治法，將原序列排序這個大問題，層層分治最后變成容易解決的小規(guī)模問題。歸并排序是分治法的經(jīng)典應用之一。

下面給出歸并排序算法的程序： /* prog：mergesort lang：c＋＋

*/ #include＜iostream＞

#include＜cstdio＞

usingnamespacestd；2.2 分治法 constintmaxn=100005；

intn，A[maxn]，tmp_A[maxn]；

voidMergeSort（int1，intr） ｛

if（1==r）return；

intmid=（1+r）＞＞1；

MergeSort（1，mid）；

MergeSort（mid+1，r）；

intp1=1，p2=mid+1；

for（inti=1；i＜=r；i++） ｛

if（p1＞mid）tmp_A[i]=A[p2]，p2++；

else

｛if（p2＞r）tmp_A[i]=A[P1]，p1++；

else

｛if（A[p1]＜A[p2]）tmp_A[i]=A[p1]，p1++；

elsetmp_A[i]=A[p2]，p2++；

｝ ｝

2.2 分治法 ｝

for（inti=1；i＜=r；i++）A[i]=tmp_A[i]；｝intmain（）｛ cin＞＞n；

for（inti=0；i＜n；i++）scanf（"%d"，&A[i]）；

MergeSort（0，n—1）；

for（inti=0；i＜n；i++）printf（"%d%c"，A[i]，i==n—1？′\n′：′′）；

return0；

｝2.2 分治法 2.二分查找算法

現(xiàn)在有一個嚴格單調(diào)遞增數(shù)列，要求在其中查找元素X（保證X一定存在）。數(shù)列中有n個數(shù)。 我們把數(shù)列從頭到尾查找一遍，時間復雜度O（n）。但是沒有用到嚴格單調(diào)遞增這個條件，利用二分查找算法可以在時間復雜度O（lnn）內(nèi)解決問題。 二分查找算法可以分為三個部分： ①如果當前區(qū)間只有一個數(shù)，那么必然是要查找的數(shù)。 ②將要查找的數(shù)與區(qū)間最中間的數(shù)進行比較，根據(jù)區(qū)間單調(diào)性可以確定要查找的數(shù)在左半部分區(qū)間還是在右半部分區(qū)間。 ③在新的區(qū)間內(nèi)繼續(xù)查找。 下面給出二分查找算法的程序：2.2 分治法2.2 分治法【2.2.2 分治法的應用】

【例2.4】比賽安排（NOIP1996提高組）。 設有2n（n≤6）個球隊進行單循環(huán)比賽，計劃在2n一1天內(nèi)完成，每個隊每天進行一場比賽，且在2n一1天內(nèi)每個隊都與不同的對手比賽。請編寫程序設計比賽安排表并按下表的格式輸出。 例如下面是n=2時的比賽安排表，見表2.1。表2.1n=2時的比賽安排表【算法分析】題目貌似很難下手，我們不妨嘗試一下找規(guī)律。

下面是n=1時的比賽安排表，見表2.2。2.2 分治法

表2.2n=1時的比賽安排表 對比兩個表，我們?nèi)菀装l(fā)現(xiàn)規(guī)律： ①表2.1的左上角與右下角和表2.2一樣。 ②表2.1的左下角和右上角一樣，且是表2.2每個值均加上2得到。 按照這兩個規(guī)律我們可以構造出n=3時的比賽安排表，注意這里要加上22，見表2.3。表2.3n=3時的比賽安排表2.2 分治法2.2 分治法2.2 分治法【2.3.1 貪心的概念與基本思想】 貪心法是解決一類最優(yōu)問題的策略。這種算法只選擇當前局部看起來的最佳策略，而不去考慮整體來講是否是最佳策略。正確的貪心算法應保證貪心策略的無后效性（即某個狀態(tài)以后的過程不影響以前的狀態(tài)，只和當前狀態(tài)有關）。

貪心法不能保證對所有問題均適用，但對很多最優(yōu)解的問題適用。

可以應用貪心法的題目必須具備貪心選擇和最優(yōu)子結構兩種性質(zhì)。所謂貪心選擇性質(zhì)，是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。貪心選擇是貪心法的核心，我們求整體最優(yōu)解的時候可以通過一系列局部最優(yōu)的選擇來達到，即我們可以迭代的選擇局部最優(yōu)選擇來得到全局最優(yōu)解。怎么去設計貪心選擇是貪心法的關鍵。最優(yōu)子結構性質(zhì)，是指一個問題的最優(yōu)解包含其子問題的最優(yōu)解。問題的最優(yōu)子結構性質(zhì)是該問題可用貪心算法求解的關鍵特征。

程序設計中，貪心算法的問題枚不勝數(shù)，且問題類型變化也很多，是信息學競賽的一個難點。貪心算法的經(jīng)典應用有單源最短路徑的Dijkstra算法（我們將在第5章介紹這種算法）、求解最小生成樹的Prim算法及Kruskal算法（我們將在第5章介紹這種算法）。很多時候貪心算法并不能保證正確性，但往往通過與隨機算法的結合可以得到靠近最優(yōu)解的近似算法，例如遺傳算法、模擬退火算法。對于這一類問題，通過一定的數(shù)學推導之后可以用貪心算法解決，這是貪心算法和數(shù)學的結合。

貪心算法類型繁多，我們主要通過例題來說明貪心算法的應用。2.3 貪心法【2.3.2 貪心法的應用】

【例2.7】背包問題。 給定背包的容量為W，給定n（n≤105）件物品，第i件物品的體積是w[i]，問背包至多能裝多少件物品?

【算法分析】顯然，背包的剩余的容量越大能裝的物品數(shù)越多。根據(jù)題意，每個物品除了體積以外沒有區(qū)別。那么我們可以得到以下貪心策略。 （1）將物品按體積從小到大排序。 （2）從體積最小的開始依次放入背包，直到背包不再能裝物品為止。

【設計技巧】排序可以應用algorithm庫中的sort函數(shù)。

【程序?qū)崿F(xiàn)】

/* prog：背包問題

lang：c++ */ #include＜iostream＞

#include＜cstdio＞

#include＜algorithm＞2.3 貪心法 usingnamespacestd； constintmaxn=100005； intw[maxn]； intmain（）

｝

intn，W；

cin＞＞n＞＞W(wǎng)；

for(inti=0；i＜n；i++)scanf("%d"，&w[i])；

sort（w，w+n）；

intres=0；

for(inti=0；i＜n&&W＞=w[i]；i++)res++，W—=w[i]；

cout＜＜res＜＜endl；

return0；

｝2.3 貪心法

【例2.8】線段。 在數(shù)軸上有n（n≤105）個線段，編號從0到n—1，第i條線段的左端點坐標為L[i]、右端點坐標為R[i]，且滿足對于任意的i，j∈[0，n—1]，i≠j都不滿足L[i]≤L[j]且R[i]≥R[j]（即不存在兩個線段滿足包含關系）。要求在數(shù)軸上選擇盡量少的點使得這個線段每個線段內(nèi)均有被選擇的點。 即求最小的K滿足K≤n且存在｛b1，b2，…，bk｝使得對于任意i∈[0，n—1]均存在j∈[1，K]使得L[i]≤b[j]≤R[i]，輸出最少要用多少個點即可。

【算法分析】將n個線段按照左端點坐標升序排序，下面證明這時右端點坐標為升序。 證明 我們利用反證法來證明這個結論。 若排序后存在i，j∈[0，n—1]且i＜j，R[i]≥R[j]。 即存在i，j∈[0，n—1]且L[i]≤L[j]，R[i]≥R[j]。 矛盾。故排序后右端點坐標也為升序。 證畢。 這時我們得到了n個左右端點都升序的線段，如圖2.8所示：圖2.8 線段2.3 貪心法 設f[i]為最少需要多少個點才能"覆蓋"第i條線段到第n一1條線段（這里的編號是排序之后的編號）。那么f[0]就是我們要求的答案。 如果我們要求f[i]，那么先選擇R[i]這個點，如果此時編號從i到n一1的線段均被"覆蓋"則f[i]=1。否則找到編號最小的不被"覆蓋"的線段j，那么f[i]=f[j]＋1。 這樣我們在貪心策略的基礎上得到了遞推式。下面我們來證明這樣的貪心策略是正確的。

證明 如果選擇R[i]這個點編號從i到n—1的線段均被"覆蓋"，那么這一定是最優(yōu)方案。我們只需討論不能全部被"覆蓋"的情況。 顯然，f[i]是不下降的序列，那么我們只需要證明選擇R[i]這個點能使得遞推式中的j最小即可。 因為這n條線段左右端點均單調(diào)遞增。顯然選擇R[i]這個點能使得遞推式中的j最小。 證畢。 因為數(shù)據(jù)規(guī)模較大，這里的值要用二分法求出。 總時間復雜度O（nlnn）。

【設計技巧】我們需要倒著去求f數(shù)組。排序可以用algorithm庫中sort函數(shù)。 【程序?qū)崿F(xiàn)】 /* prog：segmemt lang：c++ */2.3 貪心法2.3 貪心法2.3 貪心法【2.4.1 搜索與回溯的概念與基本思想】

搜索算法如同其字面意思，即窮舉所有的可能情況去解決問題，搜索算法的復雜度往往是指數(shù)級，數(shù)據(jù)規(guī)模稍大運算時間可能就會是天文數(shù)字，但搜索算法往往是解決問題最直接的方式。有些問題沒有更優(yōu)秀的方法只能應用搜索算法解決問題。搜索算法往往也用作和其他算法相互配合解決問題。

搜索算法的實質(zhì)就是構造一個“搜索樹”，這個“搜索樹”表達了整個搜索算法的過程。搜索算法從一個初始狀態(tài)出發(fā)根據(jù)一定的擴展規(guī)則來進行搜索過程，最后形成的整個過程就是一個“搜索樹”。也就相當于我們將一個問題的解決過程已經(jīng)抽象成了圖論中的模型——樹，即我們的搜索算法相當于在這個樹上進行某種形式的遍歷，如圖2.9所示。圖2.9 搜索樹2.4 搜索法與回溯法 一種搜索算法相當于樹的遍歷，通常我們有兩種實現(xiàn)方式，深度優(yōu)先搜索（簡稱DFS）和廣度優(yōu)先搜索（簡稱BFS）。 回溯算法的基本思想是：為了求得待解問題的解，我們先選擇一種可能的情況向前搜索，一旦發(fā)現(xiàn)原來的選擇是錯誤（也就是這種選擇會導致問題無解）就退回來重新選擇，如此反復進行。直到得到問題的解，或者在窮舉完所有情況后，判斷原問題無解。 下面我們來介紹深度優(yōu)先搜索和廣度優(yōu)先搜索： （1）深度優(yōu)先搜索。顧名思義，深度優(yōu)先搜索即是深度優(yōu)先的搜索算法，即在搜索樹上優(yōu)先深度遍歷。深度優(yōu)先搜索通常用遞歸法的方法實現(xiàn)。 （2）廣度優(yōu)先搜索。對比深度優(yōu)先搜索，廣度優(yōu)先搜索是以廣度優(yōu)先的搜索算法，即在搜索樹上一層層遍歷，第0層和第1層全部遍歷完才會遍歷第2層，廣度優(yōu)先搜索通常用循環(huán)結構就可以實現(xiàn)。 對比這兩種搜索算法，我們發(fā)現(xiàn)深度優(yōu)先搜索是以棧結構為基礎的搜索算法，而廣度優(yōu)先搜索是以隊列結構為基礎的搜索算法。2.4 搜索法與回溯法【2.4.2 搜索法與回溯法的應用】

【例2.11】跳馬。 如圖2.10所示的5×5的棋盤上，從左下角的方格出發(fā)，按照日字跳馬，要求不重復地跳過所有方格。輸出方案數(shù)。

【算法分析】用窗口坐標系表示棋盤上的每個格子，那么我們從（x，y）只能跳往（x—2，y—1）、（x—2，y＋1）、（x—1，y—2）、（x—1，y＋2）、（x＋1，y—2）、（x＋1，y＋2）、（x＋2，y—1）和（x＋2，y＋1）這八個格子。 我們采用深度優(yōu)先搜索，狀態(tài)表示為當前所在格子的坐標。那么初始狀態(tài)為（1，1），那么每個狀態(tài)可以擴展的狀態(tài)最多只有八個。 題目還要求不能重復經(jīng)過。我們需要加一個標志數(shù)組，標志哪些格子已經(jīng)經(jīng)過了，繼續(xù)往下搜的時候加標志搜完了退回來去掉標志即可。 一直重復這個過程直至所有狀態(tài)均已搜索出來。

【設計技巧】標志數(shù)組必須是全局變量。

【程序?qū)崿F(xiàn)】 /* Prog：跳馬 lang：c＋＋

*/2.4 搜索法與回溯法圖2.10 棋盤 #include＜iostream＞ #include＜cstring＞ usingnamespacestd； constintdir_x[8]={—2,—2,—1,—1,2,2,1,1}； constintdir_y[8]={—1,1,—2,2,—1,1,—2,2}； boolvis[5][5]； intans=0； voidDFS(intx,inty,intdeep)

｛

if(deep＞=24)

｛

ans＋＋；

return；

｝

2.4 搜索法與回溯法 for(inti=0；i＜8；i＋＋) if(x＋dir_x[i]＞=0&&x＋dir_xi＜5) if(y＋dir_y[i]＞=O&&y＋dir_y[i]＜5) if(！vis[x＋dir_x[i]][y＋dir_y[i]])

｛

vis[x＋dir_x[i]][y＋dir_y[i]]=true；

DFS(x＋dir_x[i],y＋dir_y[i],deep＋1)；

vis[x＋dir_x[i]][y＋dir_yti]=false；

｝

｝ intmain（）

｛