Программирование

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

Весьма поэтичное объяснение понятия подпрограмма дал В.Ф. Очков: "Подпрограмма - это припев песни, который поют несколько раз, а в текстах песен печатают только один раз"¹⁾.

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

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

Таким образом, подпрограмма - это в первую очередь программа. Со всеми полагающимися полноценной программе атрибутами: именем, разделами описания меток (label), констант (const), типов (type), переменных (var) и даже со своими (вложенными) функциями и процедурами.

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

Объявление и описание

Подпрограммы объявляются и описываются в начале Pascal-программы, до ключевого слова begin, означающего начало тела программы.

Различия между процедурами и функциями начинаются уже с момента их объявления.

Объявление функции

Функции объявляются следующим образом:

function <имя_функции> [(<список_параметров>)]:<тип_результата>;

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

function <имя_функции> [(<параметры>)]:<тип_результата>; forward;

Объявление процедуры

Процедуры следует объявлять так:

procedure <имя_процедуры> [(<список_параметров>)];

Если объявление процедуры оторвано от ее описания, нужно поставить после него ключевое слово forward:

procedure <имя_процедуры> [(<список_параметров>)]; forward;

Описание подпрограммы

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

[ uses <имена_подключаемых_модулей>;]
[ label <список_меток>;]
[ const <имя_константы> = <значение_константы>;]
[ type <имя_типа> = <определение_типа>;]
[ var <имя_переменной> : <тип_переменной>;]

[ procedure <имя_процедуры> <описание_процедуры>]
[ function <имя_функции> <описание_функции>;]

begin		{начало тела подпрограммы}
         <операторы>
end;		(* конец тела подпрограммы *)

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

function <имя_подпрограммы>;

или

procedure <имя_подпрограммы>;

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

Пример подпрограммы-процедуры:

procedure err(c:byte; s:string);
   var zz: byte;
   begin if c = 0
             then writeln(s)
             else writeln('Ошибка!')
   end;

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

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

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

Список параметров может и вовсе отсутствовать:

procedure proc1;
function func1: boolean;

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

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

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

[<способ_подстановки>]<имя_параметра>:<тип>;

О возможных способах подстановки значений в параметры (<пустой>, var, const) мы расскажем в разделе "Способы подстановки аргументов".

Если способ подстановки и тип нескольких параметров совпадают, описание этих параметров можно объединить:

[<способ_подстановки>]<имя1>,...,<имяN>: <тип>;

Пример описания всех трех способов подстановки:

function func2(a,b:byte; var x,y,z:real; const c:char);

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

procedure proc2(a: array[1..100]of char);

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

type arr = array[1..100] of char;
procedure proc2(a: arr);
function func2(var x: string): arr;

Возвращаемые значения

Основное различие между функциями и процедурами состоит в количестве возвращаемых ими значений.

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

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

Например:

function min(a,b: integer): integer;
   begin if a>b 
             then min:= b
             else min:= a
   end;

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

Вызов подпрограмм

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

При вызове в подпрограмму передаются фактические параметры или аргументы (в круглых скобках после имени подпрограммы, разделенные запятыми):

<имя_подпрограммы>(<список_аргументов>)

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

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

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

c:= min(a,a*2);
if min(z, min(x,y))= 0 then...;

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

err(res,'Привет!');

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

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

Как уже упоминалось выше, при вызове подпрограммы подстановка значений аргументов в параметры производится в соответствии с правилами, указанными в атрибуте <способ_подстановки>. Мы рассмотрим три различных значения этого атрибута:

Параметр-значение

Описание

В списке параметров подпрограммы перед параметром-значением служебное слово отсутствует³⁾. Например, функция func3 имеет три параметра-значения:

function func3(x:real; k:integer; flag:boolean):real;

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

dlina:= func3(shirina/2, min(a shl 1,ord('y')), true)+0.5;

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

Механизм передачи значения

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

В качестве примера рассмотрим последовательность действий, выполняемых при передаче аргументов 1+а/2, а и true в описанную выше функцию func3. Пусть а - переменная, имеющая тип byte, тогда значение выражения 1+a/2 будет иметь тип real, а true и вовсе является константой (неименованной).

Итак, при вызове func3(1+a/2,a,true) будут выполнены следующие действия:

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

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

Параметр-переменная

Описание

В списке параметров подпрограммы перед параметром-переменной ставится служебное слово var. Например, процедура proc3 имеет три параметра-переменные и один параметр-значение:

procedure proc3(var x,y:real; var k:integer; flag:boolean);

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

Механизм передачи значения

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

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

