全國(guó)青少年信息學(xué)奧賽培訓(xùn)教程(初級(jí))

1、2015年山東省信息學(xué)奧賽夏令營(yíng)2015年山東省信息學(xué)奧賽夏令營(yíng)學(xué)習(xí)第一天學(xué)習(xí)第一天信息學(xué)奧賽介紹語(yǔ)言學(xué)習(xí)開(kāi)始PascalPascal語(yǔ)言基本語(yǔ)句2015年山東省信息學(xué)奧賽夏令營(yíng)信息學(xué)奧林匹克競(jìng)賽面向全國(guó)中學(xué)生的一種競(jìng)賽活動(dòng)面向全國(guó)中學(xué)生的一種競(jìng)賽活動(dòng)旨在激發(fā)中學(xué)生在計(jì)算機(jī)科學(xué)方面的興趣旨在激發(fā)中學(xué)生在計(jì)算機(jī)科學(xué)方面的興趣培養(yǎng)他們培養(yǎng)他們邏輯思維邏輯思維的能力的能力給那些有給那些有才華才華的學(xué)生提供相互交流和學(xué)習(xí)的機(jī)會(huì)的學(xué)生提供相互交流和學(xué)習(xí)的機(jī)會(huì)通過(guò)競(jìng)賽和相關(guān)的活動(dòng)培養(yǎng)和選拔通過(guò)競(jìng)賽和相關(guān)的活動(dòng)培養(yǎng)和選拔優(yōu)秀的計(jì)算機(jī)后備人優(yōu)秀的計(jì)算機(jī)后備人才才。2015年山東省信息學(xué)奧賽夏令營(yíng) 信息學(xué)奧林匹

2、克競(jìng)賽屬于信息學(xué)奧林匹克競(jìng)賽屬于智力智力與應(yīng)用計(jì)算機(jī)解題與應(yīng)用計(jì)算機(jī)解題能力能力的比的比賽，題目有相當(dāng)?shù)碾y度，解好這類(lèi)題目，需要具備賽，題目有相當(dāng)?shù)碾y度，解好這類(lèi)題目，需要具備很很強(qiáng)的綜強(qiáng)的綜合能力合能力1.1.觀(guān)察和分析問(wèn)題的能力；觀(guān)察和分析問(wèn)題的能力；2.2.將實(shí)際問(wèn)題轉(zhuǎn)化為將實(shí)際問(wèn)題轉(zhuǎn)化為數(shù)學(xué)模型數(shù)學(xué)模型的能力；的能力；3.3.靈活地運(yùn)用各種靈活地運(yùn)用各種算法算法的能力；的能力；4.4.熟練編寫(xiě)程序熟練編寫(xiě)程序并將其調(diào)試通過(guò)的能力；并將其調(diào)試通過(guò)的能力；5.5.根據(jù)題目的要求，自己設(shè)計(jì)測(cè)試數(shù)據(jù)，檢查自己的解法根據(jù)題目的要求，自己設(shè)計(jì)測(cè)試數(shù)據(jù)，檢查自己的解法是否正確、是否完備的能力是否正確

3、、是否完備的能力 綜合能力的體現(xiàn)2015年山東省信息學(xué)奧賽夏令營(yíng)學(xué)習(xí)內(nèi)容：掌握一門(mén)計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言掌握一門(mén)計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言 （Pascal/C/C+）數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法2015年山東省信息學(xué)奧賽夏令營(yíng)信息學(xué)奧林匹克競(jìng)賽賽事：信息學(xué)奧林匹克競(jìng)賽賽事：1.NOIP1.NOIP（全國(guó)信息學(xué)奧林匹克分區(qū)聯(lián)賽）（全國(guó)信息學(xué)奧林匹克分區(qū)聯(lián)賽） National Olympiad in Informatics in Provinces 2.NOI 2.NOI （全國(guó)信息學(xué)奧林匹克競(jìng)賽）（全國(guó)信息學(xué)奧林匹克競(jìng)賽） National Olympiad in Informatics3.IOI 3.I

