信息學奧賽算法及基礎知識復習材料兩篇.doc

1、信息學奧賽算法及基礎知識復習材料兩篇第1條信息學中奧賽羅算法的基本章節(jié)學過編程的人對算法這個詞并不陌生。從廣義上說， 算法是指用來解決問題的方法和步驟。從程序設計的角度來看， 算法是指使用編程語言的各種語句來解決特定問題而形成的各種邏輯組合。在編程的過程中， 我們在實現(xiàn)某些算法， 所以編程的本質就是用計算機語言來構造算法來解決問題。算法是編程的靈魂。 一個好的程序必須有一個好的算法。 沒有有效算法的程序就像沒有靈魂的軀體。該算法有五個特點具有 1、有限性的算法應該包括有限的操作步驟。該操作將在執(zhí)行完有限操作后終止，并且不能是死循環(huán)。2、精確度算法的每一步都必須有一個明確的定義，當讀者理解它時不

2、會產(chǎn)生歧義。此外，在任何條件下，該算法只有一條執(zhí)行路徑，并且對于相同的輸入只能獲得相同的輸出。例如，在算法中不允許諸如 計算8/0 ”或將7或8加到x上”的操作， 因為前者的計算結果不清楚， 而后者不知道應該進行兩種可能的操作中的哪一種。3、輸入一個算法有0 個或更多的輸入來描述操作對象的初始條件。所謂的 0 輸入是指算法本身定義的初始條件。如果找到五個數(shù)字中最小的一個，則有五個輸入。4、 輸出算法有一個或多個輸出來反映輸入數(shù)據(jù)的處理結果，這是算法設計的目的。它們是與輸入有特定關系的量。如上所述， 在 5 個數(shù)字中找出最小的數(shù)字， 它的輸出是最小的數(shù)字。如果一個程序沒有輸出，這個程序就沒有意義

3、。5、可行性算法中的每個操作都應該是可行的。原則上， 該算法可以精確運行， 并且可以在用筆和紙進行有限次數(shù)的操作后完成。如何評估一個算法主要是從兩個方面:一是運行算法所花費的時間；我們用時間復雜度來衡量，例如，在以下三個程序中，(1)x1(2)for I 1 tondo xx 1(3)for I 1 tondo for J1 tondo xx 1 語句 xx1 包含基本運算“x+1分別出現(xiàn)1次，n和n2,那么這三個程序段的時間復雜度分別為O(1), O(n), O(n2),分別稱為常數(shù)階、線性階和平方階。在算法時間復雜度的表示中，也可以有對數(shù)有序的ogn、指數(shù)有序的 O2n 等。當 n 較大時

4、，不同數(shù)量級的時間復雜度為 O11。要求在三個實根和同一行的根之間從小到大留一個空格， 并 精確到小數(shù)點后兩位。注意等式fx0,如果有2個數(shù)字x1和x2,以及xlar其中，例如n7、k3,以下三個子方法被認為是相同的1， 1 ， 5； 1 ， 5， 1； 5， 1， 1；詢問有多少種不同的方法。輸入n, k6nk。writelnt。End.回溯法是通過嘗試和糾正錯誤來找到答案。這是一種通用的解決問題的方法。在 NOIP ，許多涉及搜索問題的問題可以用回溯法解決。信息學中的基本算法奧賽羅遞歸算法遞歸算法的定義如果一個對象的描述包括它自己， 我們稱之為對象遞歸。 這種用遞歸描述的算法稱為遞歸算法。

5、讓我們來看看一個著名的故事。 從前， 山上有一座山和一座廟。 寺廟里的一個老和尚正在給一個小和尚講故事。 他說山上有一座山和一座廟。寺廟里的一個老和尚正在給一個小和尚講故事。他說，上述故事本身是遞歸的，并描述了講述故事的過程；-帶有遞歸算法的故事。故事的結尾從前， 有一座山和一座廟， 一個老和尚在里面給一個小和尚講故事。和尚講故事；endend從上面的遞歸例子中，不難看出遞歸算法有兩個必要條件 (1)必須有一個遞歸終止條件；(2)過程的描述包括其本身；在設計遞歸算法時， 如何將問題轉化為遞歸是初學者的一個難題。 讓我們分析一下漢諾塔問題， 看看如何用遞歸算法來解決這個問題。遞歸算法應用于實例

