信息學(xué)奧賽初賽指導(dǎo)講座

1、信息學(xué)奧賽初賽指導(dǎo)講座樹的定義樹（tree）是包含n （n0）個結(jié)點的有窮集合k,且在k中定義了一個關(guān)系n, n滿足以下條件：（1）有且僅有一個結(jié)點ko,他對于關(guān)系n來說沒有前驅(qū)，稱k0為樹的根結(jié)點。 簡稱為根（root） o（2）除k0外，k屮的每個結(jié)點，對于關(guān)系n來說有且僅有一個前驅(qū)。（3）k中各結(jié)點，對關(guān)系n來說可以有ni個后繼（ni>二0）。若nl,除根結(jié)點之外的其余數(shù)據(jù)元素被分為ni （ni>0）個互不相交的結(jié)合t1, t2,tm,其中每一個集合ti （l<=i<=m）本身也是一棵樹。樹tl, t2,tm稱作根結(jié)點的子樹（sub tree）。樹也就可以這樣定義

2、：樹是有根結(jié)點和若干顆子樹構(gòu)成的。（上一段來自高林，數(shù)據(jù)結(jié)構(gòu)（c+），北京清華大學(xué)出版社）樹是由一個集合以及在該集合上定義的一種關(guān)系構(gòu)成的。集合屮的元素稱為樹 的結(jié)點，所定義的關(guān)系稱為父子關(guān)系。父子關(guān)系在樹的結(jié)點z間建立了一個層次結(jié) 構(gòu)。在這種層次結(jié)構(gòu)中有一個結(jié)點具有特殊的地位，這個結(jié)點稱為該樹的根結(jié)點， 或簡稱為樹根。我們可以形式地給出樹的遞歸定義如下：單個結(jié)點是一棵樹，樹根就是該結(jié)點本身。設(shè)tl,t2,.,tk是樹，它們的根結(jié)點分別為nl,n2,.,nko用一個新結(jié)點n作 為nl, n2,., nk的父親，則得到一棵新樹，結(jié)點n就是新樹的根°我們稱nl, n2,., nk 為一組

3、兄弟結(jié)點，它們都是結(jié)點n的兒子結(jié)點。我們還稱n 1, n2,. . , nk為結(jié)點n的 子樹。空集合也是樹，稱為空樹?？諛溴鴽]有結(jié)點。二叉樹相關(guān)：二叉樹的概念：在計算機科學(xué)中，二叉樹是每個結(jié)點最多有兩個子樹的有序樹。通常子樹的根 被稱作"左子樹” （left subtree）和"右子樹” （right subtree）。二叉樹常 被用作二叉查找樹和二叉堆。二叉樹的每個結(jié)點至多只有二棵子樹（不存在度大于2 的結(jié)點），二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的（i-l）次方個結(jié)點；深度為k的二叉樹至多有27k） -1個結(jié)點，最少有h個結(jié)點; 對任何一棵二叉樹

4、t,如果其終端結(jié)點數(shù)（即葉子結(jié)點數(shù)）為n0,度為2的結(jié)點數(shù)為 n2,則 n0 = n2 + 1。樹和二叉樹的2個主要差別：1 樹中結(jié)點的最大度數(shù)沒有限制，而二叉樹結(jié)點的最大度數(shù)為2；（度指分支） 2.樹的結(jié)點無左、右之分，而二叉樹的結(jié)點有左、右之分且不能顛倒次序。樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，肓觀地看，它是數(shù)據(jù)元素（在樹中稱為結(jié)點） 按分支關(guān)系組織起來的結(jié)構(gòu)，很象自然界中的樹那樣。樹結(jié)構(gòu)在客觀世界中廣泛存 在，如人類社會的族譜和各種社會組織機構(gòu)都可用樹形象表示。樹在計算機領(lǐng)域屮 也得到廣泛應(yīng)用，如在編譯源程序如下時，可用樹表示源源程序如下的語法結(jié)構(gòu)。 又如在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)也是信息的重要

5、組織形式之一。一切具有層次關(guān)系 的問題都可用樹來描述。（1）完全二叉樹一一若設(shè)二叉樹的高度為h,除第h層外,其它各層（1h-l）的結(jié)點數(shù)都達到最大個數(shù)，第h層所有的節(jié)點都連續(xù)集中在 最左邊，這就是完全二叉樹。 （2）滿二叉樹一一除了葉結(jié)點外，每一個結(jié)點都有 左右子葉且葉結(jié)點都處在最底層的二叉樹。遍歷是對樹的一種最基木的運算，所謂 遍歷二叉樹，就是按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點，使每一個結(jié)點都被 訪問一次，而且只被訪問一次。由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實質(zhì)上 是將二叉樹的各個結(jié)點轉(zhuǎn)換成為一個線性序列來表示。設(shè)l、d、r分別表示遍歷左 子樹、訪問根結(jié)點和遍歷右子樹，則對一棵二叉樹

