信息學(xué)奧賽輔導(dǎo)4重點

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

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

3、型是一種自定義類型，要使用枚舉類型當(dāng)然要先說明枚舉類型。枚舉類型的一般格式：type類型標(biāo)識符=（標(biāo)識符1，標(biāo)識符2,標(biāo)識符n）括號中的每一個標(biāo)識符都稱為枚舉元素或枚舉常量。它們是這種枚舉類 型的所有取值。例如，下列類型定義是合法的：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);注意：枚舉元素只能是標(biāo)識符，而不能是數(shù)值常量或字符常量。不要把此 標(biāo)識符看成變量，它不能被賦值。同一個枚舉元素不能出現(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。例如：設(shè)有定義：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。 應(yīng)注意的是：枚舉類型中的第一個元素?zé)o前趨，最后一個元素?zé)o后繼。(2) 對枚舉類型只能進(jìn)行賦值運算和關(guān)系運算，不能進(jìn)行算術(shù)運算和 邏輯運算。在枚舉羌素比較時，實際上是對其序號的比較。賦值或比較時，應(yīng)注 意類型一致。例如，設(shè)程序有如下說明：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ù)的輸入與輸出可通過間接方式進(jìn)行。輸入時，一般可輸 入一個代碼，通過程序進(jìn)行轉(zhuǎn)換，輸出時，也只是打印出與枚舉元素相 對應(yīng)的字符串。這在后面的例題中將有使用示例。3枚舉類型應(yīng)用舉例_【例4-1】一周七天用sun, mon, tue, wed, thu, fri, sa

8、t表示，要求利 用枚舉類型編程：當(dāng)輸入星期幾的數(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ù)可以進(jìn)行混合運算。 例如：設(shè)有如下說明：type typea=l. 150;Var ch:faf./ertypec=

12、l. 300:varx: typea;t: typec;z:integer;則下列語句也是合法的：Z:= xt;(x:=zt;)下列語句：t=x*z當(dāng)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 類型相容性類型相容是對參加同運算的兩個對象的類型要求。設(shè)右兩個變量，如果滿足 下列條件之一，就說這兩個變量的類型相容。(1) 兩個變量的類羽相同a兩個變量被同一類型說明。例如:vara,b:1.3O;b兩個變星的類型是同一類型標(biāo)識符。例如：vara:1.3O;c兩個變呈的類羽是不同的類型標(biāo)識符，但在類熨立義屮已經(jīng)說明兩個 標(biāo)識符相同。(2) 個變量的類型是另一個變量的子界。(3) 兩個變屋的類型都是同 基類型的子界。(4) 兩個變量的類型定基類型相容的集合類型。(5) 兩個變塑的類型是成分相同的串類型。2

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

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

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

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

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

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

21、進(jìn)行傳送。如：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ù)組的輸入與輸出，都只能對其中的元素逐個 的輸入與輸出。在下面的應(yīng)用示例中將詳細(xì)介紹。Al a2 a3a50Blb2 b50Clc2 c50數(shù)組a下標(biāo)取值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ù)組應(yīng)用示例【例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 .巴己蘭?=嚴(yán) 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練習(xí)：1.輸入50個學(xué)生的某門課程的成績，打印出高于平均 分的學(xué)生學(xué)號與成績。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】 將一個十進(jìn)制整數(shù)x轉(zhuǎn)化為二進(jìn)制。(0<x<10000) 分析：十進(jìn)制整數(shù)轉(zhuǎn)化為二進(jìn)制，采用除二取余法。有數(shù)組b來存放二進(jìn) 制數(shù)，把所得的余數(shù)依次存入bl, bbn,最后按bnb2. bl的順序輸出這些余數(shù)，得到所

26、求的二進(jìn)制數(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ù)進(jìn)行移動，第一 個數(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,且以"結(jié)束。 判斷它們是否構(gòu)成回文。分析：所謂回文指從左到右和從右到左讀一串字符的值是一 樣的，如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讀入一個字符串以''號結(jié)束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)，比它大的，則與之交換，比較結(jié)束后，則第一個數(shù)已是最大的數(shù)。同理，第二步，將第二個數(shù)與其后各個數(shù)再依次比較，又可得出次大的數(shù)。如此方法進(jìn)行比較，最后一次，將第九個數(shù)與第十個數(shù)比較，以決定次小的數(shù)。于是十個數(shù)的順序排列結(jié)束。例如下面對5個進(jìn)行排序，這個五個數(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ù)，則排序要進(jìn)行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 進(jìn)行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練習(xí):2.輸入一個由10個整數(shù)組成的序列，其中序列中任意連續(xù)三個整數(shù) 都互不相同，求該序列中所有遞增或遞減子序列的個數(shù)。例如：輸入：110 85932674輸出：6對應(yīng)的遞增或遞減子序列為:1 1010 8 55 99 3 22 6 77 4program szlx;vara:arrayl.ll of integer;izjzs:integer;beginfor