2014NOIP信息學奧賽——算法快速入門教程.

1、2014 NOIP全國青少年信息學奧林匹克聯(lián)賽（中國計算機學會出版）算法算法基礎(chǔ)篇2算法具有五個特征： 2信息學奧賽中的基本算法 （枚舉法）4采用枚舉算法解題的基本思路： 4枚舉算法應(yīng)用4信息學奧賽中的基本算法 （回溯法）7回溯基本思想8信息學奧賽中的基本算法 （遞歸算法）10遞歸算法的定義： 10遞歸算法應(yīng)用 11算法在信息學奧賽中的應(yīng)用 （遞推法）14遞推法應(yīng)用 14算法在信息學奧賽中的應(yīng)用 （分治法）18分治法應(yīng)用18信息學奧賽中的基本算法 （貪心法） 21貪心法應(yīng)用21算法在信息學奧賽中的應(yīng)用（搜索法一） 24搜索算法應(yīng)用 25算法在信息學奧賽中的應(yīng)用（搜索法二） 28廣度優(yōu)先算法應(yīng)用

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

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

4、輸出為最小的數(shù)。如果一個程序沒有輸出，這個程序就毫無意義了；5、 可行性：算法中每一步運算應(yīng)該是可行的。算法原則上能夠精確地運行， 而且人能用筆和紙做有限次運算后即可完成。如何來評價一個算法的好壞呢？主要是從兩個方面：一是看算法運行所占用的時間；我們用時間復(fù)雜度來衡量，例如：在以下 3 個程序中，(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+1含基本操作“ x增1”的語句x:=x+1的出現(xiàn)的次數(shù)分別為1，n和n2則這三個 程序段的時間復(fù)雜度分別為 0( 1)，0( n)，0 (n2),分

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

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

7、 n, sum:lo ngint;begi nt:=0; sum:=1;read ln(n);for i:=1 to n dobeg insum:=sum*i;while sum mod 10=0 dobegi nsum:=sum div 10;in c(t);計數(shù)器增加1end;sum:=sum mod 1000;舍去與生成0無關(guān)的數(shù)end;writel n(t:6);end.算法二：此題中生成0的個數(shù)只與含5的個數(shù)有關(guān)，n!的分解數(shù)中含5的個 數(shù)就等于末尾O的個數(shù)，因此問題轉(zhuǎn)化為直接求 n!的分解數(shù)中含5的個數(shù)。var t,n:i nteger;begi nread ln(n);t:=0;

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

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

10、),以三種雞的總數(shù)(x+y+z、和買雞用去的錢的總數(shù)(x*3+y*2+z)為判 定條件，窮舉各種雞的個數(shù)。下面是解這個百雞問題的程序var x,y,z:i nteger;begi nfor 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+zdiv 3=100)and(z mod 3=0)thenwritel n( x=,x,y=,y,z=,z); 驗證可能的解，并輸出符合題目要求的解 end.上面的條件還有優(yōu)化的空間，三種雞的和是固定的，我們只要枚舉二種雞(x,y ),第三種雞

11、就可以根據(jù)約束條件求得(z=100-x-y ),這樣就縮小了枚舉范 圍，請看下面的程序：var x,y,z:i nteger;begi nfor x:=0 to 100 dofor y:=0 to 100-x dobeg inz:=100-x-y;if(x*3+y*2+zdiv3=100)a nd(zmod 3=0)thenwrite ln( x=,x,y=,y,z=,z);end;end.未經(jīng)優(yōu)化的程序循環(huán)了 1013次，時間復(fù)雜度為O(n);優(yōu)化后的程序只循環(huán) 了( 102*101/2 )次，時間復(fù)雜度為O(n2)。從上面的對比可以看出，對于枚舉算 法，加強約束條件，縮小枚舉的范圍，是程序

