信息學競賽輔導交流會

1、信息學競賽輔導交流會新昌縣城關中學新昌縣人民政府信息網(wǎng)絡管理中心梁一鋒梁一鋒2010-06-21何林同學給吳文虎教授的一封信何林同學給吳文虎教授的一封信摘錄摘錄 如果有人問我，這五年的信息學生涯教會了我什么，我不會說“我會用平衡二叉樹”、也不會說“我學懂了動態(tài)規(guī)劃”。我不管學到多少，總還有很多沒學到；即便是學會了的東西，長時間不用也會遺忘。我認為我真正學到的是習慣、態(tài)度和方法。我學會了批判性的看問題、我學會了用開闊的胸懷去接受所有不同的想法、我學會了分析問題、總結問題、乃至提出問題的一系列方法和經(jīng)驗。這些才是無價之寶，是一輩子在任何地方任何時候都不會丟的寶貝。 全國青少年信息學奧林匹克聯(lián)賽(N

2、ational Olympiad in Informatics in Provinces簡稱NOIP)自1995年至今已舉辦15次。每年由中國計算機學會統(tǒng)一組織。 NOIP在同一時間、不同地點以各省市為單位由特派員組織。全國統(tǒng)一大綱、統(tǒng)一試卷。初、高中或其他中等專業(yè)學校的學生可報名參加聯(lián)賽。聯(lián)賽分初賽和復賽兩個階段。初賽考察通用和實用的計算機科學知識，以筆試為主。復賽為程序設計，須在計算機上調(diào)試完成。參加初賽者須達到一定分數(shù)線后才有資格參加復賽。聯(lián)賽分普及組和提高組兩個組別，難度不同，分別面向初中和高中階段的學生。獲得提高組復賽一等獎的選手即可免試由大學直接錄取。NOIP簡介競賽形式和成績評定

3、競賽形式和成績評定聯(lián)賽分兩個年齡組：初中組和高中組。每組競賽分兩輪：初試和復試。 初試形式為筆試，側重考察學生的計算機基礎知識和編程的基本能力，并對知識面的廣度進行測試。程序設計的描述語言采用Basic（2005年被取消）、C/C+或Pascal。各省市初試成績在本賽區(qū)前百分之十五的學生進入復賽，其分數(shù)不計入復賽的成績。初賽時間為10月的最后第二個星期六下午 2:30 - 16:30舉行。 復試形式為上機，側重考察學生對問題的分析理解能力，數(shù)學抽象能力，駕馭編程語言的能力和編程技巧、想象力和創(chuàng)造性等。程序設計語言可采用Basic（2005年后被取消）、Pascal、C或C+。各省市競賽的等第獎

4、在復試的優(yōu)勝者中產(chǎn)生。時間為 3小時。只進行一試，約在當年的11 月的第三個周六進行。 試題形式試題形式 每次聯(lián)賽的試題分四組：初中組初試賽題；初中組復試賽題；高中組初試賽題；高中組復試賽題。其中，初中組初試賽題和高中組初試賽題類型相同，初中組復試賽題和高中組復試賽題類型相同，但初中組和高中組的題目不完全相同，高中組難度略高；以體現(xiàn)年齡特點和層次要求。 初試：初試全部為筆試，滿分100分。試題由四部分組成：1、選擇題：共20題，每題15分，共30分。每題有4個備選方案。試題內(nèi)容包括計算機基本組成與原理、計算機基本操作、信息科技與人類社會發(fā)展的關系等等。2、問題求解題：共2題，每題5分，共10分

5、。試題給出一個敘述較為簡單的問題，要求學生對問題進行分析，找到一個合適的算法，并推算出問題的解。答案以字符串方式給出，考生給出的答案與標準答案的字符串相同，則得分；否則不得分。3、程序閱讀理解題：共4題，每題8分，共32分。題目給出一段程序（沒有關于程序功能的說明），有時也會給出程序的輸入，要求考生通過閱讀理解該段程序給出程序的輸出。輸出以字符串的形式給出，如果與標準答案一致，則得分；否則不得分。4、程序完善題：共 2題，第一題10分，共4空，每空2.5分；第二題18分，共6空，每空3分。兩題共28分。題目給出一段關于程序功能的文字說明，然后給出一段程序代碼，在代碼中略去了若干個語句并在這些位

