Иванова Г.С. - Основы программирования

5. Модульное программирование

else {рекурсивный вызов} ifa>b then

nod:=nod(a'b,b) else nod:=nod(a,b'a)

end; Begin

ReadLn(a,b);

r:=nod(a,b);

WriteLn(r);

End

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

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

Пример 5.12. Разработать рекурсивную подпрограмму «переворота» строки (первая буква должна стать последней, вторая - предпоследней и т.д.).

Можно предложить два способа разворота строки.

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

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

менты на исходные места.
Вариант с о т с е ч е н и е м	и д о п и с ы в а н и е м :
Function reversel (const st:string): string;
Begin iflength(st)=0	then reverserl:= "
else

reverserl: = reversel (copy(st, 2, length(st)'l)) +stflj;

End;

Определим размер фрейма активации:

V = 4 (адрес параметра) + 256 (результат-строка) + + <размер служебной области > «270 (байт).

171

Часть I. Основы алгоритмизации и процедурное программирование

Вариант с и с п о л ь з о в а н и е м

п е р е с т а н о в о к :

Procedure reverse2(var ss:string; ri:integer); Var temp:char;

Begin ifn<=Iength{ss) div 2 then begin temp:'=ss[n];

ssfnj: =ssflength(ss)' i+1]; ss[length(ss)'П+IJ: = ^emp; reverse2(ss, n+1);

end;

End;

Размер фрейма активации для этого варианта:

У=4(адрес 1-го параметра)-ь2(копия 2-го параметра) + + 1(локальная переменная)+<размер служебной области>«17 (байт).

Следовательно, второй вариант предпочтительнее.

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

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

Пример 5.13. Разработать программу определения корней уравнения у=х2-2 на заданном отрезке методом половинного деления.

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

Базисное утверждение: если абсолютная величина функции в середине отрезка не превышает заданного значения погрешности, то координата сере­ дины отрезка и есть корень.

Рекурсивное утверждение: корень расположен меисду серединой от­ резка и тем концом, значение функции в котором по знаку не совпадает со значением функции в середине отрезка (рис. 5.12).

Program ex;

Var a,b,eps,x:real;

172

5. Модульное программирование

С Root Л

(а.Ь г,е) J

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

Procedure root(a,b,eps:real;var r:real); Varf,x:real;

Begin x:=(a+b)/2; f:=x*X'l;

ifabs(f)<=eps then r:=x else

if (a *a'l) y> 0 then root(x, b, eps, r) else root(a,x,eps,r)

End;

Begin ReadLnfa, b, eps); root(a,b,eps,x); WriteLn('Корень x^ \x:9:7);

End

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

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

173

Часть 1. Основы алгоритмизации и процедурное программирование

Рис. 5.13. Пример взаимно рекурсивных подпрограмм

сывают заголовки подпрограмм с пара­ метрами, за которыми вместо тела под­ программы следует forward; затем опи­ сывают тела этих подпрограмм (причем параметры второй раз можно уже не описывать).

Например, описание процедур А и В, которые рекурсивно вызывают друг друга (рис. 5.13), можно выполнить сле­ дующим образом:

procedure В(j:byte); forward; procedure A (j:byte);

begin ... B(i); ... end; procedure B;

begin ... A(j); ... end;

Пример 5.14. Разработать программу проверки чередования букв и цифр в заданной строке (первый символ ~ обязательно буква).

Базисные утверэюдения:

•строка допустима, если она пустая;

•строка не допустима, если в ней обнаружен недопустимый символ. Рекурсивное утверэюдение: если текущий символ строки допустим, то

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

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

Program ex;
Var s.string;
Functionf_char(var	st:string;i: word):boolean; forward;
Function f_value(var	st:string;i:word):boolean;
Begin

if i>length(st) thenf_value:=true

else iffstfij in f'0\. *9'J)thenf_value:=f_char(st,i-^l) elsef_yalue:=false;

End;

174

5. Модульное программирование

Function f_char;

Begin

if i>length(st) then f_char:=true

else
if Mi]	in ['A \. 'Z\ 'a'.. *z']) then
	f_Shar: =f_value(st, /+1)
else	fjohar:=false;
End;
Begin

WriteLnCВведите строку: *); Readln(s);

iff_char(s, 1) then WriteLnCCmpoKa корректна *)

else WriteLnCCmpoKa не корректна *);

End

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