6、的遍歷有三種情況:dlr （稱為 先根次序遍歷），ldr （稱為中根次序遍歷），lrd （稱為后根次序遍歷）。前序遍歷（先根遍歷）：訪問根；按先序遍歷左子樹；按先序遍歷右子樹。如 右圖，則其前序遍歷為：abdegcf中序遍歷（中根遍歷）：按中序遍歷左子樹；訪問根；按中序遍歷右子樹。如 右圖，則其中序遍歷為：dbegafc后序遍歷（后根遍歷）：按后序遍歷左子樹；按后序遍歷右子樹；訪問根。如 右圖，則其后序遍歷為：dgebfca層次遍歷：即按照層次訪問，通常用隊列來做。訪問根，訪問子女，再訪問子 女的子女（越往后的層次越低）（兩個子女的級別相同）。練習(xí)題：二叉樹t,已知其前序遍歷序列為1 2 4

7、3 5 7 6,中序遍歷序列為4 21573 6,則其后序遍歷序列為（）。a. 4 2 5 7 6 3 1 b. 4 2 7 5 6 3 1 c. 4 2 7 5 3 6 1 d. 4 7 2 3 5 6 1 e.4 5 2 6 3 7 1遍歷的應(yīng)用：如果我們將一個正常的數(shù)學(xué)表達式用一個二叉樹來表示的話，其屮分支結(jié)點表 示運算符，葉結(jié)點表示操作數(shù)，運算符前后的操作數(shù)分別用左右結(jié)點來表示?？梢? 越深的分支結(jié)點處的運算符的優(yōu)先級越高。例如，數(shù)學(xué)表達式a+（b-c）*d的二叉樹 表示如右圖。前綴表達式：不含括號的算術(shù)表達式，而且它是將運算符寫在前面，操作數(shù)寫 在后面的表達式，也稱為“波蘭式”。在二

8、叉樹表示的表達式中，我們可以用前序 遍歷將其前綴表達式描述出來。如右圖，其前序遍歷為：+a*-bcd,此即為其前綴 表達式。表達式求值：對于一個前綴表達式的求值而言，首先要從右至左掃描表達式， 從右邊第一個字符開始判斷，如果當(dāng)前字符是數(shù)字則一直到數(shù)字串的末尾再記錄下 來，如果是運算符，貝9將右邊離得最近的兩個“數(shù)字串”作相應(yīng)的運算，以此作為 一個新的“數(shù)字串”并記錄下來。一直掃描到表達式的最左端時，最后運算的值也 就是表達式的值。中綴表達式：即正常的數(shù)學(xué)表達式，同樣可以用二叉樹的中序遍歷描述出來， 因為要表達優(yōu)先級，所以要用到括號。后綴表達式：不包含括號，運算符放在兩個運算對彖的后面，所有的計

9、算按運 算符出現(xiàn)的順序，嚴(yán)格從左向右進行。同樣，如果一個表達式建立了其二叉樹模型,則可以利用后序遍歷來得到其后綴表達式。如上圖表達式a+(b-c)*d的后綴表達式 就應(yīng)該為abc-d*+。表達式求值：建立一個棧s 從左到右讀后綴表達式，讀到數(shù)字就將它轉(zhuǎn)換為 數(shù)值壓入棧s中，讀到運算符則從棧中依次彈出兩個數(shù)分別到y(tǒng)和x,然后以“x運 算符y”的形式計算機出結(jié)果，再壓加棧s中如果后綴表達式未讀完，就重復(fù) 上面過程，最后輸出棧頂?shù)臄?shù)值則為結(jié)束。練習(xí)題：表達式a*(b+c)-d的后綴表達式是：a) abcd*+-b) abc+*d- c) abc*+d-d) -+*abcd5. 1. 1數(shù)組數(shù)組是n

10、(n>l)個相同類型數(shù)據(jù)元素ao、al.、an1構(gòu)成的有限序列，且 該有限序列存儲在一塊地址連續(xù)的內(nèi)存單元中。幾乎所有的高級程序設(shè)計語言都支 持?jǐn)?shù)組數(shù)據(jù)類型。數(shù)組這種數(shù)據(jù)結(jié)構(gòu)把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元屮， 如要保存一個學(xué)生所學(xué)五門課程的成績，可以定義一個一維數(shù)組a5,則該數(shù)組一 共有a0、al、a、a3和a4五個元素(對于任一元素,用ai表示,i稱 為下標(biāo)值)，分別保存該學(xué)生五門課程的成績。設(shè)第一個元素a0在內(nèi)存的存儲起 始地址為2000,每個數(shù)組元素在內(nèi)存中占4個存儲單元，該數(shù)組在內(nèi)存的存儲實現(xiàn) 如圖5. 1所示。由此可見,一個一維數(shù)組，一旦第一個元素a0的存儲地

