信息學(xué)奧賽——算法入門教程精編版

1、全國青少年信息學(xué)奧林匹克聯(lián)賽算法講義算法基礎(chǔ)篇2算法具有五個(gè)特征：2信息學(xué)奧賽中的基本算法( 枚舉法 )4采用枚舉算法解題的基本思路：4枚舉算法應(yīng)用4信息學(xué)奧賽中的基本算法( 回溯法 )7回溯 基本思想8信息學(xué)奧賽中的基本算法( 遞歸算法 )10遞歸算法的定義：10遞歸算法應(yīng)用11算法在信息學(xué)奧賽中的應(yīng)用( 遞推法 )14遞推法應(yīng)用14算法在信息學(xué)奧賽中的應(yīng)用( 分治法 )18分治法應(yīng)用18信息學(xué)奧賽中的基本算法( 貪心法 )21貪心法應(yīng)用21算法在信息學(xué)奧賽中的應(yīng)用（搜索法一）24搜索算法應(yīng)用25算法在信息學(xué)奧賽中的應(yīng)用（搜索法二）28廣度優(yōu)先算法應(yīng)用29算法在信息學(xué)奧賽中的應(yīng)用（動(dòng)態(tài)規(guī)劃法

2、）32動(dòng)態(tài)規(guī)劃算法應(yīng)用331算法基礎(chǔ)篇學(xué)習(xí)過程序設(shè)計(jì)的人對算法這個(gè)詞并不陌生，從廣義上講，算法是指為解決一個(gè)問題而采用的方法和步驟；從程序計(jì)設(shè)的角度上講，算法是指利用程序設(shè)計(jì)語言的各種語句，為解決特定的問題而構(gòu)成的各種邏輯組合。我們在編寫程序的過程就是在實(shí)施某種算法，因此程序設(shè)計(jì)的實(shí)質(zhì)就是用計(jì)算機(jī)語言構(gòu)造解決問題的算法。算法是程序設(shè)計(jì)的靈魂，一個(gè)好的程序必須有一個(gè)好的算法，一個(gè)沒有有效算法的程序就像一個(gè)沒有靈魂的軀體。算法具有五個(gè)特征：1、有窮性： 一個(gè)算法應(yīng)包括有限的運(yùn)算步驟，執(zhí)行了有窮的操作后將終止運(yùn)算，不能是個(gè)死循環(huán)；2、確切性： 算法的每一步驟必須有確切的定義，讀者理解時(shí)不會(huì)產(chǎn)生二義性

3、。并且，在任何條件下，算法只有唯一的一條執(zhí)行路徑，對于相同的輸入只能得出相同的輸出。如在算法中不允許有“計(jì)算 8/0 ”或“將 7 或 8 與 x 相加”之類的運(yùn)算，因?yàn)榍罢叩挠?jì)算結(jié)果是什么不清楚，而后者對于兩種可能的運(yùn)算應(yīng)做哪一種也不知道。3、輸入：一個(gè)算法有0 個(gè)或多個(gè)輸入，以描述運(yùn)算對象的初始情況，所謂0個(gè)輸入是指算法本身定義了初始條件。如在5 個(gè)數(shù)中找出最小的數(shù)，則有5 個(gè)輸入。4、輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果，這是算法設(shè)計(jì)的目的。它們是同輸入有著某種特定關(guān)系的量。如上述在 5 個(gè)數(shù)中找出最小的數(shù)，它的出輸出為最小的數(shù)。如果一個(gè)程序沒有輸出，這個(gè)程序就毫

4、無意義了；5、可行性： 算法中每一步運(yùn)算應(yīng)該是可行的。算法原則上能夠精確地運(yùn)行，而且人能用筆和紙做有限次運(yùn)算后即可完成。如何來評價(jià)一個(gè)算法的好壞呢？主要是從兩個(gè)方面：一是看算法運(yùn)行所占用的時(shí)間；我們用時(shí)間復(fù)雜度來衡量，例如：在以下 3 個(gè)程序中，（1）x:=x+1（2）for i:=1 to n dox:=x+1（3）for i:=1 to n dofor j:=1 to n dox:=x+11，n 和 n2 則這三個(gè)含基本操作“ x 增 1”的語句 x:=x+1 的出現(xiàn)的次數(shù)分別為程序段的時(shí)間復(fù)雜度分別為O（ 1），O（n），O（ n2），分別稱為常量階、線性階和平方階。在算法時(shí)間復(fù)雜度的表

5、示中，還有可能出現(xiàn)的有：對數(shù)階O(log n) ，指n數(shù)階 O(2 ) 等。在 n 很大時(shí)，不同數(shù)量級(jí)的時(shí)間復(fù)雜度有： O(1)< O(log n)<O(n)< O(nlog n)<O(n 2) <O(n 3) <O(2 n ) ，很顯然，指數(shù)階的算法不是一個(gè)好的算法。二是看算法運(yùn)行時(shí)所占用的空間，既空間復(fù)雜度。由于當(dāng)今計(jì)算機(jī)硬件技術(shù)發(fā)展很快，程序所能支配的自由空間一般比較充分，所以空間復(fù)雜度就不如時(shí)間2復(fù)雜度那么重要了，有許多問題人們主要是研究其算法的時(shí)間復(fù)雜度，而很少討論它的空間耗費(fèi)。時(shí)間復(fù)雜性和空間復(fù)雜性在一定條件下是可以相互轉(zhuǎn)化的。在中學(xué)生信息學(xué)奧賽