4、OI （國(guó)際信息學(xué)奧林匹克競(jìng)賽）（國(guó)際信息學(xué)奧林匹克競(jìng)賽） International Olympiad in Informatics 2015年山東省信息學(xué)奧賽夏令營(yíng)語(yǔ)言學(xué)習(xí)開(kāi)始Pascal語(yǔ)言一、語(yǔ)言的安裝二、界面簡(jiǎn)介三、典例分析2015年山東省信息學(xué)奧賽夏令營(yíng)安裝程序 注意如果安裝后出現(xiàn)亂碼，我們可以在FP窗口最上面的標(biāo)題欄上右擊，在彈出的快捷菜單中選擇“默認(rèn)值”，接著會(huì)彈出的控制臺(tái)窗口屬性框，在最下面的“默認(rèn)代碼頁(yè)”的下拉菜單中選擇“437（OEM-美國(guó)）”。2015年山東省信息學(xué)奧賽夏令營(yíng)界面介紹標(biāo)題欄、菜單欄、中間部分為編輯窗口、最底部一行為提示欄（顯示系統(tǒng)中常用命令的快捷鍵，如將

5、當(dāng)前正在編輯的文件存盤(pán)的命令快捷鍵為F2）1、新建程序： FileNew（默認(rèn)文件名為：Noname01.pas)2、程序運(yùn)行：RunRun(或按快捷鍵：Ctrl+F9)3、查看運(yùn)行結(jié)果：DubugUser screen(或按快捷鍵：Alt+F5)4、程序的保存：FileSave(或按F2）。第一次保存文件時(shí)屏幕上會(huì)出現(xiàn)一個(gè)對(duì)話(huà)框要求輸入文件名。注意文件保存的目錄（默認(rèn)工作目錄可以在FP的快捷方式的屬性框中的“起始位置”欄中設(shè)置。）5、程序的打開(kāi)：FileOpen（或按F3）2015年山東省信息學(xué)奧賽夏令營(yíng)多動(dòng)手、模仿是捷徑勤思考、實(shí)踐是王道2015年山東省信息學(xué)奧賽夏令營(yíng)Program ex

6、1_1;Program ex1_1;BeginBegin write(Hello!); write(Hello!);End.End.大小寫(xiě)無(wú)所謂，但是你可以改變一下單引號(hào)內(nèi)的單詞大小寫(xiě)，看看有什么變化？2015年山東省信息學(xué)奧賽夏令營(yíng)計(jì)算123+56的值Program ex1_2;Var a,b:integer;Begin a:=10; b:=5; writeln(a+b=,a+b);End.2015年山東省信息學(xué)奧賽夏令營(yíng)已知長(zhǎng)方形的長(zhǎng)和寬，求長(zhǎng)方形的周長(zhǎng)和面積。Program ex1_3;Var a,b,c,s:integer;Begin readln(a,b); c:=2*(a+b);

7、s:=a*b; writeln(c=,c,s=,s);End.2015年山東省信息學(xué)奧賽夏令營(yíng)求圓的面積Program ex1_4;Const Pi=3.1415926;var r:integer; s:real;begin read(r); s:=pi*r*r; writeln(s:0:2);end.2015年山東省信息學(xué)奧賽夏令營(yíng)模仿一下： 已知小雄的書(shū)包放了3本書(shū),5本作業(yè)本和2支筆,你能編程序讓計(jì)算機(jī)算算小雄的書(shū)包中一共有多少件學(xué)習(xí)用品嗎?2015年山東省信息學(xué)奧賽夏令營(yíng)典例分析程序由三部分組成：（一）程序首部：Program 程序名。 由保留字Program 開(kāi)頭，后跟一個(gè)程序名，程

8、序名的第一個(gè)字符必須是英文字母，其后的字符只能是字母或數(shù)字和下劃線(xiàn)組成。標(biāo)識(shí)符）（二）說(shuō)明部分：程序中所用的常量、變量等必須先定義后使用。 常量：在程序執(zhí)行過(guò)程中其值不能被改變的數(shù)據(jù)。 變量：在程序執(zhí)行過(guò)程中可以改變值的數(shù)據(jù)。 數(shù)據(jù)類(lèi)型：簡(jiǎn)單類(lèi)型（分標(biāo)準(zhǔn)類(lèi)型和用戶(hù)自定義型）、構(gòu)造類(lèi)型、指針類(lèi)型 （三）語(yǔ)句部分 由保留字begin 至end. 語(yǔ)句未尾以分號(hào);結(jié)束。 程序結(jié)束語(yǔ)句 end未尾必須用句號(hào)。整型、實(shí)型、字符型、布爾型枚舉型、子界型數(shù)組類(lèi)型、記錄類(lèi)型、集合類(lèi)型、文件類(lèi)型program 程序名；程序名；var 變量說(shuō)明；變量說(shuō)明；begin語(yǔ)句；語(yǔ)句；語(yǔ)句；語(yǔ)句；語(yǔ)句語(yǔ)句;end.201

9、5年山東省信息學(xué)奧賽夏令營(yíng)保留字Pascal語(yǔ)言中一些有特殊含義的英文單詞（這些單詞保留給Pascal本身使用）。你已學(xué)會(huì)了幾個(gè)保留字：返回2015年山東省信息學(xué)奧賽夏令營(yíng)在程序中用到的所有變量必須事先定義。在程序中用到的所有變量必須事先定義。格式：格式：Var Var : : ； : : ； 如：輸入3個(gè)整數(shù)，求這3個(gè)數(shù)的平均值。Var a，b，c：integer; aver:real;變量的定義說(shuō)明：變量的定義說(shuō)明：返回變量就相當(dāng)于一個(gè)書(shū)包，不過(guò)這個(gè)變量就相當(dāng)于一個(gè)書(shū)包，不過(guò)這個(gè)“書(shū)包書(shū)包”中存放的中存放的“書(shū)書(shū)”只是一個(gè)數(shù)據(jù)只是一個(gè)數(shù)據(jù)而已。變量的名稱(chēng)叫做而已。變量的名稱(chēng)叫做變量名變量名

10、。它可以由字母、數(shù)字或下劃線(xiàn)構(gòu)成，但第。它可以由字母、數(shù)字或下劃線(xiàn)構(gòu)成，但第一個(gè)必須是字母。一個(gè)必須是字母。2015年山東省信息學(xué)奧賽夏令營(yíng)標(biāo)準(zhǔn)數(shù)據(jù)類(lèi)型整數(shù)類(lèi)型：包括正整數(shù)、負(fù)整數(shù)和零。Var a,b,c:integer;Begin readln(a); readln(b); c:=a+b; writeln(c);End.120 20010000 2000020000 30000測(cè)試以下測(cè)試以下3組數(shù)據(jù)：組數(shù)據(jù)：輸入整數(shù)輸入整數(shù)a和和b，輸出，輸出a+b的值。的值。2015年山東省信息學(xué)奧賽夏令營(yíng)Integer：取值范圍：-3276832767(maxint) 類(lèi)型數(shù)值范圍 占字節(jié)數(shù) Byte

11、 0 . 255 1 Word 0.65535 2 Shortint -128 . 127 1 Integer -32768.32767; 2 Longint -2147483648 . 2147483647 4 Longword 0.4294967295 4 Int64 -9223372036854775808 . 9223372036854775807 8 QWord 0 . 18446744073709551615 82015年山東省信息學(xué)奧賽夏令營(yíng)整數(shù)的運(yùn)算符有：、*、DIV（整除）、mod(取余）。15 Div 6 = 2 15 Div 6 = 2 (-15) div 6=-2(-1

12、5) div 6=-215 Div (-6)=-215 Div (-6)=-2(-15) div(-6)=2(-15) div(-6)=215 mod 6 = 315 mod 6 = 3(-15) mod 6=-3(-15) mod 6=-315 mod(-6)=315 mod(-6)=3(-15) mod (-6)=-3(-15) mod (-6)=-32015年山東省信息學(xué)奧賽夏令營(yíng) 類(lèi)型類(lèi)型 范圍范圍 有效位數(shù)有效位數(shù) 占用字節(jié)占用字節(jié) Real 2.9e-39.1.7e3811.12 6 Single 1.5E-45 . 3.4E38 7-8 4 Double 5.0E-324 . 1

13、.7E308 15-16 8 Extended 1.9E-4951 . 1.1E4932 19-20 10 Comp -2E64+1 . 2E63-1 19-20 8實(shí)數(shù)類(lèi)型Real類(lèi)型運(yùn)算符有：、*、/2015年山東省信息學(xué)奧賽夏令營(yíng)Var begin read(a,b); c:=a*b; d:=a/b; writeln(c); writeln(d);End.?例例:輸入輸入:兩個(gè)正整數(shù)兩個(gè)正整數(shù)a、b(3; b:=23;2015年山東省信息學(xué)奧賽夏令營(yíng)基本語(yǔ)句一、賦值語(yǔ)句二、read語(yǔ)句三、write語(yǔ)句2015年山東省信息學(xué)奧賽夏令營(yíng)1、賦值語(yǔ)句賦值語(yǔ)句是最簡(jiǎn)單的語(yǔ)句. 1)、賦值語(yǔ)句的

14、格式 變量名:=表達(dá)式； 其中“:=”稱(chēng)為賦值號(hào)。 2)、執(zhí)行過(guò)程 計(jì)算機(jī)先計(jì)算賦值號(hào)右邊表達(dá)式的值，然后將表達(dá)式的值賦給變量名代表的變量。如：A：=（9*8）-（2-1）; A:=A+1 2015年山東省信息學(xué)奧賽夏令營(yíng)、輸入語(yǔ)句read和readln功能： 從鍵盤(pán)讀入數(shù)據(jù)項(xiàng)，并把它存到變量中去，使該數(shù)據(jù)能在以后的計(jì)算中使用。輸入語(yǔ)句的一般形式為： read(v1，v2，vn)； readln(v1，v2，vn)； 從鍵盤(pán)逐次讀入數(shù)據(jù)，分別賦給變量v1，v2，vn，一行輸入多個(gè)變量值時(shí)，要求數(shù)據(jù)之間用空格分隔，readln語(yǔ)句要求輸入數(shù)據(jù)后必須回車(chē)，使得后繼操作從下一行的頭上開(kāi)始。 2015

15、年山東省信息學(xué)奧賽夏令營(yíng)及時(shí)充電（輸入語(yǔ)句）格式作用Read（變量表）接受鍵盤(pán)輸入數(shù)據(jù)存入對(duì)應(yīng)變量Readln（變量表）接受鍵盤(pán)輸入數(shù)據(jù)存入對(duì)應(yīng)變量，然后光標(biāo)換行Readln不接受數(shù)據(jù)，光標(biāo)換行輸入數(shù)據(jù)時(shí)，數(shù)值數(shù)據(jù)之間可用空格分開(kāi)，也可以每輸入一個(gè)數(shù)按一次回車(chē)；如果是輸入字符或者字符串，兩者之間不能用空格分開(kāi)，只能每輸入一個(gè)按一次回車(chē)。2015年山東省信息學(xué)奧賽夏令營(yíng)read語(yǔ)句與readln語(yǔ)句區(qū)別是： 1) read語(yǔ)句是一個(gè)接一個(gè)地讀數(shù)據(jù)，在執(zhí)行完本Read語(yǔ)句( 讀完本語(yǔ)句中變量所需的數(shù)據(jù))后,下一個(gè)讀語(yǔ)句接著從該數(shù)據(jù)輸入行中繼續(xù)讀數(shù)據(jù)，也就是說(shuō)，不換行。如：read(a,b); re

