Основы программирования — Осенний семестр; Михалкович С.С.; 2008; II

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

Вспомогательные алгоритмы

Вспомогательный алгоритм — это алгоритм, который используется для реализации другого алгоритма.

Вспомогательные алгоритмы имеют:

• имя
• список параметров

некоторые параметры являются входными, а некоторые — выходными

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

В программировании вспомогательные алгоритмы называются подпрограммами и делятся на:

• процедуры
• функции

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

Лекция 9

Процедуры

Пример.

Даны 3 пары положительных чисел.

Найти их среднее арифметическое и среднее геометрическое.

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

procedure CalcSrASrG(a, b: real; var SA, SG: real); 
begin
  SA := (a + b) / 2;
  SG := sqrt(a * b);
end;

Строка

procedure CalcSrASrG(a, b: real; var SA, SG: real);

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

Теперь можем многократно использовать описанную процедуру в основной программе:

begin   //основной программы
for var i:=1 to 3 do
  begin
    var a, b: real;
    readln(a, b);
    var SA, SG: real;
    CalcSrASrG(a, b, SA, SG);
    writeln(SA, '|', SG);
  end;
end.

Оператор

CalcSrASrG(a, b, SA, SG);

называется оператором вызова процедуры.

<xh4>Синтаксис описания процедуры</xh4>

procedure <имя> [( <список формальных параметров> )];
<раздел описаний>
begin
  <операторы и внутриблочные переменные>
end;

Замечание. Pascal допускает внутренне описание п/п (вложенность процедур)

<список формальных пар-ов> ::= <секция ф.п.> | <секция ф.п.>; <список ф.п.>
<секция ф.п.> ::= [var] <список имен>: <тип>

<xh4>Синтаксис вызова процедуры</xh4>

<имя процедуры> [( [<список фактических параметров>] )]

<список фактических пар-ов> ::= <список выражений>
(<список выражений> ::= <выражение>{, <выражение>})

<xh4>Семантика вызова процедуры</xh4>

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

Входно-выходные параметры

Параметр x называется входно-выходным, если его значение необходимо в начале алгоритма, оно модифицируется алгоритмом и возвращается в вызывающую программу.

Входно-выходные параметры описываются с ключевым словом var, как и выходные.

Пример 1. Увеличение значения переменной на заданное число.

procedure Inc(var x: integer; n: integer);
begin
  x += n;
end;

Вызов процедуры:

var x: integer;   //неинициализированная переменная
x := 1;           //x инициализировано
Inc(x, 2);

Пример 2. Перемена местами значений двух переменных.

procedure Swap(var x,y: integer);
begin
  var v := x;
  x := y;
  y := v;
end;

begin
  var a := 5;
  var b := 3;
  Swap(a,b);
end.

Функции

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

Пример. Функция sgn(x) — знак числа

function Sign(x: real): integer;
begin
  if x > 0 then
    Result := 1
  else if x < 0 then
    Result := -1
  else
    Result := 0;
end;

Строка

function Sign(x: real): integer;

называется заголовком функции, а integer — это тип возвращаемого значения.

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

Пример неправильной (!!!) функции.

function f(x: integer): integer;
begin
  if x > 0 then
    Result := 777;
end;

begin
  writeln(f(0));
end.

Выведется непредсказуемое значение, находящееся в этот момент в памяти, т.к. по ветке x = 0 переменная Result не инициализируется.

Пример. Считывание значения с клавиатуры.

function ReadInteger: integer;
begin
  read(Result);
end;

Сравнение использования процедуры и функции

процедура           функция
var x: integer;     var x := ReadInteger();
read(x);

Пример. Сумма первых N натуральных чисел.

function SumN(N: integer): integer;
begin
  Result := 0;
  for var i:=1 to N do
    Result += i;
end;

<xh4>Синтаксис описания функции</xh4>

function <имя>[( [<список формальных параметров>] )]: <тип возвращаемого значения>;
<раздел описаний>
begin
  <операторы и внутриблочные описания>
end;

<xh4>Синтаксис вызова функции</xh4>

<имя>[( [<список формальных параметров>] )];

