Тип данных запись. Записи как состояния. Именованные декартовы произведения. Оператор присоединения. Пример описания объектов в терминах записей.

А) Запись Паскаля – структурированный комбинированный тип данных, состоящий из фиксированного числа компонент (полей) разного типа.Запись – это набор переменных N1, …,Nm, типа T1, …,Tm, воспринимаемый как единое целое. Основная операция – операция выборки, с той же семантикой, что и у массивов, но с другим синтаксисом. r.Ni, где r – переменная тип «запись», Ni – одно из имен N1, …,Nm. Комбинированные типы и записи Record N1:T1; …….. Nm:Tm; End. В) запись как состояние????? С) Значениями типа «запись» являются функцией с областью определения, состоящей из имен N1, …,Nm. Причем f(N1) Ti i = 1, …,m В математике такая конструкция называется именованном декартовым произведением. Просто декартовым произведением называется множество всех последовательностей длины m, таких, что tiTi. Например Real2=Real•Real {<t1,t2>,t1real,t2real} Понятие «запись» не вычислительное, а логическое – это описание состояния некоторого объекта. type tTochka=record x,y: real; end; {x,y – декартовы координаты точки} record ugol,radius:real; end; {полярные координаты точки } Д) Оператор присоединения Для того чтобы избежать необходимости выписывать полное точечное обозначение поля записи можно применять оператор присоединения вида: with r do s, где r – имя переменной типа «запись», а s – один оператор, в котором вместо имен вида r.Ni можно использовать имена вида Ni. Семантика: оператор эквивалентен выполнению оператора S, в котором все имена вида Ni заменены именами вида r.Ni. Е) пример описания объектов в терминах записей-???????

Вопрос 13

Множества

Множество — это структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект в множестве называется элементом множества.

Синтаксис: set of T, где Т – произвольный порядковый тип.

Семантика:

Значения типа set of T – произвольные конечные совокупности значений вида a₁, …,a_n типа Т. Рассматриваемые совокупности не считаются упорядоченными. Все множества, полученные перестановкой элементов a₁, …, a_n считаются равными.

Синтаксис констант [E₁, …, E_n], где E_i – есть выражение типа Т, либо интервалы вида Е_i¹ … E_j², где Е_i¹ … E_j² – выражение типа Т, например [2,2,1,…,7].

Прагматика: к примеру, программу пересечения, объединения, разности двух упорядоченных массивов проще написать, используя вместо массивов множества.

Пример пересечения:

 

1) [1, 2, 3, 4] * [3, 4, 5, 6] => [3, 4]

2) [‘a’..’z’]*[‘A’..’E’, ‘k’] => [‘k’]

3) [5<4, true and false] * [true] => []

 

 

Операции над множествами

1. Предикаты.

X in S ~ XÎS

S₁<=S₂ ~ S₁ S₂

2. Теоретико-множественные операции.

S₁+S₂ ~ S₁ÈS₂

S₁*S₂ ~ S₁ÇS₂

S₁-S₂ ~ S₁\ S₂

3. Эквивалентность теоретико-множественных и логических обозначений.

Любое множество однозначно связывается с формулой – характеристической формулой (предикатом множества).

F_s(x)=true(~)xÎS

Сопоставим теоретико-множественные операции, логические операции над предикатами.

x Î S ~ F_s(x) =true

S₁ S₂ ~ " x Î S₁ (x Î S₂)

x Î S₁ È S₂ ~ f_s1(x) or f_s2(x)

x Î S₁ Ç S₂ ~ f_s1(x) and f_s2(x)

x Î S₁\ S₂ ~ f_s1(x) and not f_s2(x)

 

Двойственность теории множеств и логики можно использовать для компактной записи свойств.

((x>=1)and(x<=10)) or ((x>=20)and(x<=40))

x:n[1..10]+[20..40]

 

Решето Эратосфена

Найти все простые числа меньше заданного числа n.

 

Program Eratos(input,output);

Type tNumbers=0,255;

Var n:integer;

Primes: set of tNumbers;

Numbers: set of tNumbers;

Begin

Read(n);

Numbers:=[2,n]

Primes:=[ ];

While not (p:n numbers) do p:=p+1;

P:=p+1;

While k<=n do

begin

Numbers:=numbers[k];

K:=k+p;

end;

For k:=1 to n do if k:n primes then write(k);

end.

Вопрос 14

Файлы - внутренние и внешние, общего вида и текстовые.

 

Файл — последовательный набор данных с возможностью многократного использования.

 

Внешний файл — физический (см. внешн. Память).