16、ad(c,d); read(e); 如果輸入數(shù)據(jù)行如下: 123 456則a,b,c,d,e的值分別為1,2,3,4,5,如果后面無(wú)讀語(yǔ)句則數(shù)據(jù)6是多余的，這是允許的。 2015年山東省信息學(xué)奧賽夏令營(yíng) Readln則不同，在讀完本則不同，在讀完本Readln語(yǔ)句中變量所需的數(shù)語(yǔ)句中變量所需的數(shù)據(jù)后據(jù)后, 該數(shù)據(jù)行中剩余的數(shù)據(jù)多余無(wú)用，或者說(shuō)，在讀完本該數(shù)據(jù)行中剩余的數(shù)據(jù)多余無(wú)用，或者說(shuō)，在讀完本Readln語(yǔ)句中變量所需數(shù)據(jù)后，一定要讀到一個(gè)回車(chē)，否語(yǔ)句中變量所需數(shù)據(jù)后，一定要讀到一個(gè)回車(chē)，否則多余的數(shù)據(jù)無(wú)用。則多余的數(shù)據(jù)無(wú)用。設(shè)有下列語(yǔ)句設(shè)有下列語(yǔ)句: read(a,b,c); readl

17、n(d,e); readln; readln(f,g);其中其中,所有變量均為整型。設(shè)輸入的數(shù)據(jù)如下：所有變量均為整型。設(shè)輸入的數(shù)據(jù)如下： 12 345678 910 11 12 13 Var a,b,c,d,e,f,g:integer;begin read(a,b,c); readln(d,e); readln; readln(f,g); writeln(a, ,b, ,c, ,d, ,e, ,f, ,g);end.2015年山東省信息學(xué)奧賽夏令營(yíng)2)readln語(yǔ)句與read語(yǔ)句的第二個(gè)區(qū)別是:read 后一定要有參數(shù)表,readln可以不帶參數(shù)表,即可以沒(méi)有任何輸入項(xiàng), 只是等待讀入一個(gè)

