Непейвода Н.Н., Скопин И.Н. Основания программирования

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

8.6. МОДУЛЬНОСТЬ TURBO PASCAL

455

ﬁnalization

<завершение: описание действий, которые

необходимо выполнить после использования

модуля>

end.

Имя модуля — это идентификатор, упоминание которого в специальном

разделе использующей программы, называемом uses, делает доступным ви-

димые объекты модуля.

Описания видимых объектов — это обычные описания констант, типов,

переменных и др., которые предоставляются пользователю.Их называют пре-

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

данном разделе. Поскольку от пользователя должны быть скрыты тела под-

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

языка

Pascal

Помимо видимой части локального контекста модуля, он содержит неви-

димую — описания скрытых объектов. В разделе implementation заголовки

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

procedure или function и именем подпрограммы (с учетом того, что полный

заголовок объявлен выше), либо в полной (обычной для

Pascal

’я) форме, со-

впадающей с заголовком подпрограммы из раздела interface.

Раздел инициализации описывает действия, которые необходимо выпол-

нить перед употреблением средств модуля в программе пользователя. Они

автоматически вызываются в программе перед выполнением всех ее опера-

торов. Раздел ﬁnalization в языке появился в ответ на потребность автомати-

ческого выполнения действий после работы модуля (например, отказ от за-

резервированной памяти). Если эти разделы не предусматривать, то на поль-

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

являются инородными.

На примере раздела инициализации мы имеем возможность сопоставить

варианты библиотеки с автоматически вызываемой инициализацией и без

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

варианте без инициализации пользователь должен вызвать процедуру

InitQueue

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

варианте этот вызов можно скрыть путем выполнения его в разделе инициа-

лизации и исключения

InitQueue

из интерфейса.

Таким образом, средства работы с очередью оформляются в виде следу-

ющего модуля:

456

ГЛАВА 8. ПОДПРОГРАММЫ

Программа 8.6.2

unit IntQueue;

interface

const MaxSize = 100;

NotEl = 0;

type States = ( Full, Empty, Normal );

procedure PutElQueue ( X : Integer );

function GetElQueue : Integer;

function StateQueue : States;

implementation

var

Container : array [ 1..MaxSize ] of Integer;

IB, IE : Integer;

BFull, BEmpty : Boolean;

procedure InitQueue; { реализация процедур }

... { и функций }

procedure IncI ( var I : Integer ); { InitQueue, }

... { IncI, }

procedure PutElQueue (X : Integer); { PutElQueue, }

... { GetElQueue и }

function GetElQueue : Integer; { StateQueue }

... { в точности повторяет }

function StateQueue : States; { их тексты на }

... { стандартном Pascal’е }

begin

InitQueue;

end.

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

TURBO

Pascal

’е,которой не слишком далеко ушел от стиля, достижимого в стандарт-

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

очередь. Тем не менее, модуль

IntQueue

с потребительской точки зрения не

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

а во-вторых, элементами очереди могут быть только целые числа.

8.6. МОДУЛЬНОСТЬ TURBO PASCAL

457

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

мирования инициализации очереди, вынесения процедуры

InitQueue

в ин-

терфейсную часть модуля и дополнения его процедурой

DoneQueue

, уничто-

жающей очередь по окончании работы с нею. Следует позаботиться об иден-

тификации очередей, что в стиле стандарта языка

Pascal

естественнее всего

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

ализации процедур

InitQueue

DoneQueue

целесообразно предусмотреть,

соответственно,порождение и ликвидацию массива

Container

и других пред-

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

Второй недостаток при использовании средств модуляризации, предста-

вленных выше, и других возможностей стандартного

Pascal

’я преодолеть не

удается. В языках с так называемыми абстрактными типами данных (

CLU

Alphard

и др.), а также в языке

Ada

, можно было бы воспользоваться параме-

трами-типами, заменив тип компонент массива

Container

и других структур,

принимающих значения хранимых в очереди элементов, именем формаль-

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

конкретных типов. В

TURBO Pascal

’е вместо этого предусмотрены механиз-

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

моментов объектно-ориентированного программирования.

Сделаем еще три замечания, характеризующих некоторые тонкости мо-

дульного программирования.

Во всех модульных расширениях языка

Pascal

возникает общая пробле-

ма конфликта имен. Если один и тот же идентификатор описан в нескольких

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

фликт имен. Конечно же, есть соглашение по умолчанию, какое по порядку

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

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

фицировано как

ThisUnit.Identiﬁer

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

конструкцию

with ThisUnit do begin ... end;

В программе или модуле видимы лишь те имена, которые определены в

модулях, перечисленных в соответствующем предложении

uses

. Никакого

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

458

ГЛАВА 8. ПОДПРОГРАММЫ

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

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

uses

ссылку на другой. Это не считается ошибкой,

