Множества 2012. Множество Это совокупность элементов одного порядкового типа (целого, символьного, перечислимого или диапазонного) set of 27.12.2013Чердынцева. - презентация

1 Множества 2012

2 Множество Это совокупность элементов одного порядкового типа (целого, символьного, перечислимого или диапазонного) set of Чердынцева М.И.2

3 Описание типа type ByteSet = set of Byte; CharSet = set of Char; DigitsSet = set of '0'..'9'; StringSet = set of string; // !!!! DaysSet = set of (Mon, Tue, Wen, Thr, Fri, Sat, Sun); Чердынцева М.И.3

4 Константы [1, 3..5, 8] [2..10, 12, ] [ ] ['a', 'e', 'i', 'o', 'u', 'y'] ['a'.. 'z'] Чердынцева М.И.4

5 Операции var s1,s2,s: set of byte; a:byte; q:boolean; s:=s1+s2 ; q:=s1 =s2 ; // > s:=s1-s2 ; q:=a in s1 ; q:= s1s2; q:= s1 = s2; s:= s + [a]; //s+=[a];s:= s – [a]; // s-=[a]; Чердынцева М.И.5

6 Просмотр элементов for a :=1 to 255 do // перебрать все возможные элементы if a in S then write(a,' '); foreach a in S do write(s,' '); Чердынцева М.И.6

7 Пример Ввести произвольный текст до символа точка. Напечатать все встречающиеся в нем латинские буквы в алфавитном порядке Чердынцева М.И.7

8 var s: set of char; ch:char; begin s:=[ ]; repeat read (ch); if ch in [a..z] then s:=s + [ch]; until ch =.; for ch:=a to z do if ch in s then write( ch ); end Чердынцева М.И.8

9 Пример Вывести все простые числа, меньшие Чердынцева М.И.9

10 Решето Эратосфена – реализация с использованием множества Чердынцева М.И.

11 const n=255; var primes: set of byte; i,x,c: integer; begin primes:=[2..n]; for i:=2 to round(sqrt(n)) do begin if (i in primes) then begin x:=2*i;//i оставляем 2i, 3i и т.д. вычеркиваем while x

12 Способы представления множества в памяти Логические шкалы v: set of 1..8; v:=[3,4,8]; Чердынцева М.И.12 False True False True

13 const n=1000; type MyIntSet= array [1..n] of boolean; procedure Include(var s:MyIntSet; i: integer); begin s[i]:=True end; function Intersection(const s1,s2: MyIntSet): MyIntSet; begin for i:=1 to n do Result[i]:=s1[i] and s2[i]; end; function InSet (const s:MyIntSet; a: integer): boolean; begin result := (a>=1) and (a

14 Эффективное использование памяти false = 0 true = Чердынцева М.И v: set of 1..8; v:=[3,4,8]; При мощности базового типа 256 требуется 32 байта

15 Чердынцева М.И.15 type MySet8= shortInt; // byte знаковый valSet = 1..8; function Intersection(const s1,s2: MySet8): MySet8; begin result := s1 and s2; // побитовое and end; function UnionSet (const s1,s2:MySet8): MySet8; begin result := s1 or s2; end; s s s1*s s1+s

16 Чердынцева М.И.16 procedure Include (var s:MySet8; a:valSet ); begin s := s or (1 shl 8-a); end; function InSet ( const s:MySet8; a : valSet): boolean; begin result := s shl (a-1)