信息學奧賽培訓材料

1、分支程序設計一、IF語句的嵌套在if語句中，如果then子句或else子句仍是一個if語句，則稱為if語句的嵌套。例1計算下列函數(shù)Y=1(x>0)=0(x=0)=-1(x<0)分析：根據(jù)輸入的x值，先分成x>0與xWO兩種情況，然后對于情況x<0,再區(qū)分x是小于0,還是等于0。源程序如下：programex;varx:real;y:integer;beginwrtie('Inputx:');readln(x);ifx>0theny:=1x>0時，y的值為1elsexwo時ifx=0theny:=0elsey:=-1;writeln('

2、x=',x:6:2,'y=',y);end.顯然，以上的程序中，在then子句中嵌套了一個n型if語句。當然程序也可以寫成如下形式：programex;varx:real;y:integer;beginwrtie('Inputx:');readln(x);ifx>=0thenifx>0theny:=1elsey:=0elsey=-1;writeln('x=',x:6:2,'y=',y);end.但是對于本題，下面的程序是不對的。y:=0;ifx>=0thenifx>0theny:=1elsey:=-

3、1;明顯，從此人的程序書寫格式可以看出，他想讓else與第一個if配對，而事實上，這是錯的。因為pascal規(guī)定：else與它上面的距它最近的then配對，因此以上程序段的邏輯意義就與題義不符。要使上程序段中esle與第一個then配對，應將程序段修改為：y:=0;或者y:=0;ifx>=0ifx>=0thenifx>0thentheny:=1beginelseifx>0thenY:=1;elsey:=-1;endelseY:=-1;二、case語句上面我們知道可以用嵌套的if語句實現(xiàn)多分支的選擇結構。但是如果分支越來越多時，用嵌套的if語句實現(xiàn)多分支就顯得繁雜。當多分

4、支選擇的各個條件由同一個表達式的不同結果值決定時，可以用case語句實現(xiàn)。它的選擇過程，很象一個多路開關，即由case語句的選擇表達式的值，決定切換至哪一語句去工作。因此在分支結構程序設計中，它是一種強有力的手段。在實現(xiàn)多路徑分支控制時，用case對某些問題的處理和設計，比用if語句寫程序具有更簡潔、清晰之感。（一卜情況語句的一般形式：case維達式>of情況標號表1>：語句1;情況標號表2>:語句2;情況標號表n>:語句nend;其中caseof、end是Pascal的保留字，表達式的值必須是順序類型，它可以是整型、布爾型及以后學習的字符型、枚舉型和子界型。情況標號表

5、是一串用逗號隔開的與表達式類型一致的常量序列。語句可以是任何語句，包括復合語句和空語句。（二卜case語句的執(zhí)行過程先計算表達式（稱為情況表達式）的值，如果它的值等于某一個常量（稱為情況常量，也稱情況標號），則執(zhí)行該情況常量后面的語句，在執(zhí)行完語句后，跳到case語句的末尾end處。（三卜說明情況表達式必須是順序類型的；情況常量是情況表達式可能具有的值，因而應與情況表達式具有相同的類型；情況常量出現(xiàn)的次序可以是任意的；同一情況常量不能在同一個case語句中出現(xiàn)兩次或兩次以上；每個分語句前可以有一個或若干個用逗號隔開的情況常量；如果情況表達式的值不落在情況常的范圍內，則認為本case語句無效，執(zhí)

6、行case語句的下一個語句。turbopascal中增加了一個"否則"的情況，即增加一個else子句，但也是可省的。每個常量后面只能是一個語句或一個復合語句。例2根據(jù)x的值，求函數(shù)Y的值：分析：利用case語句進行程序設計，關鍵在于巧妙地構造情況表達式。本例中三種情況可用一個表達式區(qū)分出來：Trunc(x/100)。因為x在(0100)之間時表達式值為0;x在100,200)時表達式值為1;其余部分可用else子句表示。源程序如下：programex;varx,y:real;beginwrite('Inputx:');readln(x);casetrunc(

7、x/100)of0:y:=x+1;1:y:=x-1;elsey:=0;end;endofcasewriteln('x=',x:8:2),'y=',y:8:2);end.三、選擇結構的程序設計例3輸入一個年號，判斷它是否是閏年。分析：判斷閏年的算法是：如果此年號能被400除盡，或者它能被4整除而不能被100整除，則它是閏年。否則，它是平年。源程序如下：programex;varyear:integer;beginwrite('Inputyear:');readln(year);write(year:6);if(yearmod400=0)thenwr