6、中，對程序的運(yùn)行時(shí)間作出了嚴(yán)格的限制，如果運(yùn)行時(shí)間超出了限定就會(huì)判錯(cuò)，因此在設(shè)計(jì)算法時(shí)首先要考慮的是時(shí)間因素，必要時(shí)可以以犧牲空間來換取時(shí)間，動(dòng)態(tài)規(guī)劃法就是一種以犧牲空間換取時(shí)間的有效算法。對于空間因素，視題目的要求而定，一般可以不作太多的考慮。我們通過一個(gè)簡單的數(shù)值計(jì)算問題，來比較兩個(gè)不同算法的效率（在這里只比較時(shí)間復(fù)雜度）。例：求 N！所產(chǎn)生的數(shù)后面有多少個(gè)0（中間的 0 不計(jì)）。算法一：從 1 乘到 n，每乘一個(gè)數(shù)判斷一次，若后面有0 則去掉后面的 0，并記下0 的個(gè)數(shù)。為了不超出數(shù)的表示范圍，去掉與生成0 無關(guān)的數(shù)，只保留有效位數(shù)，當(dāng)乘完 n 次后就得到 0 的個(gè)數(shù)。（ pascal

7、程序如下）vari,t,n,sum:longint;begint:=0; sum:=1;readln(n);for i:=1 to n dobeginsum:=sum*i;while sum mod 10=0 dobeginsum:=sum div 10;inc(t);計(jì)數(shù)器增加 1end;sum:=sum mod 1000; 舍去與生成 0 無關(guān)的數(shù) end;writeln(t:6);end.算法二：此題中生成 O的個(gè)數(shù)只與含 5 的個(gè)數(shù)有關(guān)， n！的分解數(shù)中含 5 的個(gè)數(shù)就等于末尾 O的個(gè)數(shù)，因此問題轉(zhuǎn)化為直接求 n！的分解數(shù)中含 5 的個(gè)數(shù)。var t,n:integer;beginre

8、adln(n);t:=0;repeatn:=n div 5 ;inc(t,n); 計(jì)數(shù)器增加 nuntil n<5;writeln(t:6);end.3分析對比兩種算法就不難看出，它們的時(shí)間復(fù)雜度分別為 O（N）、O（logN ）,算法二的執(zhí)行時(shí)間遠(yuǎn)遠(yuǎn)小于算法一的執(zhí)行時(shí)間。在信息學(xué)奧賽中，其主要任務(wù)就是設(shè)計(jì)一個(gè)有效的算法，去求解所給出的問題。如果僅僅學(xué)會(huì)一種程序設(shè)計(jì)語言，而沒學(xué)過算法的選手在比賽中是不會(huì)取得好的成績的，選手水平的高低在于能否設(shè)計(jì)出好的算法。下面，我們根據(jù)全國分區(qū)聯(lián)賽大綱的要求，一起來探討信息學(xué)奧賽中的基本算法。信息學(xué)奧賽中的基本算法(枚舉法 )枚舉法，常常稱之為窮舉法，是

9、指從可能的集合中一一枚舉各個(gè)元素，用題目給定的約束條件判定哪些是無用的，哪些是有用的。能使命題成立者，即為問題的解。采用枚舉算法解題的基本思路：（1） 確定枚舉對象、枚舉范圍和判定條件；（2） 一一枚舉可能的解，驗(yàn)證是否是問題的解下面我們就從枚舉算法的的優(yōu)化、枚舉對象的選擇以及判定條件的確定，這三個(gè)方面來探討如何用枚舉法解題。枚舉算法應(yīng)用例 1：百錢買百雞問題： 有一個(gè)人有一百塊錢， 打算買一百只雞。 到市場一看，大雞三塊錢一只，小雞一塊錢三只，不大不小的雞兩塊錢一只?，F(xiàn)在，請你編一程序，幫他計(jì)劃一下，怎么樣買法，才能剛好用一百塊錢買一百只雞？算法分析：此題很顯然是用枚舉法，我們以三種雞的個(gè)數(shù)

10、為枚舉對象（分別設(shè)為 x,y,z ）, 以三種雞的總數(shù)（ x+y+z）和買雞用去的錢的總數(shù) (x*3+y*2+z) 為判定條件，窮舉各種雞的個(gè)數(shù)。下面是解這個(gè)百雞問題的程序var x,y,z:integer;beginfor x:=0 to 100 dofor y:=0 to 100 dofor z:=0 to 100 do枚舉所有可能的解 if(x+y+z=100)and(x*3+y*2+zdiv3=100)and(zmod3=0)thenwriteln('x=',x,'y=',y,'z=',z); 驗(yàn)證可能的解，并輸出符合題目要求的解end.

11、上面的條件還有優(yōu)化的空間，三種雞的和是固定的，我們只要枚舉二種雞（ x,y ），第三種雞就可以根據(jù)約束條件求得（ z=100-x-y ），這樣就縮小了枚舉范圍，請看下面的程序：4var x,y,z:integer;beginfor x:=0 to 100 dofor y:=0 to 100-x dobeginz:=100-x-y;if(x*3+y*2+zdiv3=100)and(zmod3=0)thenwriteln('x=',x,'y=',y,'z=',z);end;end.未經(jīng)優(yōu)化的程序循環(huán)了1013 次，時(shí)間復(fù)雜度為O(n3) ；優(yōu)化后的程