лишь если открытая структура зависимостей модулей остается сетью (гра-

фом без циклов). Поэтому целесообразно обе перекрестные ссылки упрятать

в раздел

implementation

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

то придется констатировать, что возможности

TURBO Pascal

’я версии 5.0 в

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

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

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

языки линии

TURBO Pascal

Object Pascal

. Единственное, что они могут

предложить — это рецепт использовать мнемоничные имена. А этого явно

недостаточно. Из нашего примера видно, что если б мы реализовывали не

очередь, а стек, то интерфейсная часть модуля отличалась бы только имена-

ми. Чтобы можно было бы увидеть, что именно реализовано в модуле, про-

граммист должен позаботиться о соответствующем описании дополнитель-

но. Здесь и ему, и пользователю его модуля придется обратиться к призра-

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

мой программы.

8.6.3. Пример использования модуля

В качестве иллюстрации использования построенного абстрактного типа

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

циального приема программирования, основанного на накоплении порций

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

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

ко грамм рыбы

MaxW

он может съесть за один день, при этом не позволяя

себе оставлять частично съеденную рыбину.

Пусть у кота есть последовательность садков для хранения рыбы. Стра-

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

быть съедена в тот же день (суммарный вес уже накопленных в текущем сад-

ке и очередной не превосходит

MaxW

), то она помещается в текущий садок,

и тем самым величина веса рыб текущего садка

CurW

увеличивается. При

этом, если суммарный вес рыбы становится равным

MaxW

, то садок счита-

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

марный вес рыб превышает норму, возможно, что в садке есть рыба, замена

которой на очередную позволит уложиться в норматив

MaxW

. В этом случае

8.6. МОДУЛЬНОСТЬ TURBO PASCAL

459

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

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

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

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

превосходит интеллектуальные силы кота. По исчерпании поступления рыб

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

следовательность весов рыб, размещаемых в садках, и суммарные веса рыб

в каждом садке.

Задача решается путем ‘перекачки’ поступающей рыбы в очередь с одно-

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

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

ные заменить последний экземпляр из поступивших с улучшением показа-

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

последний поступивший и начинают играть роль последнего поступившего.

При этом возможно выполнение серии обменов. В программе используют-

ся вспомогательные процедуры:

InpW

, организующая ввод входного потока

с текущим контролем,

ClearQueue

, очищающая очередь и распечатывающая

ее содержимое, и

InpHandle

, выполняющая все действия, связанные с обра-

боткой очередного входного числа.

Решение опирается на использование модуля

IntQueue

, т. е. демонстриру-

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

Turbo Pascal 5.5

а не более развитых версий. Это сделано по следующим причинам:

• Достаточность средств модуля для данной задачи, для которой нет не-

обходимости использовать несколько очередей, очереди с нецелочи-

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

примеру, к объектно-ориентированным средствам особой нужды нет.

• Достаточность средств модуля для демонстрации возможностей средств

модуляризации всех языков линии

Turbo Pascal

. Как можно было уви-

деть из предыдущего обсуждения, эти средства у более развитых язы-

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

Turbo Pascal 5.5

. Допол-

нительные средства принципиально картину не меняют.

• Учебными целевыми установками. Здесь имеется ввиду возможность

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

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

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

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

InpW

, организую-

460

ГЛАВА 8. ПОДПРОГРАММЫ

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

ClearQueue

, очищающая

очередь и распечатывающая ее содержимое, и

InpHandle

, выполняющая все

действия, связанные с обработкой очередного входного числа.

Программа 8.6.3

program WWW;

uses Crt, IntQueue;

const MaxW = 15;

var InpEl, CurW : Integer;

procedure InpW;

begin

repeat

Read ( InpEl );

Writeln ( ’Ошибка: слишком большой вес.’,

’ Повторите ввод’);

until InpEl <= MaxW

end;

procedure ClearQueue;

begin

while StateQueue <> Empty do

Write ( GetElQueue, ’ ’ );

end;

procedure InpHandle;{

Обрабатывает

InpEl,

корректирует

CurW }

var S, Sn, R : Integer;

begin

S := CurW + InpEl;

if S < MaxW

then begin CurW := S;

PutElQueue ( InpEl );

end

else

if S = MaxW

8.6. МОДУЛЬНОСТЬ TURBO PASCAL

461

then

begin

ClearQueue;

Write ( InpEl, ’ ’);

Write ( ’(’, S, ’) ’);

CurW := 0;

end

else { S > MaxW - возможен обмен }

begin

while StateQueue <> Empty do begin

R := GetElQueue;

Sn:= S - R;

if ( Sn > MaxW ) or ( Sn <= CurW )

then { Отказ от обмена }

Write ( R, ’ ’ )

else begin

Write ( InpEl, ’ ’ );

if Sn = MaxW then { Оптимизация }

ClearQueue;

{ Завершение обмена }

InpEl := R;

