信息學奧賽輔導4重點

1、信息學奧賽輔導初級湖中吳第四章枚舉類型和子界類型在前面我們已經(jīng)學習了整型.實型.布爾型、字符型等數(shù)據(jù)類型, 它們都是pascal規(guī)定的標準數(shù)據(jù)類型，pascal編譯系統(tǒng)能識別并 按這些類型來處理。pascal還允許用戶自定義一些類型，這使 pascal使用靈活.功能豐富。這些自定義的數(shù)據(jù)類型在使用之前必 須先定義類型名。類型定義的語法格式： type類型名1二自定義類型; 類型名2二自定義類型;類型名n=自定義類型；其中type是Pascal保留字，表示開始一個類型定義段。在其后可以定 義若干個數(shù)據(jù)類型定義。類型g是用戶自定義的標識符，稱它為類型標 識符。類型定義后，也就確定了該類型數(shù)據(jù)取值的

2、范圍，以及數(shù)據(jù)所能執(zhí)行 的運算。用戶定義的類型應在說明部分進行類型說明。這樣定義的數(shù)據(jù)類型 適用整個程序。var變量名：類型名；本章我加學習用A自定義的簡單數(shù)據(jù)類型：枚舉類型和子界類型。4. 1枚舉類型隨著計算機的不斷普及，程序不僅只用于數(shù)值讓算，還更廣泛地用于處 理非數(shù)值的數(shù)據(jù)。例如，性別.月份.星期幾.顏色、單位名.學歷.職業(yè)等，都不是數(shù)值數(shù)據(jù)。在其它程序設計語言中，一般用一個數(shù)值來 代表某一狀態(tài)，這種處理方法不直觀，易讀性差。如果能在程序中用自 然語言中有相應含義的單詞來代表某一狀態(tài)，則程序就很容易閱讀和理 解。這種方法稱為枚舉方法，用這種方法定義的類型稱枚舉類型。1枚舉類型的定義枚舉類

3、型是一種自定義類型，要使用枚舉類型當然要先說明枚舉類型。枚舉類型的一般格式：type類型標識符=（標識符1，標識符2,標識符n）括號中的每一個標識符都稱為枚舉元素或枚舉常量。它們是這種枚舉類 型的所有取值。例如，下列類型定義是合法的：type days= (sun, mon, tue, wed, thu, fri, sat); colors=(red, yellow, blue, white, black, green);定義了枚舉類型，就可以把某些變量說明成該類型。如： var holiday, workday:days;oncolor:colors;也可以把變量的說明與類型的定義合并在一起