6、1 中的漢諾塔問題。 如下圖所示， 有三歹!J:a、b、ca 柱上從小到大堆放著n 塊板。現(xiàn)在，在 b 柱的幫助下，將所有板從a柱移至c柱。移動時有以下要求:(1)一次只能移動一個板；(2)不允許將大盤放在小盤上面；(3)板只能放置在三根柱子上；算法分析當板塊越多， 問題就越復雜， 所以我們首先分析簡單的情況。 如果只有一個板， 我們只需要一步將它從a 柱直接移動到C 柱。如果是兩塊板，則需要移動 3 個步驟 (1)將 A 柱上的小板移動到B柱上；(2)將a柱上的大板移到 C柱上；(3)將 B 柱上的大板移動到 C 柱上；如果 N 相對較大，則需要許多步驟才能完成。我們首先考慮能否將復雜的移動

7、過程轉化為簡單的移動過程。 如果我們想將a 柱上最大的板移動到 C 柱上，我們必須首先將上部N-1 板從 a 柱移動到 B 柱上，以便臨時存放。根據(jù)這一思想，我們可以將N 塊板的移動過程分為三個步驟:(1)將 A 柱上的 N-1 塊板移動到 B 柱上；(2)將 a 柱上的剩余板移動到 C 柱上；(3)將b柱上的N-1板移至c柱；根據(jù)相同的方法， N-1 個板的移動過程可以分為三個步驟，從而將移動過程轉換成遞歸過程， 直到只剩下一個板， 根據(jù)移動一個板的方法移動，并結束遞歸。遞歸過程程序a, b, c整數(shù)。；將n塊板從A列移至C歹U,B 列作為轉移柱 beginifn1thenwirita ，

8、-， C 將板直接從A 移至CelsebeginHanoiN-1, A, C, B; a、c、b; 使用列 c作為轉移列， 將N-1板從列a移至列b 寫a、-”、c； 將剩余的板從a移動到c hanoin-1, b, a, c; 將N-1板從B柱移動到C柱，A柱作為轉換柱 端；結束；從上面的例子中，我們可以看到，在使用遞歸算法時，我們應該首先找出簡單條件下的解， 然后找出如何將復雜的情況簡化為 更簡單的情況。 信息學奧賽羅 中某些問題的結構或處理的數(shù)據(jù)是遞歸定義的。這些問題非常適合用遞歸算法來解決。對于這樣的問題，我們把它們分解成幾個具有相同性質的子問題。 如果子問題解決了， 原來 的問題也就

9、解決了。例 2 第一級的 NOIP20XXpj 和 A 的值是 （4， 4） ， 這意味著坐標 （4， 4）可以從兩個點到達。兩點 （2， 3） 、 （3， 2）可以從（1 ， 1）得到，所以A 可以存儲兩點中的任何一點。遞歸后，如果一個值為 0， 0 表示沒有路徑，否則一個值就 是馬下一步遞歸輸出路徑的坐標。-1 ， -14 ， 44 ， 42 ， 3 任 務 1 源 程 序 常 量 constdxarrayofmapbeginreadn， m ； fillchara ， sizeofa， 0 ； an， m.x-1 ； an， m.y-1 ； 標記為 end for donto 2 do

