2014NOIP算法快速入門教程中國計算機學會編要點

1、中國計算機學會20142014 NOIP 算法快速入門中國計算機學會編2014算法基礎篇學習過程序設計的人對算法這個詞并不陌生，從廣義上講，算法是指為解決 一個問題而采用的方法和步驟；從程序計設的角度上講，算法是指利用程序設計 語言的各種語句，為解決特定的問題而構成的各種邏輯組合。我們在編寫程序的 過程就是在實施某種算法，因此程序設計的實質就是用計算機語言構造解決問題 的算法。算法是程序設計的靈魂，一個好的程序必須有一個好的算法，一個沒有 有效算法的程序就像一個沒有靈魂的軀體。算法具有五個特征：1、有窮性： 一個算法應包括有限的運算步驟，執(zhí)行了有窮的操作后將終止 運算，不能是個死循環(huán)；2、確切

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

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

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

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

6、。(pascal程序如下)var i,t, 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);計數器增加1end;sum:=sum mod 1000;舍去與生成0無關的數end;writel n(t:6);end.算法二：此題中生成O的個數只與含5的個數有關，n!的分解數中含5的個 數就等于末尾O的個數，因此問題轉化為直接求 n!的分解數中含5的個數。 var t,n:i nteger;

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

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

9、我們以三種雞的個數為枚舉對象(分別 設為x,y,z ),以三種雞的總數(x+y+z)和買雞用去的錢的總數(x*3+y*2+z)為判 定條件，窮舉各種雞的個數。下面是解這個百雞問題的程序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+z div 3=100)and(z mod 3=0)then writel n( 'x=',x,'y=',y,'z=',z); 驗證可能的解

10、，并輸出符合題目要求的解 end.上面的條件還有優(yōu)化的空間，三種雞的和是固定的，我們只要枚舉二種雞(x,y)，第三種雞就可以根據約束條件求得(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.未經優(yōu)化的程序循環(huán)了 1013

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

12、以下同) 此題數據規(guī)模不大，可以進行枚舉，如果我們不加思地以每一個數位為枚舉對象， 一位一位地去枚舉：for a:=1 to 9 dofor b:=1 to 9 dofor i:=1 to 9 do這樣下去，枚舉次數就有9°次，如果我們分別設三個數為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); 把整數x轉化為字符串，存放在st中str(x*2

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

14、d=0這樣的一個一元三次方程。給出該方程 中各項的系數(a，b，c，d均為實數)，并約定該方程存在三個不同實根(根的范 圍在-100至100之間)，且根與根之差的絕對值>=1。要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數點后2位。提示：記方程f(x)=0，若存在2個數x1和x2，且x1<x2，f(x1)*(x2)<0，則在 (x1，x2)之間一定有一個根。樣例輸入：1-5-420輸出：-2.002.005.00算法分析：由題目的提示很符合二分法求解的原理，所以此題可以用二分法。 用二分法解題相對于枚舉法來說很要復雜很多。此題是否能用枚舉法求解呢？

15、再 分析一下題目，根的范圍在-100到100之間，結果只要保留兩位小數，我們不妨 將根的值域擴大100倍(-10000<=x<=10000)，再以根為枚舉對象，枚舉范圍是 -10000到10000，用原方程式進行驗證，找出方程的解。有的同學在比賽中是這樣做vark:i nteger;a,b,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.用這種方法，很快就可以把程序

16、編出來，再將樣例數據代入測試也是對的，等 成績下來才發(fā)現這題沒有全對，只得了一半的分。這種解法為什么是錯的呢？錯在哪里？前面的分析好象也沒錯啊，難道這題不能用枚舉法做嗎？看到這里大家可能有點迷惑了。在上面的解法中，枚舉范圍和枚舉對象都沒有錯，而是在驗證枚舉結果時，判 定條件用錯了。因為要保留二位小數，所以求出來的解不一定是方程的精確根， 再代入ax3+bx2+cx+d中，所得的結果也就不一定等于0，因此用原方程32ax3+bx2+cx+d=0作為判斷條件是不準確的。我們換一個角度來思考問題，設f(x)=ax 3+bx2+cx+d，若x為方程的根，則根 據提示可知，必有f(x-0.005)*(x

17、+0.005)<0，如果我們以此為枚舉判定條件，問題就逆刃而解。另外，如果f(x-0.005)=0 ，哪么就說明x-0.005是方程的根，這 時根據四舍5入，方程的根也為X。所以我們用(f(x-0.005)*f(x+0.005)<0) 和 (f(x-0.005)=0)作為判定條件。為了程序設計的方便，我們設計一個函數f(x)計算ax3+bx2+cx+d的值，程序如下：$N+vark:integer;a,b,c,d,x:extended;function f(x:extended):extended;計算 ax +bx +cx+d 的值 beginf:=(a*x+b)*x+c)*x+

