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

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

2、33算法基礎(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è)程序就毫無意義了； 5、可行性： 算法中每一步運(yùn)算應(yīng)該

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

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

6、首先要考慮的是時(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程序如下）vari,t,n,sum:longint; begint:=0; sum:=1;readln(n);for

7、i:=1 to n dobegin sum:=sum*i; while sum mod 10=0 do begin sum:=sum div 10; inc(t);計(jì)數(shù)器增加1 end; 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;begin readln(n);t:=0;repeat n:=n div 5 ; inc(t,n); 計(jì)數(shù)器增加nuntil n<5;wri

8、teln(t:6);end.分析對比兩種算法就不難看出，它們的時(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é)奧賽中的基本算法(枚舉法)枚舉法，常常稱之為窮舉法，是指從可能的集合中一一枚舉各個(gè)元素，用題目給定的約束條件判定哪些是無用的，哪些是有用的。能使命題成立者，即為問題的解。采用枚舉算法解題的基

9、本思路：（1） 確定枚舉對象、枚舉范圍和判定條件；（2） 一一枚舉可能的解，驗(yàn)證是否是問題的解下面我們就從枚舉算法的的優(yōu)化、枚舉對象的選擇以及判定條件的確定，這三個(gè)方面來探討如何用枚舉法解題。枚舉算法應(yīng)用例1：百錢買百雞問題：有一個(gè)人有一百塊錢，打算買一百只雞。到市場一看，大雞三塊錢一只，小雞一塊錢三只，不大不小的雞兩塊錢一只。現(xiàn)在，請你編一程序，幫他計(jì)劃一下，怎么樣買法，才能剛好用一百塊錢買一百只雞？算法分析：此題很顯然是用枚舉法，我們以三種雞的個(gè)數(shù)為枚舉對象（分別設(shè)為x,y,z）,以三種雞的總數(shù)（x+y+z）和買雞用去的錢的總數(shù)(x*3+y*2+z)為判定條件，窮舉各種雞的個(gè)數(shù)。下面是解這

10、個(gè)百雞問題的程序var x,y,z:integer;beginfor x:=0 to 100 do for y:=0 to 100 dofor z:=0 to 100 do枚舉所有可能的解if (x+y+z=100)and(x*3+y*2+z div 3=100)and(z mod 3=0)then writeln('x=',x,'y=',y,'z=',z); 驗(yàn)證可能的解，并輸出符合題目要求的解end.上面的條件還有優(yōu)化的空間，三種雞的和是固定的，我們只要枚舉二種雞（x,y），第三種雞就可以根據(jù)約束條件求得（z=100-x-y），這樣就縮小了枚

11、舉范圍，請看下面的程序：var x,y,z:integer;begin for x:=0 to 100 dofor y:=0 to 100-x dobegin z:=100-x-y; if (x*3+y*2+z div 3=100)and(z mod 3=0)then writeln('x=',x,'y=',y,'z=',z);end;end.未經(jīng)優(yōu)化的程序循環(huán)了1013 次，時(shí)間復(fù)雜度為O(n3)；優(yōu)化后的程序只循環(huán)了（102*101/2）次 ，時(shí)間復(fù)雜度為O(n2)。從上面的對比可以看出，對于枚舉算法，加強(qiáng)約束條件，縮小枚舉的范圍，是程序優(yōu)化

12、的主要考慮方向。在枚舉算法中，枚舉對象的選擇也是非常重要的，它直接影響著算法的時(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)賽普及組試題（簡稱NOIP1998pj，以下同）。此題數(shù)據(jù)規(guī)模不大，可以進(jìn)行枚舉，如果我們不加思地以每一個(gè)數(shù)位為枚舉對象，一位一位地去枚舉：for a:=1 to 9 do for b:=1 to 9 dofor i:=1 to

13、 9 do這樣下去，枚舉次數(shù)就有9次，如果我們分別設(shè)三個(gè)數(shù)為x,2x,3x，以x為枚舉對象，窮舉的范圍就減少為，在細(xì)節(jié)上再進(jìn)一步優(yōu)化，枚舉范圍就更少了。程序如下：var t,x:integer; s,st:string; c:char;begin for x:=123 to 321 do枚舉所有可能的解 begin t:=0; str(x,st);把整數(shù)x轉(zhuǎn)化為字符串，存放在st中 str(x*2,s); st:=st+s; str(x*3,s); st:=st+s; for c:='1' to '9' do枚舉9個(gè)字符，判斷是否都在st中 if pos(c,s

14、t)<>0 then inc(t) else break;如果不在st中，則退出循環(huán)if t=9 then writeln(x,' ',x*2,' ',x*3); end;end.在枚舉法解題中，判定條件的確定也是很重要的，如果約束條件不對或者不全面，就窮舉不出正確的結(jié)果， 我們再看看下面的例子。例 一元三次方程求解(noip2001tg)問題描述 有形如：ax3+bx2+cx+d=0 這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù)(a，b，c，d 均為實(shí)數(shù))，并約定該方程存在三個(gè)不同實(shí)根(根的范圍在-100至100之間)，且根與根之差的絕