6、置給出空格，要求考生根據(jù)程序的功能說明和代碼的上下文，填出被略去的語句。填對的，則得分；否則不得分。（2009年普及組試題為第一題5空，每空3分，第二題前三空每空3分，后兩空每空2分） 競賽形式和成績評定競賽形式和成績評定*復試：復試的題型和形式向全國信息學奧賽（NOI）靠攏，全部為上機編程題，但難度略低。復試為決出競賽成績的最后一個環(huán)節(jié)。題目包括 4道題，每題100分，共計400分。難度有易有難，既考慮普及面，又考慮選拔的梯度要求。每一道試題包括：題目、問題描述、樣例說明（輸入、輸出及必要的說明）、數(shù)據(jù)范圍（數(shù)據(jù)限制條件）。測試時，測試程序為每道題提供了十組測試數(shù)據(jù)，考生程序每答對一組得10

7、 分；累計分即為該道題的得分。競賽形式和成績評定競賽形式和成績評定討論與交流：應該側重于初賽還是復賽？討論與交流：應該側重于初賽還是復賽？試題的知識范圍具體如下：試題的知識范圍具體如下： 初賽內(nèi)容與要求：初賽內(nèi)容與要求：復賽內(nèi)容與要求：復賽內(nèi)容與要求：A計算機的基本常識：B計算機的基本操作： C數(shù)據(jù)結構：1程序語言中基本數(shù)據(jù)類型(字符、整數(shù)、長整數(shù)、浮點) 2. 浮點運算中的精度和數(shù)值比較 3一維數(shù)組（串）與線性表 4記錄類型（PASCAL）/ 結構類型（C） C數(shù)據(jù)結構：1指針類型 2多維數(shù)組3單鏈表及循環(huán)鏈表 4二叉樹5文件操作（從文本文件中讀入數(shù)據(jù)，并輸出到文本文件中） 在初賽的內(nèi)容上增

8、加以下內(nèi)容：試題的知識范圍具體如下：試題的知識范圍具體如下： 初賽內(nèi)容與要求：初賽內(nèi)容與要求：復賽內(nèi)容與要求：復賽內(nèi)容與要求：D程序設計：1結構化程序設計的基本概念 2閱讀理解程序的基本能力 3具有將簡單問題抽象成適合計算機解決的模型的基本能力4具有針對模型設計簡單算法的基本能力 5程序流程描述6程序設計語言（PASCAL/C/C+） E基本算法處理：1初等算法（計數(shù)、統(tǒng)計、數(shù)學運算等）2排序算法（冒泡法、插入排序、合并排序、快速排序） 3查找（順序查找、二分法）4回溯算法 D程序設計 1算法的實現(xiàn)能力2程序調(diào)試基本能力3設計測試數(shù)據(jù)的基本能力 4程序的時間復雜度和空間復雜度的估計E算法處理

9、1離散數(shù)學知識的應用（如排列組合、簡單圖論、數(shù)理邏輯） 2分治思想 3模擬法 4貪心法 5簡單搜索算法（深度優(yōu)先 廣度優(yōu)先）搜索中的剪枝 6動態(tài)規(guī)劃的思想及基本算法 評測環(huán)境評測環(huán)境 1、使用Windows操作系統(tǒng)平臺： （1）Windows操作系統(tǒng)必須使用Windows 2000、Windows XP及更新的Windows版本； （2）Pascal語言，必須使用Free Pascal 1.0.10及以上版本作為編譯器； （3）C語言，必須使用gcc 3.4.2作為編譯器； （4）C+語言，必須使用g+ 3.4.2作為編譯器； （5）Pascal語言，可以使用Freepascal IDE Wi