18、d;end;beginread(a,b,c,d);for k:=-10000 to 10000 dobeginx:=k/100;if (f(x-0.005)*f(x+0.005)v0) or (f(x-0.005)=0) then write(x:0:2,''); 若 x 兩端的函數值異號或x-0.005剛好是方程的根，則確定 x為方程的根end;end.用枚舉法解題的最大的缺點是運算量比較大，解題效率不高，如果枚舉范圍 太大(一般以不超過兩百萬次為限)，在時間上就難以承受。但枚舉算法的思路簡 單，程序編寫和調試方便，比賽時也容易想到，在競賽中，時間是有限的，我們 競賽的最終目

19、標就是求出問題解，因此，如果題目的規(guī)模不是很大，在規(guī)定的時 間與空間限制內能夠求出解，那么我們最好是采用枚舉法，而不需太在意是否還 有更快的算法，這樣可以使你有更多的時間去解答其他難題。信息學奧賽中的基本算法(回溯法)如果上期的“百錢買百雞”中雞的種類數是變化的，用枚舉法就無能為力了， 這里介紹另一種算法一一回溯法?；厮莼舅枷牖厮莘ㄊ且环N既帶有系統(tǒng)性又帶有跳躍性的搜索法，它的基本思想是：在搜 索過程中，當探索到某一步時，發(fā)現原先的選擇達不到目標，就退回到上一步重 新選擇。它主要用來解決一些要經過許多步驟才能完成的，而每個步驟都有若干 種可能的分支，為了完成這一過程，需要遵守某些規(guī)則，但這些規(guī)

20、則又無法用數 學公式來描述的一類問題。下面通過實例來了解回溯法的思想及其在計算機上實 現的基本方法。例1、從N個自然數(1,2,n)中選出r個數的所有組合。算法分析：設這r個數為ai,a2,a，把它們從大到小排列，則滿足：(1) ai>a2>>ar；(2) 其中第i位數(1<=i<=r)滿足ai>r-i;我們按以上原則先確定第一個數，再逐位生成所有的r個數，如果當前數符合要求，則添加下一個數；否則返回到上一個數，改變上一個數的值再判斷是否符 合要求，如果符合要求，則繼續(xù)添加下一個數，否則返回到上一個數，改變上一 個數的值按此規(guī)則不斷循環(huán)搜索，直到找出r個數的

21、組合，這種求解方法就是回溯法。如果按以上方法生成了第i位數ai，下一步的的處理為：(1) 若ai>r-i且i=r，則輸出這r個數并改變ai的值:ai=a“；(2) 若ai >r-i且i工r，則繼續(xù)生成下一位 a+1=ai-1;(3) 若ai <=r-i ，則回溯到上一位，改變上一位數的值：a / =a-1-1; 算法實現步驟：第一步：輸入n,r的值，并初始化；i:=1;a1:=n;第二步：若a1>r-1則重復：若ai>r-i ，若i=r，則輸出解，并且ai:=ai-1;若 i<>r，則繼續(xù)生成下一位：ai+1:=ai-1; i:=i+1;若 ai<

22、;=r-i ，則回溯：i:=i-1; ai:=ai-1;第三步：結束；程序實現var n ,r,i,j:i nteger;a:array1.10 of in teger;begi nreadl n(n ,r);i:=1;a1:=n;repeatif ai>r-i then 符合條件if i=r then 輸出beg 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=

23、r-1;end.下面我們再通過另一個例子看看回溯在信息學奧賽中的應用。例2數的劃分(noip2001tg)問題描述 整數n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。例如：n=7，k=3,下面三種分法被認為是相同的。1，1，5;1，5，1;5，1，1;問有多少種不同的分法。輸入：n， k (6<nv=200，2<=k<=6)輸出：一個整數，即不同的分法。樣例輸入：73輸出：4四種分法為：1,1,5; 1,2,4; 1,3,3; 2,2,3;算法分析：此題可以用回溯法求解，設自然數n拆分為a1,a2,;ak,必須滿足以下兩個條件：(1) n=a1+a2+ak ；(

24、2) a 1<=a2<=y=ak ( 避免重復計算);現假設己求得的拆分數為a1,a2, &,且都滿足以上兩個條件，設 sum=n-a1-a 2- -ai,我們根據不同的情形進行處理：(1) 如果i=k,則得到一個解，則計數器t加1,并回溯到上一步，改變ai-1的值;(2) 如果i<k且sum>=a,則添加下一個元素ai+1;(3) 如果i<k且sumva,則說明達不到目標，回溯到上一步，改變a“的值； 算法實現步驟如下：第一步：輸入自然數 n,k 并初始化；t:=0; i:=1;ai:=1; sum:=n-1; nk:=n div k;第二步：如果a1&

