Бауэр Ф.Л., Гооз Г. Информатика. Том 1

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

РИС

95 Основная форма итеративного программного формуляра для вычис-

ления

функили

gcdl

тп

результат}-—

Рис

96 „Итеративный формуляр, полученный „разверткой" программного

формуляра на рис 95

192 Гл 3 Машинно-ориентированные алгоритмические языки

„развёртки"

повторительной рекурсии в плоскую таблицу ис-

пользуют (см. рис. 95) итерируемый

программный

формуляр,

содержащий правило итераций

результате

получается представленный на рис. 96 „развёрну-

тый"

формуляр для вычисления

gcd{\5,

9). Аналогичным обра-

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

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

ного (машинного) вещественного числа а:

Такие

итерационные правила

следует

повторять под управле-

нием

соответствующего условия (на рис. 95, 96 это управление

отмечено пунктирными стрелками).

3.3.2.

Повторение

Таким

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

ражается введением

оператора

цикла

условием

продолжения:

некоторый

программный формуляр, т. е. определённый опера-

тор,

повторяется до тех пор, пока не перестанет выполняться

определённое условие.

здесь

алгол-68

и паскаль используют похожие, хотя и от-

личающиеся в деталях способы записи '•

while

)условие(

•\

do )оператор( od

while

)условие( do

)оператор(

На

машине обработки формуляров повторение характери-

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

со сложенными стопкой графами, т. е. итеративным примене-

нием

некоторого программного формуляра.

Оператор цикла является

отвергающим

в том смысле, что

если условие с самого начала не выполнено, то подлежащий по-

вторению оператор не исполняется ни разу

Примем,

что

оператор

цикла — это

тоже

оператор.

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

begin

end одно-

единственное присваивание или один-единственный оператор цикла. В ал-

голе-68

скобки do.od

действуют

как скобки-уголки.

Ниже

while

и do означают соответственно „пока" и „делай"; od — это

„перевёрнутое" do. —

Прим.

перев.

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

цикла,

используемый как сомнительной ценности сокращение.

3 3

Итеративное программирование

193

funct

gcdl

(int

т. п

com

a 0 л п Й 0 со) int:

Fvar

int v=m ;

var

int r:=n;

var

int z;

while

r>0

: =\ ;

while

zgiy

z,=

z—

od;

function

gcdl

(in,

•

integer

\(m

а о) л с» > о))) ш/(?0«- i

var v. v. - :

mtegei

;

begin

v:=m ;

;•:=";

while

y>0 do

begin

z:=.\;

while

z>ydo

z:=z-y\

x:-y;

end;

gcdl

<= A:

end

Рис.

Тогда повторяемый оператор

сам

может быть оператором

цикла

или

содержать

его, как в

следующем примере

funct

qcdl

(int

га, п со т S 0 л п s

coj int;

Г var

int x:=m ;

var

int

y:=/i;

while

v>0

var cnt :'— v ;

while

:S i

z.=z-y

od ;

y,=:

od;

повторяемом операторе может встречаться

описание

пе-

ременной,

как,

скажем,

var int г в

приведённом выше примере.

Если

внешнее повторение выразить посредством соответствую-

щей

повторительной рекурсии,

то для

каждого воплощения

по-

явится

своя собственная переменная. Таким образом, машина

обработки формуляров работает

со

стопкой переменных

(0)

(1)

, г

(2)

, .. . , г

(и>

(каждая

из

которых

свою очередь

обо-

значает стопку промежуточных результатов).

Для gcdl (15, 9)

получим

Систематическое рассмотрение этого вопроса

будет

проведено

разде-

лах

3 3 22 и 3 3.4.

Ф. Л.

Ваучр,

Г.

Гооэ

194

Гл.

Машинно-ориентированные

алгоритмические

языки

В паскале описание переменных внутри оператора цикла

не

допускается. Такие описания должны быть вынесены

„на-

ружу"

— в

начало ближайшего охватывающего блока.

Хотя в

алголе-68

это

тоже допускается, однако

этом мало смысла,

поскольку теряется

результат

инициализации

(см. рис. 97).

3.3.2.1.

Итеративные

программы

Вообще, справедливо такое утверждение:

любую

рекурсив-

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

из

одной-единственной альтернативы, можно сразу

же

записать

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

оператора цикла. Действительно,

работа машины обработки формуляров

данном

случае

со-

стоит исключительно

в том, что

вычисляются новые фактические

значения

для

вызова следующего воплощения, причём

эти вы-

числения

всякий

раз

производятся

по

одним

и тем же

форму-

лам.

Для

этой цели необходимо иметь одновременно

столько программных переменных, сколько неконстантных пара-

метров

подпрограммы. Условием оператора цикла

будет

то

•самое условие, которое охраняет ветвь

рекурсивным вызовом.

В связи

этим рассмотрим

еще раз ход

реализации рекурсии

для

gcdl (15, 9),

представленный

на рис. 94.

В общем

целом

ход

вычислений отражается соответствую-

щими

последними значениями

(l)

, «

(<)

двух

переменных

mvar

nvar;

тьар

nvar*

конце вычислений

mvar

обозначает результат.

Предполагая

примитивность операции mod, получим версию,

основанную на повторении группового присваивания паре пере-

менных

(mvar,

nvar);

function

gcdl

(m,

integer

=£

0|):

iniegei

var

mvar,

nvar:

integer;

begin

{mvar,

m>ar):—(m,

ri);

while

nvar>0

unct

gcdl

s (int

СО7И=;0ЛЯЙ;0

СО) int:

["(var

int

mvar,

nrar):=(m.n)

;

while

nvar>0

(mvar,

nvar)

{nvar,

mod

(mvar,

nvar))

od;

mvar

(mvar,

nvar)',=

(nvar,

mod

(mvar,

nvar));

gcdl

<=.

mvar

end

3.3. Итеративное программирование

195

В этом примере обнаруживается типичное деление тела

под-

программы

на три

части:

(a) (Групповое) описание

инициализация переменных.

Инициализация

осуществляется параметрами

(или их

фактиче-

скими

значениями

при

вызове внутри некоторой объемлющей

подпрограммы).

(b) Повторение (группового) присваивания, соответствую-

щего замещению параметров,

при

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

жения

рекурсии.

(c)

Фиксация

(получение, вывод) результата.

Это проявляется

и при

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

sel из

примера

(g)

раздела

2.3.2.

Здесь

мы

получаем

funct

sets

(string

int

со

£i

iSlenglh

(а)

со)

char:

f(var

string

auar,

var

int irar):~(a,/);

while

ivar>'[

{auar,

iuar):^{resi{auar),

war

-1) od;

•

first

{avar)

function

sel

siring;

integer

1(1

and

(i<length{a))\);

char,

var

avar:siring;

war:

integer;

b«9'm

(jfbar,

!var)\"{a,i)x

while

four

(avar,

iuar):=

(rc.sl{avar),

iuar

—

I);

sel

aj'ml

{auar)

end

Точно

так же

можно преобразовать

итеративную форму

под-

программы типа

invert

(см.

2.6.1).

Аналогично можно поступать

и с

такими подпрограммами,

как

issorted (см.

2.4.1.5)

или isprim (см.

2.4.1.3),

только

в слу-

чае последней подпрограммы, основанной

на

функции

ispr

(см.

2.4.1.3)

надо предварительно преобразовать фигурирующее

ispr

условие:

funct

bpr&

(int

со 2Цтйп

со) booh

n mod m

then

ispr(rt,

m +1)

else

m=n

function

ispr(n,

integer

{2&tn£n});

Boolean

begin

modm+0

then

ispr

(if,

m +1)

else

ispr-&m=n

end

(Отметим справедливость импликации

nmod

тфО

=з~

тф п.)

результате

вставки (параметр

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

ispr

оказы-

вается неизменным

получим подпрограмму, представленную

на

рис. 98.

Параметр

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

ispr

можно

было

бы

опустить

ещё

раньше,

после подчинения этой подпрограммы подпрограмме

isprim (см.

подпрограм-

му

ispr в

разделе

2.5.2.1).

196

Гл. 3. Машинно-ориентированные алгоритмические языки

funct

iiprim

(int

со nt I co)

bool:

if n=l

then false

else

var int

nwar:=2i

while

n mod

mvar^Q

nwar:=mvar

-I-1

od;

function

hprlm (л : integer

{« 51]): Boolean;

var

rate/

integer;

begin

if и = I

then

isprim

-a

false

else

begin nwar'.*>2',

while

и mod miw + 0 do

end

isprim

end

Рис.

98.

Повторительные подпрограммы, в

телах

которых встречается

несколько

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

ренную выше форму с одним-единственным (гладким) вызовом:

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

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

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

3.3.5.

Итак,

если ограничиться исключительно повторительными

подпрограммами, то можно обойтись использованием одних

лишь

переменных и операторов цикла. При этом мы по-преж-

нему можем считать их способом сокращённой записи для осо-

бенно

простого случая рекурсии. С

другой

стороны, мы можем

также, следуя историческому развитию, подвести под всё это

внешне

нерекурсивную семантику; для этого нужно не только

отождествить разные воплощения формуляра, но и вынести

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

менные.

Тем самым выполнение вычисления („исполнение") сводится

движению

по программному формуляру, а

состояние

вычисле-

ния

определяется последними текущими значениями используе-

мых программных переменных и позицией в программном фор-

муляре.

Разумеется, групповые присваивания

могут

выполняться

параллельно, если для этого имеется необходимое оборудо-

вание.

Подпрограммы, которые, подобно рассмотренным в этом раз-

деле, содержат повторения, но не обнаруживают рекурсии, так-

же называют

итеративными.

Формальная

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

будет

рассмотрена в гл. 8.

3.3. Итеративное программирование

197

3.3.2.2.

Иерархические повторительные системы

вложенные циклы

Наконец,

мы можем рассмотреть и иерархическую систему

tgcdl,

mod) из примера (d) раздела

2.3.2.

Здесь лучше всего

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

mod (после подчинения этой подпрограммы подпрограмме

gcdl

(см.

2.5.2.1)). Получим

funct

modi

= (int и

со и й 0 со) int:

var int uvar:=u;

while

uvar^n

do uvur:=uvar —n od ;

uvar

function

modi

(u:

integer

{«SO}):

integer;

var

uvar:

integer;

begin

uvar:=u;

while

uvar^n

do uvar

uvar -n ;

modi

uvar

end

Теперь надо описание подпрограммы mod записать внутри

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

gcdl.

При этом глобальный параметр п подпро-

граммы

modi

должен быть замещён значением нелокальной пе-

ременной

nvar.

Это даёт подпрограмму, представленную на

рис.

99.

funct

gcdl

= (int m, я

сотйОллйО со^ int;

ffunct

modl

= (int и со «SO со) int:

Tver

int

uvar,—и

;

while

uvar

invar

uvar."

uvar—nvar

od,

war J;

{var int

mvar.

nvar):={m,

n);

•while

nvar>0

(mvar,

nvar):=

(nvar,

modl(mvar))

od;

invar

Рис.

function

gcdl

(m,

n :

integer

{m>

«SO)):

integer',

var

muar,

ni>ar:

integer;

function

modi (u : integer {u£0)): integer ;

var

uoar: integer;

begin

uvar:=u;

while

uvar invar

uvar.—uvar—nvar ;•

modi

MIW

end;

begin

(mvar, nvar);=(m,n)j

while

mw>0"

(mvar,

nvar)'.=*

(nvar,

moJl(mvar));

gcdl

mvar

end

99.

Если

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

modi

d то инициализацию нужно видоизменить так: var int

uvar :=

mvar,

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

(mvar,

nvar) :==

(nvar,

modi

(mvar))

вместо

modi

(mvar) использовать полученный в uvar результат.

Это приводит к подпрограмме, представленной на рис. J00. Здесь

198

Гл.

Машинно-оирентированные

алгоритмические

языки

funct

gcdl

s(\nt m,n

со)

int,:

int

mvar,

mw):=

(m,

n);

while

nvar>Q

•do

var int uvar:-mvar',

while nvar^nvar

war

:=uvar—nvar

od;

{mvar,

nvar):=(nvar,

var)

od;

mvar

function

gcdl{m.

11:

integer

\(m

> 0) л

(и

0))):

irt

var mvar, nvar,

war:

integer %

begin

(niter,

mw) :=

(m,

n);

while nvar>0

do begin uvar:=mvar;

while uvar^nvar

do uvar:=uvar—nvar;

(mvar, nvar):=(nvar, uvar)

end;

end

Рис.

100.

появляются вложенные операторы цикла, поскольку

теле

под-

программы

gcdl,

описанной

примере

(d)

раздела

2.3.2,

вызов

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

mod

вложен

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

gcdl.

Иначе

обстоит дело

случае следующей системы (Idfac,

Idr), (ср. с

подпрограммами

facr

из

2.4.1.3

и Id из

2.4.1.5):

•funct

Idfac

(int у, п со

JS1

со) int;

и»0

then

ldr(0,y)

else

Id/ac

(у

п, п

-1) fi

funct

Mrs (int x,m

com^l

со) int:

•=

thenx

else

ldr(x+1,

div

Для Idfac получается итеративная формулировка

последова-

тельными операторами цикла:

funct

Idfacз(intу,и corfelAnSO со)

int:

f(var int

yvar,

nvar):-=(y,ri)

;

while mar>0

do (yvar, nvar)

(гид»-

nvar, war—I)

od;

(var

int

xvar, mvar)'— (0,yvar)

;

while

mvar>\

(тоа/", miw):=(jnw+],/mw

div 2) od;

При

вызове

iafac(l,

вычисляется округленное значение

двоич-

ного'

логарифма от п\

3.3. Итеративное программирование

199

Что касается паскалевской нотации для Idfac, см. рис. 104.

Между прочим, переменные

mvar

yvar

можно отождествить,

равно как и переменные xvar и

nvar,

поскольку подпрограммы

Idfac и Idr должны выполняться строго

друг

за другом, а типы

переменных согласованы. Заметим, что после окончания первого

оператора цикла переменная

nvar

имеет значение 0.

3.3.2.3.

Диаграммы

Насси —

Шнейдермана

Компактное графическое представление

хода

исполнения

программного формуляра, отражающее структуру вложенности

while

ilii

Dnepamop

альтернатива.

повторение

РИС.

101.

СИМВОЛЫ,

ИЗ которых строятся диаграммы Насси—Шнейдермана.

function

gcdl(m,n:

integer

[тъ 0

hn>o})'.

integer;

var

mvar,

nvar:

integer-,

(mvar,

nvar):

(m,

тгУ

while

nvar>

(mvar,

nvar):

gcdl

<^mvar

(nvar,

mod

{mvar,

nvar))

Рис. 102. Диаграмма

Насси

— Шнейдермана для подпрограммы

gcdl,

опи-

рающейся

на подпрограмму mod.

составляющих конструкций, даёт

диаграмма

Насси

—Шнейдер-

мана.

Базовыми элементами, из которых строятся такие диаг-

раммы, служат изображённые на рис. 101 символы оператора,

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

ответствующий текст на принятом языке программирования; эти

символы

могут

быть произвольным образом вложены

друг

друга.

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

структуру даже весьма сложных итеративных программ. Про-

стой пример для подпрограммы

gcdl

из

3.3.2.1

показан на

рис.

102.

200

Гл.

Машинно-ориентированные алгоритмические языки

По

поводу употребления альтернативы см. 3.3.5.1. Пример

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

мы

gcdl

из

3.3.2.2).

var

mvar,

nvar,

(muar,

while

uvar:

integer;

nvar): =(m,n)

nvar > 0

uvar:

=mvar

while

uvarinvar

uvar:

uvar -nvar

(mvar,

nvar):

(nvar,

uvar)

gcdl

<^rnvar

Рис.

103.

Диаграмма

Насси

—

Шнейдермана

для gcdl.

function

Idfac

(у, n: Inleger

[у>ЛЛ

л>о}):

integer',

var yvar, nvar, xvar, mvar: integer;

(yvar,

while

{xvar,

while

nvar);

nvar>

(yvar,

mvar)

mvar>

(xvar,

Idfac

<=xuar

H/,n)

nvar)

(yuar*

nvar

nvar-

(0,

yvar)

mvar):

(xvar-V

mvar

div

Рис.

104.

Диаграмма Насси

—

Шнейдермана

для

Idfac.

Для сравнения на рис. 104 изображена диаграмма с двумя

циклами,

которые не вложены

друг

друга;

эта диаграмма со-

ответствует подпрограмме Idfac из

3.2.2.2.

3.3.3.

Решение

задач

помощью

итеративных

форм

Один из надёжных способов решения задач состоит в сле-

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

переходим к итеративной формулировке.