Основы программирования — второй семестр 08-09

Файлы

Введение

Файл — именованная область на диске, содержащая некоторую информацию.

Преимущества:

1. Хранят данные в промежутках между запусками программ.
2. Размер данных в файле может существенно превышать оперативную память компьютера.

Классификация файлов

Файлы обычно классифицируют по двум признакам:
1. По типу компонент:

• текстовые;
• двоичные:

типизированные;

бестиповые.

2. По способу доступа:

• последовательный;
• произвольный.

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

Тип text. Состоят из строк переменной длины, в конце каждой из которых находится символ перехода на новую строку (#13#10 в Windows, #10 в Linux). В PascalABC.NET это константа NewLine.

Двоичные файлы: информация хранится в виде двоичного кода.

Типизированные файлы

Тип file of <type>. Содержат данные фиксированного типа <type>.

Бестиповые файлы

Тип file. Могут хранить данные различных типов.

В двоичных файлах информация хранится в том виде, как она хранится в оперативной памяти, а в текстовых числовая информация преобразуется к строковому виду и обратно, что занимает больше времени.

Файл называется

файлом произвольного доступа, если можно перейти к его i-му элементу за время, не зависящее от размеров файла («за константное время»),

файлом последовательного доступа, если переход к i-му элементу требует количество операций, пропорциональное i («требует линейного времени»).

Все файлы, содержащие элементы разного размера могут иметь только последовательный доступ к элементам. Таковыми являются:

• текстовые,
• бестиповые файлы.

Типизированные файлы имеют произвольный доступ.

Понятие файловой переменной, файлового указателя

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

Закрытый файл можно:

• переименовывать
• перемещать
• копировать
• удалять

С каждым открытым файлом связан так называемый файловый указатель, который указывает на текущую позицию в файле.
Файловый указатель создается при открытии файла, и, как правило, устанавливается на 1й элемент файла.
После каждой операции чтения или записи файловый указатель продвигается вперед на размер считанных элементов.

Паскаль-программа

var f: file of integer;
begin
  Assign(f, 'a.dat');
    {связывает файловую переменную f с файлом на диске 'a.dat'
    (файл на диске может отсутствовать)}
  
  //файл состоит из элементов (1, 2, 3)
  Reset(f);               //файловый указатель — на элемент "1"
  
  var x: integer;
  read(f, x);             //x = 1
                          //файловый указатель — на элемент "2"
  
  write(f, x + 4, 666);   //теперь файл состоит из элементов (1, 5, 666)
                          //файловый указатель — за концом файла

  {выполнить read(f, x) НЕЛЬЗЯ, т.к. произойдет
   ошибка времени выполнения
   "чтение за концом файла"}
  write(f, 777);          //можно
  
  Close(f);
end.

2 способа открытия файла

1. Reset(f) — открытие текстового файла на чтение, а двоичного — на чтение и запись;
   файл должен существовать;
   файловый указатель — на начало файла;
2. Rewrite(f) — создание нового файла (если такого файла не существовало) или обнуление существующего;
   файловый указатель — в начало;
   текстовые файлы при этом открываются только на запись, а двоичные — на чтение и запись;

Функция Eof(f) [расшифровывается как End Of File] возвращает true, если файловый указатель находился за концом файла.

После работы с данными в файле его необходимо закрыть с помощью Close(f).
Если, не закрывая, выполнить Reset(f), то файловый указатель просто перейдет к началу.

Буферизация в файлах

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

Наличие буфера ускоряет операции чтения и записи, поскольку они выполняются преимущественно не с внешним устройством (файлом), а с участком оперативной памяти.

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

Подпрограммы для работы с закрытыми файлами

procedure Rename(f, name);
       //переименовывает файл, связанyый с файловой переменной f, давая ему имя name 
procedure Erase(f);
       //удаляет файл, связанный с файловой переменной f 

function FileExists(name): boolean;
       //возвращает True, если файл с именем name существует 

function DeleteFile(name): boolean;
       //удаляет файл. Если файл не может быть удален, то возвращает False 
function RemoveDir(name): boolean;
       //удаляет каталог. Возвращает True, если каталог успешно удален 

function GetCurrentDir: string;
       //возвращает текущий каталог 
function SetCurrentDir(name): boolean;
       //устанавивает текущий каталог. Возвращает True, если каталог успешно установлен 
function CreateDir(name): boolean;
       //создает каталог. Возвращает True, если каталог успешно создан 

function ExtractFileName(name): string;
       //выделяет имя файла из полного имени файла name 
function ExtractFileExt(name): string;
       //выделяет расширение из полного имени файла name 
function ExtractFilePath(name): string;
       //выделяет путь из полного имени файла name 

Типичные ошибки ввода-вывода при работе с файлами

1. Файл открыли, но забыли выполнить Assign.
2. Открыли, но файла нет на диске (или нет прав доступа на чтение).
3. Попытка считывания за концом файла.

Все эти ошибки нужно обрабатывать с помощью исключений.

Пример 1. Файл не существует.

Assign(f, 'a.dat');

try
  Reset(f);
  read(f, x);
  Close(f);
except
  writeln('Файл не существует');
end;

Оператор try..finally

try
  <действия, которые могут вызвать исключение>
finally
 <действия, которые надо выполнить независимо от того,
   произошло исключение, или нет>
end;

Этот оператор отличается тем, что не обрабатывает исключение, а лишь выполняет некоторое завершающее действие, которое должно быть совершено в любом случае. Для обработки нужен внешний блок try..except.

Пример 2. Попытка считывания за концом файла.

Assign(f, 'a.dat');

try
  Reset(f);
  try
    read(f, x);
  finally
    Close(f);
  end;
except
  writeln('Произошла ошибка ввода-вывода');
end;

Подпрограммы для работы с типизированными файлами

procedure Truncate(f)
       //Усекает типизированный файл f, отбрасывая все элементы с позиции файлового указателя 
function FileSize(f)
       //Возвращает количество элементов в типизированном файле f 
function FilePos(f)
       //Возвращает текущую позицию файлового указателя в типизированном файле f 
procedure Seek(f, i);
       //Устанавливает текущую позицию файлового указателя в типизированном файле f на элемент с номером i 

Варианты использования

• Перейти на конец файла для добавления элементов:

Seek(f, FileSize(f));

• Перейти на предыдущую позицию:

Seek(f, FilePos(f) - 1);

Пример 1. Добавить в конец файла 'a.dat' элемент 0 (при необходимости создать файл).

const
  fileName = 'a.dat';

var 
  f: file of integer;

begin
  Assign(f, fileName);
  if FileExists(fileName) then
  begin
    Reset(f);
    Seek(f, FileSize(f));
  end
  else
    Rewrite(f);
  
  write(f, 0);
  Close(f);
end.

Пример 2. Возведение всех элементов файла в квадрат.

const
  fileName = 'a.dat';

var 
  f: file of real;

begin
  Assign(f, fileName);
  Reset(f);
  
  for var i:=0 to FileSize(f)-1 do
  begin
    var x: real;
    read(f, x);
    Seek(f, i);
    write(f, x * x);
  end;

  Close(f);
end.

Пример 3. Использование типизированных файлов для работы с простейшими БД.
БД студентов 1.9
Опишем запись для одного студента:

type
  Student = record
    name: string[50];
    course, group: integer;
  end;

Замечание. В связи с тем, что типизированные файлы хранят данные фиксированного размера, а string — переменной длины, использовать его в типизированных файлах мы не можем. Для этого будем использовать строки фиксированной длины — string[n] (строка длины n).

Пусть уже создан файл 'Group1course.dat'.
Задача. Найти Иванова и перевести его в 8 группу.

type
  Student = record
    name: string[50];
    course, group: integer;
  end;

const
  fileName = 'a.dat';
var 
  f: file of Student;

begin
  Assign(f, fileName);
  Reset(f);
  
  while not Eof(f) do
  begin
    var x: Student;
    read(f, x);
    
    if (x.name = 'Иванов') and (x.group = 11) then
    begin
      x.group := 10;
      Seek(f, FilePos(f) - 1);
      write(f, x);
      break;
    end;
  end;

  Close(f);
end.

Пример 4. Сортировка файла по возрастанию.

for var i:=FileSize(f)-2 downto 0 do
for var j:=0 to i do
begin
  Seek(f,j);
  read(f,x,y);
  if x>y then
  begin
    Seek(f,j);
    write(f,y,x);
  end;
end;

Подпрограммы для работы с текстовыми файлами

procedure Reset(f)
       //Открывает текстовый файл f ТОЛЬКО на чтение.
procedure Rewrite(f)
       //Открывает текстовый файл f ТОЛЬКО на запись, обнуляя его содержимое
procedure Append(f)
       //Открывает текстовый файл f на дополнение
       //Файловый указатель устанавливается за концом файла
function Eoln(f)
       //Возвращает True, если файловый указатель находится на символе конца строки в текстовом файле f 
function SeekEof(f)
       //Пропускает пробельные символы, после чего возвращает True, если достигнут конец текстового файла f 
function SeekEoln(f)
       //Пропускает пробельные символы, после чего возвращает True, если достигнут конец строки в текстовом файле f 

procedure read(f, a, b, c)
       //Считывает значения в переменные a, b, c;
       //Переменные могут быть числовых типов, символьного, строкового
procedure write(f, a, b, c)
       //Записывает значения переменных a, b, c в текстовый файл f;
       //Переменные могут быть числовых типов, символьного, строкового
procedure readln(f, a, b, c);
procedure writeln(f, a, b, c);
procedure readln(f);
procedure writeln(f);

Примеры использования

Пример 1. Обработка строк в текстовых файлах.
Пусть имеется функция, которая трансформирует строку и возвращает string:

function Transform(var s: string): string;

Применить указанную трансформацию ко всем строкам файла.

var
  f, f1: text;

begin
  Assign(f, 'a.txt');
  Assign(f1, 'b$.txt');
  Reset(f);
  Rewrite(f1);
  
  while not Eof(f) do
  begin
    var s: string;
    readln(f, s);     //Важно использовать readLN, т.к. она пропускает символы перехода
                      //на новую строку (если использолвать read, произойдет зацикливание)
    s := Transform(s);
    writeln(f1, s);
  end;
  
  Close(f);
  Close(f1);
  
  Erase(f);
  Rename(f1, 'a.txt');
end.

Пример 2. Сумма целых в текстовом файле.

var f: text;

begin
  var sum := 0.0;
  
  assign(f,'a.txt');
  reset(f);
  while not SeekEof(f) do
  begin
    var x: real;
    read(f,x);
    sum += x;
  end;
  close(f);
  writeln(sum);
end.

.NET-типы File и Directory и их статические методы

uses System.IO, System.Text;

begin
  &File.Copy('p1.pas','p2.pas',true);
  &File.Exists('p2.pas');
  var s: string := &File.ReadAllText('p1.pas');
  var s1: string := &File.ReadAllText('p1.pas',Encoding.Default);
  var ss: array of string := &File.ReadAllLines('p1.pas');
  &File.WriteAllLines('p3.pas',ss);
  &File.WriteAllText('p4.pas',s);
  &File.AppendAllText('p2.pas',s);
  &File.Move('p3.pas','p5.pas');
  &File.Delete('p5.pas');
  
  Directory.GetCurrentDirectory();
  Directory.SetCurrentDirectory('d:\w');
  var fnames: array of string := Directory.GetFiles('.');
  var dnames: array of string := Directory.GetDirectories('..');
  Directory.Exists('d:\w');
end.

Указатели

Адрес

Оперативная память состоит из последовательный ячеек. Каждая ячейка имеет номер, называемый адресом.
В 32-битных системах можно адресовать 2³² байт (<math>\approx \;</math> 4Гб) памяти, в 64-битных — 2 ⁶⁴ соответственно.

Переменная (или константа), хранящая адрес, называется указателем.

Для чего нужны указатели

Указатели повышают гибкость доступа к данным:

1. Вместо самих данных можно хранить указатель на них. Это позволяет хранить данные в одном экземпляре и множество указателей на эти данные. Через разные указатели эти данные можно обновлять (пример — корпоративная БД).
2. Указателю можно присвоить адрес другого объекта (вместо старого появился новый телефонный справочник).
3. С помощью указателей можно создавать сложные структуры данных.

Типы указателей

Указатели делятся на:

• Типизированные (указывают на объект некоторого типа)
  Имеют тип: ^<тип>
  Пример. ^integer — указатель на integer
• Бестиповые (хранят адрес ячейки памяти неизвестного типа)
  Преимущество: могут хранить что угодно
  Имеют тип: pointer

Пример кода.

var
  i: integer := 5;
  r: real := 6.14;
  
  pi: ^integer;
  pr: ^real;

begin
  pi := @i;
  pr := @r;
  pi := @r; // ОШИБКА компиляции
end.

@ — унарная операция взятия адреса

Операция разадресации (разыменования)

var
  i: integer := 5;
  pi: ^integer;

begin
  pi := @i;
  
  pi^ := 8 - pi^;
  writeln(i); // 3
end.

^ — операция разыменования
pi^ — то, на что указывает pi, т.е. другое имя i или ссылка на i.

Тут надо вспомнить определение ссылки:
Ссылка — другое имя объекта.

Нулевой указатель

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

var
  pi: ^integer; //указатель pi хранит значение nil
  i: integer;

begin
  pi := @i;     //pi хранит адрес переменной i
  pi := nil;    //pi снова никуда не указывает
  
  pi^ := 7;     //ОШИБКА времени выполнения:
                //попытка разыменовать нулевой указатель

Попытка разыменовать нулевой указатель приводит к ошибке времени выполнения.

Бестиповые указатели

var
  p: pointer;
  i: integer;

begin
  p := @i;
end.

Бестиповому указателю можно присвоить адрес переменной любого типа, т.е. бестиповой указатель совместим по присваиванию с любым типовым указателем.

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

Оказывается, любой типизированный указатель совместим по присваиванию с бестиповым, т.е. следующий код верен:

var 
  pi: ^integer;
  i: integer;
  p: pointer;

begin
  p := @i;
  pi := p;
  pi^ += 2;
end.

Вопрос. Нельзя ли интерпретировать память, на которую указывает p, как принадлежащую к определенному типу?
Ответ — да, можно. Вот как это сделать:

type 
  pinteger = ^integer;
var
  i, j: integer;
  p: pointer;

begin
  p := @i;
  pinteger(p)^ := 7; //используем явное приведение типа
  writeln(i); // 7
end.

Запись

тип(переменная)

показывает, что используется явное приведение типов.

Внимание! Неконтролируемая ошибка!

type 
  preal = ^real;
var
  i, j: integer;
  p: pointer;

begin
  p := @i;
  preal(p)^ := 3.14; //ОШИБКА!
end.

Область памяти, на которую указывает p трактуется как область, хранящее вещественное число (8 байт), и потому константа 3.14 записывается в эти 8 байт. Однако, переменная i занимает только 4 байта, поэтому затираются еще 4 соседних байта (в данном случае они принадлежат переменной j).

Доступ к памяти, имеющей другое внутреннее представление

type
  Rec = record
    b1, b2, b3, b4, b5, b6, b7, b8: byte;
  end;

  PRecord = ^Rec;

var
  r: real := 3.1415;
  prec: ^Rec;

begin
  var temp : pointer := @r;
  prec := temp; 
  writeln(prec^.b1, ' ', prec^.b2, ' ', {..., } prec^.b8);
end.

Замечание. Важно, что типы real и Rec имеют один размер.

Другой способ сделать то же самое, но гораздо более безопасный - использовать класс System.BitConverter

uses System;

begin
  foreach b: byte in BitConverter.GetBytes(1.0) do
    write(b,' ');
end.

Неявные указатели в языке Pascal

1. procedure p(var i: integer)
   Для параметра-переменной при вызове на стек кладется не сама переменная, а указатель на неё.
2. var pp: procedure(i: integer)
   Для хранения процедурной переменной используется ячейка памяти, являющаяся указателем.
3. var a: array of real;
   Переменная типа динамический массив является указателем на данные массива, хранящиеся в динамической памяти.

Динамическая память

Особенности динамической памяти

Память, принадлежащая программе, делится на:

• Статическую
  (память, занимаемая глобальными переменными и константами)
• Автоматическую
  (память, занимаемая локальными данными, т.е. стек программы)
• Динамическую
  (память, выделяемая программе по специальному запросу)

В дополнение к статической и автоматической памяти, которые фиксированы после запуска программы, программа может получать нефиксированное количество динамической памяти. Ограничения на объём выделяемой динамической памяти связаны лишь с настройками операционной системы и объемом оперативной памяти компьютера.
Основная проблема — явно выделенную динамическую память необходимо возвращать, иначе не хватит памяти другим программам.

Для явного выделения и освобождения динамической памяти используются процедуры:

• New
• Dispose

var
  p: pinteger;  //p никуда не указывает
begin
  New(p);       //в динамической памяти выделяется ячейка
                //размером под один integer, и 
                //p начинает указывать на эту ячейку
  p^ := 3;
  Dispose(p);   //возвращает динамическую память, 
                //контролируемую указателем p, назад ОС
end.

По окончании работы программы, вся затребованная программой динамическая память возвращается ОС.
Но лучше освобождать динамическую память явно! Иначе в процессе работы программы она может занимать большие объёмы (ещё не освобождённой) памяти, что вредит общей производительности системы.

Ошибки при работе с динамической памятью

1.

var p: pinteger;
begin
  p^ := 5;  //ОШИБКА
end.

Ошибка разыменования нулевого указателя (попытка использовать невыделенную динамическую память).

2.

var p: pinteger;
begin
  New(p);
  New(p);  //ОШИБКА
end.

Утечка памяти (память, которая выделилась в результате первого вызова New(p), принадлежит программе, но не контролируется никаким указателем.

2a.

procedure q;
var p: pinteger;
begin
  New(p);
end;
begin
  q;  //ОШИБКА
end.

Утечка памяти в подпрограмме: обычно если динамическая память выделяется в подпрограмме, то она должна в этой же подпрограмме возвращаться. Исключение составляют т.н. "создающие" п/п:

function CreateInteger: pinteger;
begin
  New(Result);
end;

begin
  var p: pinteger := CreateInteger;
  p^ := 555;
  Dispose(p);
end.

Ответственность за удаление памяти, выделенной в подпрограмме, лежит на программисте, вызвавшем эту подпрограмму.

3.

var p: pinteger;
begin
  for var  i:=1 to 1000000 do
    New(p);  //ОШИБКА
end.

Out of Memory (очень большие утечки памяти, в результате которых динамическая память может «исчерпаться»).

4.

var p: pinteger;
begin
  New(p);
  p^ := 5;
  Dispose(p);
  p^ := 7;  //ОШИБКА
end.

После вызова Dispose(p), p называют висячим указателем (т.к. он указывает на недоступную более область памяти).

Рекурсия

Основные определения

Рекурсией называется определение объекта через такой же объект.

Пример.

(1)  <Список> ::= <Число>
                 |<Список> ',' <Число>  

В данном примере рекурсивной частью определения является "<Список> ',' <Число>".

Замечание 1. Рекурсивное определение, будучи конечным, определяет бесконечное множество объектов.

Заметим также, что <Список> можно определить и по-другому:

(2)  <Список> ::= <Число>
                 |<Число> ',' <Список>

Определение (1) называют леворекурсивным, а (2) — праворекурсивным.

Замечание 2. В рекурсивном определении обязательно (!!!) должна присутствовать нерекурсивная часть.

Рекурсивное определение может быть косвенным:

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

Пример.

<оператор> ::= <присваивание> | <составной оператор>
<присваивание> ::= <переменная> := <выражение>
<составной оператор> ::= begin <список операторов> end
<список операторов> ::= <пусто> | <оператор> ; <список операторов>

В данном примере имеется как прямое, так и косвенное рекурсивное определение.

В программировании под рекурсией понимается:

• вызов из подпрограммы самой себя (прямая рекурсия)
• вызов из подпрограммы другой подпрограммы, которая вызывает исходную (косвенная рекурсия)

При косвенной рекурсии обязательно использование опережающего объявления с помощью ключевого слова forward:

procedure q; forward;  // опережающее определение

procedure p;
begin
  ...
  q;
  ...
end;

procedure q;
begin
  ...
  p;
  ...
end;

Простые примеры использования рекурсии

Пример 1.

procedure p(i: integer);
begin
  write(i, ' ');
  p(i + 1);
end;

При вызове этой процедуры произойдет рекурсивное зацикливание, т.к. рекурсивный вызов производится безусловно.

Вывод. Чтобы рекурсивного зацикливания не произошло, рекурсивный вызов должен происходить не безусловно, а по какому-то условию, которое всякий раз меняется и при каком-то рекурсивном вызове становится ложным (так называемое условие продолжения рекурсии).

Исправим нашу процедуру в соответствии со сделанным выводом:

procedure p(i: integer);
begin
  write(i, ' ');
  if i < 5 then
    p(i + 1);
end;

При вызове p(0) будет выведено:

0 1 2 3 4 5

Графически, рекурсивные вызовы можно изобразить так:

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

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

Пример 2. Вывести

0 1 2 3 4 5 4 3 2 1 0

Решение:

procedure p(i: integer);
begin
  write(i, ' ');
  if i < 5 then then
  begin
    p(i + 1);
    write(i, ' ');
  end;
end;

Максимальная глубина рекурсивных вызовов называется глубиной рекурсии.
Текущая глубина называется текущим уровнем рекурсии.

Замечание. Чем больше глубина рекурсии, тем больше накладные расходы по памяти.

Графические изображения рекурсивных вызовов

Одно графическое изображение у нас уже было. Вспомним его:

procedure p(i: integer);
begin
  write(i, ' ');
  if i < 5 then
    p(i + 1);
end;

Рассмотрим более детально вызов p(0) процедуры

procedure p(i: integer);
begin
  write(i, ' ');
  if i < 2 then
    p(i + 1);
end;

Вспомним, что:

• Программный стек — это непрерывная область памяти, выделяемая программе, в частности, для размещения в ней вызываемых подпрограмм.
• При каждом вызове подпрограммы на стек кладется её запись активации (ЗА), а при возврате — снимается со стека.

Т.о. на стеке фактически хранятся все значения переменной i.

Замечание 1. Поскольку при каждом рекурсивном вызове на стек помещается ЗА, то при большой глубине рекурсии программный стек может переполниться, и программа завершится с ошибкой.
Это произойдет тем быстрее, чем больше суммарный объем формальных параметров и локальных переменных.

Поэтому следующий код — очень плохой!!!

procedure p(i: integer);
var a : array[1..1000] of real;
begin
  ...
  p(i + 1);
  ...
end;

Замечание 2. Накладные расходы на помещение на стек ЗА, снятие ЗА со стека, а также присваивание значений формальным параметрам на стеке достаточно велики.
Поэтому если имеется простое нерекурсивное решение (итерационное), то следует использовать именно его.

Замечание 3. Любую рекурсию можно заменить итерацией.

Примеры использования рекурсии

Пример 1. Найти n! = n(n - 1)(n - 2)...2*1
Очевидно, определить n! можем следующим образом:

<math>f(n) = \begin{cases} n (n - 1), & n > 0 \\ 1, & n = 0 \end{cases}</math>

Тогда решение имеет вид:

function nfact(n: integer): integer;
begin
  if n = 0 then
    Result := 1
  else
    Result := n * nfact(n - 1);
end;

Однако, заметим, что возвращаемое значение не определено для n < 0.
Как минимум, можно заменить условие n = 0 на n <= 0, но, в таком случае, мы получим неверный результат, т.к. факториал вообще не определен для отрицательных чисел.
Очевидно, необходимо с помощью утверждения проверить корректность входного параметра (Assert(n >= 0)). Но его использование при каждом рекурсивном вызове накладно. Поэтому можно "обернуть" рекурсивную подпрограмму, например, так:

function nfact(n: integer): integer;
  function nfactRecur(n: integer): integer;
  begin
    if n = 0 then
      Result := 1
    else
      Result := n * nfact(n - 1);
  end;
begin
  Assert(n >= 0);
  Result := nfactRecur(n);
end;

Глубина рекурсии этого алгоритма равна n.

Пример 2. Найти <math>a^n</math>. Дадим рекурсивное определение:

<math>f(n) = \begin{cases} (a^{\frac{n}{2}})^2, & \mbox{if }n\mbox{ is even}, n > 0

\\ a a^{n-1}, & \mbox{if }n\mbox{ is odd}, n > 0 \\ 1, & n = 0 \\ \frac{1}{a^n}, & n < 0\end{cases}</math>

function power(a: real; n: integer): real;
begin
  if n = 0 then
    Result := 1
  else if n < 0 then
    Result := 1 / power(a, -n)
  else  // n > 0
    if n mod 2 = 0 then
      Result := sqr(power(a, n div 2))
    else
      Result := a * power(a, n - 1);
end;

Глубина рекурсии равна:

• <math>\log_2 n</math> — в лучшем случае
• <math>2\log_2 n</math> — в худшем

Пример 3. Нахождение минимального элемента в массиве. Определить этот элемент можем как минимальный(один элемент, минимальный из массива без этого элемента), т.е. рекурсивное определение следующее:

<math>minElem(A, n) = \begin{cases} A[n-1], & n = 1

\\ min(\; minElem(A, \; n - 1),\; A[n - 1]\;), & n > 1\end{cases}</math> В соответствии с этим имеем решение:

function MinElem(A: array of integer; n: integer): integer;
begin
  if n = 1 then
    Result := A[0]
  else
    Result := min(MinElem(A, n-1), A[n-1]));
end;

Глубина рекурсии равна n - 1.

Ясно, что это не очень хороший результат.
Можно значительно уменьшить глубину, если искать минимальный среди примерно равных частей массива. Т.е. нужно поделить массив пополам, найти в каждой половине минимальные элементы и сравнить их. Поиск в половине осуществляется подобным же образом, и деление производится до тех пор, пока в подмассиве не останется один элемент.
Можно еще немного оптимизировать этот алгоритм — если в подмассиве два элемента, достаточно вернуть минимальный из них.
Теперь знания количества элементов недостаточно: необходимо знать, среди каких элементов массива вести поиск. Поэтому будем в качестве параметров передавать левую (l) и правую (r) границы подмассивов.
Дадим новое рекурсивное определение:

<math>minElem(A, l, r) = \begin{cases} A[l], & l = r

\\ min(A[l],\; A[r]), & r - l = 1 \\ min(\; minElem(A,\; l, \; (l + r) \; div\; 2), \; minElem( A, \; (l + r)\; div\; 2 + 1,\; r) \;), & l - r > 1\end{cases}</math> Решение:

function MinElem(a: array of integer; l, r: integer): integer;
begin
  if l = r then             // если всего один элемент
    Result := a[l]
  else if r - l = 1 then    // если ищем минимум из двух элементов
    Result := min(a[l], a[r])
  else
  begin
    var mid := (l + r) div 2;
    Result := min(MinElem(a, l, mid), MinElem(a, mid+1, r)); 
  end;
end;

Глубина рекурсии такого алгоритма уже примерно равна <math>\log_2 n</math> (по количеству делений).

Пример 4. Вывод односвязного линейного списка на экран.
Вспомним, как выглядит список:

Решение:

procedure Print<T>(h: Node<T>);
begin
  if h = nil then
    exit;
  write(h.data, ' ');
  Print(h.next);
end;

Глубина рекурсии равна длина списка - 1

Рекурсия называется концевой, если рекурсивный вызов является последним в подпрограмме.

Концевая рекурсия наиболее легко превращается в итеративный алгоритм:

while h <> nil do
begin
  write(h.data, ' ');
  h := h.next;
end;

Доказательство завершимости рекурсии

Добавим к рекурсивной процедуре целый параметр n:

p(n, ...);

Если при каждом рекурсивном вызове параметр n уменьшается получим вызовы

p(n)
  p(n - 1)
    p(n - 2)
      p(n - 3)

И если рекурсия завершается при n <= 0, то это служит доказательством завершимости рекурсии.

Действительно, на каждом следующем уровне рекурсии n становится меньше.
Поскольку при n <= 0 рекурсивных вызовов нет, то число рекурсивных вызовов конечно.

Утверждать, что рекурсия завершима, можно не всегда.
Пример.

procedure p(n);
begin
  if n <= 0 then
    exit
  else
    p(Random(2 * n) - n + 1);
end;

Формы рекурсивных подпрограмм

1. Действие выполняется на рекурсивном спуске

p(n) 
  S(n)
  if B(n) then
    p(n - 1)

2. Действие выполняется на рекурсивном возврате

p(n)
  if B(n) then
    p(n - 1)
  S(n)

3. Действие выполняется и на рекурсивном спуске и на рекурсивном возврате

p(n)
  S1(n)
  if B(n) then
    p(n - 1)
  S2(n)

4. Каскадная рекурсия

p(n)
  S(n)
  if B1(n) then
    p(n - 1)
  if B2(n) then
    p(n - 1)

Эта рекурсия называется каскадной, т.к. каждый вызов подпрограммы может порождать несколько рекурсивных вызовов (каскад).

5. Удаленная рекурсия:

function f(i: integer): integer;
begin
  if B1(n) then 
    Result := ...
  else 
  Result := f(f(i-1));
end;

Примером удаленной рекурсии служит функция Аккермана:

<math>A(m,\;n)=\begin{cases}n+1,&m=0;

\\A(m-1,\;1),&m>0,\; n = 0; \\A(m-1,\;A(m,\;n-1)),& m > 0,\; n > 0.\end{cases}</math>

Примеры плохого и хорошего использования рекурсии

<xh4>Пример плохого использования рекурсии - числа Фибоначчи</xh4> Числа Фибоначчи задаются следующим рекуррентным соотношением:

<math>F_1 = 1,\quad F_2 = 1,\quad F_{n+1} = F_n + F_{n-1} \quad n\in\mathbb{N}.</math>

Мы уже вычисляли их с помощью циклов. Возможно рекурсивное (плохое!) решение:

function Fib(n: integer): integer;
begin
  if (n = 1) or (n = 2) then
    Result := 1
  else
    Result := Fib(n - 1) + Fib(n - 2);
end;

Вот что произойдет при вызове Fib(7):

дерево рекурсивных вызовов

Как видим, одни и те же числа вычисляются по несколько раз:

• Fib(7): 1
• Fib(6): 1
• Fib(5): 2
• Fib(4): 3
• Fib(3): 5
• Fib(2): 8

Алгоритм можно улучшить, использовав массив, первоначально заполненный нулями.
При первом вычислении fib(n) будем заполнять соответствующий элемент, а при всех последующих — просто обращаться к его значению. Подобная методика называется мемоизацией, т.е. запоминанием промежуточных результатов для исключения их повторного вычисления.

var F: array[1..1000] of integer;

function Fib(n: integer): integer;
begin
  if F[n] <> 0 then
    Result := F[n]
  else if (n = 1) or (n = 2) then
  begin
    Result := 1;
    F[n] := 1;
  end
  else
  begin
    Result := Fib(n - 1) + Fib(n - 2);
    F[n] := Result;
  end;
end;

Очевидно, данный способ крайне неэффективен по сравнению с итерационным алгоритмом как по памяти, так и по времени работы. В частности, глубина рекурсии при вычислении n-того числа Фибоначчи составляет n-1.

Рекурсивный способ вычисления чисел Фибоначчи, построенный по итерационному алгоритму

Напомним итерационный алгоритм поиска n-того числа Фибоначчи:

a := 1;
b := 1;
for var i := 3 to n do
begin
  c := a + b;
  a := b;
  b := c;
end;
Result := c;

Построим по нему рекурсивный алгоритм, передавая в каждую рекурсивную подпрограмму переменные a,b,c, меняющиеся на каждой итерации цикла. Фактически при каждом рекурсивном вызове мы будем совершать подстановку:

(a,b)->(b,a+b)

Рекурсивный алгоритм, реализованный по этой подстановке, будет иметь вид:

function fib (a,b,n: integer): integer;
begin
  if n = 1 then
    Result := a
  else Result := fib(b,a+b,n-1)
end;

begin
  for var i:=1 to 10 do
    Print(fib(1,1,i));
end.

Рекурсия в данном примере - концевая. Как уже отмечалась, она легко заменяется итерацией, при этом как раз получается предыдущее итерационное решение. Хорошие оптимизирующие компиляторы делают это автоматически.

Пример хорошего использования рекурсии - ханойские башни

Задача состоит в следующем:
Даны три стержня. На первом лежат n дисков разного радиуса при условии, что ни один диск бОльшего радиуса не лежит на диске мЕньшего радиуса.
Hеобходимо перенести диски с первого стержня на третий, пользуясь вторым, при условии:

• за один ход можно переносить только один диск
• меньший диск должен лежать на большем

Идея алгоритма такая:

перекладываем n-1 диск с исходного стержня на вспомогательный
оставшийся диск перекладываем на требуемый стержень
лежащие на вспомогательном стержне диски перекладываем на требуемый диск

Т.о. имеем простое рекурсивное решение:

procedure MovePiramid(n: integer; f, t, w : integer);
begin
  if n = 0 then
    exit;
  MovePiramid(n - 1, f, w, t);
  writelnFormat('Переложить диск с {0} на {1}', f, t);
  MovePiramid(n - 1, w, t, f);
end;

Быстрая сортировка

<xh4>Алгоритм</xh4> Алгоритм быстрой сортировки (разновидность алгоритма «разделяй и влавствуй») состоит из двух этапов:
1. Выбор некоторого элемента массива x и разделение массива на две части так, что в первой оказываются все элементы <= x, а в о второй — >= x
2. Рекурсивное применение нашего алгоритма к полученным частям

Очевидно, алгоритм будет работать тем быстрее, чем на более равные части мы будем делить массив (в идеале — каждый раз пополам).
Поэтому мы должны стремиться выбрать элемент x так, чтобы примерно половина элементов массива была <= его, и, соответственно, вторая половина — >=. С другой стороны, выбор x не должен занимать много времени и, по крайней мере, не зависеть от n — размера массива).