<xh4>Семантика</xh4> Замечание. Формальные параметры функции не рекомендуется делать параметрами-переменными.

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

Правило.

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

Оператор exit

Оператор exit — оператор досрочного завершения подпрограммы.

Пример. Поиск числа k среди n введенных.

function Find(n: integer; k: integer): boolean;
begin
  for var i:=1 to n do
  begin
    var x := ReadInteger;
    if x = k then
    begin
      result := true;
      exit;
    end;
  end;
  result := false;
end;

Замечание. Оператор exit, в отличие от break, позволяет завершить подпрограмму и выйти сразу из нескольких вложенных циклов. При вызове его в теле основной программы программа завершается.

Локальные и глобальные переменные

var
  n: integer;
  m: integer;

function f(x: integer): integer;
var n: integer;
begin
  writeln(n);
  writeln(m);
  n := 5;
end;

Замечание. Локальная переменная, описанная в процедуре или функции, может иметь то же имя, что и глобальная переменная. Если глобальная описана ранее, то её имя внутри процедуры становится недоступным.

Глобальные переменныя по умолчанию инициализируются 0, а локальные по умолчанию не инициализируются. Локальная переменная Result в функции по умолчанию также не инициализируется.

В данном примере:

writeln(n) выведет непредсказуемый результат;

writeln(m) выведет 0;

Пространство имен

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

Различают:

• глобальное пространство имен
• пространство имен каждой п/п

Формальные параметры п/п являются локальными по отношению к эти п/п.

Примеры допустимых и недопустимых описаний:

procedure p(p: integer);        //Можно

function Result: integer;       //Можно

procedure p(i: integer);        //НЕЛЬЗЯ
var i: integer;

function f(Result: real): real; //НЕЛЬЗЯ

Лекция 10

Область видимости и время жизни объекта

Время жизни переменной — время, в течение которого существует отведенная ей память.

• для глобальных переменных это время работы программы
• для локальных — с момента описания до конца работы блока, где они описаны

Область видимости переменной — область в программе, в которой можно обратиться к переменной по имени.

Побочный эффект

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

Пример.

var n: integer;
procedure p;
begin
  n += 1;
end;

begin
  n := 5;
  p;
  write(p);
end.

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

Принцип локальности

Рассмотрим пример:

var n: integer;

procedure p;
begin
  <много кода; n не используется>
end;

procedure p1;
begin
  <еще больше кода; n не используется>
end;

begin
  <10 операторов>
  n := 1;
  <еще операторы>
end.

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

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

Пример. Вычислить произведениe целых чисел от a до b. Решение 1.

var 
  p := 1;
  a, b: integer;
  i: integer;
begin
  read(a, b);
  for i:=a to b do
    p *= i;
  writeln(p);
  writeln(i); //от компилятора зависит, будет i = b или (b + 1)
end.

Внесем изменения:

• опишем i в заголовке цикла

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

• инициализируем p непосредственно перед циклом, вычисляющим произведение

Решение 2.

var 
  p: integer;
  a, b: integer;
begin
  read(a, b);
  p := 1;
  for var i:=a to b do
    p *= i;
  writeln(p);
end.

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

Внутренний механизм передачи параметра-переменной

procedure MyInc(var a: real; n: integer);
begin
  a += n;
end;

var
  b: real;
  i: integer;
begin
  b := ReadReal;
  i := ReadInteger;
  MyInc(b, i);
  writeln(b);
end.

Здесь

b, i: фактические параметры при вызове MyInc

a, n: формальные параметры (a — параметр-переменная; n — параметр-значение)

При передаче параметра-значения i в соответствующий формальный параметр копируется значение i. А вот механизм передачи параметра-переменной называется передачей по ссылке.

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

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

При передаче параметра по ссылке в подпрограмму передается не сама переменная, а её адрес:

MyInc(var a: real; i: integer);
          |
         @b (адрес b)

Замечание 1. В 32-битных ОС размер адреса — 4 байта, это позволяет адресовать примерно 4 Гб операционной памяти.
Замечание 2. Размер адреса не зависит от размера переменной, поэтому при передаче параметров большого размера их предпочитают передавать по ссылке.