Замечание: Для экономии памяти в параметр-переменную можно передавать и такую переменную, изменять значение которой не требуется. Скажем, если нужно передать в качестве аргумента массив, то лучше не создавать его копию, как это будет сделано при использовании параметра-значения, а использовать параметр-переменную.

Параметр-константа

Описание

В списке параметров подпрограммы перед параметром-константой ставится служебное слово const. Например, процедура proc4 имеет один параметр-переменную и один параметр-константу:

procedure proc4(var k:integer; const flag:boolean);

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

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

Механизм передачи значения

В некоторых источниках⁴⁾ можно встретить утверждение о том, что для параметра-константы, как и для параметра-переменной, не создается копии в момент вызова подпрограммы. Однако выполнение простейшей проверки

var a: byte;
procedure prob(const c:byte);
      begin
         writeln(longint(addr(c)));	{физ.адрес параметра с}
      end;
begin
   a:=0;
   writeln(longint(addr(a))); 		{физ.адрес переменной а}
   prob(a);
end.

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

Области действия имен

Разграничение контекстов

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

Локальные объекты объявляются внутри какой-нибудь подпрограммы и "видны" только этой подпрограмме и тем подпрограммам, которые были объявлены как внутренние для нее. Локальные объекты не существуют, пока не вызвана подпрограмма, в которой они объявлены, а также после завершения ее работы.

program prog;
var a:byte;

procedure pr1 (p:byte);
  var b:byte;   (первый уровень вложенности)

function f (pp:byte);
  var c:byte;   (второй уровень вложенности)
  begin
   (здесь "видны" переменные a, b, c, p, pp)
  end;

  begin
   (здесь "видны" переменные a, b, p)
  end;

var g:byte

procedure pr2;
  var d:byte;     (первый уровень вложенности)
  begin
   (здесь видны переменные a, d, g)
  end;

  begin
   (тело программы; здесь "видны" переменные a, g)
  end;

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

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

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

Совпадение имен

Вообще говоря, совпадения глобальных и локальных имен допустимы, поскольку к каждому локальному имени неявно приписано имя той подпрограммы, в которой оно объявлено. Таким образом, в приведенном выше примере (см. пример 8.1) фигурируют переменные a, g, pr1.p, pr1.b, pr1.f.pp, pr1.f.c, pr2.d.

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

<имя_программы>.<имя_глобальной переменной>

Например (локальной переменной здесь присваивается значение глобальной):

a:= prog.a; 

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

Нетипизированные параметры

В объявлении подпрограммы можно не указывать тип параметра-переменной:

procedure proc5(var x);

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

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

Явное преобразование типа

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

procedure proc5(var x);
type arr = array[1..10] of byte;
var x: integer; 
   z: real;
   m: arr;
begin
   ...
   y:= integer(x);
   z:= real(x);
   m:= arr(x);
   ...
end;

Совмещение в памяти

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

<локальная_переменная>: <тип> absolute <нетипизир_параметр>;

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

function func5(var x):real;
var xxx: longint absolute x;
begin
      {здесь с началом любой переменной, 
 поступившей в параметр х,
   ... можно обращаться как с longint-числом: 
       при помощи локальной переменной ххх}
end;

Открытые параметры

Открытые параметры - это массивы и строки неопределенной длины. Открытым параметром может стать только параметр-переменная. Возможность работать с открытыми параметрами в подпрограммах появилась в версии Turbo Pascal 7.0.

Открытые массивы

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

В заголовке подпрограммы открытый параметр-массив описывается по следующему шаблону:

var <имя_параметра>: array of <тип_компонентов_массива>

Например, если описано

procedure proc6 (var a: array of byte);

то аргументом могут стать такие массивы:

a1: array[1..100] of byte;
a2: array[-10..10] of byte;
a3: array[1..2,1..3] of byte;

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

Если в качестве аргумента поступил многомерный массив, его компоненты "вытягиваются" в одну строку: сначала все компоненты первой строки массива, затем - второй строки и т.д. Например, если массив а3 имеет значения

1 2 3
4 5 6

то внутри процедуры proc6 параметр а будет иметь уже следующий вид:

1 2 3 4 5 6

причем компоненты двух массивов будут соотноситься так:

Открытые строки

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

var <имя_параметра>: string

Например:

function func6 (var s: string): byte;

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

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

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

Описание

В разделе type процедурный тип данных задается одним из следующих способов:

<имя_типа> = function[(<список_параметров>)]:<тип_результата>;

или

<имя_типа> = procedure[(<список_параметров>)];

Например:

type func = function(a,b:integer):integer;

Аргументы

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

Например, для параметра, имеющего описанный выше тип func, аргументами могут послужить такие функции:

function min(a,b: integer): integer; far;
   begin if a>b 
         then min:= b
         else min:= a
   end;

и

function max(a,b: integer): integer; far;
   begin if a<b 
         then max:= b
         else max:= a
   end;

Вызов

Приведем пример подпрограммы, имеющей параметр процедурного типа:

procedure count(i,j:integer; f:func);
var c: integer;
begin 
   ...
   c:= f(i,j);
   ...
end;

Теперь, если будет осуществлен вызов count(x,y,min), то в локальную переменную с запишется минимум из x и y. Если же вызвана будет count(x,y,max), то в локальную переменную с запишется максимум из x и y.

¹⁾   http://twt.mpei.ac.ru/ochkov/mc8Pro.book/6_text.htm
  ²⁾   Существует лишь в поздних версиях языка Pascal.
  ³⁾   Иными словами, атрибут является пустым.
  ⁴⁾   Например, Бежанова М.М., Москвина Л.А. Практическое программирование. Приемы создания программ на языке Паскаль. М.: "Научный мир", 2001.
  ⁵⁾   Способы работы с физическими адресами мы рассмотрим в лекции 11.

Динамические структуры данных

Динамические структуры данных служат полезным дополнением к стандартным структурам, уже определенным в языке Pascal. Динамическими они называются потому, что их элементы создаются и уничтожаются "на ходу" - в процессе работы программы.

Стек

Стеком называется динамическая структура данных, у которой в каждый момент времени доступен только верхний (последний) элемент. Лучше всего понятие стека можно проиллюстрировать примером стопки книг: в стопку можно добавить еще одну книжку, положив ее сверху; из стопки можно взять, не разрушив ее, только верхнюю книгу. А для того, чтобы достать книжку из середины стопки, необходимо сначала убрать по одной все лежащие выше нее.

Последовательность обработки элементов стека хорошо отражают аббревиатуры LIFO (Last In First Out - "последним вошел, первым вышел") и FILO (First In Last Out - "первым вошел, последним вышел").

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

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

Операции

Для стека должны быть определены следующие операции:

Очередь

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

Последовательность обработки элементов очереди хорошо отражают аббревиатуры LILO (Last In Last Out - "последним вошел, последним вышел") и FIFO (First In First Out - "первым вошел, первым вышел").

Реализовать очередь также можно при помощи массива, хотя здесь уже не удастся полностью избежать перемещения его компонент. Пусть k-я компонента массива хранит начало очереди, а (k+s)-я - ее конец. Тогда можно приписать новый элемент очереди в (k+s+1)-ю компоненту массива, а при удалении элемента из начала очереди ее голова сдвинется в (k+1)-ю компоненту. В процессе работы может оказаться, что вся очередь "сдвинулась" к концу массива, и ее снова нужно вернуть к началу. В этом случае и потребуется s перемещений компонент массива (s - это текущая длина очереди).

Однако наиболее эффективной снова будет реализация при помощи односвязного линейного списка (см. лекцию 10).

Операции

Для очереди должны быть определены следующие операции:

Дек

Дональд Кнут¹⁾ ввел понятие усложненной очереди, которая называется дек (deque - Double-Ended QUEue - двухконцевая очередь). В каждый момент времени у дека доступны как первый, так и последний элемент, причем добавлять и удалять элементы можно и в начале, и в конце дека. Таким образом, дек - это симметричная двусторонняя очередь.

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

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

Рекурсия

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

Например, рекурсивно определяется функция факториал:

0! =1
n! = n*(n-1)!, для любого натурального n.

Другим примером рекурсивного определения может послужить определение арифметического выражения, приведенное в лекции 2.

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

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

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

procedure rec1(k: byte);      function rec2(k: byte): byte;
    begin                     begin
        ...                       ...
        rec1(k+1);                x:= rec2(k+1);
        ...                       ...
    end;                      end;

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

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

procedure rec_А(k: byte);
begin
   ...
   reс_В(k+1);
   ...
end;
procedure rec_В(k: byte);
begin
   ...
   rec_А(k+1);
   ...
end;

И здесь полезной оказывается возможность отрывать объявление подпрограммы от ее описания (см. лекцию 8). Например, для косвенной рекурсии в случае двух процедур, вызывающих друг друга (rec_A -> rec_B -> rec_A), нужно такое описание:

procedure rec_А(k: byte); forward;
procedure rec_В(k: byte);
begin
   ...
   reс_А(k+1);
   ...
end;

procedure rec_A;
begin
   ...
   rec_В(k+1);
   ...
end;

Пример рекурсивного алгоритма