15、對值>=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 -4 20輸出：-2.00 2.00 5.00算法分析：由題目的提示很符合二分法求解的原理，所以此題可以用二分法。用二分法解題相對于枚舉法來說很要復(fù)雜很多。此題是否能用枚舉法求解呢？再分析一下題目，根的范圍在-100到100之間，結(jié)果只要保留兩位小數(shù)，我們不妨將根的值域擴(kuò)大100倍（-10000<=x<=10000），再以根為

16、枚舉對象，枚舉范圍是-10000到10000，用原方程式進(jìn)行一一驗(yàn)證，找出方程的解。有的同學(xué)在比賽中是這樣做var k:integer; a,b,c,d,x :real;begin read(a,b,c,d); for k:=-10000 to 10000 do begin x:=k/100; if a*x*x*x+b*x*x+c*x+d=0 then write(x:0:2,' '); end;end.用這種方法，很快就可以把程序編出來，再將樣例數(shù)據(jù)代入測試也是對的，等成績下來才發(fā)現(xiàn)這題沒有全對，只得了一半的分。這種解法為什么是錯(cuò)的呢？錯(cuò)在哪里？前面的分析好象也沒錯(cuò)啊，難道這

17、題不能用枚舉法做嗎？ 看到這里大家可能有點(diǎn)迷惑了。在上面的解法中，枚舉范圍和枚舉對象都沒有錯(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(x)=ax3+bx2+cx+d，若x為方程的根，則根據(jù)提示可知，必有f(x-0.005)*(x+0.005)<0，如果我們以此為枚舉判定條件，問題就逆刃而解。另外，如果f(x-0.005)=0，哪么就說明x-0.005是方程的根，這時(shí)根據(jù)四舍5入，

18、方程的根也為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:extended):extended; 計(jì)算ax3+bx2+cx+d的值begin f:=(a*x+b)*x+c)*x+d;end;begin read(a,b,c,d); for k:=-10000 to 10000 do beginx:=k/100; if (f(x-0.005

19、)*f(x+0.005)<0) or (f(x-0.005)=0) then write(x:0:2,' '); 若x兩端的函數(shù)值異號或x-0.005剛好是方程的根，則確定x為方程的根 end;end.用枚舉法解題的最大的缺點(diǎn)是運(yùn)算量比較大，解題效率不高，如果枚舉范圍太大（一般以不超過兩百萬次為限），在時(shí)間上就難以承受。但枚舉算法的思路簡單，程序編寫和調(diào)試方便，比賽時(shí)也容易想到，在競賽中，時(shí)間是有限的，我們競賽的最終目標(biāo)就是求出問題解，因此，如果題目的規(guī)模不是很大，在規(guī)定的時(shí)間與空間限制內(nèi)能夠求出解，那么我們最好是采用枚舉法，而不需太在意是否還有更快的算法，這樣可以使你有