11、址loc(ao) 確定，每個數(shù)據(jù)元素在內(nèi)存所占用的存儲單元個數(shù)k也確定，則任一數(shù)據(jù)元素ai 的存儲地址loc(ai)可由以下公式求出：loc (ai)=loc (ao)+ixk (0wi<n)圖5.1 維數(shù)組a5的存儲示意圖在一維數(shù)組的基礎(chǔ)上，我們可以引入多維數(shù)組。如要保存3個學(xué)生每人考4 門功課的成績，可以定義一個二維數(shù)組b3 4,則該數(shù)組有b0 0.b0l、 b0、b0h3、bl0、bll、bl2、bl3、b 0、b2l、 b 、b23共12個元素，其中b0 0保存第1個學(xué)生所學(xué)第1門課程的成 績，b0 1保存第1個學(xué)生所學(xué)第2門課程的成績b2 3保存第3個學(xué)生所 學(xué)第4門課程的成績

12、。由于計算機的存儲結(jié)構(gòu)是線性的，用線性的存儲結(jié)構(gòu)存放二 維數(shù)組元素則存在行/列次序排放問題。對二維數(shù)組b3 4,如果按圖5. 2所示的 方式存儲，稱為以行序為主序的存儲方式，即先存儲第0行，再存儲第1行每 行中的元素是按列下標(biāo)由小到大的次序存放；如果按圖5. 3所示的方式存儲，稱為 以列序為主序的存儲方式，即先存儲第0列，再存儲第1列每列中的元素是按行下標(biāo)由小到大的次序存放。大多數(shù)程序設(shè)計 語言如c、pascal. basic等采用的都是以行序為主序的存儲方式，少數(shù)程序設(shè)計 語言如fortran中采用的是以列序為主序的存儲方式。圖5. 2以行序為主序存儲的二維數(shù)組圖5. 3以列序為主序存儲的二

13、維數(shù)組對于一個以行序為主序方式存儲的二維數(shù)組am n(該數(shù)組有m行，每行有n 列)，若第一個元素a0 0的存儲地址l0c(a0 0)確定，每個數(shù)據(jù)元素在內(nèi)存 所占用的存儲單元個數(shù)k也確定。由于在內(nèi)存中，數(shù)組元素aij前面已存放了 i行(第0行至第i-1行)，即已存放了 ixn個元素，占用了 ixnxk個內(nèi)存單元； 第i行中元素前又已存放了 j列，即已存放了 j個數(shù)據(jù)元素(元素ai 0 至元素aij-l),占用了 jxk個內(nèi)存單元。該數(shù)組是從地址l0c(a0 0)開始 存放的，因此數(shù)組元素的存儲地址l0c(aij)可由以下公式求出：loc(aij) =l0c(a0 0)+ixnxk+jxk而在以

14、列序為主序方式存儲的二維數(shù)組am n中的任一數(shù)組元素aij的 存儲地址l0c(aij)可由以下公式求出：loc(aij)=l0c(a0 0) + jxmxk+ixk由上面分析我們知道，數(shù)組中的每個數(shù)據(jù)元素都和一組惟一的下標(biāo)值對應(yīng)，而 數(shù)組中任一數(shù)據(jù)元素的存儲地址可通過下標(biāo)值直接計算得到，因此，數(shù)組是一種隨 機存儲結(jié)構(gòu)，可通過給定下標(biāo)值隨機存取數(shù)組屮的任意數(shù)據(jù)元素，這就給程序設(shè)計 帶來很大方便。但是，用數(shù)組存放數(shù)據(jù)時，必須事先定義i古i定的長度(即數(shù)組元素的個數(shù))。比 如，耍保存一個班級的學(xué)生某一門課程的成績，可以采用一維數(shù)組，但有的班級有 可能有100人，而有的班可能只有30人，如果要用同一個

15、數(shù)組先后存放不同班級 的學(xué)牛成績，則必須定義長度為100的數(shù)組。如果事先難以確定一個班的最多人數(shù), 則必須把數(shù)組定得足夠大，以便能存放任何班級的學(xué)牛數(shù)據(jù)。顯然這將會浪費內(nèi)存。 因此，在有些情況下，要根據(jù)需要開辟內(nèi)存單元來保存數(shù)據(jù)，鏈表就是-種可以動 態(tài)地進行存儲分配的數(shù)據(jù)結(jié)構(gòu)備戰(zhàn)noip初賽問題求解z排列組合求解策略在noip中問題求解中，經(jīng)常會遇到問題求解問題。解答排列組合問題，首先必須認(rèn)真審題，明確是屈于排列問題述是組合問題， 或者屬于排列與組合的混合問題，其次要抓住問題的本質(zhì)特征，靈活運用基本原理 和公式進行分析解答。同時還要注意講究一些策略和方法技巧，使一些看似復(fù)雜的 問題迎刃而解。下

16、面介紹幾種常用的解題方法。一、合理分類與準(zhǔn)確分步法解含有約束條件的排列組合問題，應(yīng)按元素性質(zhì)進行分類，按事情發(fā)生的連續(xù) 過程分步，作到分類標(biāo)準(zhǔn)明確，分步層次清楚，不重不漏。例1、五個人排成一排，其中甲不在排頭，乙不在排尾，不同的排法有()a. 120 種 b. 96 種 c. 78 種 d. 72 種分析：由題意可先安排甲，并按其分類討論：1)若甲在末尾，剩下四人可自由 排，有種排法；2)若甲在第二，三，四位上，則有種排法，由分類計數(shù)原理， 排法共有種，選c。二、正難反易轉(zhuǎn)化法對于一些生疏問題或直接求解較為復(fù)雜或較為困難問題，從正面入手情況較多, 不易解決，這時可從反面入手，將其轉(zhuǎn)化為一個簡單