Задача. Двумерный массив целых чисел представляет цвета клеток рисунка. Найдите самую большую связную область одного цвета. (Связи по диагонали не учитываются.)

Алгоритм решения

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

array[1..N,1..M] of byte;

а как

array[0..N+1,0..M+1] of byte;

Теперь опишем рекурсивную процедуру, делающую по массиву один "шаг вперед":

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

1. Если цвет новой клетки не совпадает с цветом предыдущей "посчитанной" клетки, то нам она не нужна. Сделаем шаг назад. Если этот шаг выводит нас из массива наружу, то это означает, что мы просмотрели все клетки одной связной области: пора сравнивать их количество с ранее найденным максимумом.
2. Если клетка помечена тем же номером, что и предыдущая, увеличим счетчик найденных клеток, изменим пометку этой клетки на 0, а затем шагнем снова: поочередно вверх, вниз, влево и вправо (последовательность не принципиальна). Здесь важно понимать, что шагнем мы только в одну сторону, а остальные просто запомним. И лишь после того, как мы вновь возвратимся в эту же клетку, мы "вспомним", что из нее мы еще не пытались уйти туда-то и туда-то, и продолжим этот процесс.

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

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

Стековая организация рекурсии

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

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

Таким образом, на внутреннем уровне организован стек контекстов подпрограмм.

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

procedure razlozh(k,t:integer; s:string);
var i: integer;
         sss: string;
begin
   for i:= t to trunc(sqrt(k)) do
      if k mod i = 0
         then begin
                     str(i,sss);
                     razlozh(k div i, i,s+sss+'*');
            end;
str(k,sss);
s:=s+sss;
writeln(s);
end;
begin
   readln(n);
   razlozh(n,2,'');
end.

Для n = 24 стек контекстов этой программы пройдет последовательно такие стадии (значения параметров указаны на моменты вызова процедуры, состояния стека приведены только на моменты времени, предшествующие закрытию очередного контекста):

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

2*2*2*3
2*2*6
2*3*4
2*12
3*8
4*6
24

Ограничение глубины рекурсии

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

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

Замена рекурсивных алгоритмов итеративными

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

Если исполнение подпрограммы приводит только к одному вызову этой же самой подпрограммы, то такая рекурсия называется линейной. Линейную рекурсию довольно легко заменить итеративным алгоритмом. Например, можно реализовать функцию факториала, определенную в начале пункта "Рекурсия", двояко.

function fact(k:byte)longint;
var x: longint;
begin
  if k = 0
    then fact:= 1
    else begin x:= fact(k-1)*k;
           fact:=x;
         end;
end;

fact:= 1
for i:= 2 to k do
fact:= fact * i;

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

Пример сравнения рекурсивного и нерекурсивного алгоритма

Задача. Двое друзей решили пойти в поход, собрали и взвесили все необходимые вещи. Как им разделить набор предметов на две части наиболее честным образом?

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

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

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

Реализация рекурсивного алгоритма

program pohod_rec;
var f: text;
     a: array[1..100] of integer;
     n: integer;
     min,obsh_ves: longint;
procedure step(t:byte; ves:longint);
var j: longint;
begin
      j:= abs(obsh_ves - 2*ves);
      if j<min then min:= j;
      for j:= t+1 to n do step(j,ves+a[t]);
end;

begin
   assign(f,'in');
   reset(f);
   n:=0;                      {кол-во всех предметов}
   obsh_ves:= 0;
   while not eof(f) do
      begin inc(n);
               read(f,a[n]);
               inc(obsh_ves,a[n]);
      end;
   close(f);
   min:= MaxLongInt;

   step(1,0);
   writeln('difference ',min)
end.

Полный перебор с отсечением

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

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

Нерекурсивный алгоритм

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

Основная часть приводимой ниже программы является итеративной реализацией алгоритма полного перебора всех возможных вариантов, удовлетворяющих входным ограничениям. Ее основное отличие от рекурсии - использование малого объема памяти для хранения текущих данных. Вся информация хранится в массивах ves, take и dif. Для вычислений на каждом шаге используется только эта информация. Такой подход позволяет избежать непрерывных перевычислений, которые и являются причиной "тяжеловесности" рекурсивного алгоритма.

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

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

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

Мы не приводим в тексте программы и реализацию функции min() - как не представляющую особенного интереса.

Реализация нерекурсивного алгоритма

program pohod;
const nnn = 100;            {максимально возможное количество различных весов}
var f: text;
    d,razn,k,i,j,n: integer;
    sum: longint;
    ves,kol: array[1..nnn] of word;
    take, dif: array[0..nnn] of word;

procedure vyvod(a: integer);
begin
    writeln(a);
    halt;           {принудительное завершение работы программы}