4、，如：var holiday, workday: (sun, mon, tue, wed, thu, fri, sat); oncolor: (red, yellow, blue, white, black, green);注意：枚舉元素只能是標識符，而不能是數(shù)值常量或字符常量。不要把此 標識符看成變量，它不能被賦值。同一個枚舉元素不能出現(xiàn)在兩個或兩個 以上的枚舉類型定義中。下列類型定義是錯誤的： ，例1： type colortype=(, red",' yellow',' blue'); numbers=(l, 2, 3, 5, 9);例2： ty

5、pe colortypel=(red, yellow, blue); colortype2=(red, yellow, white);2. 枚舉類型的性質(zhì)(1) 枚舉類型屬于順序類型，根據(jù)定義類型時各枚舉元素的排列順序 確定它們的序號，第一個枚舉元素的序號為0。例如：設有定義：type days= (sun, mon, tue, wed, thu, fri, sat);則：ord (sun) =0, ord (mon)=l, ord (sat) =6; succ (sun) =mon, succ (mon) =tue, succ (fri)=sat; pred (mon) =sun, pred

6、 (tue) =mon, pred (sat) =fri。 應注意的是：枚舉類型中的第一個元素無前趨，最后一個元素無后繼。(2) 對枚舉類型只能進行賦值運算和關系運算，不能進行算術運算和 邏輯運算。在枚舉羌素比較時，實際上是對其序號的比較。賦值或比較時，應注 意類型一致。例如，設程序有如下說明：type days= (sun, mon, tue, wed, thu, fri, sat); colors=(red, yellow, blue, white, black, green);var color:colors;weekday:days;則下列比較或語句是合法的：weekday:=mon;

7、if weekday=sun then writeC rest"):weekdayOsun(3) 枚舉變量的值只能用賦值語句來獲得。也就是說，不能用read(或 readln)讀一個枚舉型的值。同樣，也不能用write (或writein)輸出一 個枚舉型的值。如write (blue)是非法的，會發(fā)生編譯錯誤。但對枚舉數(shù)據(jù)的輸入與輸出可通過間接方式進行。輸入時，一般可輸 入一個代碼，通過程序進行轉(zhuǎn)換，輸出時，也只是打印出與枚舉元素相 對應的字符串。這在后面的例題中將有使用示例。3枚舉類型應用舉例_【例4-1】一周七天用sun, mon, tue, wed, thu, fri, sa

8、t表示，要求利 用枚舉類型編程：當輸入星期幾的數(shù)字，能輸出它的后一天是星期幾 (也用英文表示)。分析：用變量day. sue day分別表示今天.明天。參考程序：program ex4_l;var(sun, mon, tue, wed, thu, fri, sat);i : integer; day, sucday :begincase sucday ofsun:writeInC Sunday); mon:writeln(，monday1); tue:writeln(，tuesday1); wed:writeln(，Wednesday1); thu:writeinthursday1); fri