12、優(yōu)化的主要考慮方向。在枚舉算法中，枚舉對象的選擇也是非常重要的，它直接影響著算法的時間 復(fù)雜度，選擇適當?shù)拿杜e對象可以獲得更高的效率。如下例：例2、將1,2.9 共9個數(shù)分成三組，分別組成三個三位數(shù)，且使這三個三位數(shù) 構(gòu)成1:2:3的比例,試求出所有滿足條件的三個三位數(shù).例如：三個三位數(shù)192,384,576滿足以上條件.(NOIP1998pj)算法分析：這是1998年全國分區(qū)聯(lián)賽普及組試題(簡稱NOIP1998pj,以下同) 此題數(shù)據(jù)規(guī)模不大，可以進行枚舉，如果我們不加思地以每一個數(shù)位為枚舉對象， 一位一位地去枚舉：for a:=1 to 9 dofor b:=1 to 9 dofor i:

13、=1 to 9 do這樣下去，枚舉次數(shù)就有9次，如果我們分別設(shè)三個數(shù)為 x,2x,3x，以x為枚舉對象，窮舉的范圍就減少為9彳，在細節(jié)上再進一步優(yōu)化，枚舉范圍就更少 了。程序如下：vart,x:i nteger;s,st:stri ng;c:char;begi nfor x:=123 to 321 do枚舉所有可能的解beg int:=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個字符，判斷是否都在 st中if pos(c,st)0 then inc(t)

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

15、：記方程f(x)=0，若存在2個數(shù)x1和x2，且x1x2，f(x1)*(x2)0，則在 (x1，x2)之間一定有一個根。樣例輸入：1-5-420輸出：-2.002.005.00算法分析：由題目的提示很符合二分法求解的原理，所以此題可以用二分法。 用二分法解題相對于枚舉法來說很要復(fù)雜很多。此題是否能用枚舉法求解呢？再 分析一下題目，根的范圍在-100到100之間，結(jié)果只要保留兩位小數(shù)，我們不妨 將根的值域擴大100倍(-10000=x=10000)，再以根為枚舉對象，枚舉范圍是 -10000到10000,用原方程式進行驗證，找出方程的解。有的同學在比賽中是這樣做vark:i nteger;a,b

16、,c,d,x :real;begi nread(a,b,c,d);for k:=-10000 to 10000 dobeg inx:=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)這題沒有全對，只得了一半的分。這種解法為什么是錯的呢？錯在哪里？前面的分析好象也沒錯啊，難道這題不能用枚舉法做嗎？看到這里大家可能有點迷惑了。在上面的解法中，枚舉范圍和枚舉對象都沒有錯，而是在驗證枚舉結(jié)果時，判 定條件用錯了。因為要保留二位小數(shù)，所以求出來的解不一定

17、是方程的精確根， 再代入ax3+bx2+cx+d中，所得的結(jié)果也就不一定等于0，因此用原方程32ax +bx +cx+d=0作為判斷條件是不準確的。我們換一個角度來思考問題，設(shè)f(x)=ax 3+bx2+cx+d，若x為方程的根，則根 據(jù)提示可知，必有f(x-0.005)*(x+0.005)0，如果我們以此為枚舉判定條件，問題就逆刃而解。另外，如果f(x-0.005)=0 ，哪么就說明x-0.005是方程的根，這 時根據(jù)四舍5入，方程的根也為x。所以我們用(f(x-0.005)*f(x+0.005)0) 和 (f(x-0.005)=0)作為判定條件。為了程序設(shè)計的方便，我們設(shè)計一個函數(shù)f(x)