12、序只循環(huán)了（ 102*101/2 ）次 ，時(shí)間復(fù)雜度為 O(n2 ) 。從上面的對比可以看出，對于枚舉算法，加強(qiáng)約束條件，縮小枚舉的范圍，是程序優(yōu)化的主要考慮方向。在枚舉算法中，枚舉對象的選擇也是非常重要的，它直接影響著算法的時(shí)間復(fù)雜度，選擇適當(dāng)?shù)拿杜e對象可以獲得更高的效率。如下例：例 2、將 1,2.9 共 9 個(gè)數(shù)分成三組 , 分別組成三個(gè)三位數(shù) , 且使這三個(gè)三位數(shù)構(gòu)成 1:2:3 的比例 , 試求出所有滿足條件的三個(gè)三位數(shù) .例如 : 三個(gè)三位數(shù) 192,384,576 滿足以上條件 .(NOIP1998pj)算法分析：這是 1998 年全國分區(qū)聯(lián)賽普及組試題 （簡稱 NOIP1998

13、pj，以下同）。此題數(shù)據(jù)規(guī)模不大，可以進(jìn)行枚舉，如果我們不加思地以每一個(gè)數(shù)位為枚舉對象，一位一位地去枚舉：for a:=1 to 9 dofor b:=1 to 9 dofor i:=1 to 9 do這樣下去，枚舉次數(shù)就有9次，如果我們分別設(shè)三個(gè)數(shù)為x,2x,3x ，以 x 為枚舉對象，窮舉的范圍就減少為，在細(xì)節(jié)上再進(jìn)一步優(yōu)化，枚舉范圍就更少了。程序如下：vart,x:integer;s,st:string;c:char;beginfor x:=123 to 321 do 枚舉所有可能的解 begint:=0;str(x,st);把整數(shù) x 轉(zhuǎn)化為字符串，存放在st 中 str(x*2,s)

14、; st:=st+s;5str(x*3,s); st:=st+s;for c:='1' to '9' do枚舉 9 個(gè)字符，判斷是否都在st 中if pos(c,st)<>0 then inc(t) else break;如果不在 st 中，則退出循環(huán) if t=9 thenwriteln(x,' ',x*2,' ',x*3);end;end.在枚舉法解題中，判定條件的確定也是很重要的，如果約束條件不對或者不全面，就窮舉不出正確的結(jié)果，我們再看看下面的例子。例 一元三次方程求解 (noip2001tg)問題描述 有形如

15、： ax3+bx2+cx+d=0 這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù) (a，b，c，d 均為實(shí)數(shù) )，并約定該方程存在三個(gè)不同實(shí)根 (根的范圍在 -100 至 100 之間 )，且根與根之差的絕對值 >=1。要求由小到大依次在同一行輸出這三個(gè)實(shí)根 (根與根之間留有空格 )，并精確到小數(shù)點(diǎn)后 2 位。提示：記方程 f(x)=0 ，若存在 2 個(gè)數(shù) x1 和 x2，且 x1<x2，f(x1)*(x2)<0 ，則在(x1，x2)之間一定有一個(gè)根。樣例輸入： 1-5-420輸出： -2.002.005.00算法分析：由題目的提示很符合二分法求解的原理，所以此題可以用二分法

16、。用二分法解題相對于枚舉法來說很要復(fù)雜很多。此題是否能用枚舉法求解呢？再分析一下題目，根的范圍在-100 到 100 之間，結(jié)果只要保留兩位小數(shù)，我們不妨將根的值域擴(kuò)大100 倍（ -10000<=x<=10000），再以根為枚舉對象，枚舉范圍是-10000 到 10000，用原方程式進(jìn)行一一驗(yàn)證，找出方程的解。有的同學(xué)在比賽中是這樣做vark:integer;a,b,c,d,x :real;beginread(a,b,c,d);for k:=-10000 to 10000 dobeginx:=k/100;if a*x*x*x+b*x*x+c*x+d=0 then write(x:

17、0:2,' ');end;end.用這種方法，很快就可以把程序編出來，再將樣例數(shù)據(jù)代入測試也是對的，等成績下來才發(fā)現(xiàn)這題沒有全對，只得了一半的分。這種解法為什么是錯(cuò)的呢？錯(cuò)在哪里？前面的分析好象也沒錯(cuò)啊， 難道這題不能用枚舉法做嗎？ 看到這里大家可能有點(diǎn)迷惑了。6在上面的解法中，枚舉范圍和枚舉對象都沒有錯(cuò)，而是在驗(yàn)證枚舉結(jié)果時(shí)，判定條件用錯(cuò)了。因?yàn)橐Ａ舳恍?shù)，所以求出來的解不一定是方程的精確根，再 代入 ax3+bx2+cx+d 中， 所得 的結(jié)果也就不 一定 等于 0， 因此用原 方程 ax3+bx2+cx+d=0 作為判斷條件是不準(zhǔn)確的。我們換一個(gè)角度來思考問題，設(shè) f