17、問題來處理。例2、馬路上有8只路燈，為節(jié)約用電又不影響正常的照明，可把其中的三只 燈關(guān)掉，但不能同時關(guān)掉相鄰的兩只或三只，也不能關(guān)掉兩端的燈，那么滿足條件 的關(guān)燈方法共有多少種？分析：關(guān)掉第1只燈的方法有6種，關(guān)第二只，第三只時需分類討論，十分復(fù) 雜。若從反面入手考慮，每一-種關(guān)燈的方法對應(yīng)著一種滿足題設(shè)條件的亮燈與關(guān)燈 的排列，于是問題轉(zhuǎn)化為“在5只亮燈的6個空中插入3只暗燈”的問題。故關(guān)燈 方法種數(shù)為。三、混合問題“先選后排”對于排列組合混合問題，可先選出元素，再排列。例3、4個不同小球放入編號為1, 2, 3, 4的四個盒中，恰有一空盒的方法 有多少種？分析：因有一空盒，故必有一盒子放兩

18、球。1）選：從四個球中選2個有 種， 從4個盒中選3個盒有種；2）排：把選出的2個球看作一個元素與其余2球共3 個元素，對選出的3盒作全排列有種，故所求放法有種。四、特殊元素“優(yōu)先安排法”對于帶有特殊元素的排列組合問題，一般應(yīng)先考慮特殊元素，再考慮其它元素。 例4、用0, 2, 3, 4, 5,五個數(shù)字，組成沒有重復(fù)數(shù)字的三位數(shù)，其中偶數(shù) 共有（）。a. 24 個 bo 30 個 co 40 個 d。60 個分析由于該三位數(shù)為偶數(shù)，故末尾數(shù)字必為偶數(shù)，乂因為0不能排首位，故 0就是其中的“特殊”元素，應(yīng)該優(yōu)先安排，按0排在末尾和0不排在末尾分兩類: 1） 0排末尾吋，有 個，2） 0不排在末尾

19、吋，則有 個，由分?jǐn)?shù)計數(shù)原理，共有偶 數(shù)二30個，選b。五、總體淘汰法對于含有否定字眼的問題，可以從總體中把不符合要求的除去，此時需注意不 能多減，也不能少減。例如在例4中，也可用此法解答：五個數(shù)字組成三為數(shù)的全排列有個，排好后 發(fā)現(xiàn)0不能排首位，而且數(shù)字3, 5也不能排末位，這兩種排法要除去，故有個偶 數(shù)。六、局部問題“整體優(yōu)先法”對于局部排列問題，可先將局部看作一個元與其余元素一同排列，然后在進行 局部排列。例5、7人站成一排照相，要求甲乙兩人之間恰好隔三人的站法有多少種？ 分析：甲、乙及間隔的3人組成一個“小整體”，這3人可從其余5人中選， 有種；這個“小整體”與其余2人共3個元素全排列

20、有種方法，它的內(nèi)部甲、乙 兩人有種站法，中間選的3人也有種排法，故符合要求的站法共有種。七、相鄰問題一 “元”法對于某幾個元素要求相鄰的排列問題，可將相鄰的元素看作一個“元”與其他 元素排列，然后在對“元”內(nèi)部元素排列。例6、7人站成一排照相，甲、乙、丙三人相鄰，有多少種不同排法？分析：把甲、乙、丙三人看作一個“元”，與其余4人共5個元作全排列，有種 排法，而甲乙、丙、之間又有種排法，故共有種排法。八、不相鄰問題“插空法”對于某兒個元素不相鄰的排列問題，可先將其他元素排好，再將不相鄰元素在 己排好的元素之間及兩端空隙中插入即可。例7、在例6中，若要求甲、乙、丙不相鄰，則有多少種不同的排法？分析

21、：先將其余四人排好有種排法，再在這人之間及兩端的5個“空”中選三 個位置讓甲乙丙插入，則有種方法，這樣共有種不同排法。九、順序固定問題用“除法”對于某幾個元素順序一定的排列問題，可先把這幾個元素與其他元素一同排列, 然后用總排列數(shù)除以這幾個元素的全排列數(shù)。例8、 6個人排隊，甲、乙、丙三人按“甲一-乙-一丙”順序排的排隊方法有 多少種？分析：不考慮附加條件，排隊方法有種，而其中甲、乙、丙的種排法中只有 一種符合條件。故符合條件的排法有種。十、構(gòu)造模型“隔板法”對于較復(fù)雜的排列問題，可通過設(shè)計另一情景，構(gòu)造一個隔板模型來解決問題。 例9、方程a+b+c+d二12有多少組正整數(shù)解？分析：建立隔板模