20、更多的時(shí)間去解答其他難題。信息學(xué)奧賽中的基本算法(回溯法)如果上期的“百錢買百雞”中雞的種類數(shù)是變化的，用枚舉法就無能為力了，這里介紹另一種算法回溯法?；厮莼舅枷牖厮莘ㄊ且环N既帶有系統(tǒng)性又帶有跳躍性的搜索法，它的基本思想是：在搜索過程中，當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先的選擇達(dá)不到目標(biāo)，就退回到上一步重新選擇。它主要用來解決一些要經(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ù)

21、為a1,a2,ar,把它們從大到小排列，則滿足：（1） a1>a2>>ar;（2） 其中第i位數(shù)(1<=i<=r)滿足ai>r-i;我們按以上原則先確定第一個(gè)數(shù)，再逐位生成所有的r個(gè)數(shù)，如果當(dāng)前數(shù)符合要求，則添加下一個(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的值:ai=ai-1;（2） 若a

22、i>r-i且ir，則繼續(xù)生成下一位ai+1=ai-1;（3） 若ai<=r-i，則回溯到上一位，改變上一位數(shù)的值:ai-1=ai-1-1;算法實(shí)現(xiàn)步驟：第一步：輸入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 read

23、ln(n,r);i:=1;a1:=n; repeat if ai>r-i then 符合條件 if i=r then 輸出beginfor j:=1 to r do write(aj:3);writeln; ai:=ai-1; endelse 繼續(xù)搜索begin ai+1:=ai-1; i:=i+1;end else回溯 begin i:=i-1; ai:=ai-1;end; until a1=r-1;end.下面我們再通過另一個(gè)例子看看回溯在信息學(xué)奧賽中的應(yīng)用。例2 數(shù)的劃分（noip2001tg）問題描述 整數(shù)n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。例如：n=7，

24、k=3，下面三種分法被認(rèn)為是相同的。1，1，5; 1，5，1; 5，1，1;問有多少種不同的分法。輸入：n，k (6<n<=200，2<=k<=6)輸出：一個(gè)整數(shù)，即不同的分法。樣例輸入： 7 3輸出：4 四種分法為：1,1,5; 1,2,4; 1,3,3; 2,2,3;算法分析：此題可以用回溯法求解，設(shè)自然數(shù)n拆分為a1,a2,ak,必須滿足以下兩個(gè)條件：（1） n=a1+a2+ak ；（2） a1<=a2<=<=ak (避免重復(fù)計(jì)算)；現(xiàn)假設(shè)己求得的拆分?jǐn)?shù)為a1,a2,ai,且都滿足以上兩個(gè)條件,設(shè)sum=n-a1-a2-ai,我們根據(jù)不同的情形進(jìn)

25、行處理：（1） 如果i=k,則得到一個(gè)解，則計(jì)數(shù)器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 div k;第二步：如果a1<=nk 重復(fù)：若i=k，搜索到一個(gè)解，計(jì)數(shù)器t=t+1;并回溯；否則：若sum>=ai則繼續(xù)搜索；若sum<ai則回溯；搜索時(shí)，inc(i);ai:=ai-1;sum:=

26、sum-ai; 回溯時(shí)，dec(i); inc(ai); sum:=sum+ai+1-1;第三步：輸出。程序如下：var n,nk,sum,i,k:integer; t:longint; a:array1.6of integer;begin readln(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 判斷是否回溯begin i

27、nc(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è)老和尚在給小和尚講故事，他說從前

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

29、下圖，有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í)，需要很多步才能完成，我們先考慮是否能把復(fù)雜的移動(dòng)過程轉(zhuǎn)化為簡單的移動(dòng)過程，如果要把