8、iteln('isaleapyear.')elseif(yearmod4=0)and(yearmod100<>0)thenwriteln('isaleapyear.')elsewriteln('isnotaleapyear.');end.例4判斷1995年，每個月份的天數(shù)。分析：程序分為：輸入月份，計算該月的天數(shù)，輸出天數(shù)源程序如下：programdays;varmonth,days:integer;beginwrite('Inputmonth:');readln(month);casemonthof1,3,5,7,8

9、,10,12:days:=31;4,6,9,11:days:=30;2:days:=28;elsedays:=0;end;ifdays<>0thenwriteln('Days=',days);end.例5期未來臨了，班長小Q決定將剩余班費X元錢，用于購買若干支鋼筆獎勵給一些學習好、表現(xiàn)好的同學。已知商店里有三種鋼筆，它們的單價為6元、5元和4元。小Q想買盡量多的筆（鼓勵盡量多的同學），同時他又不想有剩余錢。請您編一程序，幫小Q制訂出一種買筆的方案。分析：對于以上的實際問題，要買盡量多的筆，易知都買4元的筆肯定可以買最多支筆。因此最多可買的筆為xdiv4支。由于小q要

10、把錢用完，故我們可以按以下方法將錢用完:若買完xdiv4支4元錢的筆,可；若買完xdiv4支4元錢的筆,可；若買完xdiv4支4元錢的筆,還剩還剩還剩1元，則4元錢的筆少買2元，則4元錢的筆少買3元，則4元錢的筆少買1支，換成一支5元筆即1支，換成一支6元筆即2支，換成一支5元筆和支6元筆即可。從以上對買筆方案的調整，可以看出筆的數(shù)目都是xdiv4,因此該方案的確為最優(yōu)方案。源程序如下：programpen;vara,b,c:integer;a,b,c分別表示在買筆方案中，6元、5元和4元錢筆的數(shù)目x,y:integer;x,y分別表示剩余班費和買完最多的4元筆后剩的錢beginwrite(&

11、#39;x=');readln(x)輸入xc:=xdiv4;4元筆最多買的數(shù)目y:=xmod4;求買完c支4元筆后剩余的錢數(shù)ycaseyof0:begina:=0;b:=0;end;1 :begina:=0;b:=1;c:=c-1;end;2 :begina:=1;b:=0;c:=c-1;end;3 :begina:=1;b:=1;c:=c-2;end;end;writeln（'a=',a,'b=',b,'c=',c）;end.練習1 .輸入三角形的三個邊，判斷它是何類型的三角形（等邊三角形？等腰三角形？一般三角形？）。2 .輸入三個數(shù)，

12、按由大到小順序打印出來。3 .計算1901年2099年之間的某月某日是星期幾。循環(huán)程序設計（2次）一、計數(shù)循環(huán)（For循環(huán)）在實際應用中，會經(jīng)常遇到許多有規(guī)律性的重復運算，這就需要掌握本章所介紹的循環(huán)結構程序設計。在Pascal語言中，循環(huán)結構程序通常由三種的循環(huán)語句來實現(xiàn)。它們分別為FOR循環(huán)、當循環(huán)和直到循環(huán)。通常將一組重復執(zhí)行的語句稱為循環(huán)體，而控制重復執(zhí)行或終止執(zhí)行由重復終止條件決定。因此，重復語句是由循環(huán)體及重復終止條件兩部分組成。For語句的格式for<控制變量>:=<表達式1>to表達式2>do語句；for<控制變量>:=<表達式1

13、>downto表達式2>do語句；其中for、to、downto和do是Pascal保留字。表達式1與表達式2的值也稱為初值和終值。For語句執(zhí)行過程先將初值賦給左邊的變量（稱為循環(huán)控制變量）；判斷循環(huán)控制變量的值是否已"超過"終值，如已超過，則跳到步驟；如果末超過終值，則執(zhí)行do后面的那個語句（稱為循環(huán)體）；循環(huán)變量遞增（對to）或遞減（對downto）1;返回步驟；循環(huán)結束，執(zhí)行for循環(huán)下面的一個語句。說明循環(huán)控制變量必須是順序類型。例如，可以是整型、字符型等，但不能為實型。循環(huán)控制變量的值遞增或遞減的規(guī)律是：選用to則為遞增；選用downto則遞減。所謂

14、循環(huán)控制變量的值"超過"終值，對遞增型循環(huán)，"超過"指大于，對遞減型循環(huán)，"超過"指小于。循環(huán)體可以是一個基本語句，也可以是一個復合語句。循環(huán)控制變量的初值和終值一經(jīng)確定，循環(huán)次數(shù)就確定了。但是在循環(huán)體內對循環(huán)變量的值進行修改，常常會使得循環(huán)提前結束或進入死環(huán)。建議不要在循環(huán)體中隨意修改控制變量的值。for語句中的初值、終值都可以是順序類型的常量、變量、表達式。應用舉例例1.輸出1100之間的所有偶數(shù)。vari:integer;beginfori:=1to100doifimod2=0thenwrite（i:5）;end.例2.求N!=

15、1*2*3*N,這里N不大于10。分析：程序要先輸入N,然后從1累乘到No程序如下：varn,i:integer；i為循環(huán)變量S:longint;s作為累乘器beginwrite（'Entern='）;readln（n）;輸入ns:=1;fori:=2tondo從2至Un累乘到s中s:=s*i;writeln（n,'!=',s）;輸出n!的值end.練習1,求s=1+4+7+-+298的值。2 .編寫一個評分程序，接受用戶輸入10個選手的得分（0-10分），然后去掉一個最高分和一個最低分，求出某選手的最后得分（平均分）。3 .用一張一元票換1分、2分和5分的硬幣

16、，每種至少一枚，問有哪幾種換法（各幾枚）？二、當型循環(huán)（while循環(huán)）對于for循環(huán)有時也稱為計數(shù)循環(huán)，當循環(huán)次數(shù)未知，只能根據(jù)某一條件來決定是否進行循環(huán)時，用while語句或repeat語句實現(xiàn)循環(huán)要更方便。while語句的形式為：while布爾表達式do語句；其意義為：當布爾表達式的值為true時，執(zhí)行do后面的語句。while語句的執(zhí)行過程為：判斷布爾表達式的值，如果其彳1為真，執(zhí)行步驟2,否則執(zhí)行步驟4;執(zhí)行循環(huán)體語句（do后面的語句）;返回步驟1;結束循環(huán)，執(zhí)彳Twhile的下一個語句。說明：這里while和do為保留字，while語句的特點是先判斷，后執(zhí)行。當布爾表達式成立時，重

17、復執(zhí)行do后面的語句（循環(huán)體）。例1、求恰好使s=1+1/2+1/3+1/n的值大于10時n的值。分析："恰好使s的值大于10"意思是當表達式s的前n-1項的和小于或等于10,而加上了第n項后s的值大于10。從數(shù)學角度，我們很難計算這個n的值。故從第一項開始，當s的值小于或等于10時，就繼續(xù)將下一項值累加起來。當s的值超過10時，最后一項的項數(shù)即為要求的no程序如下：vars:real;n:integer;n表示項數(shù)begins:=0.0;n:=0;whiles<=10do當s的值還未超過10時beginn:=n+1;項數(shù)加1s:=s+1/n;將下一項值累加到send

18、;writlen('n=',n);輸出結果end.例2、求兩個正整數(shù)m和n的最大公約數(shù)。分析：求兩個正整數(shù)的最大公約數(shù)采用的輾轉相除法求解。以下是輾轉的算法：分別用m,n,r表示被除數(shù)、除數(shù)、余數(shù)。求m/n的余數(shù)r.若r=0,則n為最大公約數(shù).若rw映行第步.將n的值放在m中,將r的值放在n中.返回重新執(zhí)行第步。程序如下：programex4_4;varm,n,a,b,r:integer;beginwrite('Inputm,n:');readln(m,n);a:=m;b:=n;r:=amodb;whiler<>0dobegina:=b;b:=r;r

19、:=amodb;end;writeln('Thegreatestcommondivideis:',b:8);end.三、直到循環(huán)(REPEATuntil循環(huán))用while語句可以實現(xiàn)"當型循環(huán)"，用repeat-until語句可以實現(xiàn)"直到型循環(huán)repeat-until語句的含義是："重復執(zhí)行循環(huán)，直到指定的條件為真時為止”。直到循環(huán)語句的一般形式：Repeat語句1;語句n;until布爾表達式;其中Repeat、until是Pascal保留字，repeat與until之間的所有語句稱為循環(huán)體。說明：repeat語句的特點是：先執(zhí)行循環(huán)

20、，后判斷結束條件，因而至少要執(zhí)行一次循環(huán)體。repeat-until是一個整體，它是一個(構造型)語句，不要誤認為repeat是一個語句，until是另一個語句。repeat語句在布爾表達式的值為真時不再執(zhí)行循環(huán)體，且循環(huán)體可以是若干個語句，不需用begin和end把它們包起來，repeat和until已經(jīng)起了begin和end的作用。while循環(huán)和repeat循環(huán)是可以相互轉化的。對于例2中求兩個正整數(shù)的最大公約數(shù)，程序可用repeat-until循環(huán)實現(xiàn)如下：varm,n,a,b,r:integer;beginwrite('Inputm,n=');readln(m,n);

21、a:=m;b:=n;repeatr:=amodb;a:=b;b:=r;untilr=0;writeln('Thegreatestcommondivideis',a);end.以上我們已介紹了三種循環(huán)語句。一般說來，用for循環(huán)比較簡明，只要能用for循環(huán)，就盡量作用for循環(huán)。只在無法使用for循環(huán)時才用while循環(huán)和repeat-until循環(huán)，而且while循環(huán)和repeat-until循環(huán)是可以互相替代的。for循環(huán)在大多數(shù)場合也能用whiel和repeat-until循環(huán)來代替。一般for循環(huán)用于有確定次數(shù)循環(huán)，而while和repeat-until循環(huán)用于未確定循環(huán)

22、次數(shù)的循環(huán)。當一個循環(huán)的循環(huán)體中又包含循環(huán)結構程序時，我們就稱之為循環(huán)嵌套。三、循環(huán)結構程序設計例3求1!+2!+10!的值。分析：這個問題是求10自然數(shù)的階乘之和，可以用for循環(huán)來實現(xiàn)。程序結構如下：forn:=1to10dobeginN!的值&累加N!的值tend顯然，通過10次的循環(huán)可求出1!,2!,10!并同時累加起來，可求得S的值。而求T=N!,又可以用一個for循環(huán)來實現(xiàn)：t=1;forj:=1tondot:=t*j;因此整個程序為：programex4_5;vart,s:real;i,j,n:integer;beginS:=0;forn:=1to10dobegint:=

23、1;forj:=1tondot:=t*j;S:=S+t;end;writeln('s=',s:0:0);end.以上的程序是一個二重的for循環(huán)嵌套。這是比較好想的方法，但實際上對于求n!,我們可以根據(jù)求出的(n-1)!乘上n即可得到，而無需重新從1再累乘到n。程序可改為：programex4_5;vart,s:real;i,j,n:integer;beginS:=0;t:=1;forn:=1to10dobegint:=t*n;S:=S+t;end;writeln('s=',s:0:0);end.顯然第二個程序的效率要比第一個高得多。第一程序要進行1+2+-+1

24、0=55次循環(huán)，而第二程序進行10次循環(huán)。如題目中求的是1!+2!+1000!,則兩個程序的效率區(qū)別更明顯。例4一個炊事員上街采購，用500元錢買了90只雞，其中母雞一只15元，公雞一只10元,小雞一只5元，正好把錢買完。問母雞、公雞、小雞各買多少只？分析：設母雞I只公雞J只，則小雞為90-I-J只，則15*I+10*J+(90-I-J)*5=500,顯然一個方程求兩個未知數(shù)是不能直接求解。必須組合出所有可能的i,j值，看是否滿足條件。這里I的值可以是0到33,J的值可以0到50。源程序如下：programrex4_6;vari,j,k:integer;beginfori:=1to5dofor

25、j:=1to8dobegink:=90-i-j;if15*i+10*j+5*k=500thenwriteln(i:5,j:5,k:5);end;end.例5、求100200之間的所有素數(shù)。分析：我們可對100200之間的每一整數(shù)進行判斷，判斷它是否為素數(shù)，是則輸出。而對于任意整數(shù)i,根據(jù)素數(shù)定義，我們從2開始，到，找i的第一個約數(shù)。若找到第一個約數(shù)，則i必然不是素數(shù)。否則i為素數(shù)。源程序如下：vari:integer;x:integer;beginfori:=100to200dobeginx:=2;while(x<=trunc(sqrt(i)and(imodx<>0)dobe

26、ginx:=x+1;end;ifx>trunc(sqrt(i)thenwrite(i:8);end;end.練習1、輸入一個正整數(shù)n,將n分解成質因數(shù)哥的乘積形式。例如：36=22*322、編寫一程序，驗證角谷猜想。所謂的角谷猜想是："對于任意大于1的自然數(shù)n,若n為奇數(shù)，則將n變?yōu)?*n+1,否則將n變?yōu)閚的一半。經(jīng)過若干次這樣的變換，一定會使n變?yōu)??！?.有一堆100多個的零件，若三個三個數(shù)，剩二個；若五個五個數(shù)，剩三個；若七個七個數(shù)，剩五個。請你編一個程序計算出這堆零件至少是多少個？一維數(shù)組一、為什么要使用數(shù)組例1輸入50個學生的某門課程的成績，打印出低于平均分的同學號

27、數(shù)與成績。分析：在解決這個問題時，雖然可以通過讀入一個數(shù)就累加一個數(shù)的辦法來求學生的總分，進而求出平均分。但因為只有讀入最后一個學生的分數(shù)以后才能求得平均分，且要打印出低于平均分的同學，故必須把50個學生的成績都保留下來，然后逐個和平均分比較，把高于平均分的成績打印出來。如果，用簡單變量al,a2,，a50存放這些數(shù)據(jù)，可想而知程序要很長且繁。要想如數(shù)學中使用下標變量ai形式表示這50個數(shù)，則可以引入下標變量ai。這樣問題的程序可寫為：tot:=0;tot表示總分fori:=1to50do循環(huán)讀入每一個學生的成績，并累加它到總分beginread(ai);tot:=tot+ai;end;ave

28、:=tot/50;計算平均分fori:=1to50doifaiavethenwriteln('No.',i,'',ai);如果第i個同學成績小于平均分，則將輸出而要在程序中使用下標變量，則必須先說明這些下標變量的整體一數(shù)組，即數(shù)組是若干個同名(如上面的下標變量的名字都為a)下標變量的集合。二、一維數(shù)組當數(shù)組中每個元素只帶有一個下標時，我們稱這樣的數(shù)組為一維數(shù)組。1、一維數(shù)組的定義(1)類型定義要使用數(shù)組類型等卞造類型以及第6章要學習的自定義類型(枚舉類型與子界類型)，應在說明部分進行類型說明。這樣定義的數(shù)據(jù)類型適用整個程序。類型定義一般格式為：type標識符1=

29、類型1;標識符2=類型2;標識符n=類型n;其中type是Pascal保留字，表示開始一個類型定義段。在其后可以定義若干個數(shù)據(jù)類型定義。標識符是為定義的類型取的名字，稱它為類型標識符。類型定義后，也就確定了該類型數(shù)據(jù)取值的范圍，以及數(shù)據(jù)所能執(zhí)行的運算。（2）一維數(shù)組類型的定義一維數(shù)組類型的一般格式：array下標1.下標2of基類型；說明：其中array和of是pascal保留字。下標1和下標2是同一順序類型，且下標2的序號大于下標1的序號。它給出了數(shù)組中每個元素（下標變量）允許使用的下標類型，也決定了數(shù)組中元素的個數(shù)?；愋褪侵笖?shù)組元素的類型，它可以是任何類型，同一個數(shù)組中的元素具有相同類型

30、。因此我們可以說，數(shù)組是由固定數(shù)量的相同類型的元素組成的。再次提請注意：類型和變量是兩個不同概念，不能混淆。就數(shù)組而言，程序的執(zhí)行部分使用的不是數(shù)組類型（標識符）而是數(shù)組變量（標識符）。一般在定義數(shù)組類型標識符后定義相應的數(shù)組變量，如：typearraytype=array1.8ofinteger;vara1,a2:arraytype;其中arraytype為一個類型標識符，表示一個下標值可以是1到8,數(shù)組元素類型為整型的一維數(shù)組；而a1,a2則是這種類型的數(shù)組變量。也可以將其全并起來：vara1,a2:array1.8ofinteger;當在說明部分定義了一個數(shù)組變量之后，pascal編譯程

31、序為所定義的數(shù)組在內存空間開辟一串連續(xù)的存儲單元。例如，設程序中有如下說明：typerowtype=array1.8ofinteger;coltype=array'a'.'e'ofinteger;vara:rowtype;b:coltype;2、一維數(shù)組的引用當定義了一個數(shù)組，則數(shù)組中的各個元素就共用一個數(shù)組名（即該數(shù)組變量名），它們之間是通過下標不同以示區(qū)別的。對數(shù)組的操作歸根到底就是對數(shù)組元素的操作。一維數(shù)組元素的引用格式為：數(shù)組名下標表達式說明：下標表達式值的類型，必須與數(shù)組類型定義中下標類型完全一致，并且不允許超越所定義的下標下界和上界。數(shù)組是一個整體，

32、數(shù)組名是一個整體的標識，要對數(shù)組進行操作，必須對其元素操作。數(shù)組元素可以象同類型的普通變量那樣作用。如:a3:=34;是對數(shù)組a中第三個下標變量賦以34的值。read（a4）;是從鍵盤讀入一個數(shù)到數(shù)組a第4個元素中去。特殊地，如果兩個數(shù)組類型一致，它們之間可以整個數(shù)組元素進行傳送。如：vara,b,c:array1.100ofinteger;beginc:=a;a:=b;b:=c;end.在上程序中，a,b,c三個數(shù)組類型完全一致，它們之間可以實現(xiàn)整數(shù)組傳送，例子中，先將a數(shù)組所有元素的值依次傳送給數(shù)組c,同樣b數(shù)組彳給a,數(shù)組c又傳送給b,上程序段實際上實現(xiàn)了a,b兩個數(shù)組所有元素的交換。對于一維數(shù)組的輸入與輸出，都只能對其中的元素逐個的輸入與輸出。在下面的應用示例中將詳細介紹。三、一維數(shù)組應用示例例2輸入50個數(shù),要求程序按輸入日的逆序把這50個數(shù)打印出來。也就是說，請你按輸入相反順序打印這50個數(shù)。分析：我們可定義一個數(shù)組a用以存放輸入的50個數(shù)，然后將數(shù)組a內容逆序輸出。源程序如下：programex5_1;typearr=ar