18、換行符(回車(chē))。經(jīng)常用于暫停程序的運(yùn)行，直到輸入一個(gè)回車(chē)2015年山東省信息學(xué)奧賽夏令營(yíng)輸出語(yǔ)句write和writeln功能：把程序計(jì)算的結(jié)果，按適當(dāng)?shù)男问捷敵龅狡聊弧?)、write語(yǔ)句格式Write(表達(dá)式1，表達(dá)式2，)；如:write(x,5,a+b);write(My name is Liping);2)、writeln語(yǔ)句格式:Writeln(表達(dá)式1，表達(dá)式2，)或writeln2015年山東省信息學(xué)奧賽夏令營(yíng)Write語(yǔ)句與writeln語(yǔ)句格式上都相似，但它們?cè)诠δ苌嫌兴煌?，兩個(gè)語(yǔ)句的區(qū)別在于: write語(yǔ)句將其后括號(hào)中的表達(dá)式一個(gè)接一個(gè)輸出后，沒(méi)有換行。 而write

19、ln語(yǔ)句則在輸出各個(gè)表達(dá)式的值后換行。例如以下兩個(gè)程序段的輸出分別為：write(1,2,3,4);write(5,6);輸出為：123456writeln(1,2,3,4);write(5,6);輸出為：1234562015年山東省信息學(xué)奧賽夏令營(yíng)實(shí)數(shù)的輸出格式實(shí)數(shù)（real）以浮點(diǎn)型格式輸出。例如805.67對(duì)應(yīng)的浮點(diǎn)數(shù)為8.056700000000E+02。這種實(shí)數(shù)表達(dá)方式很不方便。我們可以通過(guò)下述形式強(qiáng)迫實(shí)數(shù)以定點(diǎn)型格式輸出： 實(shí)數(shù)表達(dá)式：域?qū)挘盒?shù)位數(shù)例如，t的值設(shè)為63.123。下面三條輸出語(yǔ)句分別有它們右邊所示的輸出格式： write(t)； 6.312300000000E+01