30、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:integer;)；以B柱為中轉(zhuǎn)柱將N個(gè)盤子從A柱移動(dòng)到C柱begin if N=1 then write(A,->,C

31、)把盤子直接從A移動(dòng)到Celse begin Hanoi(N-1,A,C,B)； 以C柱為中轉(zhuǎn)柱將N-1個(gè)盤子從A柱移動(dòng)到B柱 write(A,->,C)；把剩下的一個(gè)盤子從A移動(dòng)到C Hanoi(N-1,B,A,C)； 以A柱為中轉(zhuǎn)柱將N-1個(gè)盤子從B柱移動(dòng)到C柱end;end;從上面的例子我們可以看出，在使用遞歸算法時(shí)，首先弄清楚簡單情況下的解法，然后弄清楚如何把復(fù)雜情況歸納為更簡單的情況。在信息學(xué)奧賽中有的問題的結(jié)構(gòu)或所處理的數(shù)據(jù)本身是遞歸定義的，這樣的問題非常適合用遞歸算法來求解，對于這類問題，我們把它分解為具有相同性質(zhì)的若干個(gè)子問題，如果子問題解決了，原問題也就解決了。例2求先

32、序排列 (NOIP2001pj)問題描述給出一棵二叉樹的中序與后序排列。求出它的先序排列。(約定樹結(jié)點(diǎn)用不同的大寫字母表示，長度8)。樣例 輸入：BADC BDCA   輸出：ABCD算法分析：我們先看看三種遍歷的定義：先序遍歷是先訪問根結(jié)點(diǎn)，再遍歷左子樹，最后遍歷右子樹；中序遍歷是先遍歷左子樹，再訪問根結(jié)點(diǎn)，最后遍歷右子樹；后序遍歷是先遍歷左子樹，再遍歷右子樹，最后訪問根結(jié)點(diǎn)；從遍歷的定義可知，后序排列的最后一個(gè)字符即為這棵樹的根節(jié)點(diǎn)；在中序排列中，根結(jié)點(diǎn)前面的為其左子樹，根結(jié)點(diǎn)后面的為其右子樹；我們可以由后序排列求得根結(jié)點(diǎn)，再由根結(jié)點(diǎn)在中序排列的位置確定左子樹和右子樹，