Мы будем использовать простейший способ выбора x — в качестве него брать первый элемент.

На следующей анимации представлен пример применения алгоритма быстрой сортировки к массиву

4 1 7 3 2 9 5 8 6

Рассмотрим этап 1 подробнее:
- Для разделения массива на указанные части заведем 2 индекса i и j.
- В начале i будет указывать на первый элемент и двигаться вправо, а j — на последний и двигаться влево.

Шаг 1.
Будем продвигать i вперед до тех пор, пока A[i] не станет >= x.
Далее будем продвигать j назад до тех пор, пока A[j] не станет <= x.
Пришли к элементам A[i] и A[j], которые "стоят не на своих местах" (вспомним, что мы хотим раскидать все меньшие или равные x элементы влево, а большие или равные — вправо)
Шаг 2.
Поменяем их местами и продвинем i вперед на один элемент, а j — назад, также на один элемент.

Будем повторять указанные действия до тех пор, пока i не станет >= j.
В результате получим массив A, разделенный на 2 части:

• слева все элементы <= x
• справа — >= x

Код программы

// Быстрая сортировка Ч. Хоара

/// Разделение a[l]..a[r] на части a[l]..a[q] <= a[q+1]..a[r] 
function Partition(a: array of integer; l,r: integer): integer;
begin
  var i := l - 1;
  var j := r + 1;
  var x := a[l];
  while True do
  begin
    repeat
      Inc(i);
    until a[i]>=x;
    repeat
      Dec(j);
    until a[j]<=x;
    if i<j then 
      Swap(a[i],a[j])
    else 
    begin
      Result := j;
      exit;
    end;
  end;