9、:writeinC friday1); sat:writeln(，Saturday1); end; end.write ('What date is it') ;readln(i); case i of 根據(jù)輸入i轉(zhuǎn)換成枚舉型 1:day:=mon;2:day:=tue;3:day:=wed;4:day:=thu;5:day:=fri;6:day:=sat;7:day:=sun;end;計算明天sucdayif (day=sat) then sucday:=sun else sucday:=succ(day);輸出啓天是星期幾,write ('The next day

10、is ');4. 2子界類型如果我們定義一個變量i為integer類型，那么在pascal語言中i的取值范圍 為-3276832767。而事實匕 每個稈序中所用的變最的值都有一個確定的范圍。 例如，人的年齡一般不超過150, 年中的月數(shù)不超過12, 月中的天數(shù)不超過 3b等等。如果我們能在程序中對變量的值域作具體規(guī)定，就便于檢査出那些不 合法的數(shù)據(jù)。而且在一定程度上還會節(jié)省內(nèi)存空間。子界類型就幫助我們解決了如上問題。1.子界類型定義子界類型的一般格式：type子界類型名二常量1> <常量2>說明：其中常量1稱為子界的下界，常量2稱為子界的上界。下界和上界必須是同一順序

11、類型，且上界的序號必須大于下界的序號。下界 和上界所屬的類型稱為子界類型的基類型?？梢灾苯釉谧兞空f明中定義子界類型。如：type day=l. 31;var dayl, day2:day;可以合并成：var dayl, day2: 131;2.子界類型數(shù)據(jù)的運算規(guī)則(1)對基類型的運算規(guī)則同樣適用于該類型的子界類型。 例如，前面例子中的dayl, day2可以參與整型數(shù)據(jù)的一切運算。day 1: =3+10;dayl :=30 div 7:等等。(2)基類型相同的不同子界類型數(shù)據(jù)可以進行混合運算。 例如：設有如下說明：type typea=l. 150;Var ch:faf./ertypec=

12、l. 300:varx: typea;t: typec;z:integer;則下列語句也是合法的：Z:= xt;(x:=zt;)下列語句：t=x*z當X*Z的值在1二300范圍內(nèi)時是合法的，否則會出錯。例3按月.日.年順序讀入一日期，輸出該日期是這一年中的第幾天。program date;var year: 1900.5010;month4：1.12;day:1.31;dayth:integer;beginread(month,day,year); 4/20/2010 dayth:=O;for i:=l to monthdocase i of1,3,5,7,8,1042:dayth :=day

13、th+31;2:if (year mod 4=0)and(year mod 100<>0)or(year mod 400 =0) then dayth:=dayth+29 else dayth=:=dayth+28;4,6,9,11:dayth:=dayth+30;end;dayth:=dayth+day;writeln(dayth)end.1. 交換兩個變量引b的值。Var azb,c:integer;C:=a; a: = b; b:=c;2、累加器s=：l + 2+3+1000s：=o；For I: = l to 1000 do S:=s+I;3、累c=l*2*3*.*55C:

14、 = l;For I: = l to 55 doC:=c*I;四.類型相容和賦值相容1 類型相容性類型相容是對參加同運算的兩個對象的類型要求。設右兩個變量，如果滿足 下列條件之一，就說這兩個變量的類型相容。(1) 兩個變量的類羽相同a兩個變量被同一類型說明。例如:vara,b:1.3O;b兩個變星的類型是同一類型標識符。例如：vara:1.3O;c兩個變呈的類羽是不同的類型標識符，但在類熨立義屮已經(jīng)說明兩個 標識符相同。(2) 個變量的類型是另一個變量的子界。(3) 兩個變屋的類型都是同 基類型的子界。(4) 兩個變量的類型定基類型相容的集合類型。(5) 兩個變塑的類型是成分相同的串類型。2

15、賦值相容性賦值相容是對賦值操作的兩個對象的類型要求。設賦值語句“：="左邊的變 量類型為T,右邊表達式的類型為E若類型T和類型E, T:二E滿足下列條件之一，則 稱他們是賦值相容的。(1) T和E是相同的類等打 而且類中不是文件類空，也不是具有義件類成分的構造 類烈。(2) T是實熨，而E是榕型或榕型的子界。(3) T和E是類型相容的順序類空，并J1E的值不超出T所疋義的值的范圍(4) T和E是類型相容的集合類型，并且E的值不超出T所怎義的值的范圍(5) T和E是類型相容的串類世°當T和E是順序類型或都是集合類世時，不僅要求這兩個類空是相容的，而且要 求E的值不超出T所逕義

16、的值的范圍；否則將產(chǎn)生類型溢出，而這種錯誤只能在你運 行程序時進行檢含，因此你必須要避免不發(fā)生這種錯誤。第五章數(shù)組類型我們已經(jīng)學習了 pascal語言中所有的簡單 數(shù)據(jù)類型。本章開始學習結構型的數(shù)據(jù)類型。 數(shù)組是pascal結構類型中用途很廣的一種。例如：輸入50個學生的某門課程的成績，打印出低于平均分的同學號數(shù)與 成績。分析：在解決這個問題時，如果用簡單變量al, a2,，a50存放這些數(shù)據(jù)， 可想而知程序要很長且繁。要想如數(shù)學中使用下標變量ai形式表示這50個數(shù), 則可以引入下標變量ai,即用數(shù)組來表示。這樣問題的程序可寫為：const n=50var a:arrayL n of inte

17、ger;begintot: =0; tot表示總分for i:=l to 50 do 循環(huán)讀入每一個學生的成績，并累加它到總分 beginread(ai);tot:=tot+ai;end;ave:=tot/50; 計算平均分for i:=1 to 50 doif ai<ave then writeinCNo> i,1 r, ai); 如果第i個同學成績小 于平均分，則將輸出End.數(shù)組，即數(shù)組而要在程序中使用下標變量，則必須先 說明這些下標變量的整體 是若干個同名下標變量的集合。如：上面的 下標變量的名字都為a o這里引用的下標變量a i 來表示a數(shù)組 中的一個元素，方括號中的i稱