20、 write(t：6：2)； 63.12 write(t：6：5)； 63.12300 write(t:0:0);2015年山東省信息學(xué)奧賽夏令營(yíng)vara,b,t:char;begin read(a,b); t:=a; a:=b; b:=t; writeln(a=,a,b=,b)end.例：輸入兩個(gè)整數(shù)a，b，交換他們的值，并輸出.如：輸入：30 34 輸出：34 302015年山東省信息學(xué)奧賽夏令營(yíng)算術(shù)運(yùn)算符和算術(shù)表達(dá)式1.算術(shù)運(yùn)算符運(yùn)算符運(yùn)算運(yùn)算對(duì)象結(jié)果類(lèi)型+ 加整型、實(shí)型只要有一個(gè)運(yùn)算對(duì)象是實(shí)型，結(jié)果就-減 整型、實(shí)型是實(shí)型，如果全部的運(yùn)算對(duì)象都是整*乘 整型、實(shí)型型并且運(yùn)算不是除法，則

21、結(jié)果為整型/除 整型、實(shí)型若運(yùn)算是除法，則結(jié)果是實(shí)型。 div 整除整型整型mod取余整型整型Program ex1_5;Const a=128;Var b,d:integer; c:real;Begin b:=a div 16; c:=a/b; d:=a; write(a:4,b:4,c:4:0,d:4);end.Program ex1_6;Var a:integer;Begin read(a); writeln(a mod 10); writeln(a div 10 mod 10); wrteln(a div 100);End.輸入任意一個(gè)百位數(shù)2015年山東省信息學(xué)奧賽夏令營(yíng)是通過(guò)運(yùn)算符