end;
  
/// Сортировка частей
procedure QuickSort(a: array of integer; l,r: integer);
begin
  if l>=r then exit;
  var j := Partition(a,l,r);
  QuickSort(a,l,j);
  QuickSort(a,j+1,r);
end;

const n = 20;

begin
  var a := ArrRandom();
  writeln('До сортировки: ');
  Writeln(a);
  QuickSort(a,0,a.Length-1);
  writeln('После сортировки: ');
  Writeln(a);
end.

<xh4>Асимптотическая оценка сложности</xh4> Будем исходить из того, что массив всякий раз делится на 2 одинаковые части. Это самый лучший вариант.
Глубина рекурсии в этом случае = log₂n.

Очевидно, что в алгоритме Partition мы просматриваем все элементы «своей части» ровно один раз. Т.е. на каждом уровне рекурсии будут по одному разу просмотрены все элементы массива.
Это означает, что асимптотическая сложность Partition на каждом уровне рекурсии = Θ(n).

Т.о., при условии деления примерно пополам, асимптотическая сложность всего алгоритма = Θ(n log n).

Теоретически доказано, что в среднем, если делим не точно пополам, асимптотическая сложность сохраняет формулу Θ(n log n).
Вопрос: какова сложность в худшем случае? Худший — когда в качестве x выбираем минимальный (или максимальный) элемент. Это происходит (в нашей ситуации, т.к. мы выбираем первый элемент), если массив уже отсортирован.
В этом случае в результате разбиения на части большая часть будет уменьшаться на 1, и глубина рекурсии в процедуре Sort будет равна <math>n - 1</math>.
Поэтому в худшем случае асимптотическая сложность = <math>\Theta(n^2)</math>.

Утверждение. Для произвольных данных не существует алгоритма с асимптотической сложностью лучше, чем Θ(n log n) в среднем.

Генерация всех перестановок

Основная идея алгоритма генерации всех перестановок заключается в следующем. В массиве длины n, содержащем перестановку, будем менять последний элемент с каждым, после чего будем рекурсивно будем делать то же самое для массива длины n-1 и затем возвращать переставленный элемент на старое место. Если достигнута длина массива n=1, то переставлять ничего не нужно, а следует выдавать содержимое всего массива-перестановки на экран. Такой алгоритм позволит сгенерировать все перестановки, что следует из словесного рекурсивного определения: на последнем месте побывает каждый элемент, содержащийся в рассматриваемом массиве, после чего к оставшейся части массива рекурсивно будет применен тот же алгоритм.

procedure Perm(a: array of integer; n: integer);
begin
  if n=1 then
    Writeln(a)
  else
    for var i:=0 to n-1 do
    begin
      Swap(a[i],a[n-1]);
      Perm(a,n-1);
      Swap(a[i],a[n-1]);
    end;
end;
 
const n=3;
 
begin
  var a := ArrGen(n,i->i,1);
  Perm(a,n);  
end.

Нетрудно видеть, что глубина рекурсии составляет n-1, а количество вызовов процедуры Perm составляет n!.

Генерация всех подмножеств

Генерация всех подмножеств представляет собой алгоритм перебора. В алгоритмах перебора перебираются все варианты и для подходящих вариантов выполняется определенное действие. В данном случае просто выводятся все подмножества.

procedure Generate(A: array of integer; i: integer; Subset: LinkedList<integer>);
begin
  if i = A.Length then 
    Subset.Println
  else
  begin
    Generate(A,i+1,Subset);   // не добавлять
    Subset.AddLast(A[i]); 
    Generate(A,i+1,Subset); // добавить
    Subset.RemoveLast;
  end;
end;
 
begin
  var A := Arr(5,3,8,13,15);
  var Subset := new LinkedList<integer>;
  Generate(A,0,Subset);
end.

Перебор с возвратом (backtracking)

Общая схема перебора с возвратом

procedure backtracking(k: integer);     // k - номер хода
begin
  { запись варианта }

  if { решение найдено } then
    { вывод решения }
  else
    { перебор всех вариантов }
    if { вариант подходит } then
      backtracking(k+1);

  { стирание варианта }
end;

begin
  backtracking(1);
end.

Задача об обходе конем шахматной доски

const n = 8;

var 
  dx := Arr(2, 2, 1, 1, -1, -1, -2, -2);
  dy := Arr(1, -1, 2, -2, 2, -2, 1, -1);

type KnightProblem = class

  Solution := new integer[n, n];
  Success: boolean := false;
 
  procedure Step(i, x, y: integer);
  begin
    if Success then 
      exit;
    // отсечение неверных вариантов  
    if (x < 0) or (x >= n) or (y < 0) or (y >= n) or (Solution[x, y] > 0) then 
      exit;
   
    // запись частичного решения
    Solution[x, y] := i;
   
    if i = n * n then
      Success := true
    else 
      for var k:=0 to 7 do // перебор вариантов
        Step(i + 1, x + dx[k], y + dy[k]);
   
    if not Success then
      Solution[x, y] := 0; // возврат - стирание частичного решения
  end;
end;  
 
const
  x0 = 1; // начальная клетка коня
  y0 = 3;
 
begin
  var kp := new KnightProblem();
  kp.Step(1, x0, y0);
  if kp.Success then
    writeln(kp.Solution);
 
  writelnFormat('Время: {0} мс', Milliseconds/1000);
end.

Деревья

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

Количество уровней называется глубиной дерева.
Каждая вершина нижнего уровня соединяется ровно с одной вершиной предыдущего уровня.

Единственная вершина на уровне 0 называется корнем дерева.
Она не имеет вершин-предков.

Вершины, не имеющие потомков, называют листьями дерева, а совокупность всех листьев образует крону дерева.

Примеры.

• Дерево папок на диске
  
• Самый очевидный пример — генеалогическое древо
  
• Главы и пункты книги
  
• Дерево разбора выражений

