Множества. Внутреннее представление.. Механизм внутреннего представления Каждое значение базового типа представляется одним битом. В память заносится. - презентация

1 Множества. Внутреннее представление.

2 Механизм внутреннего представления Каждое значение базового типа представляется одним битом. В память заносится 1 или 0 в зависимости от того, содержит множество элемент или нет. Например, множество [2,3,5,7,11,13] представляется последовательностью при условии, что базовый тип 0..15, так как – баз. тип массив битов

3 Механизм внутреннего представления После описания переменной var m: set of и указанной ниже серии присваивания внутреннее представление будет изменяться: M:=[]; M:=[7..15]; M:=[20..25];

4 Механизм операций над множествами Операции над множествами сводятся к поразрядным логическим операциям над последовательностями битов, которые выполняются наиболее эффективно, например пересечение множеств: M:=[2,3,5,7,11,13]; N:=[1,2,3,4,5]; M*N=[2,3,5];

5 Основные операции над множествами математическая запись запись на паскале комментарий A = BA = BA=B Множества А и В совпадают A BAB Множества А и В не совпадают A B A>=B Все элементы множества В принадлежат множеству А A B A

6 Оптимизированные процедуры для работы для работы с одиночными множествами Include(A,x); - включает элемент x в множество A. Exclude(A,x ); - исключает элемент x из множества a.

7 Связь логических операций и операций над множествами x in (A+B) = (x in A) or (x in B) x in (A*B) = (x in A) and (x in B) x in (A-B) = (x in A) and not (x in B)

8 Решето Эратосфена Дано натуральное число n(n>=2). Найти все меньшие n простые числа, используя решето Эратосфена: выпишем все целые числа от 2 до n. Первое простое число 2 оставим, а все остальные кратные 2, зачеркнем. Аналогично поступим со следующим числом 3 и т. д.

9 Решение: const n=255; p:set of byte=[2..n]; var i,j:byte; begin for i:=2 to n do if i in p then begin write(i:4); for j:=i to n div i do exclude(p,j*i) end end.

10 Получить все перестановки данного множества, содержащие n элементов. В комбинаторике различные упорядоченные множества, которые отличаются лишь порядком элементов, называются перестановками. Например, перестановки множества {a,b,c} из трёх элементов имеют вид: (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a). n -элементное множество имеет n! перестановок. Uses Crt; Const n=5; TYPE M0=Set of 1..n;{n-элементное множество} Var P: Array[1..n] of Byte;{перестановки из n элементов} PROCEDURE Perest(q:byte; M:M0); Var I,j:Byte; Begin For i:=1 To n Do If I in M Then Perest(q+1,M – [i]) {рекурсивный вызов} Else Begin {вывод текущей перестановки} for j:=1 to n do Write(P[j]); {Chr(P[j]+64)} Write( :16-n){пробелы} End End; BEGIN Clrscr; Perest(1,[1..n]) ; ReadLn END.

11 Задачи обработки текста 1. Дана последовательность символов (строка). Преобразовать малые буквы латинского алфавита в большие (выполнить «подъём» регистра). Определить количество букв кириллицы в данном тексте. Const M=[А..Я,а..п,р..я,Ё,ё]; VAR s:string; i,a:integer; BEGIN WriteLn(Введите текст:); ReadLn(s); a:=0; For i:=1 To Length(s) Do Begin s[i]:=upcase(s[i]); if s[i] in M then a:=a+1; End; WriteLn(s); WriteLn(Буквы кириллицы:); WriteLn(a); END.

12 2. Дана последовательность символов (строка). Найти минимальный начальный отрезок последовательности, который содержит все символы данного текста (любой символ последовательности можно найти внутри данного отрезка)ю Малые и большие буквы алфавита считаются разными. Пример: abcbccdeabcabcdedeaaaa. Отрезок = abcbccde. Метод: просматриваем всю строку и создаём множество символов, которые входят в состав строки (M). Затем создаём пустое множество M1 и добавляем к нему по одному символу, начиная с первого символа строки. Если при очередном добавлении мы получим множество, равное M, то отрезок строки найден. Если мы достигли конца строки, то левая часть строки с эквивалентным множеством символов отсутствует.

13 VAR s:string; M,M1: set of char; i:integer; BEGIN WriteLn(Введите текст:); ReadLn(s); M:=[ ]; FOR i:=1 To Length(s) Do M:=M + [s[i]]; M1:=[ ]; i:=1; REPEATM1:=M1 + [s[i]];inc(i); UNTIL M+M1; If i>length(s) Then WriteLn(); Else WriteLn(copy(s,1,i-1)) END.

14 Дана строка из строчных латинских букв. Напечатать первые вхождения букв в текст, сохраняя их исходный взаимный порядок.

15 program mgtu_mn1; uses crt; Type mn=set of char; Var s:mn; i,k:integer; st:string[50]; begin clrscr; s:=[]; write('vvod stroki:'); readln(st); k:=ord(st[0]); for i:=1 to k do if not(st[i] in s) then begin s:=s+[st[i]]; writeln('st[i]=',st[i]); end; readln; end.

16 Дана строка из строчных латинских букв. Напечатать в алфавитном порядке все буквы, входящие в текст не менее двух раз.

17 program mgtu_mn2; uses crt; Type mn=set of char; Var s,s1:mn; ch:char; i,k:integer; st:string[50]; begin clrscr; s:=[]; write('vvod stroki:'); readln(st); k:=ord(st[0]); for i:=1 to k do if not(st[i] in s) then s:=s+[st[i]] else s1:=s1+[st[i]]; for ch:='a' to 'z' do if ch in s1 then writeln('st[i]=',ch); readln; end.

18 Вводятся натуральное число. Выписать в возрастающем порядке все цифры, не входящие в запись данного числа.

19 program mgtu_mn4; uses crt; Type mn=set of 0..9; Var s:mn; c:byte; i,k:integer; n:word; begin clrscr; s:=[]; write('vvod chislo:'); readln(n); while n>0 do begin c:=n mod 10; if not(c in s) then begin s:=s+[c]; k:=k+1;end; n:=n div 10 end; for i:=0 to 9 do if i in s then writeln('c=',i); writeln('k=',k); readln; end.