18、計算ax3+bx2+cx+d的值，程序如下：$N+vark:i nteger;a,b,c,d,x:exte nded;32function f(x:extended):extended; 計算 ax +bx +cx+d 的值 begi nf:=(a*x+b)*x+c)*x+d;end;begi nread(a,b,c,d);for k:=-10000 to 10000 dobeg inx:=k/100;if (f(x-0.005)*f(x+0.005)a2 ar；(2) 其中第i位數(shù)(1=ir-i;我們按以上原則先確定第一個數(shù)，再逐位生成所有的r個數(shù)，如果當前數(shù)符合要求，則添加下一個數(shù)；否則返

19、回到上一個數(shù)，改變上一個數(shù)的值再判斷是否符 合要求，如果符合要求，則繼續(xù)添加下一個數(shù)，否則返回到上一個數(shù)，改變上一 個數(shù)的值按此規(guī)則不斷循環(huán)搜索，直到找出r個數(shù)的組合，這種求解方法就是回溯法。如果按以上方法生成了第i位數(shù)a，下一步的的處理為：(1) 若air-i且i=r，則輸出這r個數(shù)并改變ai的值a=a-1;(2) 若air-i且i工r，則繼續(xù)生成下一位 ai+1=a-1;(3) 若ai r-1則重復(fù)：若air-i ，若i=r，則輸出解，并且ai:=ai-1;若 ir，則繼續(xù)生成下一位:ai+1:=ai-1; i:=i+1;若 air-i then 符合條件if i=r then 輸出beg

20、 infor j:=1 to r do write(aj:3); write In;ai:=ai-1;endelse 繼續(xù)搜索begi n ai+1:=ai-1; i:=i+1;e ndelse 回溯begi n i:=i-1; ai:=ai-1;e nd;un til a1=r-1; end.下面我們再通過另一個例子看看回溯在信息學奧賽中的應(yīng)用。例2數(shù)的劃分(noip2001tg問題描述 整數(shù)n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序) 例如：n=7，k=3，下面三種分法被認為是相同的。1, 1, 5;1, 5，1;5, 1, 1;問有多少種不同的分法。輸入：n, k(6n=2

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

22、,則說明達不到目標，回溯到上一步，改變aM的值； 算法實現(xiàn)步驟如下：第一步：輸入自然數(shù) n,k 并初始化；t:=0; i:=1;ai:=1; sum:=n-1; nk:=n divk;第二步：如果a1=ai則繼續(xù)搜索；若sum=ai then 判斷是否回溯beg in in c(i);ai:=ai-1;sum:=sum-ai;e nd繼續(xù)搜else beg in dec(i); in c(ai); sum:=sum+ai+1-1; en d;回溯end;un til a1 nk;writel n( t);end.回溯法是通過嘗試和糾正錯誤來尋找答案，是一種通用解題法，在NOIP中有許多涉及搜索

23、問題的題目都可以用回溯法來求解。信息學奧賽中的基本算法（遞歸算法）遞歸算法的定義：如果一個對象的描述中包含它本身，我們就稱這個對象是遞歸的，這種用遞 歸來描述的算法稱為遞歸算法。我們先來看看大家熟知的一個的故事：從前有座山，山上有座廟，廟里有個老和尚在給小和尚講故事，他說從前有 座山，山上有座廟，廟里有個老和尚在給小和尚講故事，他說上面的故事本身是遞歸的，用遞歸算法描述：procedure bon ze-tell-story；begi nif 講話被打斷then故事結(jié)束else begi n從前有座山，山上有座廟，廟里有個老和尚在給小和尚講故事；bon ze-tell-story；endend

24、;從上面的遞歸事例不難看出，遞歸算法存在的兩個必要條件：（1）必須有遞歸的終止條件；（2）過程的描述中包含它本身；在設(shè)計遞歸算法中，如何將一個問題轉(zhuǎn)化為遞歸的問題，是初學者面臨的難 題，下面我們通過分析漢諾塔問題，看看如何用遞歸算法來求解問題；遞歸算法應(yīng)用例1:漢諾塔問題，如下圖，有 A、B、C三根柱子。A柱子上按從小到大的順 序堆放了 N個盤子，現(xiàn)在要把全部盤子從A柱移動到C柱，移動過程中可以借助B 柱。移動時有如下要求：（1）一次只能移動一個盤子；（2）不允許把大盤放在小盤上邊；（3）盤子只能放在三根柱子上；兒丨I 已曰匚算法分析：當盤子比較多的時，問題比較復(fù)雜，所以我們先分析簡單的情況：

25、如果只有一個盤子，只需一步，直接把它從A柱移動到C柱；如果是二個盤子，共需要移動 3步：（1）把A柱上的小盤子移動到 B柱；（2）把A柱上的大盤子移動到 C柱；（3）把B柱上的大盤子移動到 C柱；如果N比較大時，需要很多步才能完成，我們先考慮是否能把復(fù)雜的移動過 程轉(zhuǎn)化為簡單的移動過程，如果要把 A柱上最大的盤子移動到 C柱上去，必須先 把上面的N-1個盤子從A柱移動到B柱上暫存，按這種思路，就可以把 N個盤子 的移動過程分作3大步：（1）把A柱上面的N-1個盤子移動到B柱；（2）把A柱上剩下的一個盤子移動到 C柱；（3）把B柱上面的N-1個盤子移動到C柱；其中N-1個盤子的移動過程又可按同樣

26、的方法分為三大步，這樣就把移動過 程轉(zhuǎn)化為一個遞歸的過程，直到最后只剩下一個盤子，按照移動一個盤子的方法 移動，遞歸結(jié)束。遞歸過程：procedure Hanoi（N,A,B,C:integer;）； 以B柱為中轉(zhuǎn)柱將 N個盤子從 A柱移動到C柱begi nif N=1 then write（A , - ,C）把盤子直接從 A移動到 Celse beg inHanoi（N-1,A,C,B） ； 以C柱為中轉(zhuǎn)柱將N-1個盤子從A柱移動到B柱write（A , - ,C） ； 把剩下的一個盤子從 A移動到CHanoi（N-1,B,A,C） ； 以A柱為中轉(zhuǎn)柱將N-1個盤子從B柱移動到C柱end;e

27、nd;從上面的例子我們可以看出，在使用遞歸算法時，首先弄清楚簡單情況下的 解法，然后弄清楚如何把復(fù)雜情況歸納為更簡單的情況。在信息學奧賽中有的問題的結(jié)構(gòu)或所處理的數(shù)據(jù)本身是遞歸定義的，這樣的 問題非常適合用遞歸算法來求解，對于這類問題，我們把它分解為具有相同性質(zhì) 的若干個子問題，如果子問題解決了，原問題也就解決了。例2求先序排列(NOIP2001pj)問題描述給出一棵二叉樹的中序與后序排列。求出它的先序排列。(約定樹結(jié)點用不同的大寫字母表示，長度w 8)。樣例輸入：BADC BDCA 輸出：ABCD算法分析：我們先看看三種遍歷的定義：先序遍歷是先訪問根結(jié)點，再遍歷左子樹，最后遍歷右子樹；中序遍

28、歷是先遍歷左子樹，再訪問根結(jié)點，最后遍歷右子樹； 后序遍歷是先遍歷左子樹，再遍歷右子樹，最后訪問根結(jié)點； 從遍歷的定義可知，后序排列的最后一個字符即為這棵樹的根節(jié)點；在中序 排列中，根結(jié)點前面的為其左子樹，根結(jié)點后面的為其右子樹；我們可以由后序 排列求得根結(jié)點，再由根結(jié)點在中序排列的位置確定左子樹和右子樹，把左子樹 和右子樹各看作一個單獨的樹。這樣，就把一棵樹分解為具有相同性質(zhì)的二棵子 樹，一直遞歸下去，當分解的子樹為空時，遞歸結(jié)束，在遞歸過程中，按先序遍 歷的規(guī)則輸出求得的各個根結(jié)點，輸出的結(jié)果即為原問題的解。源程序program noip2001_3;var z,h : stri ng;

29、procedure make(z,h:string); z 為中序排列,h 為后序排列 var s,m : in teger;begi nm:=length(h);m 為樹的長度write(hm); 輸出根節(jié)點s:=pos(hm,z); 求根節(jié)點在中序排列中的位置if s1 then make(copy(z,1,s-1),copy(h,1,s-1); 處理左子樹if ms then make(copy(z,s+1,m-s),copy(h,s,m-s); 處理右子樹end;begi nreadl n(z);read In (h);make(z,h);end.遞歸算法不僅僅是用于求解遞歸描述的問題

30、，在其它很多問題中也可以用到 遞歸思想，如回溯法、分治法、動態(tài)規(guī)劃法等算法中都可以使用遞歸思想來實現(xiàn)， 從而使編寫的程序更加簡潔。比如上期回溯法所講的例 2數(shù)的劃分問題，若用遞歸來求解，程序非常短 小且效率很高，源程序如下varn ,k:i nteger;tol:l ongint;procedure make(sum,t,d:i nteger);var i:i nteger;begi nif d=k then inc(tol)else for i:=t to sum div 2 do make(sum-i,i,d+1);end;begi nreadl n(n ,k);tol:=0;make(

31、n,1,1);writel n(tol);end.有些問題本身是遞歸定義的，但它并不適合用遞歸算法來求解，如斐波那契 (Fibonacci)數(shù)列，它的遞歸定義為：F(n )=1(n=1,2)F(n)=F(n-2)+F(n-1) (n2)用遞歸過程描述為：Fun ti on fb( n:i nteger):i nteger;Beg inif n3 then fb:=1else fb:=fb( n-1)+fb( n-2);End;上面的遞歸過程，調(diào)用一次產(chǎn)生二個新的調(diào)用，遞歸次數(shù)呈指數(shù)增長，時間 復(fù)雜度為0(2n),把它改為非遞歸：x:=1;y:=1;for i:=3 to n dobegi nz

32、：=y;y：=x+y;x:=z;end;修改后的程序，它的時間復(fù)雜度為0(n)。我們在編寫程序時是否使用遞歸算法，關(guān)鍵是看冋題是否適合用遞歸算法來 求解。由于遞歸算法編寫的程序邏輯性強，結(jié)構(gòu)清晰，正確性易于證明，程序調(diào) 試也十分方便，在NOIP中，數(shù)據(jù)的規(guī)模一般也不大，只要問題適合用遞歸算法求 解，我們還是可以大膽地使用遞歸算法。算法在信息學奧賽中的應(yīng)用(遞推法)所謂遞推，是指從已知的初始條件出發(fā)，依據(jù)某種遞推關(guān)系，逐次推出所要 求的各中間結(jié)果及最后結(jié)果。其中初始條件或是問題本身已經(jīng)給定，或是通過對 問題的分析與化簡后確定?？捎眠f推算法求解的題目一般有以下二個特點：(1) 問題可以劃分成多個狀

33、態(tài)；(2) 除初始狀態(tài)外，其它各個狀態(tài)都可以用固定的遞推關(guān)系式來表示。 在我們實際解題中，題目不會直接給出遞推關(guān)系式，而是需要通過分析各種狀態(tài)，找出遞推關(guān)系式。遞推法應(yīng)用例 1 騎士游歷：(noip1997tg)設(shè)有一個n*m的棋盤(2=nv=50,2v=m(2,3)-(4,4)若不存在路徑，則輸出no任務(wù)2:當N,M給出之后，同時給出馬起始的位置和終點的位置，試找出從起點到終 點的所有路徑的數(shù)目。例如:(N=10,M=10),(1,5)( 起點),(3,5)( 終點)10輸出:2（即由（1,5）到（3,5）共有2條路徑）輸入格式：n,m,x1,y1,x2,y2（分別表示n,m,起點坐標,終點

34、坐標）輸出格式:路徑數(shù)目（若不存在從起點到終點的路徑，輸出0）算法分析：為了研究的方便，我們先將棋盤的橫坐標規(guī)定為i，縱坐標規(guī)定為j,對于一個n加的棋盤，i的值從1到n, j的值從1到m棋盤上的任意點都可以用坐標（i,j）表示。對于馬的移動方法，我們用K來表示四種移動方向（1,2,3,4）;而每種移動方法用偏移值來表示，并將這些偏移值分別保存在數(shù)組dx和dy中，如下表上。我們以（n,m）為起點向左遞推，當遞推到（i-dxk,j-dyk ）的位置是（1， 1）時，就找到了一條從（1, 1 ）到（n,m）的路徑。我們用一個二維數(shù)組a表示棋盤，對于任務(wù)一，使用倒推法，從終點（n ,m）往 左遞推，設(shè)

35、初始值an,m為（-1，-1 ），如果從（i,j） 一步能走到（n,m），就將（n,m） 存放在ai,j中。如下表，a3,2和a2,3的值是（4，4），表示從這兩個點都可以到達坐標（4,4）。從（1,1 ）可到達（2，3）、（3, 2）兩個點，所以 a1,1 存放兩個點中的任意一個即可。遞推結(jié)束以后，如果a1,1值為（0,0）說明不存在路徑，否則a1,1值就是馬走下一步的坐標，以此遞推輸出路徑-1,-14,44,42,3任務(wù)一的源程序:con stdx:array1.4of in teger=(2,2,1,1);dy:array1.4of in teger=(1,-1,2,-2);typema

36、p=recordx,y:i nteger;end;vari,j, n, m,k:i nteger;a:array0.50,0.50of map;begi nread( n, m);fillchar(a,sizeof(a),0);an,m.x:=-1;an,m.y:=-1;標記為終點for i:=n dow nto 2 do 倒推for j:=1 to m doif ai,j.x0 thenfor k:=1 to 4 dobeg inai-dxk,j-dyk.x:=i;ai-dxk,j-dyk.y:=j;end;if a1,1.x=0 then writel n(no)else begin存在路

37、徑i:=1;j:=1;write(,i,j,);while ai,j.x-1 dobeg ink:=i;i:=ai,j.x;j:=ak,j.y;write(-(,i,j,);end;end;end.對于任務(wù)二，也可以使用遞推法，用數(shù)組 Ai,j存放從起點(x1,y1)到(i,j ) 的路徑總數(shù)，按同樣的方法從左向右遞推，一直遞推到(x2,y2)，ax2,y2即為所求的解。源程序(略)在上面的例題中，遞推過程中的某個狀態(tài)只與前面的一個狀態(tài)有關(guān)，遞推關(guān) 系并不復(fù)雜，如果在遞推中的某個狀態(tài)與前面的所有狀態(tài)都有關(guān)，就不容易找出 遞推關(guān)系式，這就需要我們對實際問題進行分析與歸納，從中找到突破口，總結(jié) 出

38、遞推關(guān)系式。我們可以按以下四個步驟去分析：(1)細心的觀察；(2)豐富的 聯(lián)想；(3)不斷地嘗試；(4)總結(jié)出遞推關(guān)系式。下面我們再看一個復(fù)雜點的例子。例 2、棧(noip2003pj )題目大意：求n個數(shù)通過棧后的排列總數(shù)。(K n=1)0空4初始值：f(0)=1;有了以上遞推式，就很容易用遞推法寫出程序。vara:array0.18of longint;n ,i,j:i nteger;beginread ln(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;writel

39、 n(a n);en d.遞推算法最主要的優(yōu)點是算法結(jié)構(gòu)簡單，程序易于實現(xiàn)，難點是從問題的分析中找出解決問題的遞推關(guān)系式。對于以上兩個例子，如果在比賽中找不出遞推關(guān)系式，也可以用回溯法求解。算法在信息學奧賽中的應(yīng)用（分治法）分治算法的基本思想是將一個規(guī)模為 N的問題分解為K個規(guī)模較小的子問題, 這些子問題相互獨立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的 解。分治法解題的一般步驟：（1）分解，將要解決的問題劃分成若干規(guī)模較小的同類問題；（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；（3）合并，按原問題的要求，將子問題的解逐層合并構(gòu)成原問題的解。分治法應(yīng)用例1、比賽安排（no

40、ip1996）設(shè)有25（*=6）個球隊進行單循環(huán)比賽,計劃在2An-1天內(nèi)完成,每個隊每天進 行一場比賽。設(shè)計一個比賽的安排，使在2八門-1天內(nèi)每個隊都與不同的對手比賽。 例如n=2時的比賽安排為：隊 比賽1-23-4第一天1-32-4第二天1-42-3第三天123 4算法分析：此題很難直接給出結(jié)果，我們先將問題進行分解，設(shè) m*n，將規(guī) 模減半，如果n=3（即m=8）,8個球隊的比賽，減半后變成 4個球隊的比賽（m=4，4 個球隊的比賽的安排方式還不是很明顯，再減半到兩 個球隊的比賽（m=2），兩個球隊 的比賽安排方式很簡單，只要讓兩個球隊直接進行一場比賽即可 ：|1|2 I分析兩個球隊的比

41、賽的情況不難發(fā)現(xiàn)， 這是一個對稱的方陣，我們把這個方陣 分成4部分（即左上，右上，左下，右下），右上部分可由左上部分加1 （即加m/2）得到，而右上與左下部分、左上與右下部分別相等。因此我們也可以把這個方陣 看作是由M=1的方陣所成生的，同理可得 M=4的方陣：1234214334124321同理可由M=4方陣生成M=8的方陣:1234567821465873411 278564321876556781234658721437856341287654321這樣就構(gòu)成了整個比賽的安排表。在算法設(shè)計中，用數(shù)組a記錄2An個球隊的循環(huán)比賽表，整個循環(huán)比賽表從最 初的1*1方陣按上述規(guī)則生成2*2的方

42、陣，再生成4*4的方陣，直到生成出 整個循環(huán)比賽表為止。變量h表示當前方陣的大小，也就是要生成的下一個方陣的 一半。源程序：vari,j,h,m, n:i nteger; a:array1.32,1.32of in teger; begi nreadl n(n); m:=1;a1,1:=1;h:=1;for i:=1 to n do m:=m*2;repeatfor i:=1 to h do構(gòu)造右上角方陣 構(gòu)造左下角方陣 構(gòu)造右下角方陣for j:=1 to h do beg in ai,j+h:=ai,j+h; ai+h,j:=ai,j+h; ai+h,j+h:=ai,j; end;h:=h

43、*2;un til h=m;for i:=1 to m dobeg infor j:=1 to m do write(ai,j:4); write In;end;end.在分治算法中，若將原問題分解成兩個較小的子問題，我們稱之為二分法，由 于二分法劃分簡單，所以使用非常廣泛。使用二分法與使用枚舉法求解問題相比 較，時間復(fù)雜度由0(N)降到O(log2N),在很多實際問題中，我們可以通過使用 二分法，達到提高算法效率的目的，如下面的例子。例2 一元三次方程求解(noip2001tg)題目大意：給出一個一元三次方程f(x)=ax3+bx2+cx+d=0，求它的三個根。所有的根都在區(qū)間-100，10

44、0中，并保證方程有三個實根，且它們之間的差不小于1。算法分析：在講解枚舉法時，我們討論了如何用枚舉法求解此題，但如果求解 的精度進一步提高，使用枚舉法就無能為力了，在此我們再一次討論如何用二分 法求解此題。由題意知(i,i+1 )中若有根，則只有一個根，我們枚舉根的值域中的每一個 整數(shù) x(- 100x 100),設(shè)定搜索區(qū)間x 1，X2，其中 xi=x，X2=x+1。若： f(X 1)=0，則確定X1為f(x)的根；f(X 1)*f(X 2)0，則確定根X不在區(qū)間x 1，X2內(nèi)，設(shè)定X2，X2+1為下一個搜索 區(qū)間；若確定根X在區(qū)間X 1， X2內(nèi)，米用二分法，將區(qū)間X 1， X2分成左右兩

45、個子 區(qū)間：左子區(qū)間x 1,x和右子區(qū)間x，(其中x=(x1+x2)/2 )。如果f(x 1)*f(x) 0, 則確定根在左區(qū)間X1, X內(nèi)，將X設(shè)為該區(qū)間的右界值(X2=X)，繼續(xù)對左區(qū)間 進行對分；否則確定根在右區(qū)間X，X2內(nèi)，將X設(shè)為該區(qū)間的左界值(X1=x)， 繼續(xù)對右區(qū)間進行對分；上述對分過程一直進行到區(qū)間的間距滿足精度要求為止(即X2-X 10.005 )。此時確定X1為f(x)的根。源程序：$N+varx:i nteger;a,b,c,d,x1,x2,xx:exte nded;function f(x:exte nded):exte nded;begi nf:=(a*x+b)*x+c)*x+d;end;begi nread(a,b,c,d);for x:=-100 to 100 dobeg inx1:=x;x2:=x+1;if f(x1)=0 then write(x1:0:2,)else if f(x1)*f(x2)=0.005 dobegi nxx:=(x1+x2)/2;if f(x1)*f(xx)從取3張牌放到 購(9 1110 10 )-從 取1張牌放到(10 10 10 10 )。輸 入:鍵盤輸入文件名。文件格式：N (N堆紙牌，1 = N = 100)A1 A2An (N堆紙牌，每堆紙牌初始數(shù)，l= Ai =10000)輸出:輸出至屏幕。格式為