Перегрузка имен подпрограмм

Предположим, у нас описана процедура:

procedure Swap(a, b: integer);
begin
  var t := a;
  a := b;
  b := t;
end;

Возможно ли описать процедуру с таким же именем, параметры которой были бы вещественными? Да, возможно:

procedure Swap(a, b: integer);
begin
  var t := a;
  a := b;
  b := t;
end;

procedure Swap(a, b: real); 
begin
  var t := a;
  a := b;
  b := t;
end;

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

Замечание 1. Тип возвращаемого значения функции не участвует в операции разрешения перегрузки.

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

Замечание 2. Разрешить перегрузку можно не всегда.
Пример.

procedure p(i: integer; r: real);
...

procedure p(r: real; c: char);
...

procedure p(r: real; i: integer);
...

begin
  p(1, 2); //неоднозначность
end.

Замечание 3. В процессе разрешения перегрузки происходит неявное преобразование типов. Лекция 11

Параметры по умолчанию

procedure DoOp(a, b: integer; var res: integer; op: char := '+');
begin
  case op of
    '+': res := a + b;
    '-': res := a - b;
    '*': res := a * b;
  end;
end;
...
DoOp(1,2, res, '-'); // res = -1
DoOp(3,4, res1);     // res1 = 7

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

Замечание. Параметры по умолчанию корректно сочетаются с перегрузкой.

Предварительное объявление подпрограмм

procedure p;
begin
  q;
end;

procedure q;
begin
  ...
end;

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

procedure q; forward;

procedure p;
begin
  q;
end;

procedure q;
  ...

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

Процедурные переменные

Процедурный тип и переменные

var pr: procedure(a, b: real; var res: real);

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

type
  BinOpType = procedure(a, b: real; var res: real);

var
  pr: BinOpType;

procedure AddOp(a, b: real; var res: real);
begin
  res := a + b;
end;
procedure MultOp(a, b: real; var res: real);
begin
  res := a * b;
end;

begin
  pr := AddOp;
  var r: real;
  pr(1,2, r);   //вызов процедуры через процедурную переменную

  pr := MultOp;
  pr(3,4, r);
end.

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

<имя процедурной переменной>( <список параметров> );

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

Замечание. До первого присваивания процедурная переменная имеет тип nil. В этот момент вызывать процедуру через переменную нельзя — будет ошибка выполнения.

Функции обратного вызова (callback)

type ActionType = procedure;

procedure DoActions(Action1, Action2, Action3: ActionType);
begin
  Action1;
  Action2;
  Action3;
end;

procedure Eat;
begin
  writeln('Студент ест');
end;
procedure Think;
begin
  writeln('Студент думает');
end;
procedure Sleep;
begin
  writeln('Студент спит');
end;

begin
  DoActions(Sleep, Eat, Sleep);   // Первый алгоритм подготовки к сессии
  DoActions(Think, Eat, Sleep);   // Второй алгоритм подготовки к сессии
  DoActions(Sleep, Sleep, Think); // Третий алгоритм подготовки к сессии
end.

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

Такой вызов называется обратным вызовом (callback).
Примечание. Прямой вызов — это передача процедуры в качестве параметра.

Пример. Вычисление определённого интеграла методом прямоугольников.

type func = function(x: real): real;
function Integral(a, b: real; N: integer; f: func);
begin
  assert(a < b);
  var h := (b - a) / N;
  result := 0;
  var x := a;
  for var i:=0 to N-1 do
  begin
    result += f(x);
    x += h;
  end;
  result *= h;
end;

Вызов нескольких процедур через процедурную переменную

type ActionType = procedure;

procedure Eat;
begin
  ...
end;
procedure Think;
begin
  ...
end;
procedure Sleep;
begin
  ...
end;

var pr: ActionType;
begin
  pr += Sleep;
  pr += Eat;
  pr += Think;
  pr;
  pr -= Eat;
  pr;
end.

Замечание 1. Такое возможно только в .NET;
Замечание 2. Подобный механизм не имеет смысла использовать для функций;

Лекция 12

Методы разработки подпрограмм