CurW := Sn

end

end;

Write ( ’(’, CurW, ’) ’);

CurW := InpEl;

PutElQueue ( InpEl )

end

end;

begin

CurW := 0;

Writeln (’Поток входных значений:’);

while not eoln do

begin

InpW; InpHandle; end;

ClearQueue;

Writeln ( ’(’, CurW, ’) ’ );

462

ГЛАВА 8. ПОДПРОГРАММЫ

repeat until KeyPressed

end.

Решение данной задачи, вообще говоря, может базироваться не только на ис-

пользовании

IntQueue

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

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

стратегию, можно чисто механически заменить в программе

WWW

вызовы

подпрограмм модуля

IntQueue

на вызовы подпрограмм подходящего моду-

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

решение будет отличаться от приведенного лишь порядком установки кон-

тейнеров (съедения рыб котом). Читателю настоятельно рекомендуется убе-

диться в этом.

Анализ предложенного решения и сопоставление его с только что упомя-

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

или стека не влияет на эффективность программы. Уровень эффективности

будет зависеть от качества реализаций этих двух структур данных. Как оче-

редь, так и стек обеспечивают правильную дисциплину обращения к памяти

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

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

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

метить,что очередь позволяет ‘почти’сохранять в выводе порядок, в котором

вводятся элементы данных, тогда как стек делает его ‘почти’ произвольным.

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

С точки зрения демонстрации модуляризации уместно заметить, что сме-

на одного модуля (

IntQueue

) на другой (работа со стеком или с очередью,

базирующейся на списковой организации) практически не приводит к из-

менению алгоритма. С точностью до имен процедур решение сохраняется.

Но это достигнуто благодаря тому, что модулем

IntQueue

на уровень исполь-

зования вынесены только необходимые возможности, никак не завязанные

на реализацию. Поддержка разделения контекстов языком программирова-

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

В свою очередь, именно это обстоятельство позволяет провести анализ раз-

личных вариантов организации памяти.

Задания для самопроверки

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

эффективно организовать работу,воспользовавшись секциями

initialization

8.7. РЕКУРСИВНЫЕ ПРОГРАММЫ

463

ﬁnalization

модуля. Проделайте это для случая, когда в программе

всего одна очередь.

2. Реализовать стратегию кота, механически заменив в программе

WWW

использование модуля

IntQueue

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

для работы со стеком и вызовы подпрограмм модуля

IntQueue

на вызо-

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

3. Чем новое решение будет отличаться от приведенного в тексте?

§ 8.7. РЕКУРСИВНЫЕ ПРОГРАММЫ

Методы составления рекурсивных алгоритмов занимают заметное место

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

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

понимании процессов вычислений в целом. Главная цель настоящего раздела

в том, чтобы обеспечить возможность на практике ознакомиться с рекурси-

ей, сопоставить рекурсивность с другими, в некотором смысле родственны-

ми понятиями, в первую очередь, с итеративностью. В соответствии с этой

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

Этому посвящена глава в части III.

Если алгоритм построен таким образом, что в ходе его работы возможно

повторение некоторых действий посредством обращения к самому себе (т. е.

обращение к вычислениям, описанным этим алгоритмом), то такой алгоритм

называется рекурсивным.

При изучении этого понятия следует обратить внимание на две стороны

рекурсивности: способы задания рекурсивных алгоритмов (описание их на

языке программирования) и механизм выполнения рекурсивного алгоритма

в ходе работы программы.

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

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

ством такого рода являются операционные подпрограммы: обозначение ал-

горитма — имя процедуры или функции, снабженное списком фактических

параметров — используется при вызове подпрограммы для исполнения. Вы-

зов подпрограммы,помещенный непосредственно в тело подпрограммы (т.е.

в описание алгоритма на языке) приводит к активизации повторного выпол-

нения алгоритма еще до того, как первое выполнение подпрограммы не за-

вершено.

464

ГЛАВА 8. ПОДПРОГРАММЫ

Рассмотрим следующий пример. Пусть требуется вычислить N! для не-

больших значений N. Определение этой функции как произведения

1 ∗ 2 ∗ ··· ∗ N

приводит к почти однозначному описанию требуемого алгоритма в виде ци-

кла — итеративная схема:

F := 1;

for I := 2 to N do F := F * I;

C *

F = 1;

for (int i = 2; i<= N; i++) F = F*I;

Если же N! определяется рекуррентным соотношением:

1! = 1;

N! = (N − 1)! ∗ N, при N > 1,

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

согласуется с ним следующее описание функции, которое называется рекур-

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

схеме:

Программа 8.7.1

function FACT ( N : Integer ) : Integer;

begin

if N < 2

then FACT := 1

else FACT := FACT ( N - 1 ) * N

end;

int FACT ( int N )

if (N<2) return 1;

else return ( FACT (N-1)*N);

}