33、把左子樹和右子樹各看作一個(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; begin m:=length(h);m為樹的長度write(hm); 輸出根節(jié)點(diǎn)s:=pos(hm,z); 求根節(jié)點(diǎn)在中序排列中的位置if s>1 then make(copy(z,1,s-

34、1),copy(h,1,s-1); 處理左子樹if m>s then make(copy(z,s+1,m-s),copy(h,s,m-s); 處理右子樹end; begin readln(z); readln(h); make(z,h); end.遞歸算法不僅僅是用于求解遞歸描述的問題，在其它很多問題中也可以用到遞歸思想，如回溯法、分治法、動(dòng)態(tài)規(guī)劃法等算法中都可以使用遞歸思想來實(shí)現(xiàn)，從而使編寫的程序更加簡潔。比如上期回溯法所講的例2數(shù)的劃分問題，若用遞歸來求解，程序非常短小且效率很高，源程序如下var n,k:integer; tol:longint;procedure make(sum

35、,t,d:integer);var i:integer;begin if d=k then inc(tol) else for i:=t to sum div 2 do make(sum-i,i,d+1);end;begin readln(n,k);tol:=0; make(n,1,1); writeln(tol);end.有些問題本身是遞歸定義的，但它并不適合用遞歸算法來求解，如斐波那契(Fibonacci)數(shù)列，它的遞歸定義為：F(n)=1   (n=1,2)F(n)=F(n-2)+F(n-1) (n>2)用遞歸過程描述為：Funtion fb(n:integer

36、):integer;Begin if n<3 then fb:=1 else 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 dobegin z:=y;y:=x+y;x:=z;end;修改后的程序，它的時(shí)間復(fù)雜度為O（n）。我們在編寫程序時(shí)是否使用遞歸算法，關(guān)鍵是看問題是否適合用遞歸算法來求解。由于遞歸算法編寫的程序邏輯性強(qiáng)，結(jié)構(gòu)清晰，正確性易于證明，程序調(diào)試也十分方便，在NOIP中，數(shù)據(jù)的規(guī)模一般也不大，只要問題適合用遞歸算法求解，我們還

37、是可以大膽地使用遞歸算法。算法在信息學(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)，找出遞推關(guān)系式。遞推法應(yīng)用例1騎士游歷:（noip1997tg）設(shè)有一個(gè)n*m的棋盤(2<=n<=50,2<=m<=50),如下圖,在棋盤上任

38、一點(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)的所有路徑的數(shù)目。例如:(N=10,M=10),(1,5)(起點(diǎn)),(3,5)(終點(diǎn))輸出:2(即由(1,5)到(3,5)共有2條路徑)輸入格式:n,m,x1,y1,x2,y2(分別表示n,m,起點(diǎn)坐標(biāo),終點(diǎn)坐標(biāo))輸出格式:路徑數(shù)目(

39、若不存在從起點(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)方法用偏移值來表示，并將這些偏移值分別保存在數(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)向左遞

40、推，當(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)，就將(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

41、   任務(wù)一的源程序：const dx:array1.4of integer=(2,2,1,1); dy:array1.4of integer=(1,-1,2,-2);type map=record x,y:integer; end;var i,j,n,m,k:integer; a:array0.50,0.50of map;begin read(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 do if ai,j.x&l

42、t;>0 then for k:=1 to 4 do begin ai-dxk,j-dyk.x:=i; ai-dxk,j-dyk.y:=j; end; if a1,1.x=0 then writeln('no') else begin存在路徑 i:=1;j:=1; write('(',i,',',j,')'); while ai,j.x<>-1 dobegin k:=i;i:=ai,j.x;j:=ak,j.y; write('->(',i,',',j,')')

43、; 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)，遞推關(guān)系并不復(fù)雜，如果在遞推中的某個(gè)狀態(tài)與前面的所有狀態(tài)都有關(guān)，就不容易找出遞推關(guān)系式，這就需要我們對實(shí)際問題進(jìn)行分析與歸納，從中找到突破口，總結(jié)出遞推關(guān)系式。我們可以按以下四個(gè)步驟去分析：（1）細(xì)心的觀察；（2）豐富的聯(lián)想；（3）不斷地嘗試；（4）總結(jié)出遞推關(guān)系式。下面我們再看一個(gè)復(fù)雜點(diǎn)的例子。例2、棧（noip2003pj

44、）題目大意：求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,通過觀察，看不出它們之間的遞推關(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í)

45、的總數(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);所以有：f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3);若設(shè)0個(gè)數(shù)通過棧后的排列總數(shù)為：f(0)=1；上式可變?yōu)椋篺(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)= (n>=1)初始值：f(0)=1;有

46、了以上遞推式，就很容易用遞推法寫出程序。var a:array0.18of longint; n,i,j:integer;begin readln(n); fillchar(a,sizeof(a),0); a0:=1; for i:=1 to n do for 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)系式，也可以用回溯法求解。算法在信息學(xué)奧賽中的應(yīng)用 (分治法)分治算法的基本思想是將一個(gè)規(guī)模為N的問題

47、分解為K個(gè)規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。分治法解題的一般步驟：（1）分解，將要解決的問題劃分成若干規(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ì)    1 2  3 4比賽

48、  1-2  3-4  第一天1-3  2-4  第二天1-4  2-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)行一場比賽即可：1221分析兩個(gè)球隊(duì)的比賽的情況不難發(fā)現(xiàn)，這是一個(gè)對稱的方陣，我們把這個(gè)方陣分成4部分（即左上，右上，左下，右下），右上部分可由左上部分加1（即加m/2）得

49、到，而右上與左下部分、左上與右下部分別相等。因此我們也可以把這個(gè)方陣看作是由M=1的方陣所成生的，同理可得M=4的方陣：1234214334124321同理可由M=4方陣生成M=8的方陣：1234567821436587341278564321876556781234658721437856341287654321這樣就構(gòu)成了整個(gè)比賽的安排表。在算法設(shè)計(jì)中，用數(shù)組a記錄2n個(gè)球隊(duì)的循環(huán)比賽表，整個(gè)循環(huán)比賽表從最初的1*1方陣按上述規(guī)則生成2*2的方陣，再生成4*4的方陣，直到生成出整個(gè)循環(huán)比賽表為止。變量h表示當(dāng)前方陣的大小,也就是要生成的下一個(gè)方陣的一半。源程序：var i,j,h,m,n:

50、integer; a:array1.32,1.32of integer;begin readln(n); m:=1;a1,1:=1;h:=1;for i:=1 to n do m:=m*2; repeat for i:=1 to h do for j:=1 to h do begin ai,j+h:=ai,j+h;構(gòu)造右上角方陣 ai+h,j:=ai,j+h;構(gòu)造左下角方陣 ai+h,j+h:=ai,j;構(gòu)造右下角方陣 end; h:=h*2; until h=m; for i:=1 to m do begin for j:=1 to m do write(ai,j:4); writeln;

51、end;end.在分治算法中，若將原問題分解成兩個(gè)較小的子問題，我們稱之為二分法，由于二分法劃分簡單，所以使用非常廣泛。使用二分法與使用枚舉法求解問題相比較，時(shí)間復(fù)雜度由O（N）降到O（log2N），在很多實(shí)際問題中，我們可以通過使用二分法，達(dá)到提高算法效率的目的，如下面的例子。例2 一元三次方程求解（noip2001tg） 題目大意：給出一個(gè)一元三次方程f(x)=ax3+bx2+cx+d=0 ,求它的三個(gè)根。所有的根都在區(qū)間-100，100中，并保證方程有三個(gè)實(shí)根，且它們之間的差不小于1。算法分析：在講解枚舉法時(shí)，我們討論了如何用枚舉法求解此題，但如果求解的精度進(jìn)一步提高，使用枚舉法就無能為

52、力了，在此我們再一次討論如何用二分法求解此題。由題意知（i,i+1）中若有根，則只有一個(gè)根，我們枚舉根的值域中的每一個(gè)整數(shù)x(-100x100),設(shè)定搜索區(qū)間x1，x2，其中x1=x，x2=x+1。若：f(x1)=0，則確定x1為f(x)的根；f(x1)*f(x2)<0，則確定根x在區(qū)間x1，x2內(nèi)。f(x1)*f(x2)>0，則確定根x不在區(qū)間x1，x2內(nèi)，設(shè)定x2，x2+1為下一個(gè)搜索區(qū)間；若確定根x在區(qū)間x1，x2內(nèi)，采用二分法，將區(qū)間x1，x2分成左右兩個(gè)子區(qū)間：左子區(qū)間x1，x和右子區(qū)間x，x2（其中x=（x1+x2）/2）。如果f(x1)*f(x)0，則確定根在左區(qū)間x

53、1，x內(nèi)，將x設(shè)為該區(qū)間的右界值（x2=x），繼續(xù)對左區(qū)間進(jìn)行對分；否則確定根在右區(qū)間x，x2內(nèi)，將x設(shè)為該區(qū)間的左界值（x1=x），繼續(xù)對右區(qū)間進(jìn)行對分；上述對分過程一直進(jìn)行到區(qū)間的間距滿足精度要求為止（即x2-x1<0.005）。此時(shí)確定x1為f(x)的根。源程序：$N+var x:integer; a,b,c,d,x1,x2,xx:extended;function f(x:extended):extended;begin f:=(a*x+b)*x+c)*x+d;end;begin read(a,b,c,d); for x:=-100 to 100 do begin x1:=x;x

54、2:=x+1; if f(x1)=0 then write(x1:0:2,' ') else if f(x1)*f(x2)<0 then begin while x2-x1>=0.005 do begin xx:=(x1+x2)/2; if f(x1)*f(xx)<=0 then x2:=xx else x1:=xx; end;while write(x1:0:2,' '); end; then end;forend.信息學(xué)奧賽中的基本算法(貪心法)在求最優(yōu)解問題的過程中，依據(jù)某種貪心標(biāo)準(zhǔn)，從問題的初始狀態(tài)出發(fā)，直接去求每一步的最優(yōu)解，通過若干次的貪心選擇，最終得出整個(gè)問題的最優(yōu)解，這種求解方法就是貪心算法。從貪心算法的定義可以看出，貪心法并不是從整體上考慮問題，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而由問題自身的