25、lt;=nk 重復：若i=k，搜索到一個解，計數器t=t+1;并回溯；否則：若sum>=ai則繼續(xù)搜索；若sum<ai則回溯；搜索時，inc(i);ai:=ai-1;sum:=sum-ai;回溯時，dec(i); inc(ai); sum:=sum+ai+1-1;第三步：輸出。程序如下：varn,n k,sum,i,k:i nteger;t:lo ngint;a:array1.6of in teger;begi nreadl n(n ,k);nk:=n div k;t:=0; i:=1;ai:=1; sum:=n-1;初始化repeatif i=k then判斷是否搜索到底beg

26、in in c(t); dec(i);i nc(ai); sum:=sum+ai+1-1; end 回溯else beg inif 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中有許多涉及搜索問題的題目都可以用回溯法來求解。信息學奧賽中的基本算法（遞歸算法）遞歸算

27、法的定義：如果一個對象的描述中包含它本身，我們就稱這個對象是遞歸的，這種用遞 歸來描述的算法稱為遞歸算法。我們先來看看大家熟知的一個的故事：從前有座山，山上有座廟，廟里有個老和尚在給小和尚講故事，他說從前有 座山，山上有座廟，廟里有個老和尚在給小和尚講故事，他說上面的故事本身是遞歸的，用遞歸算法描述：procedure bon ze-tell-story ； begi nif講話被打斷then故事結束else begi n從前有座山，山上有座廟，廟里有個老和尚在給小和尚講故事；bon ze-tell-story；endend;從上面的遞歸事例不難看出，遞歸算法存在的兩個必要條件：（1）必須有遞

28、歸的終止條件；（2）過程的描述中包含它本身；在設計遞歸算法中，如何將一個問題轉化為遞歸的問題，是初學者面臨的難 題，下面我們通過分析漢諾塔問題，看看如何用遞歸算法來求解問題；遞歸算法應用例1:漢諾塔問題，如下圖，有 A、B、C三根柱子。A柱子上按從小到大的順 序堆放了 N個盤子，現在要把全部盤子從A柱移動到C柱，移動過程中可以借助B 柱。移動時有如下要求：（1）一次只能移動一個盤子；（2）不允許把大盤放在小盤上邊；（3）盤子只能放在三根柱子上；丄丨丨 已曰匚算法分析：當盤子比較多的時，問題比較復雜，所以我們先分析簡單的情況：如果只有一個盤子，只需一步，直接把它從A柱移動到C柱；如果是二個盤子，

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

30、一個盤子，按照移動一個盤子的方法 移動，遞歸結束。遞歸過程：procedure Hanoi（N,A,B,C:integer;）； 以B柱為中轉柱將 N個盤子從 A柱移動到C柱 begi nif N=1 then write（A , ' -> ' ,C）把盤子直接從 A移動到 Celse beg inHanoi（N-1,A,C,B）； 以C柱為中轉柱將N-1個盤子從A柱移動到B柱write(A , ' -> ' ,C) ; 把剩下的一個盤子從 A移動到CHanoi(N-1,B,A,C) ; 以A柱為中轉柱將 N-1個盤子從B柱移動到C柱 end;end

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

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

33、cedure make(z,h:string); z為中序排列,h 為后序排列var s,m : in teger;begi nm:=length(h);m 為樹的長度write(hm); 輸出根節(jié)點s:=pos (h m,z); 求根節(jié)點在中序排列中的位置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;begi nreadl n(z);read In (h);make(z,h);end.遞歸算法不僅僅是用于求解遞歸

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

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

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

37、特點：(1) 問題可以劃分成多個狀態(tài)；(2) 除初始狀態(tài)外，其它各個狀態(tài)都可以用固定的遞推關系式來表示。 在我們實際解題中，題目不會直接給出遞推關系式，而是需要通過分析各種狀態(tài)，找出遞推關系式。遞推法應用例 1 騎士游歷:(noip1997tg)設有一個n*m的棋盤(2<=*=50,2<=m<=50),如下圖,在棋盤上任一點有一個中國象 棋馬，-1 _F -®-（.1, 1）馬走的規(guī)則為:1.馬走日字2.馬只能向右走，即如下圖所示任務1:當N,M輸入之后，找出一條從左下角到右上角的路徑。 例如：輸入N=4,M=4輸出：路徑的格式：(1,1)->(2,3)-&g