18、(x)=ax 3+bx2+cx+d，若 x 為方程的根，則根據(jù)提示可知，必有 f(x-0.005)*(x+0.005)<0 ，如果我們以此為枚舉判定條件，問題就逆刃而解。另外，如果 f(x-0.005)=0 ，哪么就說明 x-0.005 是方程的根，這時(shí)根據(jù)四舍5 入，方程的根也為x。所以我們用 (f(x-0.005)*f(x+0.005)<0)和(f(x-0.005)=0)作為判定條件。為了程序設(shè)計(jì)的方便，我們設(shè)計(jì)一個(gè)函數(shù)f(x) 計(jì)算 ax3+bx2+cx+d 的值，程序如下： $N+var k:integer;a,b,c,d,x:extended;function f(x:e

19、xtended):extended; 計(jì)算 ax3+bx2 +cx+d 的值 beginf:=(a*x+b)*x+c)*x+d;end;beginread(a,b,c,d);for k:=-10000 to 10000 dobeginx:=k/100;if (f(x-0.005)*f(x+0.005)<0) or (f(x-0.005)=0) then write(x:0:2,''); 若 x 兩端的函數(shù)值異號(hào)或 x-0.005 剛好是方程的根，則確定 x 為方程的根 end;end.用枚舉法解題的最大的缺點(diǎn)是運(yùn)算量比較大，解題效率不高，如果枚舉范圍太大（一般以不超過兩百

20、萬次為限） ，在時(shí)間上就難以承受。但枚舉算法的思路簡單，程序編寫和調(diào)試方便，比賽時(shí)也容易想到，在競賽中，時(shí)間是有限的，我們競賽的最終目標(biāo)就是求出問題解，因此，如果題目的規(guī)模不是很大，在規(guī)定的時(shí)間與空間限制內(nèi)能夠求出解，那么我們最好是采用枚舉法，而不需太在意是否還有更快的算法，這樣可以使你有更多的時(shí)間去解答其他難題。信息學(xué)奧賽中的基本算法(回溯法 )如果上期的“百錢買百雞”中雞的種類數(shù)是變化的，用枚舉法就無能為力了，7這里介紹另一種算法回溯法?；厮莼舅枷牖厮莘ㄊ且环N既帶有系統(tǒng)性又帶有跳躍性的搜索法，它的基本思想是：在搜索過程中，當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先的選擇達(dá)不到目標(biāo)，就退回到上一步重新選擇

21、。它主要用來解決一些要經(jīng)過許多步驟才能完成的，而每個(gè)步驟都有若干種可能的分支，為了完成這一過程，需要遵守某些規(guī)則，但這些規(guī)則又無法用數(shù)學(xué)公式來描述的一類問題。下面通過實(shí)例來了解回溯法的思想及其在計(jì)算機(jī)上實(shí)現(xiàn)的基本方法。例 1、從 N 個(gè)自然數(shù) (1,2, ,n)中選出 r 個(gè)數(shù)的所有組合。算法分析：設(shè)這 r 個(gè)數(shù)為 a1,a 2 , ar , 把它們從大到小排列，則滿足：（ 1） a 1>a2> >ar ;（ 2） 其中第 i 位數(shù) (1<=i<=r) 滿足 ai >r-i;我們按以上原則先確定第一個(gè)數(shù)，再逐位生成所有的 r 個(gè)數(shù)，如果當(dāng)前數(shù)符合要求，則添加

22、下一個(gè)數(shù) ; 否則返回到上一個(gè)數(shù)，改變上一個(gè)數(shù)的值再判斷是否符合要求，如果符合要求，則繼續(xù)添加下一個(gè)數(shù)，否則返回到上一個(gè)數(shù)，改變上一個(gè)數(shù)的值 按此規(guī)則不斷循環(huán)搜索，直到找出 r 個(gè)數(shù)的組合，這種求解方法就是回溯法。如果按以上方法生成了第 i 位數(shù) ai ，下一步的的處理為：（1） 若 ai >r-i 且 i=r ，則輸出這 r 個(gè)數(shù)并改變 ai 的值 :a i =ai -1;（2） 若 ai >r-i且 i r ，則繼續(xù)生成下一位ai+1 =ai -1;（3） 若 ai <=r-i ，則回溯到上一位，改變上一位數(shù)的值:a i-1 =ai-1 -1;算法實(shí)現(xiàn)步驟：第一步：輸入

23、n,r 的值，并初始化； i:=1;a1:=n; 第二步：若 a1>r-1 則重復(fù)：若 ai>r-i ，若 i=r ，則輸出解，并且 ai:=ai-1;若 i<>r ，則繼續(xù)生成下一位： ai+1:=ai-1; i:=i+1;若 ai<=r-i ，則回溯： i:=i-1; ai:=ai-1;第三步：結(jié)束；程序?qū)崿F(xiàn)var n,r,i,j:integer; a:array1.10 of integer;begin readln(n,r);i:=1;a1:=n;repeatthen 符合條件 if ai>r-iif i=rthen 輸出 beginfor j:=1

24、 to r do write(aj:3);writeln;ai:=ai-1;end繼續(xù)搜索 else elsebegin ai+1:=ai-1; i:=i+1;end回溯 begini:=i-1; ai:=ai-1;end;8until a1=r-1;end.下面我們再通過另一個(gè)例子看看回溯在信息學(xué)奧賽中的應(yīng)用。例 2 數(shù)的劃分（ noip2001tg）問題描述整數(shù) n 分成 k 份，且每份不能為空，任意兩份不能相同(不考慮順序 )。例如： n=7， k=3，下面三種分法被認(rèn)為是相同的。1，1，5;1， 5， 1;5，1，1;問有多少種不同的分法。輸入： n，k(6<n<=200，

25、2<=k<=6)輸出：一個(gè)整數(shù)，即不同的分法。樣例輸入：73輸出： 4 四種分法為： 1,1,5; 1,2,4; 1,3,3; 2,2,3;算法分析：此題可以用回溯法求解，設(shè)自然數(shù)n 拆分為 a1,a 2,a k, 必須滿足以下兩個(gè)條件：（ 1） n=a 1 +a2+ +ak ；（ 2） a 1<=a2<= <=ak ( 避免重復(fù)計(jì)算 ) ；現(xiàn) 假 設(shè) 己 求 得 的 拆 分 數(shù) 為a1 ,a 2,ai , 且 都 滿 足 以 上 兩 個(gè) 條 件 , 設(shè)sum=n-a1-a 2-a i , 我們根據(jù)不同的情形進(jìn)行處理：（ 1） 如果 i=k, 則得到一個(gè)解，則計(jì)數(shù)