10、ndows版、Lazarus Windows版、Dev-Pascal作為集成開發(fā)環(huán)境，推薦使用Lazarus Windows版; （6）C和C+語言，可以使用Dev-C+、RHIDE Windows版作為集成開發(fā)環(huán)境，推薦使用Dev-C+； 2、使用Linux操作系統(tǒng)平臺： 討論與交流：關于語言的選擇？討論與交流：關于語言的選擇？我選用的教學順序：我選用的教學順序：0、體驗程序設計1、順序結構2、選擇結構（判斷）3、循環(huán)結構4、數(shù)組（一維）5、函數(shù)與過程6、數(shù)組（多維）7、集合與記錄、子界與枚舉（自學為主，簡單介紹）8、指針、文件操作9、基本算法歸納總結10、其他算法講解復賽輔導：以歷年復賽試

11、題的解題為主。0、體驗程序設計、體驗程序設計Pascal語言介紹1、基本符號：A-Z a-z 0-9 + - * / = = ( ) := , . : . 2、保留字AND, ARRAY, BEGIN, CASE, CONST, DIV, DO, DOWNTO , ELSE, END,FILE, FOR, FUNCTION, GOTO, IF, IN, LABEL, MOD, NIL, NOT, OF, OR, PACKED,PROCEDURE, PROGRAM, RECORD, REPEAT, SET, THEN, TO, TYPE,UNTIL , VAR, WHILE, WITH 3、標識

12、符以字母開頭的字母、數(shù)字組合。自己定義，例如：x, y, max, min, sum, a15, a3b7, 是合法的。5x, x-y, ex10.5 ,不是標識符，非法的。用途：表示各種常量、變量、類型、文件、函數(shù)、過程、或程序的名字。特殊標識符：（標準標識符）常量：false, true, maxint類型：integer, real, char, Boolean, text文件：input,output函數(shù)：abs, arctan, chr, cos, eof, eoln, exp, ln, odd, ord, pred, round, sin, sqr, sqrt, succ, tru

13、nc過程：get, new, pack, page, put, read, readln, reset, rewrite, unpack, write, writeln程序結構例1 ：已知半徑，求圓周長和面積的程序 數(shù)學公式：l=2r s=r2PROGRAM circle(input,output);CONST pi=3.1415926;VAR r, l ,s : real;BEGIN read (r); l:=2*pi*r; s:=pi*r*r; write (r, l, s)END.程序說明：1、常量定義：CONST pi:=3.1415926;定義一個常量pi， 值為3.14159262

14、、變量定義：r,l,s:real;定義了半徑r,周長l,面積s,三個變量，類型為實型數(shù)據(jù)。3、表達式： 2r 2*pi*r r2 pi*r*r b2-4ac b*b-4*a*c a+b (a+b)/2 24、輸入輸出語句：read(r) 從鍵盤輸入一個數(shù)，賦給變量rwrite(r, l, s) 把r,l,s,的值輸出到屏幕。5、標點符號的寫法：整個程序一個句號，在最后 END.每句語句后一個分號；逗號用來分隔分量等:= 是一個賦值號6、整個程序的書寫格式：保留字大寫；縮進格式。選用的習題：1、輸入三個數(shù)，計算并輸出它們的平均值及三個數(shù)的乘積。2、已知地球半徑為6371km，計算并輸出地球的表面

15、積和體積。3、已知勻加速運動的初速度為10m/s,加速度為2m/s2,求20s以后的速度，20s內(nèi)走過的路程及平均速度。4、已知物體的質量為m，求其在地球和月球受到的重力。1、順序結構、順序結構一、用計算機解題的基本方法-“自頂而下，逐步求精”上節(jié)的簡單程序已體現(xiàn)出處理問題步驟、思路的順序關系，這就是順序結構程序。解題時，對問題有一清楚了解，再仔細構造解題步驟算法。算法可以“自頂而下，逐步求精”。對大問題先構造大致輪廓，再逐步分解成小問題，直到可以用PASCAL語言描述出來。二、基本標準數(shù)據(jù)類型 （一）實型（real）1、簡介：包括正實數(shù)、負實數(shù)和實數(shù)零，其實就是常說的小數(shù)，pascal中表示