Внутренний файл — переменная файлового типа.

 

Текстовые файлы.

В Паскале под файлом понимается последовательный набор данных с возможностью многократного использования.

Рассмотрим частный случай текстовых файлов

text (textfile)

Имена файлов, как и имена любых других переменных, обязаны быть описаны в области Var.

Var f: text;

По стандарту все внешние входные и выходные файлы должны быть перечислены также в заголовке программы.

Семантика (упрощенная)

Множество значений типа text – последовательность значений стандартных типов integer, real, char, string.

Функции и операторы

1. assign (AssignFile) – в стандарте отсутствует

В реальном программировании естественно разделять понятия логического файла (файл как математический объект, тип данных) и физического файла (файл как набор данных на материальном носителе). Функция assign задает соответствие между логическими и физическими именами.

Assign(логическое имя файла (идентификатор, имя переменной), физическое имя файла (имя файла в синтаксисе ОС))

Пример:

Assign(f,’c:\dir\file.txt’);

2. Eof(f); Предикат конца файла. Семантика такая же, как и потоков.

3. Read(f, v1, …, vn); Write(f, e1, …, em); Семантика как для потоков.

4. Reset(f);

Подготовка (открытие) файла для чтения. Любой оператор reset предшествует любому read, то есть попытке чтения из файла f. Потоки Input и Output – не файлы, так как нельзя многократно записывать.

5. Rewrite(f);

Подготовка к режиму записи, обязан предшествовать оператору write, то есть любой попытке записи в файл f.

Операторы reset и rewrite опускаются для так называемых входных и выходных файлов input и output. Имена этих файлов также опускаются в операторах чтения и записи.

6. close(f) (CloseFile(f))

Обратный по функции оператору assign, разрывает связь между логическим и физическим файлами. Хотя по умолчанию все файлы должны автоматически закрываться после выполнения программы, лучше делать это явно.

Замечание:

Как подсказывает название, множеством значений типа text в реальности является последовательность символов произвольной конечной длины, в том числе специальных символов, так называемых маркеров конца строки и конца файла. При чтении и записи текстовых файлов происходит неявное преобразование последовательности символов в значения нужного типа. Очевидно, для этого необходимо, чтобы последовательность символов могла служить обозначением константы нужного типа.

Натуральные числа: c1…cn

ci= ‘0’,’1’,…

Вещественные числа: c1…cn.d1…dm– запись с «плавающей» точкой.

DEP – экспоненциальная запись, где D – запись с «плавающей» точкой, P – целое число. DEP = D•10P

С понятием строки связаны операторы: readln(f) – найти начало следующей строки, writeln(f) – записать символ конца строки.

readln(f,x1,…,xn) Û read(f,x1,…,xn); readln(f);

writeln(f,e1,…,en)Û write(f,e1,…,en); writeln(f);

 

Файлы общего вида.

file of T, где Т– произвольный статический тпи, кроме файла.

Семантика: последовательность компонент типа Т, произвольной длины.

Операторы: Assign (AssignFile), reset, rewrite, eof, close (CloseFile) – имеют ту же семантику. Операторы read и write имеют очевидную семантику, но другой синтаксис.

Read(f,v), где f – имя файла, v – единственная переменная типа Т.

Write(f,e), где f – имя файла, где е – единственное выражение типа Т.

Понятие строки и операции readln, writeln, eoln в этом случае не определены.

file - нетипизированный файл.

same

 

Файлы как последовательности (декартовы степени).

 

(Вики) {

Декартова степень

-я Декартова степень множества X определяется для целых неотрицательных n, как n - кратное Декартово произведение X на себя:

Обычно обозначается как X^n или X^xn.

При положительных n. Декартова степень X^n состоит из всехупорядоченных наборов элементов из X длины n. Так вещественное пространство R^3 (множество кортежей из трех вещественных чисел), есть 3 степень множествавещественных чисел R.

При n = 0, Декартова степень X^0 по определению, содержит единственный элемент — пустой кортеж.

 

Пример

 

Сравнение - массивы и файлы (на примере).

Your own example.

 

Вопрос 15

А) Упорядоченные файлы исключают недостатки использования неупорядоченных файлов. Записи в упорядоченных файлах можно отсортировать по значениям одного или нескольких полей, т.е. образовать набор данных, упорядоченный по некоторому ключу. Поле или набор полей, по которому сортируется файл, называется полем упорядочения. Если поле упорядочения является также ключом доступа к файлу, т.е. гарантирует наличие в каждой записи уникального значения этого поля, то оно называется ключом упорядочения для данного файла.