Пример. Вывести таблицу простых чисел <= 1000.

Метод разработки сверху вниз

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

Решение.

writeln(2);
var x := 3;
while x <= 1000 do
begin
  if IsPrime(x) then
    writeln(x);
  x += 2;
end;

После этого реализуем функцию IsPrime;

Этот метод используется, когда:

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

Замечание. В коде главной программы имеются вызовы других подпрограмм, которые реализуются позже (возможно, другими разработчиками);
На период, пока они не написаны, вместо них могут использоваться "заглушки" (подпрограммы с тривиальными телами)

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

Метод разработки снизу вверх

Вначале составляется "нижняя" подпрограмма, она всесторонне тестируется, и, потом, 
пишется основная программа или подпрограмма.

Метод используется, когда:

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

Замечание 1. Написание самых "нижних" подпрограмм позволяет лучше войти в предметную область;
Замечание 2. С какого-то момента разработка хотя бы упрощенного главного алгоритма становится необходимой;

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

Оператор goto

Синтаксис

goto <метка>
...
<метка>: <оператор>

Метка представляет собой идентификатор или целое положительное число.
Метка должна описываться в разделе описаний меток в виде:

label <метка1>, <метка2>...;

Семантические ограничения

• метка должна использоваться в той же подпрограмме, в которой описана;
• нельзя, используя goto, перейти внутрь какой-нибудь конструкции (цикла или условного оператора);

<xh4>Пример плохого кода</xh4>

label 1, 2, 3;
begin
   goto 1;
   <100 операторов>
2: write(2);
   goto 3;
   <100 операторов>
1: write(1);
   goto 2;
   <100 операторов>
3: write(3);
end.

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

Пример.

найти a, b, c:

a² + b² = c², 50 <= a,b,c <= 100

label fin;
var aa, bb, cc: integer;
var flag := false;

for var a:=50 to 100 do
for var b:=50 to 100 do
for var c:=50 to 100 do
  if a*a + b*b = c*c then
  begin
    flag := true;
    aa := a;
    bb := b;
    cc := c;
    goto fin;
  end;

fin: if flag then
       writeln(aa, bb, cc);

Вызов подпрограммы на этапе выполнения

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

<здесь будет рисунок>

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

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

Пример.

<здесь будет рисунок>

Устройство ЗА подпрограммы

<здесь будет рисунок>

<xh4></xh4>

Понятие программного стека.

Запись активации, ее структура.

Алгоритм вызова подпрограммы на этапе выполнения.

Лекция 13

Пример, иллюстрирующий алгоритм вызова процедуры.

Замечания:

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

Модули

Определение

Структура модуля с разделами интерфейса и реализации.

Принцип сокрытия информации.

Преимущества разделения модуля на интерфейс и реализацию.

Лекция 14

Упрощенная структура модуля.

Разделы инициализации и финализации.

Схема компиляции программы с модулями.

Алгоритм поиска имен в модулях. Модуль как пространство имен.

Системный модуль PABCSystem

Лекция 15

Документирующие комментарии ///

Библиотеки. Отличие библиотек от модулей. Подключение библиотек в PascalABC.NET.

Перечислимый и диапазонный типы. Стандартные функции Ord Pred Succ. Стандартные процедуры Inc Dec.

Использование перечислимого типа в for и case.

Массивы

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

Определение массива.

Описание массивов. Тип массива. Тип индексов массива. Понятие порядкового типа.

Лекция 16

Обращение к элементам массивов.

Выход за границы диапазона. Контроль выхода в Delphi и PascalABC.NET.

Динамические массивы. Хранение в памяти.

Инициализация массивов.

Присваивание массивов. Сравнение массивов.

Присваивание a := nil для динамических массивов.

Цикл foreach.

Именная и структурная эквивалентность типов.

Лекция 17

Массивы как параметры подпрограмм

При передаче статического массива должна соблюдаться именная эквивалентность

  procedure xxx(a: array [1..100] of integer); // неверно
 
  type IArr = array [1..100] of integer;
  procedure yyy(a: IArr);