16、實型數(shù)的形式有兩種。十進制表示法：這是人們?nèi)粘Ｊ褂玫膸?shù)點的表示方法，如0.0、-0.0、+5.61、-8.0、-6.050等都是實型常量，而0.、.37都不是合法的實數(shù)形式科學記數(shù)法：采用指數(shù)形式的表示方法，如1.25105可表示成1.25E+05。在科學記數(shù)法中，字母E表示10這個底數(shù)，而E之前為一個十進制表示的小數(shù)，稱為尾數(shù)，E之后必須為一個整數(shù)，稱為指數(shù)。如-1234.56E+26、+0.268E-5 、1E5是合法形式，而.34E12、2.E5、E5、E、1.2E+0.5都不是合法形式的實數(shù)。 無論實數(shù)是用十進制表示法還是科學表示法，它們在計算機內(nèi)的表示形式是一樣的，總是用浮點方式

17、存儲。2、實型量的運算： (加) (減) (乘) (實數(shù)除)3、實型量的標準函數(shù)：abs-絕對值 sqr-平方 sqrt-開方 sin-正弦 cos-余弦 arctan反正切 exp-以e為底的指數(shù) ln-自然對數(shù) trunc-取整 round-舍入取整例：|-3| 寫為abs(-3) e2.5 寫為exp(2.5) x y 寫為exp(y*ln(x) trunc(1.7)=1（二）整型（integer）1、整型量，包括正整數(shù)、負整數(shù)和零，即-32768至+32767。 例如：25 -32 02、整型量的運算： (加) (減) (乘) DIV (整除) MOD（取余）例：8 DIV 3=2 8

18、 MOD 3=2 7 DIV 3=2 7 MOD 3=13、整型量的標準函數(shù)：abs-絕對值 sqr-平方 pred-前導 succ-后繼 odd-奇函數(shù) chr-取字符 例：pred(5)=4 odd(7)=true chr(65)=A chr(97)=a （三）字符型（char）1、在Pascal語言中，字符量是由單個字符組成，所有字符來自ASCII字符集，共有256個字符。在程序中，通常用一對單引號將單個字符括起來表示一個字符常量 ，如：a，A，0等 ；特殊地，對于單引號字符，則要表示成。對于ASCII字符集中，按每個字符在字符集中的位置，將每個字符編號為0255，編號稱為對應字符的序號

19、，因此字符也存在大小，如：Aa2、字符量的標準函數(shù) Ord-取序號（與chr為反函數(shù)） pred-前導 succ-后繼 例：ord(A)=65 ord(a)=97 pred(b)=a succ(a)=b（四）布爾型或邏輯型（boolean） 1、布爾型量僅有兩個值，真和假，分別用標準常量名true和false表示 ，它們的序號分別為1和0。2、布爾量的標準函數(shù)：Ord-取序號 pred-前導 succ-后繼 3、布爾量的布爾運算（邏輯運算）：and-與 or-或 not-非 說明：and 有并且之意, 只有當a與b都為true時，a and b 才為真，否則為假。 or 有或者之意, 當a與b

20、之一為true時，a or b就為真，否則為假。 Not為非運算，取反值：not(true)=false 4、關系運算：, , =(大于等于),(不等于)例： 3=b 值為false (12) or (32) 值為true 三、基本語句1、read / readln語句 ，強調(diào)區(qū)別。格式：read() readln()； 例：read(a,b,c);2、write / writeln 語句 ；單雙域寬輸出格式。 格式：write() writeln() 例：writeln(s=, s , v= , v :6:1);3、表達式與賦值語句 形式：:= 例：x:=sqrt(b*b-4*b*c); i

21、:=i+1;四、例題： 1、已知ABC中的二邊長a,b及夾角alfa，求第三邊c和ABC的面積。 2、輸入二個數(shù)x , y，交換x與y的值。 3、輸入一個字符，輸出字符的序號、前導、后繼。 4、輸入x, y ,判斷點(x,y)是否在圓環(huán)內(nèi)。若在環(huán)內(nèi)，輸出true；否則輸出false。 (若1=x2+y2=4，則在環(huán)內(nèi))習題：1、已知ABC中的三邊長分別為a,b,c，求ABC的面積。s=p(p-a)(p-b)(p-c) 其中p=(a+b+c)/22、求一元二次方程ax2+bx+c=0的兩個實數(shù)根。（保證有實數(shù)根）3、輸入三位字符，將其反向輸出。例輸入abc，輸出cba。4、輸入一個三位整數(shù)，將其

22、反向輸出。例輸入321，輸出123。5、輸入經(jīng)緯度（西經(jīng)與南緯用負數(shù)表示），若在東北半球輸出true,否則輸出false。0 1 2 xy2、選擇結構（判斷，分支）、選擇結構（判斷，分支）限于篇幅，以下不再整理講義。限于篇幅，以下不再整理講義。if語句語句IF語句是由一個布爾表達式和兩個供選擇的操作序列組成。運行時根據(jù)布爾表達式求值結果，選取其中之一的操作序列執(zhí)行。有兩種形式的IF語句：ifthen ；ifthen else ； 當if 語句嵌套嵌套時，Pascal約定else總是和最近的一個if配對。 case語句語句case語句是由一個表達式和眾多可選擇的操作序列組成。運行時，根據(jù)表達式的

23、求值結果，在眾多的分支中選取一個分支執(zhí)行。其形式為：case表達式of常量1：語句1；常量2：語句2；常量n：語句n；else語句 n+1 可選項 end;復合語句復合語句 語句要用多個語句描述時，就必須用begin和 end括來，寫成復合語句，當做一條語句用。 典型例題與習題：典型例題與習題：例：求y=f(x),當x0時，y=1，當x=0時，y=0，當x0 then y:=1;if x=0 then y:=0;if x0時候，計算x*x，并且輸出x和x*x，program lianxie3;var x,x1:real;beginreadln(x=,x);if x= then beginx1:

24、=x*x;writeln(x*x=,x1);writeln(x=,x);end;end.例：根據(jù)學生的成績給予相應的等低，對應關系如下：以下program chengji;var s:real;ch:char;beginwrite(input the score: );readln(s);if(s=0)and(s=100)thencase s div 10 of10,9:ch:=B;8:ch:=B;7,6:=C;else ch:=D;end;writeln(s,-,ch);end. 習題：習題：1、輸入經(jīng)緯度（西經(jīng)與南緯用負數(shù)表示），輸出所在半球。2、判斷某年是否閏年。3、根據(jù)身高體重，判斷體

25、型。3、循環(huán)結構、循環(huán)結構while 布爾表達式do語句；Repeat語句; until布爾表達式；for 控制變量：初值to終值do語句；for 控制變量：初值downto終值do語句；goto標號； （不要讓學生用）典型例題與習題：典型例題與習題：計算從到某個數(shù)之間所有奇數(shù)的和。 計算1+2+3+99+100 計算階乘，N！判斷素數(shù)、驗證歌德巴赫猜想輸出各種數(shù)列求公約數(shù)，公倍數(shù)1、計算下列式子的值：（1）1+3+99 （2）1+2+4+8+128+2562、輸入一個整數(shù)，計算它各位上數(shù)字的和。（是任意位的整數(shù)）3、輸入一整數(shù)A，判斷它是否質數(shù)。（提示：若從2到A的平方根的范圍內(nèi)，沒有一個數(shù)

26、能整除A，則A是質數(shù)。）4、求兩個數(shù)的最小公倍數(shù)和最大公約數(shù)。（提示：公約數(shù)一定小于等于兩數(shù)中的小數(shù)，且能整除兩數(shù)中的大數(shù)。公倍數(shù)一定大于等于兩數(shù)中的大數(shù)，且是大數(shù)的倍數(shù)，又能給兩數(shù)中的小數(shù)整除。）5、編寫一個譯碼程序，把一個英語句子譯成數(shù)字代碼。譯碼規(guī)則是以數(shù)字1代替字母A，數(shù)字2代替字母B，26代替字母Z，如遇空格則打印一個星號*，英文句子以.結束。6、求水仙花數(shù)。所謂水仙花數(shù)，是指一個三位數(shù)abc，如果滿足a3+b3+c3=abc，則abc是水仙花數(shù)。 7、“百錢買百雞”是我國古代的著名數(shù)學題。題目這樣描述：3文錢可以買1只公雞，2文錢可以買一只母雞，1文錢可以買3只小雞。用100文錢買

27、100只雞，那么各有公雞、母雞、小雞多少只？與之相似，有雞兔同籠問題。8、輸入一個正整數(shù)N，把它分解成質因子相乘的形式。如：36=1 X 2 X 2 X 3 X 3； 19=1 X 19（提示：設因子為I，從2開始到N，讓N重復被I除，如果能整除，則用商取代N，I為一個因子；如果不能整除，再將I增大，繼續(xù)以上操作，直到I等于N。） 9、宰相的麥子 ：第一格一粒，第二格兩粒， 4、數(shù)組（一維）、數(shù)組（一維）數(shù)組的定義形式：array ， of E基本算法處理：基本算法處理：1初等算法（計數(shù)、統(tǒng)計、數(shù)學運算等）2排序算法（冒泡法、插入排序、合并排序） 3查找（順序查找、二分法）4 排列與組合5 高

28、精度計算循環(huán)結構、數(shù)組綜合練習題循環(huán)結構、數(shù)組綜合練習題1、 數(shù)學黑洞6174已知：一個任意的四位正整數(shù)。將數(shù)字重新組合成一個最大的數(shù)和最小的數(shù)相減，重復這個過程，最多七步，必得6174。即：7641-1467=6174。將永遠出不來。求證：所有四位數(shù)數(shù)字（全相同的除外），均能得到6174。輸出掉進黑洞的步數(shù)。2、 隨機產(chǎn)生20個三位數(shù)，將這20個數(shù)按從小到大的順序排列，要求在排列中，用盡可能少的交換次數(shù)。3、 輸入10個學生的姓名，編一程序將它們按字母的順序排列。4、有一組數(shù)，其排列形式如下：11，19，9，12，5，20，1，18，4，16，6，10，15，2，17，3，14，7，13，8

29、，且尾部8和頭部11首尾相連，構成環(huán)形的一組數(shù)，編程找出相鄰的4個數(shù)，其相加之和最大，并給出它們的起始位置。5、 有一組數(shù)其排列順序如下：（設有N個）3，6，11，45，23，70，67，34，26，89，90，15，56，50，20，10。編一程序交換這組數(shù)中任意指定的兩段。6、 輸入一個十進制數(shù)，將其轉換成二進制數(shù)。有趣的題目：有趣的題目：約瑟夫環(huán) ：猴子選大王:一群(M)猴子排成一列,數(shù)到N的退出,直到剩下一個。狡兔三窟：狼捉兔，有10個洞。神奇魔方：N*N奇數(shù)方。各種數(shù)字矩陣的填充。八皇后問題的非遞歸解法。5、函數(shù)與過程、函數(shù)與過程function函數(shù)名(形式參數(shù)表):函數(shù)類型；說明部

30、分；begin語句1;語句nendprocedure 過程名(形式參數(shù)表); 說明部分; begin 執(zhí)行語句; end;形參和實參 值參數(shù)、變量參數(shù) 、無類型變量參數(shù)、子程序參數(shù) 標識符的作用域1.全局變量和它的作用域2.局部變量和它的作用域 標識符的作用域1.全局變量和它的作用域全局變量是指在程序開頭的說明部分定義和說明的量。它的作用域分為兩種情況：(1)在全局變量和局部變量不同名時，其作用域是整個程序。(2)在全局變量和局部變量同名時，全局變量的作用域不包含同名局部變量的作用域。2.局部變量和它的作用域凡是在子程序內(nèi)部使用的變量，必須在子程序中加入說明。這種在子程序內(nèi)部說明的變量稱為局部

31、變量。局部變量的作用域是其所在的子程序。形式參數(shù)也只能在子程序中有效。因此也屬于局部變量。局部變量的作用域分為兩種情況：(1)當外層過程序的局部變量名和嵌套過程中的局部變量不同名時，外層過程的局部變量作用域包含嵌套過琛。(2)當外層過程的局部變量名和嵌套過程內(nèi)的局部變量名同名時，外層局部變量名的作用域不包含此過程。 到此，可解的題目將極度豐富。碰到具體問題時，插入下節(jié)的多維數(shù)組。到此，可解的題目將極度豐富。碰到具體問題時，插入下節(jié)的多維數(shù)組。典型的遞歸類題目：典型的遞歸類題目：漢諾塔：有三根塔,第一根塔上從小到大擺有n片銅片,要求把這些銅片擺到第三根塔上.但大銅片不能壓在小銅片上面. 八皇后問

32、題:在一個8*8的國際象棋棋盤上放置八個皇后,使他們不互相攻擊,求解的數(shù)量. 迷宮跳馬一筆畫、城市交通及最短線路選擇背包問題、裝箱問題快速排序樹的編歷改進前面的題目解法：改為遞歸解法。如：改進前面的題目解法：改為遞歸解法。如：公約數(shù)與公倍數(shù)階乘菲波那契 數(shù)列遞歸的應用遞歸的應用1.經(jīng)典遞歸例如hanoi塔問題：經(jīng)典的遞歸，原問題包含子問題。有些問題或者數(shù)據(jù)結構本來就是遞歸描述的，用遞歸做很自然。2.遞歸與遞推利用遞歸的思想建立遞推關系，如由兔子生崽而來的fibonacci數(shù)列。但遞推由于沒有返回段，因此更為簡單，有時可以直接用循環(huán)實現(xiàn)。3.分治不少分治方法是源于遞歸思想，或是遞歸分解+合并處理

33、。4.回溯規(guī)模較小的問題用回溯解決比較自然。注意遞歸前后要保證現(xiàn)場的保存和恢復，即正確的轉化問題。5.動態(tài)規(guī)劃動態(tài)規(guī)劃的子問題重疊性質與遞歸有某種相似之處。遞歸+動態(tài)修改查表是一種不錯的建立動態(tài)規(guī)劃模型的方法。6.其他其他么，就是不好歸類。例如表達式處理，排列組合等。附帶說一下，用遞歸來處理打印方案的問題還是很方便的。都是些遞歸定義的函數(shù)。6、數(shù)組（多維）、數(shù)組（多維）數(shù)組的定義形式：array ， of sample2=arrayp1.5,1.5of real；通過前面的學習，引入多維數(shù)組將很自然，不多講了。通過前面的學習，引入多維數(shù)組將很自然，不多講了。用遞歸法的基本解題框架用遞歸法的基本

34、解題框架例：遞歸回溯法算法框架procedure search(k:integer);begin if k=n+1 then begin 輸出解 exit (如果只求一個解，改為halt; ) end; 保存：使用新狀態(tài)之前的狀態(tài)for i:=1 to 狀態(tài)數(shù) do begin 計算狀態(tài)i (應該去掉不能導致解的狀態(tài),也就是剪枝) search(k+1); 恢復：使用本狀態(tài)之前的狀態(tài) end;end;遞歸算法Procedure try( 本步狀態(tài)，深度等參量);Var 局部變量；Begin If 終止條件 then 跳出本過程; else If 找到目標 then 輸出解;else For i

35、:=1 to 本步可擴展的可能性 或者 本步的步驟 do Begin 計算i步的初始狀態(tài)； try(下步狀態(tài),深度+1); End;End;體現(xiàn)的思想：化歸，即把一個問題轉化成另一個的方法。遞歸，它是轉化成性質相似，但規(guī)模更小的問題。用遞歸法解題舉例用遞歸法解題舉例八皇后問題八皇后問題:在一個8*8的國際象棋棋盤上放置八個皇后,使他們不互相攻擊,求解的數(shù)量. program eightqueens;varx:array1.8 of integer;a,b,c:array-7.16 of boolean;i:integer;procedure print;var k:integer;beginf

36、or k:=1 to 8 do write(xk:4);writeln;end;procedure try(i:integer);var j:integer;beginfor j:=1 to 8 doif aj and bi+j and ci-j then beginxi:=j;aj:=false;bi+j:=false;ci-j:=false;if i8 then try(i+1)else print;aj:=true;bi+j:=true;ci-j:=trueendend;beginfor i:=-7 to 16 dobeginai:=true;bi:=true;ci:=trueend;t

37、ry(1);end. 遞歸算法Procedure try( 本步狀態(tài)，深度等參量);Var 局部變量；Begin If 終止條件 then 跳出本過程; else If i=8 (找到目標) then 輸出解;else For i:=1 to 8（共8個位置可放 ）do Begin 計算i步的初始狀態(tài)； try(下步狀態(tài),深度+1); End;End;用遞歸法解題舉例用遞歸法解題舉例漢諾塔：漢諾塔：有三根塔,第一根塔上從小到大擺有n片銅片,要求把這些銅片擺到第三根塔上.但大銅片不能壓在小銅片上面. program hanoi(input,output);var total:integer;pr

38、ocedure move(n,a,b,c:integer); begin if n=1 then write(a,-,c, ) else begin move(n-1,a,c,b); write(a,-,c, ); move(n-1,b,a,c) end end;begin read(total); writeln(move disk:,total); move(total,1,2,3) end.遞歸算法Procedure try( 本步狀態(tài)，深度等參量);Var 局部變量；Begin 此處略。 If n=1 (最小規(guī)模) then 直接輸出;else （本步可分3步走，不用for ） Beg

39、in try(降規(guī)模,n-1);本步分3步: End;End;用遞歸法解題舉例用遞歸法解題舉例跳馬問題跳馬問題: 在5*5格的棋盤上，有一個國家象棋的馬，它可以朝8個方向跳，但不允許出界或跳到已跳過的格子上，要求在跳遍整個棋盤后再條回出發(fā)點。 program jump;varh:array-1.7,-1.7 of integer; a,b:array1.8 of integer; i,j,num:integer; procedure print;(輸出過程略) procedure try(x,y,i:integer); var j,u,v:integer; begin for j:=1 to

40、8 do begin u:=x+aj; v:=y+bj; if hu,v=0 then begin hu,v:=i; if i=1)and(i=1)and(j=5) then hi,j:=0 else hi,j:=1; a1:=2;b1:=1; a2:=1;b2:=2; a3:=-1;b3:=2; a4:=-2;b4:=1; a5:=-2;b5:=-1; a6:=-1;b6:=-2; a7:=1;b7:=-2; a8:=2;b8:=-1; num:=0; h1,1:=1; try(1,1,2); writeln(num=,num);end. 遞歸算法Procedure try( 本步狀態(tài)，深度

41、等參量);Var 局部變量；Begin If 終止條件 then 跳出本過程; else If i=25 (找到目標) then 輸出解;else For i:=1 to 8（8個方向 ）do Begin 計算i步的初始狀態(tài)； try(下步狀態(tài),深度+1); End;End;這種邊界處理方法，要學生掌握。這種狀態(tài)處理方法，要學生掌握。用遞歸法解題舉例用遞歸法解題舉例迷宮問題迷宮問題: 類似于跳馬問題。 program p7t20(input,output); var a:array1.25,1.80 of integer; b:array1.4,1.2 of integer; i,j,m,n,