end;

begin
{---- Ввод данных и их сортировка ---}
    ...
{---- Основная часть программы -----}
    d:= sum mod 2;          {показатель четности общего веса}
    sum:=(sum div 2)+ d;    {"большая половина" общего веса}

    dif[0]:= sum;
    razn:= sum;
    for i:= 1 to k do
        begin
            take[i]:= min(dif[i-1] div ves[i],kol[i]);
            dif[i]:= dif[i-1]- take[i]*ves[i];
            if dif[i]< razn then razn:= dif[i];
            if razn <= d then vyvod(d);
    {проверка того, что уже на первом шаге найдено решение}
        end;

{---- Заполнение массива --------}
    i:= k;
    while i>0 do
        begin
            if take[i]= 0
                then i:= i-1                {переход к следующей компоненте}
                else begin		
                    dec(take[i]);            уменьшение текущей компоненты на 1}
                    inc(dif[i],ves[i]);     {увеличение остатка на соотв. величину}
                    for j:= i+1 to k do     {перезаполнение хвоста}
                    begin
                    take[j]:= min(dif[j-1] div ves[j],kol[j]);
                    dif[j]:= dif[j-1]- take[j]*ves[j];
                    if dif[j]< razn then razn:= dif[j];
                    if razn <= d then vyvod(d); {проверка результата}
                end;
                i:= k;
            end;
        end;
    vyvod(2*razn-d);
end.

Иллюстрация

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

Пусть имеется семь предметов (n = 7) с весами 9, 5, 25, 11, 9, 5, и 11 единиц (килограмм, фунтов, бушелей...). Тогда всего есть четыре разных вида предметов (k = 4).

Общая сумма весов равна 75; следовательно, "большая половина" sum = 38. Теперь нужно найти такой набор предметов, чей суммарный вес будет наиболее близким к этой "золотой середине". Кроме того, не стоит забывать и о сделанном ранее замечании: как только найдется набор, вес которого отличается от "золотого" лишь на единицу, поиск можно закончить.

Начнем теперь заполнять массивы take и dif (массив dif хранит остатки, в пределах которых можно проводить дальнейшие вычисления).

На начальном ("нулевом") шаге мы заполним массив take так, чтобы в создаваемый набор попали по возможности самые тяжелые предметы (см. раздел реализации "Основная часть программы"). Таким образом, получим следующие состояния массивов:

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

Двигаясь от конца массива take к его началу, будем уменьшать поочередно каждую его ненулевую компоненту. Разумеется, при этом будут возникать изменения в хвосте этого массива; эти изменения мы будем вносить туда в обычной последовательности "от начала к концу".

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

1

2

3

4

5

6

7

10

12

17

22

24

Итак, мы убедились в том, что найденное в самом начале значение переменной razn и было минимальным (найденные группы весов соответственно 25 + 11 = 36 и 11 + 9 + 9 + 5 + 5 = 39). Необходимо отметить, что из приведенных выше таблиц видно (см. шаг 5), что существует еще один способ разделить приведенный набор весов таким же оптимальным образом: (11 + 11 + 9 + 5 = 36 и 25 + 9 + 5 = 39). Найденная разница 39 - 36 = 3 и будет окончательным результатом, который программа сообщит пользователю.

Эффективность

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

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

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

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

Алгоритм Быстр

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

Теперь применим эти же действия к левой и к правой части массива - рекурсивно.

Реализация алгоритма Быстр

type index = 1..N;
var a: array[index] of integer;

procedure quicksort(l,r:index);
   var i,j: index; 
        x,z: integer;
   begin
         i:= l;
         j:= r;
         x:= a[(l+r)div 2];
         repeat
               while a[i]< x do inc(i);
               while a[j]> x do dec(j);
               if i <= j
                  then begin
                           z:= a[i];
                           a[i]:= a[j];
                           a[j]:= z;
                           inc(i);
                           dec(j);
                        end;
            until i>j;
         if l<j then quicksort(l,j);
         if i<r then quicksort(i,r);
   end;
begin   {тело программы}
   ...
   quicksort(1,n);
   ...
end.

Эффективность алгоритма Быстр

Алгоритм Быстрой сортировки имеет в среднем²⁾ сложность N*log N и, следовательно, относится к улучшенным методам сортировки массивов (см. лекцию 4). Кроме того, даже среди улучшенных методов упорядочения Быстрая сортировка дает наилучшие результаты по времени (для относительно больших входных последовательностей - начиная с N = 100).

Конечно же, существует и итеративный вариант алгоритма Быстрой сортировки, который еще более эффективен. Мы предлагаем читателям построить его самостоятельно.