22、型：將12個完全相同的球排成一列，在它們之間形成的11 個間隙中任意插入3塊隔板，把球分成4堆，而每一種分法所得4堆球的各堆球的 數(shù)目，即為a, b, c, d的一組正整解，故原方程的正整數(shù)解的組數(shù)共有。再如方程a+b+c+d二12非負(fù)整數(shù)解的個數(shù)；三項式，四項式等展開式的項數(shù)， 經(jīng)過轉(zhuǎn)化后都可用此法解。十一、分排問題“直排法”把幾個元素排成前后若干排的排列問題，若沒有其它的特殊要求，可采取統(tǒng)一 排成一排的方法來處理。例10、7個人坐兩排座位，第一排3個人，第二排坐4個人，則不同的坐法有 多少種？分析：7個人可以在前兩排隨意就坐，再無其它條件，故兩排可看作一排來處 理，不同的坐法共有種。十二、

23、表格法有些較復(fù)雜的問題可以通過列表使其直觀化。例11、9人組成籃球隊，其屮7人善打前鋒，3人善打后衛(wèi)，現(xiàn)從中選5人（兩 衛(wèi)三鋒，且鋒分左、中、右，衛(wèi)分左右）組隊岀場，有多少種不同的組隊方法？分析：由題設(shè)知，其中有1人既可打鋒，又可打衛(wèi)，則只會鋒的有6人，只會 衛(wèi)的有2人。列表如下：人數(shù)6人只會鋒2人只會衛(wèi)1人即鋒乂衛(wèi)結(jié)果不同 選法32311 （衛(wèi)）221 （鋒）由表知，共有種方法。除了上述方法外，有時還可以通過設(shè)未知數(shù)，借助方程來解答，簡單一些的問 題可釆用列舉法，還可以利用對稱性或整體思想來解題等等。排列組合是高中數(shù)學(xué) 的重點和難點之一，也是進一步學(xué)習(xí)概率的基礎(chǔ)。事實上，許多概率問題也可歸結(jié)

24、 為排列組合問題。這一類問題不僅內(nèi)容抽象，解法靈活，而且解題過程極易出現(xiàn)“重 復(fù)”和“遺漏”的錯誤，這些錯誤其至不容易檢查岀來，所以解題吋要注意不斷積 累經(jīng)驗，總結(jié)解題規(guī)律，掌握若干技巧。noip初賽閱讀程序解題方法解題步驟做閱讀程序題，首先要想方設(shè)法弄清楚程序的功能，每個題目總有一點“寫作 目的”。抓住了它，不僅答案變得容易了，而且對自己的結(jié)果也比較有信心。1、從總體上通讀程序，大致把握程序的目的和算法。2、猜測變量的作用，跟蹤主要變量值的變化(列表)，找出規(guī)律。3、將程序分段，理清每一小段程序的作用和目的。4、看清輸入，按照輸出格式，寫出結(jié)果。5、帶著到的結(jié)果凹到程序進行檢查。幾大方法a.

25、 直接模擬b. 先模擬幾次循環(huán)后找規(guī)律c. 直接看程序了解算法功能d. 了解程序本質(zhì)后換一個方法解決0.有時不知道算法可以通過觀察猜出來一、基礎(chǔ)題送分題，主要考查選手的程序設(shè)計基礎(chǔ)知識和計算能力。細(xì)心program ex301;varu:array0. 3 of integer;i, a, b, x, y: integer;begin y:=10;for i:=0 to 3 do read(ui);a: = (u0+ul+u2+u3) div 7;b:=u0 div (ul-u2) div u3);x: = (u0+a+2) u (u3+3) mod 4;if (x>10) theny:

26、二y+(b*100-u3) div (uu0 mod 3*5)el sey:=y+20+(b*100-u3) div (uu0 mod 3*5);writeln (x,',',y);end. *注：本例中，給定的輸入數(shù)據(jù)可以避免分母為0或下標(biāo)越界。 輸入：9 3 9 4輸出:注意事項1、負(fù)數(shù)整除、求模表達式(4 mod (-3)與(-4 mod 3)的值為()a.-1,-1 b. 1,-1c.-l, 1 d. 1, 1(-14) mod (-3)二()模運算的規(guī)律：結(jié)果與被除數(shù)的符號相同。即被除數(shù)為正，模為正，否則 為負(fù)。結(jié)果與除數(shù)的符號沒有關(guān)系函數(shù)一：算術(shù)函數(shù)logexpas

27、cal中無幕運算,要求xy可以用后面的公式:xy=eylnx=exp(yin(x) (x>0) e2. 71828平方函數(shù)一sqr、正平方根函數(shù)一sqrt： sqr是英文單詞square (平方)的縮寫; sqrt是英文單詞square root (平方根)的縮寫函數(shù)二：類型轉(zhuǎn)換函數(shù)取整數(shù)函數(shù)一trunc：如trunc(7. 8)的值為7, trunc(-6. 1)的值為-6 四舍五入函數(shù)一round：如round(7. 8)的值為8, round(-6. 1)的值為-6 序號函數(shù)一ord：返回參數(shù)的對應(yīng)的序號；若參數(shù)為字符，則返回其ascii碼('0'的 ascii 碼

28、為 48, ' a'的 ascii 碼為 65, ' a'的 ascii 碼為 97)值，如 0rd( )的值為 66；若參數(shù)為 boolean,則 ord (true)的值為 1 , ord (false)的 值為0字符函數(shù)一chc返回序號所對應(yīng)的字符，與ord互為反函數(shù)；如chr(66)的值 為'b'函數(shù)三：順序函數(shù)與判斷函數(shù)前趨函數(shù)一pred：返回參數(shù)的前一個數(shù)據(jù)，若參數(shù)為第一項，則函數(shù)無意義 (predecessor )后繼函數(shù)一succ：返回參數(shù)的后一個數(shù)據(jù)，若參數(shù)為最后一項，則函數(shù)無意義 (successor )奇偶判斷函數(shù)一odd：

29、判斷參數(shù)的奇偶性，當(dāng)參數(shù)為偶數(shù)時，函數(shù)值為false；當(dāng)參數(shù)為奇數(shù)時，函數(shù)值為true 函數(shù)四：字符串函數(shù)函數(shù)名功能說明concal(stl,.,stn)將n個字符串連接起來等效于 st1+.+st2copy (s, m, n)取s中第m個字符開始 的n個字符若m大于s的長度，則返回空串； 否則，若m+n大于s的長度,則 截斷l(xiāng)ength (s)求s的動態(tài)的長度返回值為整數(shù)pos (sub,s)在s中找子串sub返回值為sub在s中的位置，為 byte 型upcase (ch)將字母cii轉(zhuǎn)換成大寫字 母若ch不為小寫字母，則不轉(zhuǎn)換字符串過程過程名功能說明insert (sour, s, m)

30、在s的第m個字符位置處插入子 串 sour若返回吊超過255,則截斷delete (s,m, n)刪除s中第m個字符開始的n個 字符串若m大于s的長度，則不刪 除；否則，若m+n大于s的 長度，則刪除到結(jié)尾str(x:w:d,s)將整數(shù)或?qū)崝?shù)x轉(zhuǎn)換成字符串sw和d是整型表達式，意義同 帶字寬的write語句val (s, x, code)將字符串s轉(zhuǎn)換成整數(shù)或?qū)崝?shù)x若s中有非法字符，則code 存放非法字符在s中的下標(biāo); 否則，code為零,code為整 型特殊運算1數(shù)字之jhi的and or not xor運算：將數(shù)字化為二進制，1為true, 0為false, 逐位運算，結(jié)果再化為10進制

31、。2、移位運算：shl shrx shl y=x * 2yx shr y=x div 2 y3、地址運算：4、邏輯運算：設(shè)a=b=true, od二false, 下邏輯運算表達式值為假的有()。a. (-aab) v(cadva)b. -(aab) vc) ad)c. aa(bvcvd) vdd. (aa(dvc) ab看程序?qū)懡Y(jié)果(n01p2007)program j302;vara, b:integer;varx, y:"integer;procedure fun(a, b:i nteger);vark:integer;begin k:=a; a:=b; b:=k; end;be