a*b + c*d

Теперь дадим рекурсивное определение дерева:

Дерево ::= корень список_поддеревьев
         | ε 
Список поддеревьев ::= список_поддеревьев дерево
                     | ε
// ε означает «пусто»

Определения

Дерево называется бинарным (двоичным), если каждая его вершина имеет не более двух потомков.
(Далее бинарные деревья будем сокращать как БД)

Двоичное_дерево  ::= корень левое_поддерево правое_поддерево
                  | ε
Левое_поддерево  ::= двоичное_дерево
Правое_поддерево ::= двоичное_дерево

БД называется идеально сбалансированным, если для каждого узла количество узлов в его правом поддереве отличается от количества узлов в его левом поддереве максимум на единицу. <здесь будут рисунки деревьев>

Полным называют БД, у которого каждая вершина, не являющаяся листом, имеет ровно двух потомков, и все листья находятся на последнем уровне.

Количество узлов (u) и количество ребер (v) в произвольном дереве связаны простой формулой: <math>u = v + 1</math>.

Количество узлов в полном БД вычисляется по формуле

<math>\ 2^{n+1} - 1,</math>

где n — глубина дерева.

Доказательство  

Действительно:
u₀ = 1 = 2⁰
u₁ = 2 = 2¹
u₂ = 4 = 2²
...
u_n = 2ⁿ
Значит общее количество узлов в дереве глубины n:
u(n) = 2⁰ + 2¹ + 2² + ... + 2ⁿ
Узнаем геометрическую прогрессию с n + 1 членами. А её сумма:
<math>\ S_{n+1} = b_1 \frac{q^{n+1} - 1}{q - 1} = 1 \frac{2^{n+1} - 1}{2 - 1} = 2^{n + 1} - 1</math>

Порядки обхода деревьев

Требуется составить алгоритм, обходящий все узлы дерева в некотором порядке.
Существует несколько вариантов обходов, каждый из которых описывается рекурсивным алгоритмом.

Рассмотрим эти алгоритмы для обычного и бинарного деревьев:
   

• Инфиксный

Д₁ К Д₂ Д₃ Д_n

и

БД: Левое_поддерево Корень Правое_поддерево

• Префиксный

К Д₁ Д₂ Д₃ ... Д_n

и

БД: Корень Левое_поддерево Правое_поддерево

+ * a b c — префиксная запись выражения

Примечание. Для вычисления выражений, записанных в префиксной форме, применяется рекурсивный алгоритм.

• Постфиксный

Д₁ Д₂ Д₃ ... Д_n К

и

БД: Левое_поддерево Правое_поддерево Корень

a b * с + — обратная польская бесскобочная запись выражения

Обратная польская запись  

Или Обратная польская нотация (ОПН) (Обратная бесскобочная запись (ОБЗ), Постфиксная нотация, Бесскобочная символика Лукашевича, Польская инверсная запись, Полиз) —
форма записи математических выражений, в которой операнды расположены перед знаками операций.

Обратная польская нотация была разработана австралийским философом и специалистом в области теории вычислительных машин Чарльзом Хэмблином в середине 1950-х на основе польской нотации, которая была предложена в 1920 году польским математиком Яном Лукасевичем. Работа Хэмблина была представлена на конференции в июне 1957, и издана в 1957 и 1962.

ОПН является наиболее удобной формой записи математических выражений и широко используется в вычислительной технике.
Основными её преимуществами являются возможность однократного просмотра при вычислении и простота преобразования из инфиксной записи (на основе простого алгоритма, предложенного Дейкстрой).

Подробнее см. Википедию

Реализация бинарного дерева

type
  TreeNode<T> = class
    data: T;
    left, right: TreeNode<T>;
  
    constructor (d: T; l, r: TreeNode<T>);
    begin
      data := d;
      left := l;
      right := r;
    end;
  end;

<xh4>Создание идеально-сбалансированного бинарного дерева</xh4>

function CreateTree(n: integer): TreeNode<integer>;
begin
  if n <= 0 then
    Result := nil
  else
    Result := new TreeNode<integer>(
      Random(100), 
      CreateTree((n-1) div 2), 
      CreateTree(n - 1 - (n-1) div 2));
end;

<xh4> Обходы БД </xh4>

• Инфиксный

procedure InfixPrintTree(root: TreeNode<integer>);
begin
  if root = nil then
    exit;
  
  InfixPrintTree(root.left);
  write(root.data, ' ');
  InfixPrintTree(root.right);
end;

Заметим, что кроме вывода root.data, над ним можно совершать еще массу действий (например, уменьшать на 1, или выводить его квадрат).
Поэтому есть смысл передавать в процедуру обхода выполняемое действие. Для этого определим процедурный тип и внесем в процедуру соответствующие изменения:

type
  IntAction = procedure (var data: integer);

procedure InfixTraverseTree(root: TreeNode<integer>; Action: IntAction);
begin
  if root = nil then
    exit;
  
  InfixTraverseTree(root.left, Action);
  Action(root.data);
  InfixTraverseTree(root.right, Action);
end;

• Префиксный

procedure PrefixTraverseTree(root: TreeNode<integer>; Action: IntAction);
begin
  if root = nil then
    exit;
  
  Action(root.data);
  PrefixTraverseTree(root.left, Action);
  PrefixTraverseTree(root.right, Action);
end;

• Постфиксный

procedure PostfixTraverseTree(root: TreeNode<integer>; Action: IntAction);
begin
  if root = nil then
    exit;
  
  PostfixTraverseTree(root.left, Action);
  PostfixTraverseTree(root.right, Action);
  Action(root.data);
end;

Замечание. Видим, что процедуры отличаются только моментом вызова Action. Поэтому можем избежать дублирования кода, написав процедуру, которой в качестве параметра также передается порядок обхода:

type
  /// Порядок обхода
  TraversalOrder = (Infix, Prefix, Postfix);

procedure TraverseTree(root: TreeNode<integer>; Action: IntAction; order: TraversalOrder := Infix);
begin
  if root = nil then
    exit;
  
  if order = Prefix then    // если префиксный порядок обхода, 
    Action(root.data);      // то сначала обрабатываем корень

  TraverseTree(root.left, Action, order);

  if order = Infix then     // если инфиксный, то корень надо обработать
    Action(root.data);      // после левого поддерева, но перед правым

  TraverseTree(root.right, Action, order);

  if order = Postfix then   // и если порядок постфиксный,
    Action(root.data);      // то корень обрабатывается последним
end;

<xh4> Связь деревьев и рекурсии </xh4> Пусть у нас есть такое бинарное дерево:

Вызовем процедуру InfixPrintTree(root).
Заметим, что её дерево рекурсивных вызовов совпадет с нашим деревом:

С ним же совпадет и дерево рекурсивных вызовов каждой из процедур: InfixPrintTree, PrefixPrintTree или PostfixPrintTree.

Сделаем несколько замечаний:

• Форма дерева рекурсивных вызовов не зависит от порядка обхода.
• В каждый момент времени глубина рекурсии совпадает с текущей глубиной дерева.
• Стрелочки вниз соответствуют рекурсивному спуску, а стрелочки вверх — рекурсивному возврату.
• Все алгоритмы на деревьях наиболее компактно записываются в рекурсивной форме.

// В ширину
function TraverseTreeWidth<T>(root: Node<T>): sequence of T;
begin
  if root = nil then
    exit;
  var q := new Queue<Node<T>>;
  q.Enqueue(root);
  while q.Count>0 do
  begin
    var d := q.Dequeue();
    yield d.data;
    if d.left<>nil then 
      q.Enqueue(d.left);
    if d.right<>nil then
      q.Enqueue(d.right);
  end;
end;

// В глубину (нерекурсивный аналог Prefix)
function TraverseTreeDepth<T>(root: Node<T>): sequence of T;
begin
  if root = nil then
    exit;
  var s := new Stack<Node<T>>;
  s.Push(root);
  while s.Count>0 do
  begin
    var d := s.Pop();
    yield d.data;
    if d.right<>nil then
      s.Push(d.right);
    if d.left<>nil then 
      s.Push(d.left);
  end;
end;

Лекция 9

Задачи на бинарные деревья

Поиск элемента в бинарном дереве

function Find(root: TreeNode<integer>; k: integer): TreeNode<integer>;
begin
  if root = nil then
  begin
    Result := nil;
    exit;
  end;

  if root.data = k then  // если нашли элемент, то возвращаем его и прекращаем поиск
  begin                  
    Result := root;
    exit;              
  end;

  // ищем элемент в левом поддереве
  Result := Find(root.left, k);

  // если не нашли в левом поддереве, то ищем в правом
  if Result = nil then             
    Result := Find(root.right, k);
end;

Примечание. Если в списке находятся несколько искомых элементов, то будет возвращена ссылка на первый из них, а именно — находящийся в «самом левом» поддереве.

Определение минимальной суммы от корня к листу

Решение 1. Очевидный рекурсивный алгоритм

function SimplePathSum(root: TreeNode<integer>): integer;
begin
  if root = nil then
    Result := integer.MaxValue 
  else if (root.Left = nil) and (root.Right = nil) then // правка 
    result := root.Data
  else 
    result := root.Data + Min(SimplePathSum(root.Left), SimplePathSum(root.Right));
end;

Здесь осуществляется полный обход дерева (посещение всех узлов)

Решение 2. Алгоритм перебора с возвратом.

Изменим стратегию нахождения минимальной суммы. Будем накапливать сумму в глобальной переменной sum и всякий раз по достижении листа сравнивать ее с глобальной переменной min.

Заметим, что всякий раз мы, добавляя к сумме очередное значение, осуществляем перебор, и если решение неполное, то продолжаем рекурсивные вызовы. После рекурсивных вызовов мы осуществляем возврат суммы к предыдущему значению. В результате в каждой точке в переменной sum хранится сумма элементов от корня к текущему узлу.

Подобный алгоритм называется алгоритмом перебора с возвратами.

var 
  sum: integer := 0;
  min: integer := MaxInt;
 
procedure MinSumPath1(r: TreeNode<integer>);
begin
  if r=nil then
    exit;    
  sum += r.data;
  if (r.left=nil) and (r.right=nil) and (sum<min) then
    min := sum;
  MinSumPath1(r.left);    
  MinSumPath1(r.right); 
  sum -= r.data;
end;

Данный метод работает примерно с той же скоростью, что и предыдущий (т.к. осуществляется полный перебор). Однако, в отличие от предыдущего метода, он может быть существенно ускорен за счет отсечения заведомо неоптимальных решений. В данном случае если значение sum превысит min, то далее рекурсивные вызовы можно не делать - решение не оптимально (минимум на этом пути достигнут не будет).

Реализуем предыдущий алгоритм в виде функции и уберем все глобальные переменные

function MinSumPath2(r: TreeNode<integer>; sum,min: integer): integer;
begin
  if r<>nil then
  begin
    sum += r.data;
    if (r.left=nil) and (r.right=nil) and (sum<min) then
      min := sum;
    min := MinSumPath2(r.left,sum,min);    
    min := MinSumPath2(r.right,sum,min); 
  end;
  Result := min;
end;

Изменим данный алгоритм, осуществляя выход из рекурсии если сумма на каком-то шаге окажется не меньше min.

Решение 2. Алгоритм перебора с возвратом. Метод ветвей и границ

Метод ветвей и границ является вариацией полного перебора, но производит отсев подмножеств допустимых решений, заведомо не содержащих оптимальных решений.

function MinSumPath3(r: TreeNode<integer>;sum,min: integer): integer;
begin
  if r<>nil then
  begin
    sum += r.data;
    if (r.left=nil) and (r.right=nil) and (sum<min) then
      min := sum;
    if sum<min then
    begin
      min := MinSumPath3(r.left,sum,min);    
      min := MinSumPath3(r.right,sum,min); 
    end;
  end;
  Result := min;
end;

Данный алгоритм работает практически мгновенно.

Вот время работы при n=20000000

• Построение дерева: 6.5 с.
• Алгоритм перебора с возвратом: 0.828 с.
• Метод ветвей и границ: 0.015 с.

Количество рекурсивных вызовов при различных запусках: 25000, 16000, 28000 (в алгоритме 1 количество рекурсивных вызовов равно n=20000000)

Бинарные деревья поиска

Бинарное дерево называют бинарным деревом поиска (БДП), если для каждого узла дерева выполнено следующее:
все элементы, находящиеся в левом поддереве, меньше элемента в корне, а все элементы, находящиеся в правом поддереве — больше.

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

Пример БДП:

Обойдем наше БДП с помощью инфиксного обхода:

10 15 17 27 28 32 45 50 59 64 67 71 77 80 89

Значит, при инфиксном обходе БДП получаем отсортированную последовательность данных.
Т.о., в каждый момент времени БДП хранит отсортированные данные.