26、器 t 加 1，并回溯到上一步， 改變 ai-1 的值；（ 2） 如果 i<k 且 sum>=ai, 則添加下一個(gè)元素 ai+1 ；（ 3） 如果 i<k 且 sum<ai, 則說明達(dá)不到目標(biāo)，回溯到上一步，改變 ai-1 的值；算法實(shí)現(xiàn)步驟如下：第一步：輸入自然數(shù)n,k 并初始化； t:=0; i:=1;ai:=1; sum:=n-1; nk:=n divk;第二步：如果 a1<=nk重復(fù)：若 i=k ，搜索到一個(gè)解，計(jì)數(shù)器 t=t+1; 并回溯；否則：若 sum>=ai 則繼續(xù)搜索；若 sum<ai 則回溯；搜索時(shí)， inc(i);ai:=ai-1

27、;sum:=sum-ai;回溯時(shí)， dec(i); inc(ai); sum:=sum+ai+1-1; 第三步：輸出。程序如下：varn,nk,sum,i,k:integer;t:longint;9a:array1.6of integer;beginreadln(n,k);nk:=n div k;t:=0; i:=1;ai:=1; sum:=n-1;初始化 repeatif i=k then判斷是否搜索到底 begin inc(t); dec(i);inc(ai); sum:=sum+ai+1-1; end 回溯 else beginif sum>=ai then 判斷是否回溯 begi

28、n inc(i);ai:=ai-1;sum:=sum-ai;end繼續(xù)搜 else begin dec(i); inc(ai); sum:=sum+ai+1-1; end;回溯 end;until a1>nk;writeln(t);end.回溯法是通過嘗試和糾正錯(cuò)誤來尋找答案，是一種通用解題法，在 NOIP中有許多涉及搜索問題的題目都可以用回溯法來求解。信息學(xué)奧賽中的基本算法( 遞歸算法 )遞歸算法的定義：如果一個(gè)對象的描述中包含它本身，我們就稱這個(gè)對象是遞歸的，這種用遞歸來描述的算法稱為遞歸算法。我們先來看看大家熟知的一個(gè)的故事：從前有座山，山上有座廟，廟里有個(gè)老和尚在給小和尚講故事，

29、他說從前有座山，山上有座廟，廟里有個(gè)老和尚在給小和尚講故事，他說 上面的故事本身是遞歸的，用遞歸算法描述：procedure bonze-tell-story；beginif講話被打斷 then故事結(jié)束else begin從前有座山，山上有座廟，廟里有個(gè)老和尚在給小和尚講故事；bonze-tell-story；endend;從上面的遞歸事例不難看出，遞歸算法存在的兩個(gè)必要條件：（1） 必須有遞歸的終止條件；10（2） 過程的描述中包含它本身；在設(shè)計(jì)遞歸算法中，如何將一個(gè)問題轉(zhuǎn)化為遞歸的問題，是初學(xué)者面臨的難題，下面我們通過分析漢諾塔問題，看看如何用遞歸算法來求解問題；遞歸算法應(yīng)用例 1：漢諾塔

30、問題，如下圖，有 A、B、C 三根柱子。 A 柱子上按從小到大的順序堆放了 N個(gè)盤子，現(xiàn)在要把全部盤子從 A 柱移動(dòng)到 C 柱，移動(dòng)過程中可以借助 B 柱。移動(dòng)時(shí)有如下要求：（1） 一次只能移動(dòng)一個(gè)盤子；（2） 不允許把大盤放在小盤上邊；（3） 盤子只能放在三根柱子上；算法分析：當(dāng)盤子比較多的時(shí)，問題比較復(fù)雜，所以我們先分析簡單的情況：如果只有一個(gè)盤子，只需一步，直接把它從 A 柱移動(dòng)到 C柱；如果是二個(gè)盤子，共需要移動(dòng) 3 步 : （1） 把 A 柱上的小盤子移動(dòng)到 B 柱;（2） 把 A 柱上的大盤子移動(dòng)到C柱；（3） 把 B 柱上的大盤子移動(dòng)到C柱；如果 N 比較大時(shí)，需要很多步才能完成