32、gina:=3; b:=6;x:=a; y:=b; fun(x y j ; writeln (a/ / , b);end.集合運算設(shè)全集 i=a, b, c, d, e, f, g, h,集合 a = a, b, c, d, e, f, b=c, d, e, c=a,d,那么集合 aqbq c% ()。(n01p2005 普及)a. c, e b. d, e c. e d. c, d, e e. d, f為補集符號notp2004普及組75名兒童到游樂場去玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船。已 知其屮20人這三種東西都玩過，55人至少玩過其屮的兩種。若每樣乘坐一次的費 用是5元，游

33、樂場總共收入700,可知有 名兒童沒有玩過其中任何一種。10二、動態(tài)模擬找不出其中的規(guī)律，也看不出明顯的算法，便可以嘗試進行動態(tài)模擬。動態(tài)模 擬是采用人工模仿機器執(zhí)行程序的方法計算結(jié)果。首先選擇比較重要的變量作為工 作現(xiàn)場。人工執(zhí)行程序時，只要按照時間先后一步步記錄現(xiàn)場的變化，就能最后得 出程序的運算結(jié)果。1、畫表，畫出程序執(zhí)行時要用的現(xiàn)場情況表。2、基本讀懂各語句的功能。3、動態(tài)執(zhí)行程序program tl；var n, k, s： longint；beginreadln(n);k:二 0；s:二 1；while s <= n do begi nk:=k+l;n:=n-s;s:二s+6

34、*kend;writein (k)end.輸入：100輸出:解題列表跟蹤變量的變化：var p, q, s, t： integer；beginreadln (p)；for q:二p+1 to 2*p dobegint:=0； s:二(p*q)mod (q-p)；if s=0 thenbegint:=p+q+(p*q)div(q-p)； write (t： 4)；end；end；end.var a, d:array 1.100 of integer;n, i, j, k, x, s: integer; beginn:=5;al :=1 ;dl :=1;for i:=1 to n dobegins

35、:二i+1;x:=0;for j:=1 to n+l-i dobegink:=s+x;x:=x+l;aj+l:=aj+k; write(aj,'');end;writcln( "'); di+l:=di+l; al:=di+l;end;end.三、找規(guī)律(n0ip2001提高組第四題)4. program ga07_4；var x, yl, y2, y3： integer；beginreadln(x)；yl：二0； y2： =1； y3： =1；while y2<=x dobeginyl：二yl+1； y3：二y3+2； y2：二y2+y3end；wri

36、teln(yl)；end.輸入：23420 輸岀： 本題求y2超過x時yl的值 核心語句：y1： =¥1+1； y3： =¥3+2； y2：二y2+y3 例二(全國青少年信息學(xué)奧林匹克聯(lián)賽模擬訓(xùn)練試卷精選) var n, k, s:longint;begi nn:=1000000000;k:=0;s: = l;while s<=n dobegink:=k+l;n:=n-s;s:二s+6*k;end;writcln (k);end.輸出：1000四、算法題考查選手對一些常用的算法的熟練掌握情況，關(guān)于素數(shù)的判定、排序、高精度、 進制轉(zhuǎn)換、幾何等算法題比較多。ogram g

37、xp2;var i , j , s , spl : integer ;p : boolean ;a : array1. 10 of integer ;beginspl:=l; al:=2; j:=2;while spl<10 dobeginj:二j+l; p:二true;for i:-2 to jl doif (j mod i=0) then p:=false;if p then beginspl:=spl+l; aspl:=j;end;end;j:二2; p:二true;while p dobegins: = l;for i:二 1 to j do s:二s*ai;s:二s+1;for

38、 i:=2 to s-1 doif s mod i=0 then p:=false;j:二j+l;end;wri teln (s); wri teln;end.輸出：30031分析前半段求10個素數(shù)依次存丁數(shù)組a中2 3 5 7 11 13 17 19 23 29后半段求最小的j,使得前j個素數(shù)之積+1為合數(shù)j=22*3+1二7j二32*3*5+1二31j=42*3*5*7+1二211j=52*3*5*7*11+1=2311j=62*3*5*7*11*13+1二30031小技巧：s為integer類型，預(yù)示著結(jié)果不會超過32767program ex2;var i,j,n:longint;b:

39、 array 0. . 31 of 0. . 1;beginn二1999;i :=0;while n<>0 dobeginbi:=n mod 2;i:二i+1;n:=n div 2end;for j:二it downto 0 do write(bj);end.很明顯，是把十進制整數(shù)轉(zhuǎn)換成二進制數(shù)，所以輸出11111001111五、子程序n01p1998 提高 2const n=10;var s,i:integer;function co(i1:integer):integer;var ji,si:integer;beginsi:=n;for j1:=(n-1) downto (n-

40、ll+1) do si:二s1*j1 div (n-jl+1);co:=s1;end;begins:=n+1;for t:二2 to n do s:=s+co(t); writeln(，s，s);end.分析主程序是累加算法：s二 10+1+c0(l)+c0(2) +c0(3) + +c0仃0)函數(shù)co的作用：程序是累乘算法，找一個具體值作為參數(shù)代入計算，例如執(zhí)行co(6),co(6)二10*(9*8*7*6*5) /2/3/4/5/6=(10*9*8*7*6*5)/(2*3*4*5*6)二10!/ (10-6 )!*6!)二可見c0(i)的作用是求組合數(shù)代入，復(fù)習(xí)：排列組合公式 n01p20

41、01 提高 1program gao7_1：function acktm, n： integer): integer；beginif m=0 then ack：二n+lelse if n二0 then ack:=ack(m-1, 1)else ack:=ack(m-1, ack (m, n-l)end；beginwr1teln(ack(3, 4)； readln；end.輸出信息學(xué)初賽專題訓(xùn)練一一看程序?qū)懡Y(jié)果(1)program examl;type arr=array1 .100 of integer;var a:arr;a,n,m,ij,k,tot:integer;beginread(n,

42、m,k);s:=0;for i:=1 to n do s:=s+1;for i:=1 to n do ai:=s;i:=0;j:=0;tot:=0;repeati:=i+1;if i=n+1 then i:=1;if ai=s then j:=j+1;iff j=m then begin ai:=-100;tot:=tot+1 ;j:=0;write(i/，);end; until tot=k;end輸入數(shù)據(jù)：100 36 6輸出結(jié)果：program exam2;const maxn=100;type arr=arrayo.maxn off longint;varans:array1 .max

43、n of arr;n:integer; i,j:integer;procedure main;beginfillchar(ans,sizeof(ans),0);for i:=1 to n do ans1,i:=1;for i:=2 to n dobeginfor j:=1 to i-1 do ansi,j:=ansi-jj+ansi,j-1;for j:=i to n do ansi,j:=ansi,i-1+1;end;end;beginreadln(n);main;write(ansn,n);end輸入n=7時輸出結(jié)果：program exam3;var a:array1.9,1.9 of

44、string; st,x:string; i,j,n,m:integer; beginrepeatwriteln(cplease input a string(length<10):,);readln(st); n:=length(st);until (n<10) and odd(n);m:=trunc(n+1 )/2);for i:=1 to n dofor j:=1 to n do aij:=9 £for i:=1 to m dofor j;=i to n+1-i dobegin x:=copy(st,j,1);aij:=x;an+1-i,n+1-j:=x; end;