10、backward foj1 tomidifaI ， j.x0 然后用于 k1 至 4dobegina i-dx k ， j-dyk.Xi ； ai-dxk ，j-dyk.yj ；結束； IFA .x0 Thenwritelnoelsbein 存在路徑 i1J1 ；寫，I ， ， j ， ；而 i ， j.x-1 ； iai ， j.x ； jak ， j.y ；寫 -， I ， ， ， j ， ；結束；結束；End.對于任務2,也可以使用遞歸方法。陣列 Ai , j用于存儲從起始點x1, y1到(I, j)的路徑總數(shù)。遞歸以同樣的方式從左到右進行， 直到(x2, y2)。x2, y2是期望的解

11、決方案。源程序 (略)在上面的例子中，遞歸過程中的某個狀態(tài)只與前一個狀態(tài)相關， 遞歸關系并不復雜。 如果遞歸中的某個狀態(tài)與以前的所有狀態(tài)都相關， 那么就不容易找到遞歸關系，這就要求我們分析和總結實際問題，尋找突破口，總結遞歸關系。我們可以按照以下四個步驟進行分析:(1)仔細觀察；(2)豐富的聯(lián)想；(3)堅持嘗試；(4)總結遞歸關系。讓我們看看另一個更復雜的例子。示例 2、堆棧 (noip20XXpj) 本主題的主要思想是在通過堆棧后找到 n 行的總數(shù)。(iwnwi勵如，輸入3輸出5算法分析首先模擬入棧、出棧操作，看是否能找到規(guī)則。我們使用 fn 來表示堆棧操作后排列的 n個數(shù)字的總數(shù)。當n很小

12、時，f11可以很容易地模擬。f22F35,通過觀察， 我們看不出它們之間的復發(fā)關系。 我們將再次分析N4 的情況，假設進入堆棧前的排列是“ 4321?！?我們將根據(jù)離開堆棧后第一個數(shù)字“ 4的位置來討論這種情況?！?1)如果先輸出“ 4，則與”N3 完全相同，總數(shù)為F3; (2)如果“4是第二個輸出，它只能是“4之前的“1和“4”之后的“237此時可分別視為N1和N2兩種情況，排列號分別為fl 和f2,所以此時的總數(shù)為fl * f2(3)如果“4是第三個輸出，“4的前兩 個數(shù)字是122：最后一個數(shù)字是“3；排列的總數(shù)是f2 * f1(4)如果第 四個輸出“4與情況(1)相同，則總數(shù)為F3;因此

13、，有F4 F3 fl * F2 F2 * fl F3;如果零的數(shù)目通過堆棧，排列的總數(shù)是 f01;上述公式可改為f4f0*f3f1*f2f2*f1f3*f0 。經(jīng)過進一步推導， 不難推導出遞推公式fnf 0 * fn-1 fl * fn-2fn-1 * F0 ;即 fn101*niinfifn1初始值f01有了上述遞推公式，用遞推方法編寫程序就很容易了。瓦拉雷 018倫敦；n, I, jintegerbeginreadlnnfillchara, sizeofa, 0; a01;對于1東多弗羅里0托伊-1多阿1阿1阿1*阿1; n; end遞歸算法的主要優(yōu)點是結構簡單，易于實現(xiàn)。難點在于從問題的

14、 分析中找到解決問題的遞推公式。對于以上兩個例子，如果在競爭中找不到遞推公式，也可以 用回溯法求解。算法在信息學中的應用奧賽羅分治算法的基本思想是將一個n大小的問題分成k個較小的子問題，這些子問題相互獨立，并且 具有與原問題相同的性質。通過尋找子問題的解，可以得到原問題的解。分治法的一般步驟如下：(1)分解，將待解決的問題分成幾個較小的類似問題;（2）當子問題劃分得足夠小時，用更簡單的方法解決；（3）合并 :根據(jù)原問題的要求，逐層合并子問題的解，形成原問題的解。分治法的應用1、比賽安排noip1996 有 2nn 張牌從中取出并放入（10101010）。輸入 鍵盤輸入文件名。文件格式N（N堆卡