18、為下標。i表 示下標變量在數(shù)組中的位置。5. 1 一維數(shù)組當數(shù)組中每個元素只帶有一個下標時，我們稱這 樣的數(shù)組為一維數(shù)組。1. 一維數(shù)組的定義 一維數(shù)組類型的一般格式：type藪組類型名=array 下標類型of基類型;說明：其中array和of是pascal保留字。下標類型是 順序類型，通常用子界類型或枚舉類型。下標類型 的作用是指定了下標的取值范圍和下標的編制方式?；愋褪侵笖?shù)組元素的類型，它可以是任何類型, 同一個數(shù)組中的元素具有相同類型。一般在定義數(shù)組類型標識符后定義相應的數(shù)組變量，如： type student二array160of integer;var al, a2： stude

19、nt;其中student為一個類型標識符，表示一個下標值可以是1到 60,數(shù)組元素類型為整型的一維數(shù)組；而al, a2則是這種類型 的數(shù)組變量。也可以將其合并起來；var al, a2:array160of integer;組也可以使用常量，其定義方式如下:當在說明部分定義了一個數(shù)組變量之后,pascal編譯程序為 所定義的數(shù)組在內(nèi)存空間開辟一串連續(xù)的存儲單元。all al2al60Const ha: array 1. 5 of integer= (3, 11, 5, 18, 9); 相當于定義數(shù)組元素：hal=3, ha2=ll, ha3=5, ha4=l8, ha5 =92. 數(shù)組元素的引

20、用當定義了一個數(shù)組，則數(shù)組中的各個元素就共用一個數(shù) 組名(即該數(shù)組變量名)，它們之間是通過下標不同來區(qū)分 的。對數(shù)組的操作就是對數(shù)組元素的操作。一維數(shù)組元素的引用格式為：數(shù)組名下標表達式 說明： 下標表達式值的類型，必須與數(shù)組類型定義中下標類型完 全一致，并且不允許超過所定義的下標下界和上界。 數(shù)組是一個整體，數(shù)組名是一個整體的標識，要對數(shù)組進 行操作，必須對其元素操作。數(shù)組元素可以象同類型的普通 變量那樣作用。如:al：二67;是對數(shù)組al中第6個下標變量賦以67的值。read (al 7);是從鍵盤讀入一個數(shù)到數(shù)組al第7個元素中去。特殊地，如果兩個數(shù)組類型一致，它們之間可以整個數(shù)組 元素

21、進行傳送。如：var a, b, c:arrayT1. 501 of integer;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ù)組的輸入與輸出，都只能對其中的元素逐個 的輸入與輸出。在下面的應用示例中將詳細介紹。Al a2 a3a50Blb2 b50Clc2 c50數(shù)組a下標取值1到50,Var a:array1.5O of integer; I:integer;Be