45、for j:=n downto 1 dobegin for i:=1 to n do write(ai,j:2); writein; end;end輸入數(shù)據(jù)：please input a string(length<10): rutyfpe輸出結(jié)果：program exam4;var a:array1.10 off integer; s,n,m:longint; flag:set of byte;procedure try(dep:integer);var i:integer;beginfor i:=1 to n doif not(i in flag) thenbeginflag:=fl

46、ag+i；adep:=i;if dep=m then inc(s) else try(dep+1);flag:=flag-i;end;end;beginwriteln(cplease input m and nf);readlri(m,n);flag:= ; s:=0;try ;writeln(s);end.輸入數(shù)據(jù)：please input m arid n:4 5 輸出結(jié)果：program go8_1;var n,i,min,k,buffsword;b:array0.3000 of byte;function max(a,b:byte):byte;beginif a>b then m

47、ax:=a else max:=b;end;beginb0:=0;b1 :=0;b2:=1 write(n=f);readln(n);for i:=3 to n dobeginmin:=999;for k:=1 to i div 2 dobegin buf:=max(b i-2*k,bk); if min>buf then min:=buf;end;bi:=1+min;end;writeln(cb(sn/)=bn);end輸入：n=32 輸出：b(32)=?program go8_2;const n=10;var a:array0.n-1 of integer;p,q:integer;b

48、eginp:=1;ap:=1 writein; q:=2; aq:=1;while(p<>(q+1 )mod n) dobeginif(ap=1) and (a(p+1) mod n=1) thenbeginq:=(q+1) mod n; aq:=1; q:=(q+1) mod n; aq:=1; writeln(ap:4);p:=(p+1) mod n;end;q:=(q+1) mod n; aq:=ap+a(p+1) mod n; if(p<>q) then write(ap:4); p:=(p+1) mod n; end;endprogram go8_3;var

49、nzinteger;function count(n:integer):integer;beginif n=1 then count:=0else if n mod 2=0 then count:=count(n div 2) +1 else count:=count(n*3+1 )+1;end;beginreadln(n);writeln(count(n);end輸入：99 輸出：program go8_4;var hi,lo:integer;procedure pl(m,n:integer;var hi,lo:integer); var i:integer;begini:=n;hi:=0;

50、lo:=0;repeati:=i-1; lo:=lo+m;if lo>=10000 then begin lo:=lo-10000; hi:=hi+1；end;until i=0;write(hi:4/,lo:4);end;beginpl(4567,5678,li,lo);end輸出：program t1;var a,b,c:integer;function d(b:integer):integer;var t:integer;beginif b=0 then d:=1else begint:=d(b div 2); mod c;if odd(b) then d:=t*a mod c e

51、lse d:=t; end;end;beginreadln(a,b,c); writeln(d(b);end輸入：99329410 輸出：program t2;var a,b,n:longint;beginreadln(n);a:=0;b:=0;repeat a:=a+1;b:=b+a;until b>=n; writeln(a);end輸入：415377 輸出：program t3;var szstring;a:array1.300 of byte;k,i,l:integer;beginreadln(s);a1:=0;k:=0;l:=length(s);for i:=2 to i do

52、 begin while(k>0) and (sk+1<>si) do k:=ak;if sk+1=si then inc(k); ai:=k;end;for i:=1 to i doif ai>0 then write(i:3); writein;end輸入：cdcabecaddcdcabddbda 輸出：program t4;var i,k,n:integer;x,w:array1 .500 of integer;begin readln(n); for i:=1 to n do begin xi:=0;wi:=1; end; for i:=2 to trunc(s

53、qrt(n)+1 doif xi=0 thenbegin k:=i*i;while k<=n do beginxk:=i;k:=k+i； end;end;for i:=n downto 1 doif xi<>0 thenbegin wxi:=wxi+wi; wi div xi:=wi div xi+wi; wi:=0;end; writeln(w2,w3:5,w5:5);end輸入：20輸出：輸入：294輸出：信息學(xué)初賽專題訓(xùn)練看程序?qū)懡Y(jié)果(2 )program no4; var m,n,i9p9k:integer;r:array1.200 of integer; b:boo

54、lean;beginm:=6;n:=2;for i:=1 to m-1 do ri:=i+1;rm:=1 ;i:=0;p:=1 ;b:=true;while b dobegini:=i+1 ;k:=p;p:=rp;if k=p then begin writeln(p);b:=false end else if i=n+1 thenbegin write(p/ c)h：-o;p:=rp;rk:=p; end endend結(jié)果：program myt1;var a,b:integer;procedure p1 (x:integer;var y:integer); beginx:=x+y;y:=x+y;end;begina:=5;b:=8;p1 (a,b);writeln(a:3,b:3);p1 (b-a,b);writeln(a:3,b:3);readlnend輸出：program myt2;va