Передавать массив по значению крайне неэффективно (т.к.происходит копирование всех элементов на стек). Его следует передавать по ссылке: для этого есть специальное ключевое слово const, которое также запрещает изменять данные внутри п/п.

  procedure zzz(const a: IArr);
  procedure sss(var a: IArr);

Динамический массив можно передавать в виде array of integer, т.к. для него определена структурная эквивалентность типов.

  procedure ttt(a: array of integer);

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

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

Переменное число параметров подпрограмм

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

Лекция 18

Шаблоны подпрограмм

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

Выход - шаблоны.

Пример:

 procedure Print<T> (array of T);

В момент вызова п/п происходит:

• выведение типов шаблона по фактическим параметрам
• инстанцирование - подстановка конкретных типов шаблонов и генерация кода подпрограммы с этими конкретными типами.

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

Задачи на одномерные массивы

• инвертирование массива (шаблон)
• поиск элемента в массиве - найти и вернуть индекс (шаблон)

можно с for и break,

можно и другим способом - с while

• поиск с барьером (шаблон). Его преимущества
• минимальный элемент массива и его индекс
• слияние двух упорядоченных массивов в один упорядоченный (барьер)
• сдвиг элементов массива влево (шаблон)

знакомство со значением default(T), Т - тип

Лекция 19

Задачи на одномерные массивы

pas-файл с задачами

doc-файл

используется тип IArr = array [1..size] of integer

• сдвиг элементов массива вправо (ShiftRight)

[ два варианта определения граничных значений цикла (от n-1 до 1; от n до 2) ]

• циклический сдвиг элементов массива вправо (CycleShiftRight)
• удаление элемента по заданному индексу (Delete)
• вставка элемента по заданному индексу (Insert)

Задачи с процедурными переменными в качестве параметров

Определяется тип IUnPred = function (x: integer): boolean

• поиск элемента по заданному условию (Find)
• количество элементов, удовлетворяющих условию (Count)
• условный минимум (MinElem)
• удаление всех элементов, удовлетворяющих условию (DeleteAll)

Примечание. Для проверки выхода индекса за границы диапазона (внутри цикла) следует проверять граничные значения счетчика, подставляя их во все индексы

Лекция 20

Сортировки

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

• Пузырьковая

Это самый компактный алгоритм сортировки. Его можно оптимизировать, проверяя случай "холостого" прохода по элементам массива. Т.е. если за проход ни один элемент не изменил позицию, значит массив уже отсортирован и проверять дальше нет смысла.

• Вставками (вставка элемента из еще не упорядоченного участка массива в "нужную" позицию отсортированного, для чего сдвиг части элементов вправо и вставка нового в освободившуюся позицию)

Замечание. Рассмотренные виды сортировки не являются самыми эффективными. Асимптотическая сложность алгоритмов

Определение. Число шагов алгоритма асимптотически равно Θ(f(n)) если, существуют такие N, с1, с2>0 (c1<c2), что для любых n ≥ N выполняется:

   c1*f(n) ≤ число шагов ≤ c2*f(n)

Замечание 1. Для рассмотренных алгоритмов сортировки асимптотическая сложность = Θ(n²).

Замечание 2. Существуют алгоритмы сортировки с асимптотической сложностью = Θ(n*logn) (они будут рассмотрены в следующем семестре).

Лекция 21

Алгоритм бинарного поиска в отсортированном массиве

Его асимптотическая сложность - Θ(logn). Двумерные массивы

Двумерный массив как матрица (соответствие индексов строкам и столбцам)

Элементы строки. Элементы столбца (рисунки)

Понятие замороженного индекса

Задачи на двумерные массивы

• Вывод матрицы
  • внешний цикл по строкам
  • если внешним сделать цикл по столбцам будет выведена транспонированная матрица

• Сумма элементов в j-том столбце

• Сумма элементов в каждом столбце
  • использование функции для нахождения суммы в j-ом столбце
• Минимальный элемент в каждой строке
  • в отличие от предыдущей задачи, для реализации не создается дополнительная п/п.

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

• Квадратные матрицы и элементы выше-ниже главной (побочной) диагонали.

Лекция 22

• Поиск элемента в матрице