15、片，1ba,將a放在b前面，否則將a放 在 b 后面字 符 串 的 源 程 序 瓦 爾 薩 爾 雷 120 ； tstringI ， j ， k ， nlongintbeginreadlnnforiltondobeginreadkL世； 結束；國際單項體育 聯(lián)合會國際單項體育聯(lián)合會分會 2， 4， 4。如果沒有路徑，則輸出“否 ”算法分析。我們以一個44 棋盤為例進行分析。我們使用樹形結構來表示所有的走馬過程（如下圖所示） 。找到從起點到終點的路徑實際上是先從根節(jié)點開始深入搜索樹。馬從 （1， 1）開始，根據(jù)深度優(yōu)先搜索方法前進一步到（2， 3），以判斷它是否已經(jīng)到達終點。如果沒有，它會繼續(xù)前

16、進，然后再前進一步到達 （4， 4） 。然后它判斷是否已經(jīng)到達終點。如果有，則退出，搜索過程結束。為了減少搜索次數(shù)， 在走馬的過程中， 判斷下一步是否在棋盤上，如果不是，選擇另一條路徑再次行走。程序如下 :整數(shù) 2， 2， 1， 1 的常數(shù) 14 ； 1， -1 ， 2， -2 的；typemaprecordx， yinteger 結 束 ； vari ， n ， minteger050of map ； proceduredfsiintegervarjintegerI-1.xdxj0andaI-1.xdxj0andaI-1.ydyj , aj.x , aj.y;停止；輸出結果和退出程序結束；

17、dfsi1搜索下一個 aI.x0 ; aI.y0 ; push 結束。結束；begina1.x1; a1.y1; readlnn, m; dfs2writelnno。End.從上面的例子中，我們可以 看到深度優(yōu)先搜索算法有兩個特點1、 生成的節(jié)點按深度排序。 具有大深度的節(jié)點首先被擴展， 即它們的子節(jié)點首先被生成。深度為2、的節(jié)點生成較晚，但它們先擴展，即“生成較晚，先擴展 ” ，這與堆棧的工作原理相同。因此，堆棧被用作算法的主要數(shù)據(jù)結構來存儲生成的節(jié)點。對于不同的問題， 深度優(yōu)先搜索算法基本相同， 但具體的處理方法和編程技巧不同，甚至有很大差異。讓我們看看另一個例子。第二個選擇數(shù)（保存名稱n

18、o p20x xPj）問題描述被稱為n個 整數(shù) x1、 x2、 xn 和一個整數(shù)kk n一系列的和可以通過將n 個整數(shù)中的任意k 個整數(shù)相加而得到。例如，當n4、 k = 3 和 4個整數(shù)分別為 3、 7、 12和 19 時，所有組合及其總和為 3+7+12223+7+19 = 297+12+19 = 383+12+19 = 34?，F(xiàn)在，你需要計算有多少種和是質數(shù)。例如，在上面的例子中，只有一個素數(shù)的和 3+7+19 = 29。輸入鍵盤輸入，格式為n, kithenincans依口果是質數(shù)，總數(shù)加 1 結束；proceduredfsi， mbyte。 搜索依賴項d； beginreadlnn， k；對于一世;ansOsQ dfsl, 1; writelnansEnd.從以上兩個例子中，我 們可以看到使用遞歸實現(xiàn)深度優(yōu)先搜索比使用非遞歸更方便。在使用深度搜索方法解決問題時， 搜索效率不高， 因此要注意算法的優(yōu)化，盡可能縮小搜索范圍，提高程序速度。另一種搜索方法， 廣度優(yōu)先搜索， 將在下一篇文章中繼續(xù)介紹。算法在信息學中的應用奧賽羅 （搜索方法2）在深度優(yōu)先搜索算法中， 深度較大的節(jié)點首先被擴展。 如果將其改為深度較小的節(jié)點并先擴展，則是廣度優(yōu)先的搜索方法。廣度優(yōu)先搜索的基本算法程序；初始化；建立隊列數(shù)據(jù)；設置隊列頭指針關閉0;隊列尾部指針打開1; Re