31、，我們先考慮是否能把復(fù)雜的移動(dòng)過程轉(zhuǎn)化為簡單的移動(dòng)過程，如果要把A 柱上最大的盤子移動(dòng)到C 柱上去，必須先把上面的 N-1 個(gè)盤子從 A 柱移動(dòng)到 B 柱上暫存，按這種思路，就可以把N 個(gè)盤子的移動(dòng)過程分作3 大步：（ 1） 把 A 柱上面的 N-1 個(gè)盤子移動(dòng)到 B 柱；（ 2） 把 A 柱上剩下的一個(gè)盤子移動(dòng)到 C柱；（ 3） 把 B 柱上面的 N-1 個(gè)盤子移動(dòng)到 C柱；其中 N-1 個(gè)盤子的移動(dòng)過程又可按同樣的方法分為三大步，這樣就把移動(dòng)過程轉(zhuǎn)化為一個(gè)遞歸的過程，直到最后只剩下一個(gè)盤子，按照移動(dòng)一個(gè)盤子的方法移動(dòng)，遞歸結(jié)束。遞歸過程：procedure Hanoi(N,A,B,C:in

32、teger;)； 以 B 柱為中轉(zhuǎn)柱將N 個(gè)盤子從 A 柱移動(dòng)到 C柱beginif N=1 then write(A, -> ,C) 把盤子直接從 A 移動(dòng)到 Celse beginHanoi(N-1,A,C,B)； 以 C柱為中轉(zhuǎn)柱將 N-1 個(gè)盤子從 A 柱移動(dòng)到 B 柱 write(A, -> ,C) ； 把剩下的一個(gè)盤子從A 移動(dòng)到 CHanoi(N-1,B,A,C)； 以 A 柱為中轉(zhuǎn)柱將 N-1 個(gè)盤子從 B 柱移動(dòng)到 C柱end;end;11從上面的例子我們可以看出，在使用遞歸算法時(shí)，首先弄清楚簡單情況下的解法，然后弄清楚如何把復(fù)雜情況歸納為更簡單的情況。在信息學(xué)奧

33、賽中有的問題的結(jié)構(gòu)或所處理的數(shù)據(jù)本身是遞歸定義的，這樣的問題非常適合用遞歸算法來求解，對于這類問題，我們把它分解為具有相同性質(zhì)的若干個(gè)子問題，如果子問題解決了，原問題也就解決了。例 2 求先序排列 (NOIP2001pj) 問題描述 給出一棵二叉樹的中序與后序排列。求出它的先序排列。 ( 約定樹結(jié)點(diǎn)用不同的大寫字母表示，長度 8) 。 樣例 輸入： BADC BDCA輸出： ABCD算法分析：我們先看看三種遍歷的定義：先序遍歷是先訪問根結(jié)點(diǎn)，再遍歷左子樹，最后遍歷右子樹；中序遍歷是先遍歷左子樹，再訪問根結(jié)點(diǎn)，最后遍歷右子樹；后序遍歷是先遍歷左子樹，再遍歷右子樹，最后訪問根結(jié)點(diǎn)；從遍歷的定義可知

34、，后序排列的最后一個(gè)字符即為這棵樹的根節(jié)點(diǎn)；在中序排列中，根結(jié)點(diǎn)前面的為其左子樹，根結(jié)點(diǎn)后面的為其右子樹；我們可以由后序排列求得根結(jié)點(diǎn)，再由根結(jié)點(diǎn)在中序排列的位置確定左子樹和右子樹，把左子樹和右子樹各看作一個(gè)單獨(dú)的樹。這樣，就把一棵樹分解為具有相同性質(zhì)的二棵子樹，一直遞歸下去，當(dāng)分解的子樹為空時(shí)，遞歸結(jié)束，在遞歸過程中，按先序遍歷的規(guī)則輸出求得的各個(gè)根結(jié)點(diǎn)，輸出的結(jié)果即為原問題的解。源程序program noip2001_3;varz,h : string;procedure make(z,h:string); z為中序排列 ,h 為后序排列 vars,m : integer;beginm:=