38、t;(4,4)若不存在路徑，則輸出"no"任務2:當N,M給出之后，同時給出馬起始的位置和終點的位置，試找出從起點到終 點的所有路徑的數目。例如:(N=10,M=10),(1,5)( 起點),(3,5)( 終點)10輸出:2（即由（1,5）到（3,5）共有2條路徑）輸入格式：n,m,x1,y1,x2,y2（分別表示n,m,起點坐標,終點坐標）輸出格式:路徑數目（若不存在從起點到終點的路徑，輸出0）算法分析：為了研究的方便，我們先將棋盤的橫坐標規(guī)定為i，縱坐標規(guī)定為j ,對于一個n>m的棋盤，i的值從1到n, j的值從1到m棋盤上的任意點都可以 用坐標（i,j）表示。對

39、于馬的移動方法，我們用 K來表示四種移動方向（1,2,3,4）;而每種移動方法用偏移值來表示，并將這些偏移值分別保存在數組dx和dy中，如下表KDxkDyk12122-131241-2根據馬走的規(guī)則，馬可以由（i-dxk,j-dyk ）走到（i,j）。只要馬能從（1, 1）走到（i-dxk,j-dyk ），就一定能走到（i,j ）,馬走的坐標必須保證在棋盤 上。我們以（n,m）為起點向左遞推，當遞推到（i-dxk,j-dyk ）的位置是（1， 1）時，就找到了一條從（1, 1 ）至（ n,m）的路徑。我們用一個二維數組a表示棋盤，對于任務一，使用倒推法，從終點（n ,m）往 左遞推，設初始值a

40、 n,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 存放兩個點中的任意一個即可。遞推結束以后，如果a1,1值為（0,0）說明不存在 路徑，否則a1,1值就是馬走下一步的坐標，以此遞推輸出路徑。-1,-14,4 14,42,3任務一的源程序:con stdx:array1.4of in teger=(2,2,1,1);dy:array1.4of in teger=(1,-1,2,-2);typ