Каково же количество действий при обходе БДП?
Поскольку при обходе мы проходим по каждому ребру дважды (один раз — вниз, на рекурсивном спуске, и один раз — вверх, на рекурсивном возврате), то мы тратим количество действий, в два раза превышающее количество ребер.
Т.к. количество ребер на 1 меньше количества вершин, то всего тратится <math>2(n - 1)</math> действий, где <math>n</math> — количество вершин (для сравнения: в массиве обход занимает <math>n</math> действий.

<xh4>Алгоритм добавления элемента к БДП</xh4> Алгоритм добавления элемента к БДП с повторяющимися элементами будет немного отличаться от алгоритма добавления к БДП без повторяющихся элементов — во втором случае, если элемент, который мы хотим добавить, в дереве уже есть, мы ничего не делаем.
Этот случай и рассмотрим:

procedure Add(var root: TreeNode<integer>; x: integer);
begin
  if root = nil then
  begin
    root := new TreeNode<integer>(x, nil, nil);
    exit;
  end;

  if x < root.data then
    Add(root.left, x)
  else if x > root.data then
    Add(root.right, x);
end;

Теперь создание дерева не представляет сложности:

var n := 15;
var r: TreeNode<integer> := nil;

for var i := 1 to n do   // создание случайного БДП с количеством вершин, равным n
  Add(r, Random(100));

Вспомним, что при инфиксном выводе БДП получаем отсортированную последовательность данных, значит при n вызовах процедуры добавления элемента к БДП, получим отсортированную последовательность из n элементов.
Поэтому данный алгоритм называется алгоритмом сортировки деревом.

Разберемся, сколько действий потребует одно добавление в среднем.
Пусть дерево, в которое мы добавляем, является идеально-сбалансированным, тогда количество его уровней <math>k \approx \; log_2 n</math>, где <math>n</math> — количество узлов.
Видим, что количество операций в Add совпадает глубиной дерева <math>k</math> (при каждом рекурсивном вызове Add мы опускаемся вниз по дереву на 1 уровень, и вставка осуществляется в лист дерева)

Т.о., при добавлении <math>n</math> элементов, в случае, если дерево всякий раз остается близким к идеально-сбалансированному, тратится <math>n\log_2 n</math> действий (столько же, сколько при быстрой сортировке).

Замечание 1. Данная оценка справедлива в среднем.
Замечание 2. Данная оценка совпадает с оценкой количества операций при быстрой сортировке, а значит является оптимальной для произвольных данных.

<xh4>Оценка количества операций при сортировке деревом в худшем случае</xh4> Будем добавлять элементы в БДП в возрастающем порядке:

Add(10);
Add(15);
Add(17);
...
Add(87);

Получим "однобокое" дерево:

10
  \
   15
     \
      17
        \
         ...
           \
            87     

При таком порядке добавлений, количество операций составляет примерно <math>n^2</math> (как и в худшем случае быстрой сортировки).

Замечание. Чтобы сохранить асимптотическую оценку <math>n\log_2 n</math> и в худшем случае, всякий раз, при добавлении в дерево, надо проводить так называемую перебалансировку, которая сохраняет свойство дерева быть деревом поиска, но уменьшает, по возможности, его глубину до минимальной.

<xh4>Поиск элемента в БДП</xh4>

function Find(root: TreeNode<integer>; x: integer): boolean;
begin
  if root = nil then
    Result := false
  else if root.data = x then
    Result := True
  else if x < root.data then 
    Result := Find(root.left, x) 
  else // if x > root.data then 
    Result := Find(root.right, x);
end;

Очевидно, количество операций совпадает с глубиной БДП <math>k \approx \; log_2 n</math> в среднем.
Заметим, что алгоритм бинарного поиска в отсортированном массиве занимает столько же действий.

АТД — Абстрактные Типы Данных. Классы как реализация АТД

Что мы знаем о классах

1. Класс — это составной тип данных
2. Класс, как и запись, содержит поля и методы
3. Переменная типа класс и переменная типа запись по-разному хранятся в памяти (ссылочная и размерная организация данных)
4. Для создания объекта класса и связывания его с переменной класса вызывается специальная функция-метод, называемая конструктором
5. Можно создавать шаблоны классов, параметризованные одним или несколькими типами

Понятие абстрактного типа данных

До сих пор мы сталкивались с конкретными типами данных, которые характеризуются:

• набором допустимых значений
• представлением в памяти
• набором допустимых операций, которые можно выполнять над объектами данного типа

Абстрактный тип данных — это тип данных, доступ к которым осуществляется только через некоторый набор действий (операций, команд).
Этот набор действий называется интерфейсом абстрактного типа данных.
То, как реализован абстрактный тип данных, самим АТД не определяется.

Итак, абстрактный тип данных - это интерфейс, набор операций без реализации.

Класс является одной из возможных реализацией абстрактного типа данных (АТД).
Т.е. класс определяет интерфейс абстрактного типа данных и дает реализацию этого интерфейса (без которой использование АТД невозможно).

Деление операций, расположенных в классе, на интерфейс и реализацию очень важно в современном программировании и называется принципом отделения интерфейса от реализации.
Он заключается в том, что клиентская программа, пользующаяся классом, использует только его интерфейс (в то время, как его реализация важна только разработчикам класса).

Более того, реализацию в классе принято скрывать от клиента специальными конструкциями.
Этот принцип называется принципом сокрытия реализации (или защитой доступа).

А теперь рассмотрим пример абстрактного типа данных — стек.

АТД Стек

Стек — это набор данных, устроенный по принципу LIFO (Last In First Out) — последним пришел — первым вышел.

Мы уже знакомы со стеком. Хорошими примерами могут служить программный стек, колода карт или магазин автомата.
Т.о. стек следует представлять как стопку объектов, положенных один на другой. В каждый момент можно:

• положить значение на вершину стека (Push, втолкнуть значение в стек)
• посмотреть значение на вершине стека (Top)
• снять значение с вершины стека (Pop)
• проверить, пуст ли стек (IsEmpty)

Причем, если предмет последним положили на вершину стопки, то он будет снят первым - отсюда и название LIFO.

Описывать стек будем в виде класса.

<xh4>Интерфейс класса Stack</xh4>

type 
  /// Шаблон класса Stack
  Stack<T> = class 
    constructor Create;
     
    /// Кладет элемент x на вершину стека
    procedure Push(x: T);

    /// Возвращает элемент типа T, снимая его с вершины стека
    function Pop: T;
    /// Возвращает значение элемента на вершине стека
    function Top: T;

    /// Возвращает истину, если стек пуст
    function IsEmpty: boolean;
  end;

Чтобы обеспечить защиту доступа к коду класса, следует поместить описание класса в модуль и откомпилировать его, или же создать библиотеку.
При создании модуля интерфейс класса помещается в интерфейсную секцию модуля, а реализация методов класса — в секцию реализации модуля.

Теперь, когда у нас есть интерфейс класса Stack , напишем клиентскую программу.
Задача. Вычислить выражение, записанное в обратной польской записи (ПОЛИЗ).

Пусть в строке a хранится выражение в обратной польской бесскобочной нотации, например:
a = '598+46**7+*'
Условимся, что каждый символ представляет собой либо цифру, являющуюся числом, либо знак, являющийся операцией.

<xh4> Алгоритм вычисления выражения в ПОЛИЗ </xh4>

Цикл по символам {
  если текущий символ — цифра, то
    положить её на стек
  иначе, если текущий символ — знак операции, то {
    снять со стека два последних числа
    совершить над ними указанную операцию
    поместить результат на стек
  }
}

В результате работы этого алгоритма на стеке останется единственное число, являющееся значением выражения.

Для указанной строчки алгоритм выполнит со стеком следующие операции:

ε (пусто)
5
5 9
5 9 8 

5 9 8 
   + 
5 17

5 17 4 
5 17 4 6 

5 17 4 6
      * 
5 17 24

5 17 24
    * 
5 408

5 408 7 

5 408 7
     + 
5 415 

5 415
 *
2075

Запрограммируем этот алгоритм.
Пусть класс Stack определен в модуле Collections.
Код клиентской программы:

uses Collections;

var 
  a: string := '598+46**7+*';
  s: Stack<real> := new Stack<real>;

begin
  for var i := 1 to a.Length do
    case a[i] of
      '0'..'9': s.Push(StrToInt(a[i]));
      '+': s.Push(s.Pop + s.Pop);
      '*': s.Push(s.Pop * s.Pop);
      '-': begin
             var minuend := s.Pop;
             var subtrahend := s.Pop;
             s.Push(minuend - subtrahend);
           end;
      '/': begin
             var dividend := s.Pop;
             var divisor := s.Pop;
             s.Push(dividend / divisor);
           end;
    end;
  writeln(s.Pop);
  Assert(s.IsEmpty);
end.

Замечание 1. Именно деление на интерфейс и реализацию позволило нам приступить к написанию клиентской программы, имея только интерфейс класса Stack и ничего не зная о его реализации.
Т.о. в большом проекте налицо разделение обязанностей:

• Одна группа программистов — разработчики библиотек — создают АТД в виде классов и предоставляют остальным интерфейс этих классов
• Другая группа программистов пользуется этими классами, как АТД, вызывая методы интерфейсов этих классов

При таком способе разделения обязанностей обычно используется следующий сценарий:

• Вначале быстро создается первая реализация класса (неэффективная) и предоставляется клиентам
• Клиенты с помощью этой реализации пишут клиентские программы
• В этот момент группа разработчиков класса делает более эффективную реализацию, после чего меняет на неё исходную.
  При этом, все уже написанные клиентские программы продолжают работать.

Замечание 2. Поскольку интерфейс впоследствии поменять практически нельзя (в отличие от реализации), разработка интерфейсов является важнейшим мероприятием на начальном этапе разработки проекта.

<xh4> Реализация стека на базе массива </xh4>

unit Collections;

interface

type
  /// Шаблон класса Stack
  Stack<T> = class
  private    // содержимое этой секции недоступно из клиентской программы  
    /// Массив элементов стека
    datas: array of T;
    /// Индекс первого пустого элемента
    tp: integer;  
   
  public     // содержимое этой секции открыто для клиентской программы
    constructor Create;

    /// Кладет элемент x на вершину стека
    procedure Push(x: T);

    /// Возвращает элемент типа T, снимая его с вершины стека
    function Pop: T;
    /// Возвращает значение элемента на вершине стека
    function Top: T;

    /// Возвращает истину, если стек пуст
    function IsEmpty: boolean;
  end;
   
implementation

/// Максимальный размер стека
const MAX_STACK = 1000;

constructor Stack<T>.Create;
begin
  tp := 0;
  SetLength(datas, MAX_STACK);
end;

{Кладет элемент x на вершину стека} 
procedure Stack<T>.Push(x: T);
begin
  Assert(tp < MAX_STACK);
  datas[tp] := x;
  tp += 1;
end;

{Возвращает элемент типа T, снимая его с вершины стека}
function Stack<T>.Pop: T;
begin
  Assert(not IsEmpty);
  result := datas[tp-1];
  tp -= 1;
end;

{Возвращает значение элемента на вершине стека}
function Stack<T>.Top: T;
begin
  Assert(not IsEmpty);
  result := datas[tp-1];
end;

{Возвращает истину, если стек пуст}
function Stack<T>.IsEmpty: boolean;
begin
  result := (tp <= 0);
end;

end.

<xh4> Реализация стека на базе односвязного линейного списка </xh4>

unit Nodes;

interface

type
  /// Узел с одним полем связи
  SingleNode<DataType> = class
    /// Значение
    data: DataType;
    /// Ссылка на следующий элемент
    next: SingleNode<DataType>;
    
    constructor (dt: DataType; nxt: SingleNode<DataType>);
    begin
      data := dt;
      next := nxt;
    end;
  end;

implementation

end.

unit Collections;

interface

uses Nodes;

type
  /// Шаблон класса Stack
  Stack<T> = class
  private    // содержимое этой секции недоступно из клиентской программы  
    /// Указатель на вершину стека
    tp: SingleNode<T> := nil;  
    
  public     // содержимое этой секции открыто для клиентской программы
    constructor Create;
    
    /// Кладет элемент x на вершину стека
    procedure Push(x: T);

    /// Возвращает элемент типа T, снимая его с вершины стека
    function Pop: T;
    /// Возвращает значение элемента на вершине стека
    function Top: T;
    
    /// Возвращает истину, если стек пуст
    function IsEmpty: boolean; 
  end;

implementation

constructor Stack<T>.Create;
begin
  tp := nil;
end;

{Кладет элемент x на вершину стека} 
procedure Stack<T>.Push(x: T);
begin
  tp := new SingleNode<T>(x, tp);
end;

{Возвращает элемент типа T, снимая его с вершины стека}
function Stack<T>.Pop: T;
begin
  Assert(not IsEmpty);
  result := tp.data;
  tp := tp.next;
end;

{Возвращает значение элемента на вершине стека}
function Stack<T>.Top: T;
begin
  Assert(not IsEmpty);
  result := tp.data;
end;

{Возвращает истину, если стек пуст}
function Stack<T>.IsEmpty: boolean;
begin
  result := (tp = nil);
end;

end.

АТД и класс Очередь

Очередь — это набор данных, устроенный по принципу FIFO (First In First Out) — первым пришел — первым вышел.

В каждый момент можно:

• добавить значение в хвост очереди (Enqueue)
• убрать значение из головы очереди (Dequeue)
• проверить, пуста ли очередь (IsEmpty)

Оформим АТД «очередь» в виде шаблона класса.

<xh4> Интерфейс класса Queue </xh4>

type  
  /// Шаблон класса Queue
  Queue<T> = class
    constructor Create;
    
    /// Добавляет элемент x в хвост очереди
    procedure Enqueue(x: T);
    
    /// Возвращает элемент типа T, убирая его из головы очереди
    function Dequeue: T;
    
    /// Возвращает истину, если очередь пуста
    function IsEmpty: boolean; 
  end;

<xh4> Реализация очереди на базе односвязного линейного списка </xh4>

unit Collections;

interface

uses Nodes;

type
  // Здесь описан шаблон класса Stack

  /// Шаблон класса Queue
  Queue<T> = class
  private
    /// Голова очереди
    head: SingleNode<T>;
    /// Хвост очереди
    tail: SingleNode<T>;
    
  public
    constructor Create;
    
    /// Добавляет элемент x в хвост очереди
    procedure Enqueue(x: T);
    
    /// Возвращает элемент типа T, убирая его из головы очереди
    function Dequeue: T;
    
    /// Возвращает истину, если очередь пуста
    function IsEmpty: boolean;
  
  end;

implementation

// Здесь реализованы методы шаблона класса Stack

constructor Queue<T>.Create;
begin
  head := nil;
  tail := nil;
end;

{Добавляет элемент x в хвост очереди} 
procedure Queue<T>.Enqueue(x: T);
begin
  if IsEmpty then
  begin
    head := new SingleNode<T>(x, nil);
    tail := head;
  end
  else  // if not IsEmpty
  begin
    tail.next := new SingleNode<T>(x, nil);
    tail := tail.next;
  end;
end;

{Возвращает элемент типа T, убирая его из головы очереди}
function Queue<T>.Dequeue: T;
begin
  Assert(not IsEmpty);
  
  result := head.data;
  head := head.next;
  if head = nil then
    tail := nil;
end;

{Возвращает истину, если очередь пуста}
function Queue<T>.IsEmpty: boolean;
begin
  result := (head = nil);
end;
  
end.

Наследование

Основные определения

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

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

Пример. Главный алгоритм работы операционной системы.

* начальная инициализация
* цикл обработки сообщений
    если сообщение пришло то 
      обработать сообщение 
    до сообщения «Конец»
* заключительные действия

Как видим, этот алгоритм тривиален и ничего не говорит о том, как работает ОС.
————————————

Поскольку главный алгоритм сложной системы не существует или тривиален, то для программирования работы этой сложной системы мы:

• выявляем классы объектов, присутствующих в этой системе
• их свойства и методы
• выявляем то общее, что есть в различных классах
• выявляем различные зависимости между классами и взаимодействие между объектами этих классов

Примеры зависимостей между классами

1. класс содержит в качестве поля объект другого класса
2. в методе класса параметром является объект другого класса
3. метод класса вызывает статический метод другого класса
4. один из классов является разновидностью другого

Определение. Наследованием называется такая зависимость между классами, при которой один из классов является разновидностью другого.

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

Для классов, связанных наследованием, используют следующие термины:

• базовый — производный
• предок — потомок
• надкласс — подкласс

Каковы цели наследования?

1. Повторное использование кода.
2. Обеспечение вариабельности и изменчивости кода.

Наследование — это расширение или сужение?
Наследование — это расширение интерфейса класса, но сужение количества объектов (представителей) класса.

Наследование на примере Student - SeniorStudent

Про переменную Self см. здесь.

Рассмотрим следующий пример наследования:

Класс SeniorStudent (студент старших курсов) является разновидностью класса Student. Будем считать, что на младших курсах студент еще не знает, сколько лет он будет учиться и какую академическую степень получит, поэтому считается, что он учится 4 года. Будем также считать, что он узнает, какую академическую степень получит (бакалавр, специалист, магистр), когда становится студентом старших курсов (SeniorStudent). В этот же момент к нему прикрепляется научный руководитель из числа преподавателей (Teacher).

<xh4> Базовый класс Student </xh4>

interface
uses System;
   
const
  /// Минимальный допустимый возраст студента
  MIN_AGE = 1;
  /// Максимальный допустимый возраст студента
  MAX_AGE = 120;
  
  /// Первый курс
  FIRST_COURSE = 1;
  /// Максимальный курс для студентов младших курсов
  LAST_UNDERGRADUATE_COURSE = 4;

type
  /// Студент
  Student = class
  private
    fName: string;
    fAge, fCourse, fGroup: integer;

  public
    /// Имя — только на чтение
    property Name: string read fName;
    /// Возраст — только на чтение
    property Age: integer read fAge;
    /// Курс — только на чтение
    property Course: integer read fCourse;
    /// Группа — только на чтение
    property Group: integer read fGroup;
    
    /// <summary>
    /// Создает нового студента
    /// </summary>
    /// <param name="Name">Имя (пустое недопустимо)</param>
    /// <param name="Age">Возраст (отрицательный или больший MAX_AGE недопустим)</param>
    /// <param name="Course">Курс (отрицательный или больший LAST_UNDERGRADUATE_COURSE недопустим)</param>
    /// <param name="Group">Группа (отрицательная недопустима)</param>
    constructor Create(Name: string; Age, Course, Group: integer);
    
    procedure SetAge(Age: integer);
    procedure SetGroup(Group: integer);
    
    /// Переводит студента на следующий курс, если он меньше LAST_UNDERGRADUATE_COURSE
    procedure NextCourse;
    
    procedure Print;
    procedure Println;
  end;
  
implementation

constructor Student.Create(Name: string; Age, Course, Group: integer);
begin
  if Name <> '' then
    fName := Name
  else
    raise new Exception(
    'Попытка присвоить студенту пустое имя!');
    
  SetAge(Age);
  
  if (Course >= FIRST_COURSE) and (Course <= LAST_UNDERGRADUATE_COURSE) then
    fCourse := Course
  else
    raise new Exception(
    'Выход за границы диапазона допустимых курсов [' + 
    FIRST_COURSE.ToString + '..' + LAST_UNDERGRADUATE_COURSE.ToString + ']!');
    
  SetGroup(Group);
end;

procedure Student.SetAge(Age: integer);
begin
  if (Age >= MIN_AGE) and (Age <= MAX_AGE) then
    fAge := Age
  else
    raise new Exception(
    'Выход за границы диапазона допустимого возраста [' + 
    MIN_AGE.ToString + '..' + MAX_AGE.ToString + ']!');
end;

procedure Student.SetGroup(Group: integer);
begin
  if (Group > 0) then
    fGroup := Group
  else
    raise new Exception(
    'Попытка присвоить группе отрицательный номер!');
end;

procedure Student.NextCourse;
begin
  if fCourse < LAST_UNDERGRADUATE_COURSE then
    fCourse += 1
  else
    raise new Exception(
    'Выход за границы диапазона допустимых курсов [' + 
    FIRST_COURSE.ToString + '..' + LAST_UNDERGRADUATE_COURSE.ToString + ']!');
end;

procedure Student.Print;
begin
  WriteFormat(
    'Имя: {0}  Возраст: {1}  Курс: {2}  Группа: {3}  ',
    fName, fAge, fCourse, fGroup);
end;

procedure Student.Println;
begin
  Print;
  writeln();
end;

<xh4> Производный класс SeniorStudent </xh4> SeniorStudent — студент старших курсов.
Помимо имени, возраста, курса и группы:

• у него будет научный руководитель (Advisor: Teacher)
• он будет знать тему курсовой работы, которую получает от своего научного руководителя
• и для него будет известно, какую он получает академическую степень Degree (бакалавра, специалиста или магистра)

Будем считать, что класс преподавателя у нас уже есть, и у него есть метод SayCourseWorkTheme(MyStudent: SeniorStudent): string.

Приступим к реализации SeniorStudent.
Для начала нам понадобится вспомогательный тип DegreeType (академическая степень):

type
  /// Академическая степень (Бакалавр, Специалист, Магистр)
  DegreeType = (Bachelor, Specialist, Magister);

Теперь напишем интерфейс нашего старшекурсника:

  /// Студент старших курсов
  SeniorStudent = class (Student)
  private
    fAdvisor: Teacher;
    fDegree: DegreeType;

  public
    /// Научный руководитель — только на чтение
    property Advisor: Teacher read fAdvisor;
    /// Образовательная степень — только на чтение
    property Degree: DegreeType read fDegree;
    
    /// <summary>
    /// Создает нового студента старших курсов
    /// </summary>
    /// <param name="Name">Имя (пустое недопустимо)</param>
    /// <param name="Age">Возраст (отрицательный или больший MAX_AGE недопустим)</param>
    /// <param name="Course">Курс (отрицательный или больший MAX_COURSE недопустим)</param>
    /// <param name="Group">Группа (отрицательная недопустима)</param>
    /// <param name="Advisor">Научный руководитель</param>
    /// <param name="EduModel">Академическая степень (бакалавр, специалист, магистр)</param>
    constructor Create(Name: string; Age, Course, Group: integer; 
      Advisor: Teacher; Degree: DegreeType);
    
    /// Возвращает тему курсовой работы 
    function CourseWorkTheme: string;
    
    procedure NextCourse;
    
    procedure Print;
    procedure Println;
  end;

Как CourseWorkTheme и NextCourse мы знаем:

function SeniorStudent.CourseWorkTheme: string;
begin
  Result := fAdvisor.SayCourseWorkTheme(self);
end;

procedure SeniorStudent.NextCourse;
begin
  var lastCourse: integer;
  case fDegree of
    Bachelor:   lastCourse:= 4;
    Specialist: lastCourse:= 5;
    Magister:   lastCourse:= 6;
  end;

  if fCourse < lastCourse then
    fCourse += 1
  else
    raise new Exception(
    'Выход за границы диапазона допустимых курсов [' + 
    FIRST_COURSE.ToString + '..' + lastCourse.ToString + ']!');
end;

Замечание. В процессе разработки возникла проблема доступа к приватным полям предка (fCourse)
Если Student и SeniorStudent реализованы в одном модуле, то такой проблемы нет и доступ возможен, однако, если они они реализованы в разных модулях, то данный код не откомпилируется.
Исправим это в дальнейшем, а пока будем считать, что классы реализованы в одном модуле.

Заметим, что процедура NextCourse была полностью переопределена в потомке.
Но, как правило, одноименный метод в потомке не переписывается полностью, а вызывает соответствующий метод предка.

Напомним, что переопределяющий метод называется также замещающим.

Для вызова в методе Method замещенного метода предка используется конструкция

inherited Method

Inherited — значит унаследованный.

Воспользуемся этим при реализации оставшихся методов:

constructor SeniorStudent.Create(Name: string; Age, Course, Group: integer; 
  Advisor: Teacher; Degree: DegreeType);
begin
  inherited Create(Name, Age, Course, Group);
  
  if Advisor <> nil then
    fAdvisor := Advisor
  else
    raise new Exception(
    'Параметр «Advisor» конструктора является нулевой ссылкой!');
    
  fDegree := Degree;
end;

procedure SeniorStudent.Print;
begin
  inherited Print;
  
  write('Преподаватель: ');  
  fAdvisor.Print;
  
  write('Академическая степень: ');
  case fDegree of
    Bachelor:   write('Бакалавр');
    Specialist: write('Специалист');
    Magister:   write('Магистр');
  end;
end;

procedure SeniorStudent.Println;
begin
  Print;
  writeln();
end;

Полный текст модуля University

Вызов унаследованных конструкторов

Конструктор — это функция, создающая объект класса и возвращающая ссылку на него.

Вспомним, как выглядел конструктор класса SeniorStudent (студента старших курсов):

type SeniorStudent = class (Student)
   ...
  constructor SeniorStudent.Create(Name: string; Age, Course, Group: integer; 
    Advisor: Teacher; Degree: DegreeType);
  begin
{*} inherited Create(Name, Age, Course, Group);
    
    if Advisor <> nil then
      fAdvisor := Advisor
    else
      raise new Exception(
      'Параметр «Advisor» конструктора является нулевой ссылкой!');
    fDegree := Degree;
  end;

...

var ss: SeniorStudent := new SeniorStudent(...);

(*) Унаследованный конструктор базового класса вызывается как процедура, т.е. возвращаемое значение игнорируется.

Вопрос. Создает ли вызов унаследованного конструктора базового класса объект в динамической памяти?
Ответ. Нет. Объект создается вызовом конструктора производного класса. А вызов унаследованного конструктора производится как вызов обычного метода.

Вопрос. Можно ли совершать вызов унаследованного конструктора не первым оператором в коде основного конструктора?
Ответ. В PascalABC.NET нельзя, как и в таких языках, как Java, C++ и C#.

Принцип «открыт - закрыт»

Принцип «открыт - закрыт» состоит в следующем: код программы должен быть закрыт для изменения текста и открыт для модификации поведения и функциональности.

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

Замечание. Базовый класс в настоящем должен проектироваться с учетом будущих изменений. Т.е. так, чтобы в будущем мы могли породить от него потомка с нужной нам функциональностью.

Пример. Очередь с подсчетом элементов.
Реализуем класс очереди с подсчетом элементов (CountingQueue<T>) как производный от обычной очереди (Queue<T>) (см. модуль Collections):

interface
uses Collections;
  
type 
  /// Очередь с подсчетом элементов
  CountingQueue<T> = class (Queue<T>)
  private
    /// Количество элементов
    fCount: integer;
    
  public
    /// Количество элементов
    property Count: integer read fCount;
    
    /// Создает пустую очередь
    constructor Create;
    
    /// Добавляет элемент x в хвост очереди
    procedure Enqueue(x: T);
    /// Возвращает значение элемента в голове, удаляя его из очереди
    function Dequeue: T;
  end;

implementation

constructor CountingQueue<T>.Create;
begin
  inherited Create;
  fCount := 0;
end;

{Добавляет элемент x в хвост очереди}
procedure CountingQueue<T>.Enqueue(x: T);
begin
  inherited Enqueue(x);
  fCount += 1;
end;

{Возвращает значение элемента в голове, удаляя его из очереди}
function CountingQueue<T>.Dequeue: T;
begin
  Result := inherited Dequeue;
  fCount -= 1;
end;

end.

Замечание. В классе CountingQueue часть методов унаследована от класса Queue без замещения (например, метод IsEmpty).

Наследование и включение

Реализуем класс CountingQueue другим способом: включим очередь Queue в качестве приватного поля в класс CountingQueue и переопределим все методы очереди, делегируя вызов методов внутреннему объекту класса Queue:

interface
uses Collections;
  
type 
  /// Очередь с подсчетом элементов (на базе Queue)
  CountingQueue<T> = class
  private
    /// Встроенная очередь
    fq: Queue<T>;  // включение объекта класса
    /// Количество элементов
    fCount: integer;
    
  public
    /// Количество элементов
    property Count: integer read fCount;
    
    /// Создает пустую очередь
    constructor Create;
    
    /// Добавляет элемент x в хвост очереди
    procedure Enqueue(x: T);
    /// Возвращает значение элемента в голове, удаляя его из очереди
    function Dequeue: T;
    /// Возвращает значение элемента в голове очереди, не удаляя его
    function First: T;
    /// Возвращает истину, если очередь пуста
    function IsEmpty: boolean;
  end;

implementation

constructor CountingQueue<T>.Create;
begin
  fq := new Queue<T>;
  fCount := 0;
end;

{Добавляет элемент x в хвост очереди}
procedure CountingQueue<T>.Enqueue(x: T);
begin
  fq.Enqueue(x);
  fCount += 1;
end;

{Возвращает значение элемента в голове, удаляя его из очереди}
function CountingQueue<T>.Dequeue: T;
begin
  Result := fq.Dequeue;
  fCount -= 1;
end;

{Возвращает значение элемента в голове очереди, не удаляя его}
function CountingQueue<T>.First: T;
begin
  Result := fq.First;
end;

{Возвращает истину, если очередь пуста}
function CountingQueue<T>.IsEmpty: boolean;
begin
  Result := fq.IsEmpty;
end;

end.

В данном случае способ реализации с включением объекта класса хуже способа наследования от этого класса по следующим причинам:

• Мы считаем класс CountingQueue разновидностью класса Queue, поэтому он должен содержать все, что есть в Queue, и, возможно, что-то еще
• При включении нам придется, поэтому, переопределять все методы, а при наследовании — только необходимые

А вот в примере, где мы определяли класс SimpleSet на базе динамического массива, мы пользовались включением.
Почему тогда не использовалось наследование? Зададим вопрос: а является ли множество разновидностью динамического массива? Ответ: нет.

<xh4> Когда выбирать наследование, а когда — включение? </xh4> Есть два класса: A и B.
Зададим вопросы:

1. B является разновидностью A?
   (B is A?)
   Если ответ «да», то это — наследование.
2. A состоит из B?
   (A has B?)
   Если ответ «да», то это — включение.
3. A использует объект B для реализации?
   (A use B?)
   Если ответ «да», то это — включение.

Однако, не всегда ответы на эти вопросы однозначны. Приведем несколько примеров.

• Matrix является разновидностью Vector.
  Да. Можем рассматривать Matrix как вектор-строку, состоящую из векторов-столбцов.
• Vector является разновидностью Matrix.
  Тоже да. Можем рассматривать Vector как Matrix из одного столбца.
• Matrix состоит из Vector.
  Да.

Как видим, эти утверждения противоречивы. Становится понятно, что не всегда можно однозначно определить отношения между классами. Это зависит от задачи.

Приведем еще один пример: Circle и Ellipse.
С точки зрения аналитической геометрии, окружность — это разновидность эллипса. А с точки зрения программирования, возможно, удобнее унаследовать эллипс от окружности (Ведь окружность характеризуется координатами центра и радиусом, а эллипс — координатами центра и двумя радиусами. Поэтому можно реализовать эллипс, добавив к окружности еще один радиус).

Виды отношений между классами (нотация UML-диаграмм классов)

1. Ассоциация (связь)
   
   
   
   
2. Агрегация (слабая форма has — состоит логически)
   
   
   
   
3. Композиция (сильная форма has — состоит физически)
   
   
   
   
4. Наследование (обобщение)
   
   
   
   
5. Реализация интерфейсов
   
   
   (пока не знаем)

Пример 1. UML-диаграмма классов: персона, преподаватель, студент, студент старших курсов, группа.

Пример 2. UML-диаграмма факультета.

Вид доступа protected. Рефакторинг метода NextCourse

Иногда возникает необходимость разрешить доступ к полям или методам предка в методе потомка, но запретить для всех остальных. Такой вид доступа называется protected (защищенный).

Поскольку в одном модуле все имеют доступ и к приватной, и к публичной секциям класса, то данный вид доступа в Pascal'е имеет смысл только, если предок и потомок находятся в разных модулях.

Вернемся к примеру Student <— SeniorStudent: и у обычного студента, и у студента старших курсов есть метод NextCourse

procedure Student.NextCourse;
begin
  if fCourse < LAST_UNDERGRADUATE_COURSE then
    fCourse += 1
  else
    raise new Exception(
    'Выход за границы диапазона допустимых курсов [' + 
    FIRST_COURSE.ToString + '..' + LAST_UNDERGRADUATE_COURSE.ToString + ']!');
end;

...

procedure SeniorStudent.NextCourse;
begin
  var lastCourse: integer;
  case fDegree of
    Bachelor:   lastCourse := 4;
    Specialist: lastCourse := 5;
    Magister:   lastCourse := 6;
  end;
  if fCourse < lastCourse then
    fCourse += 1
  else
    raise new Exception(
    'Выход за границы диапазона допустимых курсов [' + 
    FIRST_COURSE.ToString + '..' + lastCourse.ToString + ']!');
end;

Проведем рефакторинг (изменение кода с целью улучшения, не влияющее на функциональность) нашего кода, т.к., если классы Student и SeniorStudent находятся в разных модулях, то у SeniorStudent нет доступа к приватному полю fCourse предка Student.
Выход: сделать fCourse protected-полем:

Student = class
private
  fName: string;
  fAge, fGroup: integer;
protected
  fCourse: integer;
public
  ...
end;

Замечание. Делать protected-поля и методы надо только в крайнем случае, т.к. они ослабляют защиту доступа.

Теперь проведем рефакторинг метода NextCourse.
1. Заметим, что реализации этого метода у предка и потомка включают очень похожие части:

(Student)
  if fCourse < LAST_UNDERGRADUATE_COURSE then
    fCourse += 1
  else
    raise new Exception(
    'Выход за границы диапазона допустимых курсов [' + 
    FIRST_COURSE.ToString + '..' + LAST_UNDERGRADUATE_COURSE.ToString + ']!');

(SeniorStudent)
  if fCourse < lastCourse then
    fCourse += 1
  else
    raise new Exception(
    'Выход за границы диапазона допустимых курсов [' + 
    FIRST_COURSE.ToString + '..' + lastCourse.ToString + ']!');

Оформим их в специальный метод ProtectedNextCourse(lastCourse) и поместим данный метод в protected-секцию класса Student. Тогда им можно будет пользоваться в методах классов Student, SeniorStudent, и нигде более.

Поскольку упоминание поля fCourse теперь полностью находится в методе ProtectedNextCourse, это поле вновь можно сделать приватным в классе Student.

2. Оформим участок кода метода SeniorStudent.NextCourse:

  var lastCourse: integer;
  case fDegree of
    Bachelor:   lastCourse := 4;
    Specialist: lastCourse := 5;
    Magister:   lastCourse := 6;
  end;

в виде глобальной функции LastCourseByDegree(degree), которая возвращает последний курс, соответствующий академической степени degree.

Полный текст модулей после рефакторинга

Наследование и выявление общего предка

Пример 1.
Рассмотрим следующие классы:

Вынесем то общее, что есть в классах Student и Teacher в базовый класс Person:

Реализация полученных классов

Пример 2.
Рассмотрим следующие классы:

Point
   - x
   - y
   + Draw()

Circle
   - radius
   + Draw()

Какой класс является предком, а какой потомком?

Пусть потомок — окружность.
Замечание. Данный вид наследования неудачен, т.к. окружность не наследуется от «точки с возможностью рисования», а скорее содержит точку как центр. Но, и окружность, и точка являются разновидностями некоторого класса, содержащего координаты и метод Draw.
Поэтому правильнее сделать так :

Присваивание в иерархии предок-потомок

Рассмотрим уже знакомую иерархию классов:

Что будет происходить при выполнении следующего кода?

begin
  var s: Student := new Student('Иванов', 17, 1, 11);
  var p: Person := new Person('Петров', 23);
  s := p; 
  p := s;
end;

Правило: Переменной базового класса можно присваивать объект производного класса. Это соответствует тому, что ячейка памяти отведённая под переменную базового класса, будет хранить адрес объекта производного класса. Переменной производного класса нельзя присвоить объект базового класса.
Соответствующий принцип в объектно-ориентированном программировании получил название принципа подстановки: во всех ситуациях, где используется объект базового класса, можно использовать объект производного класса без потери функциональности.

В соответствии со сказанным получаем:

s := p; // ошибка компиляции

p := s; // корректное присваивание

Пример.
Группу студентов послали на субботник. Без потери функциональности можно отправить на субботник:

• студентов младшекурсников
• студетнтов старшекурсников
• аспирантов

Что же происходит при присваивании

p := s;

?

В этом присваивании возникает приведение типа от производного класса к базовому (UpCast).

Приведение же от базового типа к производному (DownCast) осуществляется только с помощью явного приведения типа:

var p: Person;
p := new Student('Иванов', 17, 1, 11);

var s : Student;
s := Student(p); // явное приведение типа
s.NextCourse;

Примечание. Для явного приведения типа не обязательно явно создавать переменную, можем воспользоваться уже известной конструкцией

Student(p).NextCourse;

Замечание. Если к моменту явного приведения типа в переменной p находится объект базового класса, то возникнет исключение и программа завершится с ошибкой.

var p := new Student('Петров', 23);
var s := Student(p); // ошибка выполнения

Операции is и as

<xh4> is </xh4>

p is Student

Возвращает true, если переменная p ссылается в данный момент на объект типа Student (или производного от него типа) и false в противном случае.

Пример.

if p is Student then
  Student(p).NextCourse;

<xh4> as </xh4>

p as Student

Возвращает ссылку на студента, если преобразование возможно, и nil в противном случае.

Пример.

var s: Student := p as Student;
if s <> nil then
  s.NextCourse;

Замечание. Код с as будет работать немного быстрее, т.к. в первом примере преобразование, фактически, осуществляется дважды: первый раз — в операции is, а второй — при явном приведении типа.

Исключения

Введение. Что нам уже известно об исключениях

Впервые мы столкнулись с исключениями в начале курса, когда изучали оператор ввода и обработку ошибок ввода с помощью блока try..except.

Позже, при работе с файлами, возник термин «исключение». Мы узнали, как обрабатывать исключения с помощью оператора try..except и познакомились с оператором try..finally.

И, наконец, мы научились генерировать собственные исключения.

Теперь пришло время подробнее изучить исключения.

Иерархия исключений в .NET

Стандартные исключения связаны отношением наследования. Базовым классом для всех исключений является класс Exception, который находится в пространстве имен System.

<xh4> Классы исключений в .NET </xh4> Требуется подключить пространство имен System.

Exception (базовый класс исключения)
  Свойства:
  e.Message - текстовое описание ошибки, 
  e.StackTrace - последовательность вызовов функций, которая привела к исключению
    ApplicationException
        Все пользовательские исключения
    SystemException
        AccessViolationException (несанкционированный доступ к памяти)
        ArgumentException (один из передаваемых методу аргументов является недопустимым)
           ArgumentNullException
           ArgumentOutOfRangeException
        ArithmeticException
           DivideByZeroException (целочисленное деление на 0)
        IndexOutOfRangeException
        InvalidCastException (явное приведение к неправильному типу)
        FormatException (данные не соответствуют формату или форматная строка неправильная)
        NullReferenceException (попытка воспользоваться методом, полем или свойством через NULL-ссылку)
        OutOfMemoryException
        StackOverflowException
        NotImplementedException (метод не реализован)
        NotSupportedException (метод не поддерживается)
        System.Collections.Generic.KeyNotFoundException
        System.IO.IOException (пространство имен System.IO)
           System.IO.FileNotFoundException
           System.IO.EndOfStreamException (попытка чтения за концом потока)

Секции обработки исключений в блоке try

Полный синтаксис блока try выглядит так:

try
  ...
except
  on e: Exception1 do
    <оператор>;
  on e: Exception2 do
    <оператор>;
  ...
  [else <оператор>]
end;

Вопрос: надо ли обрабатывать все возникшие исключения?
Ответ: надо обрабатывать только те, которые понятно, как обрабатывать в данном месте программы. Остальные — не обрабатывать, а считать, что это должен сделать вызывающий код.

Пример 1.

procedure DoAnything(fName: string);
begin
  var f: text;
  assign(f, fName);
  reset(f);
  ...
end;

Вопрос: надо ли в данном контексте обрабатывать исключение FileNotFinfException?
Попробуем обработать:

try
  reset(f);
  ...
except
  // <ничего>
end;

Замечание. Обычно, тот, кто пишет код подпрограммы, которая может генерировать исключение, не знает, что с этими исключениями делать. А тот, кто вызывает — знает.
Поэтому обрабатывать исключение следует только в том месте, где уже известно, что надо делать (в нашем примере — в коде, вызывающем процедуру DoAnything).

Примечание. Раньше мы пользовались Assert:

var f: text;
Assert(FileExists(fName));
...

Недостаток этого способа состоит в том, что конкретное исключение FileNotFoundException заменяется на общее AssertionException, что плохо.

В более развитых средах, как мы уже знаем, вызов Assert не генерируется в версии Release, а только в версии Debug (при разработке). Поэтому в коде могут быть оставлены как Assert, так и обработчики специфических исключений (в версии Debug будет срабатывать Assert, а в версии Release — обработчик исключения).

Пример 2.

function MyMod(a, b: integer): integer;
begin
  Result := a - (a div b)*b;
end;

try
  readln(a, b);
  writeln(MyMod(a, b) div (a-1));
except
  on FormatException do
    ..
  on DivideByZeroException do
    ..
end;

Замечание. Деление на ноль может возникнуть дважды: в функции MyMod и в основной программе.
Вопрос: хотим ли мы отличать эти исключения?

Создание индивидуального класса исключения. Генерация исключений при обработке исключений

Создадим свой класс исключения MyModException, унаследовав его от класса исключений приложений ApplicationException:

uses System;

type
  MyModException = class(ApplicationException)
  end;

function MyMod(a, b: integer): integer;
begin
  try
    Result := a - (a div b)*b;
  except
    raise new MyModException;
  end;
end;

begin
  var a, b: integer;
  try
    readln(a, b);
    writeln(MyMod(a, b) div (a-1));
  except
    on FormatException do
      writeln('Неверный формат чисел a, b');
    on MyModException do
      writeln('Ошибка в функции MyMod');
    on DivideByZeroException do
      writeln('Ошибка деления на ноль в основной программе');
  end;
end.

Возможен и другой вариант. Сделаем MyModException наследником класса DivideByZeroException:

type
  MyModException = class(DivideByZeroException)
  end;

Это позволит сделать следующее: если нужно обработать любые исключения типа «деление на ноль», то достаточно написать обработчик

on DivideByZeroException do

В данном случае

try
    readln(a, b);
    writeln(MyMod(a, b) div (a-1));
  except
    on FormatException do
      writeln('Неверный формат чисел a, b');
    on DivideByZeroException do
      writeln('Ошибка деления на ноль');
  end;

в секции

on DivideByZeroException do

обрабатываются все исключения-наследники DivideByZeroException, в том числе MyModException.

Вопрос: в каком порядке следует писать обработчики исключений наследников и предков?

Правило. Вначале записываются обработчики классов-потомков, а потом — классов-предков.

Именно поэтому, если и писать

on Exception do

то только последним обработчиком.

Замечание. Класс исключения может не быть таким простым. Его можно корректировать в соответствии с уже известными правилами наследования.

Полиморфизм и виртуальные методы

Вводные понятия

Для объектно-ориентированного программирования часто приводят следующую формулу:

ООП = инкапсуляция + наследование + полиморфизм

Рассмотрим последнюю часть этой формулы - полиморфизм.

Полиморфизм дословно означает многообразие форм.
Более точно, полиморфизм — это способность родственных классов выполнять действия с одинаковыми именами сходным образом.

Пример.
Есть класс

Студент
    Готовиться_к_экзамену()

И два его наследника:

Хороший_студент
    Готовиться_к_экзамену()

и

Плохой студент
    Готовиться_к_экзамену()

Действие Готовиться_к_экзамену() они выполняют по-разному.

Рассмотрим следующий код:

var p: Person;
p := new Student('Иванов', 17, 1, 11);
p.Print();

Вопрос: какой метод Print вызовется?
Ответ: В разных языках программирования вызовутся Print разных классов:

• в таких языках, как Java, Eiffel — Student.Print
• а в C++, C#, PasacalABC.NET — Person.Print

Т.о. в PascalABC.NET вызовется метод Person.Print, но, хотелось бы, чтобы вызывался метод Student.Print.

Если решение о том, какой метод вызывать, принимается на этапе компиляции (рано), то связывание имени метода с конкретным кодом называется ранним связыванием.

Если же решение о том, какой метод вызывать, принимается на этапе выполнения программы (поздно), то связывание имени метода с конкретным кодом называется поздним связыванием.
Позднее связывание осущесвляется с методом того класса, на который ссылается переменная в процессе выполнения программы.

Итак, в PascalABC.NET по умолчанию реализовано раннее связывание.

Позднее связывание и виртуальные методы

Чтобы обеспечить позднее связывание в языке Pascal, соответствующие методы надо сделать виртуальными в базовом классе.

type
  Person = class
  ...
  public
    ...
    procedure Print; virtual;
    begin
      WriteFormat('Имя: {0}  Возраст: {1}  ', 
        fName, fAge);
    end;
  end;
  
  Student = class(Person)
  ...
  public
    procedure Print; override;
    begin
      inherited Print;
      WriteFormat('Курс: {0}  Группа: {1}  ', 
        fCourse, fGroup);
    end;
  end;

При переопределении виртуального метода в классе-потомке используется ключевое слово override.

Примечание. Переопределяющий виртуальный метод должен иметь те же параметры и тот же тип возвращаемого значения.

Вернемся к рассмотренному ранее коду:

var p: Person;
p := new Student('Иванов', 17, 1, 11);
p.Print();

Теперь решение о том, какой метод вызывать, будет отложено до этапа выполнения, и будет вызвано Print того класса, на объект которого ссылается переменная в текущий момент (в данном случае — для Student).

Вызов виртуального метода осуществляется немного медленнее обычного метода.

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

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

Замечание. Обычная подпрограмма также может быть полиморфной.
Пример.

procedure Print(p: Person);
begin
  p.Print(); // обращение полиморфизма
end;
...
Print(new Student(...));

Обычная подпрограмма называется полиморфной, если она содержит хотя бы один полиморфный параметр.

Виртуальные методы как блоки замены кода

Рассмотрим следующий полиморфный метод:

procedure polymorph(p: Base);
begin
  p.Method1;
  p.Method2;
  p.Method3;
end;

Напишем класс StudentInSession, унаследовав его от Base:

procedure polymorph(p: Base);
type
  Base = class
  public 
    procedure Method1; virtual; begin end;
    procedure Method2; virtual; begin end;
    procedure Method3; virtual; begin end;
  end;
  
  StudentInSession = class(Base)
  public
    procedure Method1; override;
    begin
      writeln('Sleep');
    end;
    procedure Method2; override;
    begin
      writeln('Eat');
    end;
    procedure Method3; override;
    begin
      writeln('Think');
    end;
  end;

...

polymorph(new StudentInSession);

Места вызовов виртуальных методов в некотором коде могут быть заменены все одновременно с использованием следующего приема:

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

Замечание. Код, содержащий вызовы виртуальных методов, всегда проектируется с учетом будущих изменений. При создании, в будущем, нового потомка этот код может вести себя совершенно по-другому, выполняя лишь основную роль. Поэтому мы всегда, когда пишем код с вызовами виртуальных методов, думаем о будущем.

Класс Base создавался только для того, чтобы его виртуальные методы были переопределены в потомке.

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

В соответствии с этим, сделаем наш базовый класс Base абстрактным:

type Base = class
public 
  procedure Method1; virtual; abstract;
  procedure Method2; virtual; abstract;
  procedure Method3; virtual; abstract;
end;

Класс Object — неявный предок всех классов .NET

Все классы в PascalABC.NET, если не указан другой предок, наследуются от класса Object.

Т.е. и integer, и string — классы.

<xh4> Интерфейс класса Object </xh4>

Object = class
    function Equals(o: Object): boolean; virtual;
    function ToString: string; virtual;
    function GetType: System.Type;

Примечание. Как нам известно, использовать ключевые слова в качестве идентификаторов запрещено. Однако, можно использовать перед ними символ «&». Тогда можно, например, описать переменную &type.

Метод Equals

Сравнивает текущий объект с объектом o и, если они равны, возвращает true, иначе — false.

По умолчанию, все встроенные (а именно — размерные) типы и тип string сравниваются по значению, а все классы — по ссылке (две переменные считаются равными, если ссылаются на один объект).
Это можно изменить, переопределив метод Equals в потомке.

Метод ToString

Возвращает строковое представление объекта.
Если не переопределен, то возвращает имя типа.

Метод GetType

Возвращает объект типа System.Type, который характеризует тип данного объекта.

Пример 1.

var i: integer := 5;
begin
  var s: string := i.ToString;
end.

<xh4> Переопределение методов Equals и ToString в классах Person и Student </xh4>

type  Person = class 
...
public
...
function Equals(o: object): boolean;
begin
  if o = nil then
    Result := false
  else if GetType <> o.GetType then
    Result := false
  else
  begin
    var p := Person(o);
    Result := (Name = p.Name) and (Age = p.Age);
  end;
end;

function ToString: string;
begin
  Result := Format(
    'Имя: {0}  Возраст: {1}  ', 
    fName, fAge);
end;

type  Student = class(Person)
...
public
...
function Equals(o: object): boolean;
begin
  Result := inherited Equals(o);
  if Result then
  begin
    var s := Student(o);
    Result := (Course = s.Course) and (Group = s.Group);
  end;
end;

function ToString: string;
begin
  Result := inherited ToString + Format(
    'Курс: {0}  Группа: {1}  ', 
    fCourse, fGroup);
end;

Полный текст новой версии классов Person и Student

Пример 2. Родословная переменной.

uses University;

procedure PrintLineage(o: object);
begin
  var t := o.GetType;
  writeln(t.Name);
  
  repeat
    t := t.BaseType;
    if t = nil then
      exit;
    writeln(t.Name);
  until false;
end;

begin
  var s := new SeniorStudent('Иванов', 20, 4, 11, new Teacher('Петров'), Magister);
  PrintLineage(s);
end.

Замечание. Полиморфизм обеспечивает изменчивость в будущем уже откомпилированного кода за счет создания подклассов.

Цепочка виртуальности и её разрыв

Пусть у нас есть следующая иерархия наследования:

            A            <—             B             <—             C
procedure Print; virtual;   procedure Print; override;   procedure Print; override;

Говорят, что методы A.Print, B.Print и C.Print завязаны в цепочку виртуальности.

Унаследуем от класса C класс D следующим образом:

D (C)
  procedure Print;

Будет предупреждение: «Укажите override или reintroduce».

Ключевое слово reintroduce служит для разрыва цепочки виртуальности.
Если написать:

... reintroduce; virtual;

то это будет началом новой цепочки виртуальности.

Интерфейсы

Интерфейс - это специальным образом оформленный легковесный класс, задающий набор требований, которые должен реализовывать обычный класс.

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

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

Пример.

interface IPrintable
  procedure Print;
  procedure Println;
end;

interface ICoords<T>
  property X: T read;
  property Y: T read;
end;

interface ICloneable // стандартный, из пространства имен System
  procedure Clone;
end;

Интуитивно: интерфейсы - это роли, которые играют объекты классов в разных ситуациях.

Один и тот же класс может реализовывать несколько интерфейсов, один и тот же интерфейс может реализовываться совершенно различными классами.

Реализация интерфейсов

type Student = class(Person,ICloneable,IPrintable)
...
  function Clone: Object;
  begin
    Result := new Student(Name,Age,Course,Group);
  end;
  procedure Print;
  begin
    ...
  end;
  procedure Println;
  begin
    ...
  end;
end;
type List<T> = class(ICloneable,IPrintable)
...
end;

Класс наследуется от одного класса, но может реализовывать несколько интерфейсов.

Все методы и свойства интерфейса, реализуемые классом, должны быть объявлены публичными

Совершенно разнородные классы могут реализовывать одинаковые интерфейсы.

Совместимость по := и операции is as для интерфейсов

Для интерфейсов работают те же правила совместимости по присваиванию, что и для обычных классов:

1. Если класс реализует интерфейс, то переменной типа интерфейс можно присвоить объект этого класса
2. Можно использовать конструкции вида p is MyClass, p as MyClass, где p - переменная типа интерфейс

Интерфейсы и полиморфизм

Все методы интерфейсов, реализуемые классами, являются виртуальными - для этого необязательно использовать virtual

Если virtual не используется, то цепочка виртуальности прерывается, если используется - продолжается:

type IShape = interface(ICoords<integer>)
  procedure Draw;
  procedeure Hide;
  procedeure MoveTo(x,y: integer);
  procedeure MoveOn(dx,dy: integer);
end;
Shape = class(IShape)
...
  procedure Draw; virtual;
  procedeure Hide; virtual;
end;

Абстрактные методы и классы

Сделать Shape абстрактным

Полиморфные контейнеры

List<Shape> Цикл по полиморфному контейнеру

1. с вызовом виртуального метода
2. с вызовом индивидуального метода и использованием as
3. с вызовом индивидуального метода и использованием GetType

Интерфейсы и наследование

Реализация интерфейсов является одной из форм наследования. В этой форме всегда выполняется принцип подстановки. Недостатки: все методы необходимо реализовывать с нуля Достоинства: нет "груза прошлого" - тяжеловесной реализации базовых классов, которая уже не нужна в производных. Пример с наследованием с ограничениями (круг от эллипса): реализация эллипса тяжеловесна, при реализации круга мы используем лишь часть этих возможностей.

Стандартные интерфейсы .NET

Пример 1. Интерфейс IComparable и его использование.

uses System;

type Student = class(Person,IComparable<Student>)
...
public
  function CompareTo(o: Student): integer;
  begin
    var s := Student(o);
    if (Course < s.Course) or (Course = s.Course) and (Group < s.Group) then
      Result := -1
    else if (Course = s.Course) and (Group = s.Group) then
      Result := 0
    else Result := 1;   
  end;
end;

Пример 2. Интерфейс IComparer и его использование.

Пример 3. Написание MinElem<T>(a: array of T); where T: IComparable<T>

Методы расширения

integer.Print

 write(Self)

Методы расширения и интерфейсы

uses System.Collections.Generic;

function Identity(i: integer): integer;
begin
  Result := i;
end;

procedure Print<T>(ie: IEnumerable<T>);
begin
  foreach i: integer in ie do
    write(i,' ');
  writeln;  
end;

begin
  var a: array of integer := (1,5,3,10,7,4,8,3,11,2,2,3,4);
  var a1: array of integer := (2,5,7,4,11,9,23,34);
  writeln(a.All(Odd));
  writeln(a.Any(Odd));
  writeln(a.Average());
  writeln(a.Contains(10));  
  writeln(a.Count());
  writeln(a.Distinct().Count());
  writeln(a.ElementAt(2));
  writeln(a.ElementAtOrDefault(100));

  Print(a.Concat(a1));
  Print(a.Distinct());
  Print(a.Except(a1));
  Print(a.Intersect(a1));
  Print(a.Union(a1));
  Print(a.Skip(5));
  Print(a.Take(5));
  Print(a.TakeWhile(Odd));
  Print(a.Where(Odd));
  writeln(a.Where(Odd).Average());

  writeln(a.Last());
  writeln(a.Max());
  writeln(a.Min());
  var ff: System.Func<integer,integer> := f;
  a.Select(Identity); // !!
  writeln(a.SequenceEqual(a));
  writeln(a.Sum());
  a.OrderBy(Identity);
end.

Лямбды

uses Arrays;

var a: array of integer := (1,2,3,5,7);

begin
  a := a.Select((x: integer)->x*x).ToArray(); 
  a.Writeln;
end.

uses Core,Arrays;

var a: array of string := ('Hello','Abracadabra','Hi','Good','Bye');

begin
  var res := a.OrderBy((x: string) -> x.Length);
  res.ToArray().Writeln();
end.

  writeln(a.First((x: integer) -> x>5));