если для поиска используется функция, то при нахождении элемента выходить из циклов с помощью exit,

иначе удобно использовать goto КОНЕЦ_ВНЕШНЕГО_ЦИКЛА

Записи

 type <имя записи>= record
  <поля записи>
 end;

Поля записей

Инициализация записей при описании (на примере Student)

Доступ к полям записей. Точечная нотация.

Замечание. Для записей имеет место именная эквивалентность типов.

Передача записей в п/п (Print(s)). Запись как возвращаемое значение функции (s := ReadStudent;).

Передавать записи по значению неэффективно, т.к. копируются все поля. Поэтому следуют передавать их по ссылке (с ключевым словом const - если значения полей не изменяются, и var - если внутри п/п их требуется изменить.

Оператор with.

 with <переменная типа запись> do
 begin
   <поле>:=<значение>
 end;

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

Методы в записях

На примере Student.Print.

Запись как пространство имен

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

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

Создается окружение при описании переменной типа запись.

• Сравнение s.Print и Print(s)

s.Print - объектно-ориентированный подход, доминирует объект, который сам выполняет над собой действие.

Print(s) - процедурно-ориентированный подход, главным является действие, выполняющееся над переменной.

• Метод Init - инициализатор полей записи.

Лекция 23

Создание простейших графических объектов

 RPoint = record x, y: integer end;
 RRectangle = record p1,p2: RPoint end;

Для каждого типа определяются методы Print, Draw, MoveOn

Записи как средство упаковки параметров

Пример. Используем определенные типы записей для создания перегруженных версий процедур Rectangle и Line:

 Rectangle(x1,y1, x2,y2: integer)
 Rectangle(p1,p2: RPoint)
 Rectangle(r: RRectangle)

 Line(x1,y1, x2,y2: integer)
 Line(p1,p2: RPoint)
 Line(r: RRectangle)

Переменная типа запись как объект

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

Поля записи как состояние объекта.

Методы записи как действия, воздействующие на состояние объекта.

Методы делятся на две категории

• меняющие состояние объекта (MoveOn для RPoint)
• осуществляющие доступ к состоянию объекта на чтение (Draw для RPoint)

Сортировка массива записей.

Лекция 24

Индексная сортировка

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

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

---

Пример.

Дан массив целых (с реальными индексами):

 5[1]  15[2]  3[3]  1[4]  9[5]  8[6]  20[7]  12[8]

А так выглядит отсортированный массив по виртуальным индексам:

 1[1]  3[2]  5[3]  8[4]  9[5]  12[6]  15[7]  20[8]

Т.е.

 index[1] = 4
 index[2] = 3
 index[3] = 1
 index[4] = 6
 index[5] = 5
 index[6] = 8
 index[7] = 2
 index[8] = 7

---

Соответственно, алгоритм сортировки меняется таким образом, что вместо перемены местами самих элементов упорядочиваемого массива меняется содержимое элементов index.

Вначале удобно положить элементы index соответствующими тождественной подстановке (т.е. a[i] = i).

type CmpFunc = function (const s1,s2: Student): boolean;

procedure BubbleIndexStudentSort(const a: StArr; var Index: IArr; n: integer; Cmp: CmpFunc);
begin
  for var i:=1 to n do
    Index[i] := i;
  for var i:=n downto 2 do
  for var j:=1 to i-1 do
    if Cmp(a[Index[j+1]],a[Index[j]]) then
      Swap(Index[j+1],Index[j]);
end;

procedure WriteArrByIndex(const a: StArr; const Index: IArr; n: integer);
begin
  for var i:=1 to n do
    writeln(a[Index[i]].name,' ',a[Index[i]].course,' ',a[Index[i]].group);
end;

Множества

Описание множеств. Множества-константы. Пустое множество.

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

s1+s2 - объединение
s1*s2 - пересечение
s1-s2 - разность
s += s1
s -= s1
s *= s1
s1<s2 - строгое вложение
s1<=s2 - нестрогое вложене
s1>s2 - строгое вложение
s1<=s2 - нестрогое вложене
i in s - принадлежность

Include(s,i);
Exclude(s,i); 

Вывод множеств.

Цикл foreach по множеству.

Пример использования множеств: решето Эратосфена. Алгоритм.

Лекция 25

Алгоритм Эратосфена

Код алгоритма Эратосфена

const n = 10000;
var primes: set of byte;
begin
   primes := [2..n];
   for var i:=2 to round(sqrt(n)) do
   begin
     if not (i in primes) then
       continue;
     var x := 2*i;
     while x<=n do
     begin
       Exclude(primes,x);
       x += i;
     end;
   end;
   for var i:=0 to n do
     if i in primes then
        write(i,' ');
end.

Статические методы записей

type RRectangle = record
  class function EqualSquare(const r1,r2: RRectangle): boolean;
  class function CreateRandom: RRectangle;
end;

Символы

Коды символов. Однобайтовые и двухбайтовые кодировки. ASCII - стандарт на символы с кодами 0..127. Unicode. Однобайтовые кодировки: Windows, DOS (CP866), Koi8

Литеральные константы-символы:

#13 - символ возврата "каретки"
#10 - символ перехода на следующую строку 
#9  - символ табуляции

Стандартные подпрограммы работы с символами

OrdUnicode(c)
ChrUnicode(i)
Succ(c)
Pred(c) 
Inc(c,5)
Dec(c,5)
Ord(c)
Chr(i)
UpperCase(c)
LowerCase(c)

Для символов с кодами 0..127

OrdUnicode(c)=Ord(c)
ChrUnicode(i)=Chr(i)

char - тип, содержащий ряд статических методов:

char.IsDigit(c)
char.IsLetter(c)
char.IsLetterOrDigit(c)
char.IsLower(c)
char.IsUpper(c)
char.ToLower(c)
char.ToUpper(c)

Лекция 26

Строки

Тип string

Отводится память (до 2 Гб), равная длине строки, плюс некоторая дополнительная информация

Строки - массивы символов, индексируемые с 1: s[i] - i - тый символ строки. var s := 'IT'; // s[1]='I', s[2]='T'

Операции со строками:

s1+s2  
s1 += s2  
s1<s2  
...

Основные подпрограммы работы со строками

Length(s) - функция, возвращающая длину строки s

SetLength(s,n) - процедура, устанавливающая длину строки s равной n

Copy(s,from,len) - функция, возвращающая подстроку s с позиции from длины len

Insert(subs,s,form) - процедура, вставляющая подстроку subs в строку s с позиции from

Delete(s,from,len) - процедура, удаляющая из строки s len символов с позиции from

Pos(subs,s) - функция, возвращающая позицию первого вхождения подстроки subs в строку s или 0, если подстрока не найдена

PosEx(subs,s,from=1) - функция, возвращающая позицию первого вхождения подстроки subs в строку s, начиная с позиции from, или 0, если подстрока не найдена

TrimLeft(s) - функция, возвращающая строку s, в которой удалены все начальные пробелы

TrimRight(s) - функция, возвращающая строку s, в которой удалены все заключительные пробелы

Trim(s) - функция, возвращающая строку s, в которой удалены все удаляет все начальные и заключительные пробелы

Преобразование строка ↔ число

Str(x,s) - процедура, преобразующая целое или вещественное выражение x к строковому представлению и записывающая результат в строку s

Val(s,x,errcode) - процедура, преобразующая строку s к целому или вещественному значению и записывающая результат в целую или вещественную переменную x. Переменная errcode - целая; если преобразование невозможно, то в errcode содержится номер первого символа, вызвавшего ошибку

IntToStr(i) - функция, преобразующая целое x в строку

StrToInt(s) - функция, преобразующая строку s к целому; может генерировать исключение

FloatToStr(i) - функция, преобразующая вещественное x в строку

StrToFloat(s) - функция, преобразующая строку s к вещественному; может генерировать исключение

Некоторые задачи на строки

Посимвольная обработка

• Строка 'ABCD...XYZ'
• Сумма всех цифр в строке s

Использование стандартных подпрограмм

• Вывести индексы всех вхождений подстроки s1 в s (на Delete, PosEx)

Ссылки

• Первая часть конспекта
• Другие конспекты