22、把常量、變量、函數(shù)調(diào)用結(jié)合起來(lái)組成的。 3+x1+bPASCAL表達(dá)式有以下計(jì)算優(yōu)先順序規(guī)則：1.括號(hào)內(nèi)的表達(dá)式首先計(jì)算；2.運(yùn)算符的優(yōu)先級(jí)有四級(jí)，按其優(yōu)先順序從高到低排列為：not； *，/，div，mod，and； +，-，or； =，=，IN；不同優(yōu)先級(jí)的兩運(yùn)算符之間的操作數(shù)先與具有較高優(yōu)先級(jí)的運(yùn)算符進(jìn)行運(yùn)算；3.同級(jí)的運(yùn)算從左到右進(jìn)行；另外，有一點(diǎn)需要指出的是，因?yàn)殛P(guān)系運(yùn)算符的優(yōu)先級(jí)最低，當(dāng)用關(guān)系式構(gòu)造復(fù)雜的布爾表達(dá)式時(shí)，這些關(guān)系式作為初等條件必須放在括號(hào)里。如: (xy) and (z=y) or (x=0)若不加括號(hào)，就是一個(gè)錯(cuò)誤的表達(dá)式。 表達(dá)式2015年山東省信息學(xué)奧賽夏令營(yíng)輸

23、入一個(gè)3位的正整數(shù)，輸出他們的各位數(shù)字之和與乘積。如：輸入：436輸出：1372var n,a,b,c,x,y:integer;begin readln(n); a:=n div 100; b:=(n div 10) mod 10; c:=n mod 10; x:=a+b+c; y:=a*b*c; writeln(x); writeln(y);end.上機(jī)練習(xí)題目：2015年山東省信息學(xué)奧賽夏令營(yíng)展示實(shí)力1 1、寫(xiě)出下列表達(dá)式的值。、寫(xiě)出下列表達(dá)式的值。 1212* *3+6/4=3+6/4=45 div 4=45 div 4=98 mod 10 =98 mod 10 =2 2、寫(xiě)出下列程序段

24、的運(yùn)行結(jié)果。、寫(xiě)出下列程序段的運(yùn)行結(jié)果。 Var my:real;Var my:real;BeginBegin my:=18/4-3; my:=18/4-3;Writeln(my:10:2)Writeln(my:10:2)End.End.Var n,v:integer;Var n,v:integer;BeginBegin read(n); read(n); v:=n mod 5; v:=n mod 5; writeln( writeln(VP=VP=,v),v)End.End. 運(yùn)行時(shí)輸入運(yùn)行時(shí)輸入 3434Var w1,w2:integer;Var w1,w2:integer;BeginBe

25、gin writeln( writeln(EnterEnter););Read(w1,w2);Read(w1,w2);W1:=0;W1:=0;W1:=w1+w2;W1:=w1+w2;Writeln(w1)Writeln(w1)End.End.運(yùn)行時(shí)輸入運(yùn)行時(shí)輸入1515，3636Var k1,k2,fn:integer;Var k1,k2,fn:integer;BeginBeginRead(k1,k2);Read(k1,k2);fn:=k1+2fn:=k1+2* *k2;k2;If fn7 then writeln(fn)If fn7 then writeln(fn)End.End.運(yùn)行時(shí)輸入運(yùn)行時(shí)輸入1,2,31,2,32015年山東省信息學(xué)奧賽夏令營(yíng)展示實(shí)力3、從鍵盤(pán)輸入一個(gè)字符，然后顯示一個(gè)由該字符組成的圖案。輸入樣例輸出樣例Kkk