信息學(xué)競(jìng)賽輔導(dǎo)交流會(huì)

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

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

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

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

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

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

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

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

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

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

11、題的解題為主。0、體驗(yàn)程序設(shè)計(jì)、體驗(yàn)程序設(shè)計(jì)Pascal語(yǔ)言介紹1、基本符號(hào)：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、標(biāo)識(shí)

12、符以字母開(kāi)頭的字母、數(shù)字組合。自己定義，例如：x, y, max, min, sum, a15, a3b7, 是合法的。5x, x-y, ex10.5 ,不是標(biāo)識(shí)符，非法的。用途：表示各種常量、變量、類型、文件、函數(shù)、過(guò)程、或程序的名字。特殊標(biāo)識(shí)符：（標(biāo)準(zhǔn)標(biāo)識(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過(guò)程：get, new, pack, page, put, read, readln, reset, rewrite, unpack, write, writeln程序結(jié)構(gòu)例1 ：已知半徑，求圓周長(zhǎng)和面積的程序 數(shù)學(xué)公式：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.程序說(shuō)明：1、常量定義：CONST pi:=3.1415926;定義一個(gè)常量pi， 值為3.14159262

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

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

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

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

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

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

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

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

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

23、求值結(jié)果，在眾多的分支中選取一個(gè)分支執(zhí)行。其形式為：case表達(dá)式of常量1：語(yǔ)句1；常量2：語(yǔ)句2；常量n：語(yǔ)句n；else語(yǔ)句 n+1 可選項(xiàng) end;復(fù)合語(yǔ)句復(fù)合語(yǔ)句 語(yǔ)句要用多個(gè)語(yǔ)句描述時(shí)，就必須用begin和 end括來(lái)，寫(xiě)成復(fù)合語(yǔ)句，當(dāng)做一條語(yǔ)句用。 典型例題與習(xí)題：典型例題與習(xí)題：例：求y=f(x),當(dāng)x0時(shí)，y=1，當(dāng)x=0時(shí)，y=0，當(dāng)x0 then y:=1;if x=0 then y:=0;if x0時(shí)候，計(jì)算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ù)學(xué)生的成績(jī)給予相應(yīng)的等低，對(duì)應(yīng)關(guān)系如下：以下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. 習(xí)題：習(xí)題：1、輸入經(jīng)緯度（西經(jīng)與南緯用負(fù)數(shù)表示），輸出所在半球。2、判斷某年是否閏年。3、根據(jù)身高體重，判斷體

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

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

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

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

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

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

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

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

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

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

35、:=1 to 本步可擴(kuò)展的可能性 或者 本步的步驟 do Begin 計(jì)算i步的初始狀態(tài)； try(下步狀態(tài),深度+1); End;End;體現(xiàn)的思想：化歸，即把一個(gè)問(wèn)題轉(zhuǎn)化成另一個(gè)的方法。遞歸，它是轉(zhuǎn)化成性質(zhì)相似，但規(guī)模更小的問(wèn)題。用遞歸法解題舉例用遞歸法解題舉例八皇后問(wèn)題八皇后問(wèn)題:在一個(gè)8*8的國(guó)際象棋棋盤(pán)上放置八個(gè)皇后,使他們不互相攻擊,求解的數(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 跳出本過(guò)程; else If i=8 (找到目標(biāo)) then 輸出解;else For i:=1 to 8（共8個(gè)位置可放 ）do Begin 計(jì)算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;用遞歸法解題舉例用遞歸法解題舉例跳馬問(wèn)題跳馬問(wèn)題: 在5*5格的棋盤(pán)上，有一個(gè)國(guó)家象棋的馬，它可以朝8個(gè)方向跳，但不允許出界或跳到已跳過(guò)的格子上，要求在跳遍整個(gè)棋盤(pán)后再條回出發(fā)點(diǎn)。 program jump;varh:array-1.7,-1.7 of integer; a,b:array1.8 of integer; i,j,num:integer; procedure print;(輸出過(guò)程略) 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 跳出本過(guò)程; else If i=25 (找到目標(biāo)) then 輸出解;else For i:=1 to 8（8個(gè)方向 ）do Begin 計(jì)算i步的初始狀態(tài)； try(下步狀態(tài),深度+1); End;End;這種邊界處理方法，要學(xué)生掌握。這種狀態(tài)處理方法，要學(xué)生掌握。用遞歸法解題舉例用遞歸法解題舉例迷宮問(wèn)題迷宮問(wèn)題: 類似于跳馬問(wèn)題。 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; ;(輸出過(guò)程略) 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 跳出本過(guò)程; else If 出口 (找到目標(biāo)) then 輸出解;else Fo

44、r i:=1 to 4（4個(gè)方向 ）do Begin 計(jì)算i步的初始狀態(tài)； try(下步狀態(tài),深度+1); End;End;用遞歸法解題舉例用遞歸法解題舉例爬樓梯問(wèn)題爬樓梯問(wèn)題: 共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 (