22、ginFor I: = l to 50 do read(ai); For I: = l to 50 do write(aizr End.3. 一維數(shù)組應用示例【例5-1】 輸入15個數(shù)，要求程序按輸入時的逆序把這15個 數(shù)打印出來。也就是說，請你按輸入相反順序打印這15個數(shù)。 分析：我們可定義一個數(shù)組a用以存放輸入的15個數(shù)，然后 將數(shù)組a內(nèi)容逆序輸出。參考程序：說明一數(shù)組類program ex5_l;type arr=array1.50of integer;型 arrjvar a:arr; i:integer;beginfor i :=1 to 15 do read(ai) ； 從鍵盤上 輸

23、入15個整數(shù)分別存入到al至a15中for i :=15 down to 1 do 逆序輸出這15個數(shù) write(ai,r 9;end.2. var i> j, h, m, n, k： integer； N=1244b : array 1. 10 of integed訂2 .巴己蘭?=嚴 beginreadln(n)；廠 for i:=1 tobeginm： =n； j：r while m>0I begin j：=j-l； bj:二m mod 10； m:=m div 10 end； for h:=j to 10 doJ end；writeln(n)；end.輸入123410 d

24、o二 11；do 高精度分解輸出J = 10 b10=4 m=124 j=9 b9=4 m=12 j=8b8 = 2 m=lJ = 7 b7 = l m=0 n=1244+l+2+4+4=12 5n:=n+bh; 數(shù)位累加N=12341=1 m=1234 j=llJ = 10 b10=4 m=123 j=9 b9 = 3 m=12 j=8b8 = 2 m=lJ=7 b7 = l m=0 n=1234+l+2+3+4=1244練習：1.輸入50個學生的某門課程的成績，打印出高于平均 分的學生學號與成績。program szlx;var a:array1.51 of integer;totzi:

25、integer; ave:real;beginfor i: = l to 50 do read(ai); tot:=0;for i: = l to 50 do tot:=tot+ai; ave:=tot/50;for i: = l to 50 doif ai>ave then writeln('No.'zi/ ',ai); end【例5-3】 將一個十進制整數(shù)x轉(zhuǎn)化為二進制。(0<x<10000) 分析：十進制整數(shù)轉(zhuǎn)化為二進制，采用除二取余法。有數(shù)組b來存放二進 制數(shù)，把所得的余數(shù)依次存入bl, bbn,最后按bnb2. bl的順序輸出這些余數(shù)，得到所

26、求的二進制數(shù)。參考程序：x, k, i : integer;21program ex5_3(input, output); Var b:array1. 30 of 0l; beginreadln(x);for i:=1 to 30 do bi:=0; k:=l;while x>0 dobeginbk :=x mod 2; x:=x div 2;k:=K+l;end;for i:=k-l downto 1 do write(bi); writein;end.參考程序：program ex5_3 (input, output);Var b:array1. 10 of 0. 7; x, k,

27、i:integer; beginreadln(x);for i:=1 to 10 do bi :=0;k:=l;while x>0 dobeginbk :=x mod 8;x:=x div 8;k:=K+l;end;for i:=k-l downto 1 do write(bi);writein; end.參考程序：program ex5_4(input, output); const n二20;vara:array1n of integer; i,p:integer;beginfor i:=lP：=a1;for i:=l an:二p; for i:=1end.tototonl do a

28、i：=aI+l;n do write(ai:5);【例5-4】將用一維數(shù)組依次存放的20個數(shù)進行移動，第一 個數(shù)值移動到最后一個數(shù)組變量，其余數(shù)據(jù)依次往前移動一 個位置。1034567891011參考程序：program ex5_4(input, output);const n=20;vara：array1n of integer;i,p：integer;beginfor i:=1 to n do read(ai);P：=an;for i:=n downto 2 do ai:=aI-l;al ：=p;for i:=1 to n do write(ai:5);end.1 |o |3 |4 |5

29、6|8 |91. varu: array 0.3 of integer;a, b, c, x, y, z: integer;beginread(uO, ul, u2, u3);a := ufOl + ul + u2 + u3 - 5;b := u0 * (ul - u2 div u3 + 8);c := u0 * ul div u2 * u3;x := (a + b + 2) * 3 - u(c + 3) mod 4;y := (c * 100 - 13) div a div (ub mod 3 * 5);if(x+y) mod 2 = 0) then z := (a + b + c + x

30、+ y) div 2; z := (a + b + c x y)*2;writeln(x + y - z);end輸入：2574輸出：o【例5-5】輸入一串字符，字符個數(shù)不超過100,且以"結束。 判斷它們是否構成回文。分析：所謂回文指從左到右和從右到左讀一串字符的值是一 樣的，如12321, ABCBA,AA等。先讀入要判斷的一串字符（放 入數(shù)組letter中），并記住這串字符的長度，然后首尾字符 比較，并不斷向中間靠攏，就可以判斷出是否為回文。Letl .letk 幺ABCBA12345211=1JJ=kaccaRSt5：program ex5_5;ABCS BA.varJ Il

31、etter : array1. 100of char;i, j: 0.100; ch: char;begini-=0(rh)while chO*.' 'do讀入一個字符串以''號結束begini:=i+l; letteri :=ch;read (ch)end;判斷它是否是回文j：=l；while (j<i)and(letteri= letterj )do begini:=i-l;j:=j+l;end;if j>=ithen writelnC Yes.')else writeln(*No')；end.VAR I,J,L,N,K,S,T:

32、INTEGER; B:ARRAY1.1O OF 0.9; BEGINREADLN(L,N); S:=L; K:=l; T:=L;IF N>L THEN BEGINWHILE S<N DOBEGIN K:=K+1;T:=T*L;S:=S+T END; S:=S-T;N:=N-S-1;FOR I:=l TO 10 DO BI:=0;J：=ll;WHILE N>0 DOBEGIN J:=J-1;BJ:=N MOD L;N:=N DIV L END;FOR I:=10-K+l TO 10 DO WRITE(CHR(ORD( A )+BI); READLN;ENDELSE WRITEL

33、NCCHRfORDC A RN-l)END輸入： 4167輸出：【例5-6】 輸入十個正整數(shù)，把這十個數(shù)按由大到小的順序 排列。將數(shù)據(jù)按一定順序排列稱為排序，排序的算法有很多，其中 選擇排序是一種較簡單的方法。分析：要把十個數(shù)按從大到小順序排列，則排完后，第一個數(shù)最大，第二個數(shù)次大,因此，我們第一步可將第一個數(shù)與其后的各個數(shù)依次比較，若發(fā)現(xiàn)，比它大的，則與之交換，比較結束后，則第一個數(shù)已是最大的數(shù)。同理，第二步，將第二個數(shù)與其后各個數(shù)再依次比較，又可得出次大的數(shù)。如此方法進行比較，最后一次，將第九個數(shù)與第十個數(shù)比較，以決定次小的數(shù)。于是十個數(shù)的順序排列結束。例如下面對5個進行排序，這個五個數(shù)分

34、別為8 2 910按選擇排序方法，過程如下：10 2 9 8 5初始數(shù)據(jù):829105第一次排序：829105928105FOr I: = l to n-1 do102895begin k: = I;102895for j: = I+l to n do第二次排序：108295If ak<aj then109285k：=j；109285If koi then第三次排序：109825begin t：=ai;109825ai:=ak;第四次排序：109852ak:=t;對于十個數(shù)，則排序要進行9次。End;參考程序：program ex5_6;var a:array1. 1002of inte

35、ger;i, j, t: integer;beginreadln(n);for i :=1 to n do read(ai):for i:=1 to n-1 dofor j:= 1+1 to n do 將第i個數(shù)與其后所有數(shù)比較 if ai>aj then 若有比ai大,則與之交鎮(zhèn) begint:=ai ;ai :=aj: aj :=t; end;for i:=1 to n do write(ai:5):writein;end.F 為甜:program ex5_6;var a:array1. 1002of integer;i, j, t, k, n: integer;begin read

36、ln(n);for i :=1 to n do read(ai): 讀入n個初始數(shù)據(jù) for i :=1 to nl do 進行nT 次排序 begink:=I;for j:= 1+1 to n do 將第k個數(shù)與其后所有數(shù)比較 辻 ak <aj then k:=j;辻 I>k thenbegin t:=ai : ai :=ak ; ak :=t;end;end;for i :=1 to n do write(ai :5):writein;end.2.Program ex302; const m:array0.4 of integer=(2z3/5z7z13); varizj: i

37、nteger; t: longint; begin for i:=0 to 4 dobegint: = l;for j: = l to mi-l do t:=t*2;t: = (t*2-l)*t; write (t/ f); end;writein; end.輸出:6 28 496 8128 33550336N,23 ,4,6,8,1/20,25A1an const n = 10000;Var a:arrayl.n of integer; Izj練習:2.輸入一個由10個整數(shù)組成的序列，其中序列中任意連續(xù)三個整數(shù) 都互不相同，求該序列中所有遞增或遞減子序列的個數(shù)。例如：輸入：110 85932674輸出：6對應的遞增或遞減子序列為:1 1010 8 55 99 3 22 6 77 4program szlx;vara:arrayl.ll of integer;izjzs:integer;beginfor