41、emap=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.x<>0 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('

42、no')else begi n存在路徑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.對于任務二，也可以使用遞推法，用數組Ai,j存放從起點(x1,y1)到(i,j ) 的路徑總數，按同樣的方法從左向右遞推，一直遞推到(x2,y2)，ax2,y2即為所求的解。源程序(略)在上面的例題中

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

44、 ; f(2)=2 ;f(3)=5,通過觀察，看不出它們之間的遞推關系，我們再分析N=4的情況，假設入棧前的排列為“ 432T,按第一個數“ 4”在出棧后的位置進行分情況討論：(1) 若“4”最先輸出，剛好與N=3相同，總數為f(3);(2) 若“4”第二個輸出，則在“4”的前只能是“ 1”“23”在“4”的后面，這時可以分別看作是N=1和N=2時的二種情況，排列數分別為f(1)和f(2),所以此時的總數為f(1)*f(2);(3) 若“4”第三個輸出，則“4”的前面二個數為“ 12”，后面一個數為“ 3”， 組成的排列總數為f(2)*f(1);(4) 若“4”第四個輸出，與情況(1)相同，總

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

46、nread 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 n(a n);en d.遞推算法最主要的優(yōu)點是算法結構簡單，程序易于實現，難點是從問題的分析中找出解決問題的遞推關系式。對于以上兩個例子，如果在比賽中找不出遞推關系式，也可以用回溯法求解。算法在信息學奧賽中的應用（分治法）分治算法的基本思想是將一個規(guī)模為 N的問題分解為K個規(guī)模較小的子問題, 這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的 解。分治法解題的一般步驟：（1）

47、分解，將要解決的問題劃分成若干規(guī)模較小的同類問題；（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；（3）合并，按原問題的要求，將子問題的解逐層合并構成原問題的解。分治法應用例1、比賽安排（noip1996）設有25（*=6）個球隊進行單循環(huán)比賽,計劃在2An-1天內完成,每個隊每天 進行一場比賽。設計一個比賽的安排，使在2八門-1天內每個隊都與不同的對手比賽。 例如n=2時的比賽安排為：1 23 41-23-4第一天1-32-4第二天1-42-3第三天隊 比賽算法分析：此題很難直接給出結果，我們先將問題進行分解，設m=2An，將規(guī)模減半，如果n=3（即m=8）,8個球隊的比賽，減半后變

48、成 4個球隊的比賽（m=4，4 個球隊的比賽的安排方式還不是很明顯，再減半到兩 個球隊的比賽（m=2），兩個球隊 的比賽安排方式很簡單，只要讓兩個球隊直接進行一場比賽即可 ：|1|2 I分析兩個球隊的比賽的情況不難發(fā)現， 這是一個對稱的方陣，我們把這個方陣分成4部分（即左上，右上，左下，右下），右上部分可由左上部分加1 （即加m/2）得到，而右上與左下部分、左上與右下部分別相等。因此我們也可以把這個方陣 看作是由M=1的方陣所成生的，同理可得 M=4的方陣：12342143 134124321同理可由M=4方陣生成M=8的方陣:1234567821465873411 2785643218765

49、56781234658721437856341287654321這樣就構成了整個比賽的安排表。在算法設計中，用數組a記錄2An個球隊的循環(huán)比賽表，整個循環(huán)比賽表從最 初的1*1方陣按上述規(guī)則生成2*2的方陣，再生成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構

50、造右上角方陣 構造左下角方陣 構造右下角方陣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*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.在分治算法中，若將原問題分解成兩個較小的子問題， 我們稱之為二分法，由 于二分法劃分簡單，所以使用非常廣泛。使用二分法與使用枚舉法求解問題相比 較，時間復雜度由0(N)降到O(log2N),在很多實際問題中，我們可以通過使用

51、二分法，達到提高算法效率的目的，如下面的例子。例2 一元三次方程求解(noip2001tg)題目大意：給出一個一元三次方程 f(x)=ax3+bx2+cx+d=0 ,求它的三個根。所有的 根都在區(qū)間-100，100中，并保證方程有三個實根，且它們之間的差不小于1。算法分析：在講解枚舉法時，我們討論了如何用枚舉法求解此題，但如果求解的精度進一步提高，使用枚舉法就無能為力了，在此我們再一次討論如何用二分 法求解此題。由題意知(i,i+1 )中若有根，則只有一個根，我們枚舉根的值域中的每一個 整數 x(- 100<x< 100),設定搜索區(qū)間x 1，X2，其中 xi=x，X2=x+1。若

52、： f(X 1)=0，則確定X1為f(x)的根；f(X 1)*f(X 2)<0，則確定根X在區(qū)間X 1，X2內。f(X 1)*f(X 2)>0，則確定根X不在區(qū)間x 1，X2內，設定X2，X2+1為下一個搜索 區(qū)間；若確定根X在區(qū)間X 1， X2內，米用二分法，將區(qū)間X 1， X2分成左右兩個子 區(qū)間：左子區(qū)間x 1,x和右子區(qū)間x ,X2(其中x=(x1+x2)/2 )。如果f(x 1)*f(x)< 0,則確定根在左區(qū)間X1，X內，將X設為該區(qū)間的右界值(X2=X)，繼續(xù)對左區(qū)間 進行對分；否則確定根在右區(qū)間X，X2內，將X設為該區(qū)間的左界值(X1=x)， 繼續(xù)對右區(qū)間進行

53、對分；上述對分過程一直進行到區(qū)間的間距滿足精度要求為止(即X2-X 1<0.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 t

54、he nbeg inwhile x2-x1>=0.005 dobegi nxx:=(x1+x2)/2;if f(x1)*f(xx)<=0 then x2:=xxelse x1:=xx;en d;whilewrite(x1:0:2,'');end; the n22中國計算機學會2014en d;for end.信息學奧賽中的基本算法(貪心法)在求最優(yōu)解問題的過程中，依據某種貪心標準，從問題的初始狀態(tài)出發(fā)，直 接去求每一步的最優(yōu)解，通過若干次的貪心選擇，最終得出整個問題的最優(yōu)解， 這種求解方法就是貪心算法。從貪心算法的定義可以看出，貪心法并不是從整體上考慮問題，它所做出

55、的 選擇只是在某種意義上的局部最優(yōu)解，而由問題自身的特性決定了該題運用貪心 算法可以得到最優(yōu)解。我們看看下面的例子貪心法應用例1均分紙牌(NOIP2002tg)問題描述有N堆紙牌，編號分別為1, 2，,N。每堆上有若干張，但紙牌 總數必為N的倍數?？梢栽谌我欢焉先∪舾蓮埣埮?，然后移動。移牌規(guī)則為：在 編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙 牌，只能移到編號為 N-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊 的堆上?，F在要求找出一種移動方法，用最少的移動次數使每堆上紙牌數都一樣 多。例如N=4，4堆紙牌數分別為：98 176移動3次可達到目的：從取4張牌放到 (9 8 13 10)->從取3張牌放到 購(9 1110 10 )->從 取1張牌放到(10