Операторы, которые на схеме помечены как «операторы после вызова», выполняются после возврата управления из рекурсивно вызванной подпро­

	граммы. Если попытаться	изобразить	f
	последовательность действий при ли­			Имя	Л
	нейной рекурсии, то она будет выгля­		V	(-0	J
	деть, как это показано на рис. 5.15.		да	Выход	нет
	Таким образом, сначала в каждой
	активации выполняются	операторы,
	расположенные до рекурсивного вызо­		Базисная		Операторы
	ва, затем (при достижении условия вы­		ветвь		"до вызова"
	хода) ~ нерекурсивная часть очеред­				Имя
	ной активации, а затем ~ операторы,
	записанные после рекурсивного вызо­				(...)
	ва. На этом построены многие рекур­				—\—
					Операторы
	сивные алгоритмы.
					"после
	Пример 5.15. Разработать про­				вызова"
	грамму, которая выводит из заданного				т-
	массива, завершающегося	нулем, сна­	(	Return	j
	чала положительные значения, а за­
	тем - отрицательные в любом поряд­
	ке. Между положительными и отрица­		Рис. 5.14. Структура
	тельными элементами массива вывес­		подпрофаммы с линейной
	ти три звездочки.		рекурсией

175

Часть J. Основы алгоритмизации и процедурное программирование

	Основная программа
	Первая активация
	Вторая активация
Операторы	Третья активация -	базис	Операторы
"до вызова"			"после вызова"

Рис. 5.15. Рекурсивное погружение и рекурсивный выход при линейной рекурсии

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

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

Program ex;

Type mas =array[I.. JOJ of real; Var x:mas;

i:integer;

Procedure print(var x:mas;i: integer); Begin

ifx[i]=Othen WriteLnf'***') else

begin

ifx[i]>0 then WriteLnfi,': xfij); print(Xyi+l); {рекурсивный вызов} ifx[i]<0 then WriteLn(i,' ^ xfiJ);

end

End;

Begin

i:=0;

repeat i:=i+l; Read(x[i]) until x[ij=0; ReadLn;

print(xj);

End.

\16

5, Модульное программирование

Примечание. Обратите внимание, что значение i в
каждой активации свое, и оно не меняется во время	л л л
выполнения подпрограммы: одно и то же как до рекурсив­
ного вызова, так и после него.
Кроме линейной достаточно часто встреча­	12 li13	21 23	31 32	1
ется рекурсия, получившая название древовид­	1 1I I		1
ной. При древовидной рекурсии подпрограмма в	123 132	213 231	312 321
течение одной активации вызывает саму себя	Рис. 5.16. Дерево
более одного раза. Полученная в данном случае
	формирования
последовательность вызовов имеет форму дере­
	перестановок
ва, с чем и связано название данного вида орга­
		при т=3
низации процесса вычислений.

Пример 5.16. Разработать программу, которая формирует все переста­ новки без повторений некоторого массива значений. Например, если задан массив, содержащий символы ABC, то необходимо сформировать следую­ щие комбинации: ABC, АСВ, ВАС, ВСА, CAB, СВА.

Будем исходить из того, что в комбинации на первое место можно поста­ вить любой из имеющихся m символов. На второе место в каждом варианте можно поставить любое из оставшихся т-1 значений. На третье место - лю­

	бое из П1-2 значений и т.д. На послед­	Perest	Л
	нее т-е место -- единственное остав­
	шееся значение. На следующем т+1-м	((п,т,г,р)	J
	шаге перестановку можно выводить.
	На рис. 5.16 представлено дерево фор­
	мирования вариантов перестановок	r^^:=l,m-n+lV-|
	для т=3.
	Таким образом, каждая активация	Вывод	p[n]:=i
	подпрограммы уровня п должна вызы­	p[m]
	вать саму себя n-m+1 раз, каждый раз		Получение
	передавая следующей активации мас­
	сив еще не расставленных значений г1.		rl
	Окончательный алгоритм подпрограм­		Perest
	мы формирования перестановок пред­		(n+l,m,rl,p)|
	ставлен на рис. 5.17.
	Program ex;	( Return	j
	Type
	mas=array[L,5] ofchar;	Рис. 5.17. Схема алгоритма
	Const a:mas= 'ABCDE V
		подпрофаммы формирования
	Var pole:mas;	перестановок

177

Часть I. Основы алгоритмизации и процедурное программирование

procedure Perest(n,m:integer; Const г:mas; Var pole:mas); Var rl:mas;

kjJ: integer; Begin

ifn>m then begin

for i:=l to m do Write(pole fij); WriteC '):

end else

for i:-l to m-n+l do begin

pole[n]:^r[i];

k:=l;

forji^l	to m-n^l do
ifjoi	then
	begin

rl[k]:-r[j]; k:=k+];

end;

Perest(n-^l,m,rl,pole); end;

End;

Begin

Perest(l, 5, a.pole); End

Определим размер фрейма активации. Параметры: V, = 2*2 + 4 + 4; локальные переменные: V2 = m + 3*2; служебная информация: V3 « 12.

Откуда

V = V, + V2 + Уз = 12 + m + 6 + 12 « 30 + т .

Максимальное количество одновременно существующих активаций равно т+1 . Соответственно максимальный объем используемой памяти сте­ ка

^тах = (30 + п^)(п1 + 1) = т2 4- 31т + 30.

Так, для т=5

Vj^^^^ ="210 (байт).

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

178

5. Модульное программирование

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

Задание 1. Разработайте рекурсивную подпрофамму, формирующую последо­ вательность строк:

А

ВВ

ССС

DDDD

ЕЕЕЕЕ

FFFFFF и т. д. Всего 26 строк. Разработайте тестирующую профамму.

Задание 2. Разработайте рекурсивную подпрограмму вычисления биномиаль­ ных коэффициентов:

Г	О,	если m>n>0;
C{m,n} = ^	U	^сли (т=0 и п>0) или (m=n=0);

I C{m-l,n-l} + C{m,n-1} в остальных случаях.

Задание 3. Разработайте рекурсивную подпрофамму быстрой сортировки эле­ ментов массива (сортировка Хоора [3, 6]). Быстрая сортировка выполняется следую­ щим образом. Выбирают любой, например, первый элемент массива, и затем элемен­ ты переставляют так, чтобы слева располагались элементы меньше выбранного, а справа - больше. Для этого массив просматривают с двух сторон и меняют местами элементы, стоящие не в своей части массива. Тем самым выбранный элемент оказы­ вается на своем месте. После этого описанный алгоритм применяют к левой и пра­ вой частям подмассива и т. д., пока очередной подмассив не окажется состоящим из одного элемента. Корректная реализация данного метода обеспечивает вычислитель­ ную сложность Оср(п Iog2 п).

Задание 4. Разработайте рекурсивную подпрограмму «Ханойская башня». Имеется три колышка. На первом нанизаны m пронумерованных колец. Необходимо расположить кольца в том же порядке на любом из оставшихся колышков. При этом кольца можно переносить только по одному, причем не разрешается класть кольцо с большим номером на кольцо с меньшим номером.

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

Существует класс задач, в которых из некоторого количества вариантов необходимо выбрать наиболее подходящий (оптимальный). Для таких задач далеко не всегда удается найти алгоритм, который позволил бы получить ре­ шение без анализа всех или большого количества комбинаций исходных дан­ ных, т.е. без осуществления перебора. Осуществление полного перебора тре­ бует много времени. Вычислительная сложность решения задач с использо­ ванием перебора обычно оценивается как 0(п!) или даже 0(п").

179

Часть I. Основы алгоритмизации и процедурное программирование

Для решения задач данного типа применяют две стратегии:

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

•генерацию и анализ комбинации осуш.ествляют по частям.

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

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

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

Цикл-пока еще есть варианты Генерировать комбинацию исходных данных если вариант удовлетворяет условию,

то Обработать вариант

все-если Все-цикл

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

Пример 5.17. Разработать программу генерации следующих комбина­ ций: 1111, 1112, 1113, 1121, 1122, 1123, 1131, 1132, 1133, 1211,..., 3333.

В а р и а н т 1. Для генерации комбинаций используем вложенные цик­ лы. Количество разрядов - 4. Следовательно, для генерации всех комбинаций понадобится 4 цикла, вложенных один в другой (рис. 5.18, а). Если ввести параметр m - максимальное значение в каждом разряде, то эта же програм­ ма будет генерировать комбинации от 1111 до mmmm.

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

Ва р и а н т 2. С точки зрения увеличения универсальности программы для генерации всех комбинаций лучше использовать программно реализуе­ мый счетчик в общем случае на п разрядов, который в каждом разряде счи­ тает от 1 до т . Каждое состояние такого счетчика соответствует комбинации. Для генерации следующего варианта в младший разряд счетчика добавляют 1 и осуществляют межразрядные переносы в соответствии с характеристика­ ми каждого разряда (рис. 5.18, б). Ниже представлена программа, реализую­ щая данный алгоритм для п < 10.

180