第五章第三節(jié)集合類型

1、第三節(jié)集合類型Pascal系統(tǒng)把具有共同特征的同一有序類型的對象匯集在一起,形成一個集合,可將集合類型的所有元素作為一個整體進行集合運算。例5.11用隨機函數(shù)產(chǎn)生20個互不相同的40到100的隨機整數(shù),然后按從小到大順序打印。解:按以下步驟處理:為使產(chǎn)生的隨機整數(shù)互不相同。因此,每產(chǎn)生一個數(shù),都要判斷集合中已否包含,如果沒有包含,就放到集合中,并統(tǒng)計個數(shù),直到20個。將集合中的數(shù)移到數(shù)組中,此題利用下標序號從小到大的特征進行映射排序打印。Pascal程序:Program Exam511;Uses Crt ;Var a: Array40.100 Of boolean;dd: set Of 40.

2、100; 定義集合ddn: Integer;Procedure Init; 定義產(chǎn)生并處理隨機數(shù)的過程Var i,m: Integer;Beginn:=0;dd:= ; 集合dd初值為空repeatbeginRandomize; 將隨機發(fā)生器作初始化處理m:=Random(100; 產(chǎn)生隨機整數(shù)mif not (m in dd and (m 40 thenbegindd:=dd+m; inc(n 把m放入集合dd中end;enduntil n=20;End;Procedure Print; 定義打印過程Var i,j,k:Integer;Beginfillchar(a,sizeof(a,fal

3、se; 將數(shù)組a的各元素置false值For i:=40 To 100 Doif i in dd then a i :=true; 以集合元素值為下標的數(shù)組元素賦真值For i:=40 To 100 Do 以下標號為序(從小到大輸出If a i Then Write(i:4; 輸出a數(shù)組中元素值為真的下標號End;Begin 主程序Clrscr;init; 產(chǎn)生隨機數(shù),并存入集合中print; 打印Repeat Until KeyPressed;End.程序中定義了集合類型DD,集合的元素為子界類型。定義集合類型的一般格式是:集合的值放在一對方括號中,各元素用逗號隔開,與排列的順序無關(guān),因此,

4、9,2,5和2,5,9的值相等,沒有任何元素的集合是空集合,用 表示。如果集合的元素是連續(xù)的,可用子界表示,如5,6,7,8,9可表示為5 . 9 。集合的賦值格式為: Array集合有以下幾種運算:1.集合的交、并、差運算:(設(shè)兩個集合 a:=1,2,4,6 和 b:=4,6,7,8 集合的并: a+b即組合成新的集合(為1,2,4,6,7,8;集合的交: a*b即將a,b集合中的公共元素組合成新的集合(為4,6,;集合的差: a-b即在a中的元素去掉在b中出現(xiàn)的之后,所剩下的集合(為1,2。2.集合的比較:相等:a=b,若兩個集合中的元素個數(shù)相等,每個元素相同,則兩個集合相等,比較結(jié)果為真

5、(ture,否則為假(false;不等:a b表示兩個集合不相等;包含:a = b表示a集合包含b集合中的所有元素;a = b表示a集合是b集合的子集。3.集合的測試運算:檢查某個數(shù)據(jù)在集合中,測試結(jié)果為ture;不在集合中,測試結(jié)果為false;例如:6 in 8,6,9,4 結(jié)果為ture; 6在集合8,6,9,4中為真 2 in 8,6,9,4 結(jié)果為false; 2在集合8,6,9,4中為假 從程序Exam511的輸出部分可看到,集合類型的值不能直接輸出,要用測試方法進行輸出或轉(zhuǎn)換成數(shù)組元素的值。例5.12用集合進行篩法求200以內(nèi)的素數(shù)。解:將2.200放入集合S中;取S中的第一個元

6、素值nxt,放入集合P中,同時將S中的凡是nxt的倍數(shù)的元素全部“劃”去;重復(fù)步驟,直至S集合為空;用測試運算打印P集合中全部元素值。Pascal程序:Program Exam512;Uses crt;const n=200;var s,p: set of 2.n; s,p為集合類型nxt,j,t: byte;beginclrscr;s:=2.n; 將2.n賦給sp:= ;nxt:=2; t:=0;repeatwhile not(nxt in s donxt:=succ(nxt; 后繼函數(shù)p:=p+nxt; j:=nxt; 將nxt放入P中while j=n dobegins:=s-j; in

7、c(j,nxt 篩掉S中的處理過的元素end;if nxt in p then 用測試運算進行輸出begininc(t; write(nxt :6;if t mod 6=0 then writelnend;until s= ;readlnend.集合內(nèi)的元素個數(shù)不能超過255個,如果要用超過255個成員的集合類型求素數(shù),必須用小集合的數(shù)組來表示大集合,即把大集合分成若干個小集合,每個小集合只是數(shù)組的元素,(數(shù)組元素為一個小集合整個數(shù)組就是一個大集合。篩法運用在每個數(shù)組元素(小集合中進行。例5.13將自然數(shù)1-9這九個數(shù)分成三組,將每組的三個數(shù)字拼成為三位數(shù),每個數(shù)字不能重復(fù),且每個三位數(shù)都是完

8、全平分數(shù)。請找出這樣的三個三位數(shù)。解:自定義函數(shù)yes,用集合判定九個數(shù)字是否有重復(fù),采用逆向思維,假設(shè)做鄧了三個三位完全平方數(shù):將三個三位完全平方數(shù)分離成單個數(shù)字放入集合dd中,檢查集合dd,如果自然數(shù)19每個數(shù)恰好都在集合dd中,函數(shù)yes賦真(ture;只要有一個不在集合中,九個數(shù)字沒有占完集合中的九個位置,則必有重復(fù),函數(shù)值為假(false,因為集合中對相同數(shù)字視為同一成員,如果有重復(fù),則集合中不足9個成員(用測試運算。程序用1131平方產(chǎn)生三位的完全平方數(shù)。用循環(huán)方式每次取三個數(shù)為一組,存入a數(shù)組。對a數(shù)組的三位數(shù)調(diào)用自定義函數(shù)yes處理;如果函數(shù)yes值為真,就打印a數(shù)組中的三個數(shù)

9、。Pascal程序:Program exam513;Uses Crt;Var a: Array1.3 Of Integer;i, j, k, x: Integer;Function yes: Boolean; 處理是否有重復(fù)數(shù)字Var i: Integer;d: Set Of 0 . 9; 集合元素為子界類型Begind:= ; 集合的初值為空集合For i:=1 To 3 Do 將a數(shù)組中三個數(shù)分離成單個數(shù)并放入集合dd:=d+a i Div 100, (a i Mod 100 Div 10, a i Mod 10;yes:=true;For i:=1 To 9 DoIf Not ( i I

10、n d Then yes:=false; 只要有一個不在集合中即為假End;Beginwriteln;for i:=11 to 29 do 在三位完全平方數(shù)范圍內(nèi)循環(huán)推出三個數(shù)Begina1:=i*i; 第一個三位的完全平方數(shù)for j:=i+1 to 30 dobegina2:=j*j; 第一個三位的完全平方數(shù)for k:=j+1 to 31 dobegina3:=k*k; 第一個三位的完全平方數(shù)If yes Then 調(diào)用自定義yes函數(shù)結(jié)果為真就輸出For x:=1 To 3 Do Writeln( x:8, :, ax:8 ;endendend;Repeat Until KeyPressed;End.習(xí)題5.31.設(shè)計一個將十六進制數(shù)轉(zhuǎn)換為十進制數(shù)的程序。2.將自然數(shù)1-9數(shù)字不重復(fù)組成三個三位數(shù),且三個數(shù)之比為123。求出能滿足條件的全部方案。3.從鍵盤輸