42、m1,n1,m2,n2:integer; procedure print; ;(輸出過程略) procedure try(x,y,k:integer); var u,v,i:integer; begin for i:=1 to 4 do begin u:=x+bi,1; v:=y+bi,2; if (u0) and (u0) and (v=n) and (au,v=0) then begin au,v:=k; if (u=m2) and (v=n2) then print else try(u,v,k+1); au,v:=0; end; end; end;begin assign(input,

43、p7t20.txt); reset(input); readln(m,n,m1,n1,m2,n2); for i:=1 to m do for j:=1 to n do read(ai,j); b1,1:=-1; b1,2:=0; b2,1:=1; b2,2:=0; b3,1:=0; b3,2:=-1; b4,1:=0; b4,2:=1; am1,n1:=2; try(m1,n1,3); end.遞歸算法Procedure try( 本步狀態(tài)，深度等參量);Var 局部變量；Begin If 終止條件 then 跳出本過程; else If 出口 (找到目標) then 輸出解;else Fo

44、r i:=1 to 4（4個方向 ）do Begin 計算i步的初始狀態(tài)； try(下步狀態(tài),深度+1); End;End;用遞歸法解題舉例用遞歸法解題舉例爬樓梯問題爬樓梯問題: 共m步樓梯，每步可走1-3步，多少走法？ program p7tlt(input,output); var a:array1.20 of integer; m,i,s:integer; procedure print(k:integer); var i:integer; begin s:=s+1; for i:=1 to k do write(ai:3); writeln; end; procedure try(p,k:integer); var i:integer; begin for i:=1 to 3 do begin if (p+i=m) then begin ak:=i; print(k); ak:=0; end; if (