35、length(h);m為樹的長度 write(hm); 輸出根節(jié)點(diǎn) s:=pos(hm,z); 求根節(jié)點(diǎn)在中序排列中的位置if s>1 then make(copy(z,1,s-1),copy(h,1,s-1); 處理左子樹 if m>s then make(copy(z,s+1,m-s),copy(h,s,m-s); 處理右子樹 end;beginreadln(z);readln(h);make(z,h);end.遞歸算法不僅僅是用于求解遞歸描述的問題，在其它很多問題中也可以用到遞歸思想，如回溯法、分治法、動(dòng)態(tài)規(guī)劃法等算法中都可以使用遞歸思想來實(shí)現(xiàn)，從而使編寫的程序更加簡潔。比如

36、上期回溯法所講的例 2數(shù)的劃分問題，若用遞歸來求解，程序非常短小且效率很高，源程序如下12varn,k:integer;tol:longint;procedure make(sum,t,d:integer);var i:integer;beginif d=k then inc(tol)else for i:=t to sum div 2 do make(sum-i,i,d+1); end;beginreadln(n,k);tol:=0;make(n,1,1);writeln(tol);end.有些問題本身是遞歸定義的，但它并不適合用遞歸算法來求解，如斐波那契 (Fibonacci) 數(shù)列，它的

37、遞歸定義為：F(n)=1(n=1,2)F(n)=F(n-2)+F(n-1) (n>2)用遞歸過程描述為：Funtion fb(n:integer):integer;Beginif n<3 then fb:=1else fb:=fb(n-1)+fb(n-2);End;上面的遞歸過程，調(diào)用一次產(chǎn)生二個(gè)新的調(diào)用，遞歸次數(shù)呈指數(shù)增長，時(shí)間復(fù)雜度為 O（2n）, 把它改為非遞歸：x:=1;y:=1;for i:=3 to n dobeginz:=y;y:=x+y;x:=z;end;修改后的程序，它的時(shí)間復(fù)雜度為O（n）。我們在編寫程序時(shí)是否使用遞歸算法，關(guān)鍵是看問題是否適合用遞歸算法來求解。

38、由于遞歸算法編寫的程序邏輯性強(qiáng)，結(jié)構(gòu)清晰，正確性易于證明，程序調(diào)試也十分方便，在 NOIP中，數(shù)據(jù)的規(guī)模一般也不大，只要問題適合用遞歸算法求解，我們還是可以大膽地使用遞歸算法。13算法在信息學(xué)奧賽中的應(yīng)用( 遞推法)所謂遞推，是指從已知的初始條件出發(fā)，依據(jù)某種遞推關(guān)系，逐次推出所要求的各中間結(jié)果及最后結(jié)果。其中初始條件或是問題本身已經(jīng)給定，或是通過對問題的分析與化簡后確定?？捎眠f推算法求解的題目一般有以下二個(gè)特點(diǎn)：（ 1） 問題可以劃分成多個(gè)狀態(tài)；（ 2） 除初始狀態(tài)外，其它各個(gè)狀態(tài)都可以用固定的遞推關(guān)系式來表示。在我們實(shí)際解題中，題目不會(huì)直接給出遞推關(guān)系式，而是需要通過分析各種狀態(tài)，找出遞推

39、關(guān)系式。遞推法應(yīng)用例 1 騎士游歷 : （ noip1997tg ）設(shè)有一個(gè) n*m的棋盤 (2<=n<=50,2<=m<=50), 如下圖 , 在棋盤上任一點(diǎn)有一個(gè)中國象棋馬 ,馬走的規(guī)則為 :1. 馬走日字2.馬只能向右走，即如下圖所示:任務(wù) 1: 當(dāng) N,M 輸入之后 , 找出一條從左下角到右上角的路徑。例如 : 輸入 N=4,M=4輸出 : 路徑的格式 :(1,1)->(2,3)->(4,4)若不存在路徑 , 則輸出 "no"任務(wù) 2: 當(dāng) N,M 給出之后 , 同時(shí)給出馬起始的位置和終點(diǎn)的位置 , 試找出從起點(diǎn)到終點(diǎn)的所有路徑的

40、數(shù)目。例如 :(N=10,M=10),(1,5)(起點(diǎn) ),(3,5)(終點(diǎn) )14輸出 :2( 即由 (1,5) 到(3,5) 共有 2 條路徑 )輸入格式 :n,m,x1,y1,x2,y2(分別表示 n,m, 起點(diǎn)坐標(biāo) , 終點(diǎn)坐標(biāo) )輸出格式 : 路徑數(shù)目 ( 若不存在從起點(diǎn)到終點(diǎn)的路徑, 輸出 0)算法分析：為了研究的方便，我們先將棋盤的橫坐標(biāo)規(guī)定為i ，縱坐標(biāo)規(guī)定為j ，對于一個(gè) n×m的棋盤， i 的值從 1 到 n， j 的值從 1 到 m。棋盤上的任意點(diǎn)都可以用坐標(biāo) (i,j)表示。對于馬的移動(dòng)方法，我們用K 來表示四種移動(dòng)方向 (1,2,3,4)；而每種移動(dòng)方法用偏

41、移值來表示，并將這些偏移值分別保存在數(shù)組dx 和 dy 中，如下表KDxkDyk12122-131241-2根據(jù)馬走的規(guī)則，馬可以由（ i-dxk,j-dyk）走到 (i,j)。只要馬能從（ 1，1）走到（ i-dxk,j-dyk），就一定能走到（ i,j）, 馬走的坐標(biāo)必須保證在棋盤上。我們以（ n,m）為起點(diǎn)向左遞推，當(dāng)遞推到（i-dxk,j-dyk）的位置是（ 1，1）時(shí)，就找到了一條從（1，1）到（ n,m）的路徑。我們用一個(gè)二維數(shù)組a 表示棋盤，對于任務(wù)一，使用倒推法，從終點(diǎn)(n,m) 往左遞推， 設(shè)初始值 an,m 為（ -1 ，-1 ），如果從 (i,j)一步能走到 (n,m)

42、，就將 (n,m)存放在 ai,j 中。如下表， a3,2 和 a2,3 的值是（ 4， 4），表示從這兩個(gè)點(diǎn)都可以到達(dá)坐標(biāo)（ 4,4 ）。從（ 1,1 ）可到達(dá)（ 2， 3）、（ 3，2）兩個(gè)點(diǎn)，所以 a1,1 存放兩個(gè)點(diǎn)中的任意一個(gè)即可。 遞推結(jié)束以后， 如果 a1,1 值為 (0,0) 說明不存在路徑，否則 a1,1 值就是馬走下一步的坐標(biāo)，以此遞推輸出路徑。-1,-14,44,42,3任務(wù)一的源程序：constdx:array1.4of integer=(2,2,1,1);15dy:array1.4of integer=(1,-1,2,-2);typemap=recordx,y:int

43、eger;end;vari,j,n,m,k:integer;a:array0.50,0.50of map;beginread(n,m);fillchar(a,sizeof(a),0);an,m.x:=-1;an,m.y:=-1;標(biāo)記為終點(diǎn) for i:=n downto 2 do 倒推 for j:=1 to m doif ai,j.x<>0 thenfor k:=1 to 4 dobeginai-dxk,j-dyk.x:=i;ai-dxk,j-dyk.y:=j;end;if a1,1.x=0 then writeln('no')else begin存在路徑 i:=

44、1;j:=1;write('(',i,',',j,')');while ai,j.x<>-1 dobegink:=i;i:=ai,j.x;j:=ak,j.y;write('->(',i,',',j,')');end;end;end.對于任務(wù)二，也可以使用遞推法，用數(shù)組Ai,j存放從起點(diǎn) (x1,y1) 到（i,j）的路徑總數(shù)，按同樣的方法從左向右遞推，一直遞推到（x2,y2 ）， ax2,y2即為所求的解。源程序（略）在上面的例題中，遞推過程中的某個(gè)狀態(tài)只與前面的一個(gè)狀態(tài)有關(guān)，遞推

45、關(guān)系并不復(fù)雜，如果在遞推中的某個(gè)狀態(tài)與前面的所有狀態(tài)都有關(guān)，就不容易找出遞推關(guān)系式，這就需要我們對實(shí)際問題進(jìn)行分析與歸納，從中找到突破口，總結(jié)出遞推關(guān)系式。我們可以按以下四個(gè)步驟去分析：（ 1）細(xì)心的觀察；（ 2）豐富的16聯(lián)想；（3）不斷地嘗試；（4）總結(jié)出遞推關(guān)系式。下面我們再看一個(gè)復(fù)雜點(diǎn)的例子。例 2、棧（ noip2003pj ）題目大意：求 n 個(gè)數(shù)通過棧后的排列總數(shù)。 （1n18）如輸入3輸出5算法分析：先模擬入棧、出棧操作，看看能否找出規(guī)律，我們用f(n) 表示 n個(gè)數(shù)通過棧操作后的排列總數(shù)，當(dāng)n 很小時(shí)，很容易模擬出f(1)=1 ；f(2)=2 ；f(3)=5,通過觀察，看不出

46、它們之間的遞推關(guān)系，我們再分析N=4的情況，假設(shè)入棧前的排列為“ 4321”，按第一個(gè)數(shù)“ 4”在出棧后的位置進(jìn)行分情況討論：（1） 若“ 4”最先輸出，剛好與N=3相同，總數(shù)為 f(3);（2） 若“4”第二個(gè)輸出，則在“ 4”的前只能是“ 1”，“23”在“4”的后面，這時(shí)可以分別看作是 N=1和 N=2時(shí)的二種情況，排列數(shù)分別為 f(1) 和 f(2), 所以此時(shí)的總數(shù)為 f(1)*f(2);（3） 若“4”第三個(gè)輸出， 則“ 4”的前面二個(gè)數(shù)為 “ 12”, 后面一個(gè)數(shù)為 “ 3”，組成的排列總數(shù)為 f(2)*f(1);（4） 若“ 4”第四個(gè)輸出，與情況（ 1）相同，總數(shù)為 f(3)

47、; 所以有： f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3);若設(shè) 0 個(gè)數(shù)通過棧后的排列總數(shù)為：f(0)=1 ；上式可變?yōu)椋?f(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0); 再進(jìn)一步推導(dǎo)，不難推出遞推式：f(n)=f(0)*f(n-1)+f(1)*f(n-2)+f(n-1)*f(0);即 f(n)=f (i ) * f (ni1)(n>=1)0 in 1初始值： f(0)= 1;有了以上遞推式，就很容易用遞推法寫出程序。vara:array0.18of longint;n,i,j:integer;beginreadln(

48、n);fillchar(a,sizeof(a),0);a0:=1;for i:=1 to n dofor j:=0 to i-1 do ai:=ai+aj*ai-j-1;writeln(an);end.遞推算法最主要的優(yōu)點(diǎn)是算法結(jié)構(gòu)簡單， 程序易于實(shí)現(xiàn)， 難點(diǎn)是從問題的分析中找出解決問題的遞推關(guān)系式。 對于以上兩個(gè)例子， 如果在比賽中找不出遞推關(guān)系式， 也可以用回溯法求解。17算法在信息學(xué)奧賽中的應(yīng)用( 分治法)分治算法的基本思想是將一個(gè)規(guī)模為 N 的問題分解為 K 個(gè)規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。分治法解題的一般步驟：（1）分解，

49、將要解決的問題劃分成若干規(guī)模較小的同類問題；（2）求解，當(dāng)子問題劃分得足夠小時(shí)，用較簡單的方法解決；（3）合并，按原問題的要求，將子問題的解逐層合并構(gòu)成原問題的解。分治法應(yīng)用例1、 比賽安排 (noip1996)設(shè)有 2n(n<=6) 個(gè)球隊(duì)進(jìn)行單循環(huán)比賽 , 計(jì)劃在 2n-1 天內(nèi)完成 , 每個(gè)隊(duì)每天進(jìn)行一場比賽。設(shè)計(jì)一個(gè)比賽的安排, 使在 2n-1 天內(nèi)每個(gè)隊(duì)都與不同的對手比賽。例如 n=2 時(shí)的比賽安排為 :隊(duì)1234比賽1-23-4第一天1-32-4第二天1-42-3第三天算法分析：此題很難直接給出結(jié)果，我們先將問題進(jìn)行分解，設(shè) m=2n ，將規(guī)模減半，如果 n=3( 即 m=8),8 個(gè)球隊(duì) 的比賽，減半后變成 4 個(gè)球隊(duì) 的比賽（ m=4），4個(gè)球隊(duì) 的比賽的安排方式還不是很明顯，再減半到兩 個(gè)球隊(duì) 的比賽 (m=2)，兩 個(gè)球隊(duì)的比賽安排方式很簡單，只要讓兩個(gè)球隊(duì)直接進(jìn)行一場比賽即可：1 22 1分析兩個(gè)球隊(duì)的比賽的情況不難發(fā)現(xiàn)，這是一個(gè)對稱的方陣， 我們把這個(gè)方