Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ВВЕДЕНИЕ 3
1. РЕКУРСИВНЫЕ АЛГОРИТМЫ 3
1.1. Рекурсивные определения 3
1.2. Рекурсивные подпрограммы 5
Что выполняется 6
1.3. Косвенная рекурсия и опережающее описание 8
1.4. Рекурсивные структуры 9
1.4.1. Список 9
1.5. Примеры решения задач с помощью рекурсии 12
1.5.5. Числа Фибоначчи 18
Система программирования Турбо Паскаль представляет собой единство двух в известной степени самостоятельных начал: компилятора с языка программирования Паскаль (язык назван в честь выдающегося французского математика и философа Блеза Паскаля (1623-1662)) и некоторой инструментальной программной оболочки, способствующей повышению эффективности создания программ.
Паскаль – замечательный язык программирования, который относительно прост в изучении, довольно ясен и логичен и, будучи первым изучаемым языком программирования, приучает к хорошему стилю. Паскаль воспитывает дисциплину структурного программирования и программирования вообще лучше, чем другие языки программирования, такие, как, например, БЕЙСИК.
Паскаль – гибкий и развитый в отношении типов данных язык. Привлекательны его рекурсивные возможности, а также поддержка технологии объектно-ориентированного программирования.
Изучение программирования на языке Паскаль может дать хороший старт в огромный и увлекательный мир программирования. Обучение языку программирования проходит намного более эффективно с изучением примеров.
Чаще всего (процедурное) программирование использует итерации, то есть циклы; однако рекурсия – описание объекта или вычисления в терминах самого себя – является более простым математическим понятием, а также мощной, но мало используемой техникой программирования.
Некоторые программисты считают (и не без оснований), что рекурсия – это сердце и душа языка Паскаль. В этой работе мы рассмотрим применение рекурсии в программах на Паскале. Здесь рассматриваются примеры рекурсивных алгоритмов и программирование комбинаторных вычислений.
Ко всему прочему мы научимся представлять данные в памяти ЭВМ и разрабатывать программы в среде Турбо Паскаль.
Часто говорят, что рекурсивные определения – это когда что-то определяется с его же помощью. Фраза эта не совсем точная, а вернее, совсем неточная. Каждое определение задаёт что-то, и этим чем-то являются, как правило, объекты, образующие некоторое множество. Определение называется рекурсивным, если оно задаёт элементы множества с помощью других элементов этого же множества. Объекты, заданные рекурсивным определением, также называются рекурсивными. И наконец, рекурсия – это использование рекурсивных определений.
Пример 1
Значение функции факториал задаются выражением: 0!=1, n=n*(n-1)!. Они образуют множество {1,2,6,…}: 0!=1, 1=1*0!, 2=2*1!, 6=3*2! и т.д. Все его элементы, кроме первого, определяются рекурсивно.
Как видим, функция факториал задаётся рекуррентным соотношением порядка 1 и начальным отрезком 0!=1. Вообще, любое рекуррентное соотношение порядка k вместе с заданием первых k элементов последовательности является примером рекурсивного определения.
Пример 2
Арифметические выражения с константами и знаком операции “+” в полной скобочной записи (ПСЗ) задаются таким определением:
1) константа является выражением в ПСЗ;
2) если Е и F являются выражениями в ПСЗ, то (Е)+(F) также является выражением в ПСЗ.
Такими выражениями являются, например, 1, 2, (1)+(2), ((1)+(2))+(1). Все они, кроме констант 1 и 2, определяются рекурсивно.
Объекты, определённые в примерах 1 и 2, т.е. значения функции факториал и скобочные записи выражений, являются рекурсивными.
В рекурсивном определении не должно быть “заколдованного круга”, когда объект определяется с помощью себя самого или с помощью других, но заданных через него же.
Пример 3
Изменим определение функции факториал на следующее: n!=n*(n-1)! При n>0, 0!=1!. Сначала значение функции от 1 выражается через её же значение от 0, которое, в свою очередь, – через значение от 1. По такому определению так и не узнать, чему же равно 1!.
Пример 4
“У попа была собака, поп её любил, она съела кусок мяса, поп её убил, в землю закопал и на камне написал, что у попа…” и т.д. Эта печальная история не имеет конца, и нельзя сказать, что же именно поп написал на камне.
Пример 5
“Где ты деньги берёшь?” – “В тумбочке”. – “А там они откуда?” – “Жена кладёт”. – “А у неё откуда?” – “Я даю”. – “А где ты берёшь?” – “В тумбочке…”
В этом старом анекдоте не называется настоящий источник хранения денег. Если через А, В, С обозначить мужа, его жену и тумбочку, то перемещение денег изображается так: АßСßВßАß…и настоящий источник денег остаётся неизвестным.
Чтобы подобная “дурная бесконечность” не возникала в рекурсивном определении, должны выполняться следующие условия:
1) множество определяемых объектов является частично упорядоченным;
2) каждая убывающая по этому упорядочению последовательность элементов заканчивается некоторым минимальным элементом;
3) минимальные элементы определяются нерекурсивно;
4) неминимальные элементы определяются с помощью элементов, которые меньше их по этому упорядочению.
Нетрудно прийти к убеждению, что определения из примеров 1 и 2 удовлетворяют этим условиям, а из примеров 3–5 – нет.
Для тех, кому не знакомы термины “частично упорядоченное множество” и “минимальный элемент”, дадим небольшое пояснение.
Любое множество пар, составленных из элементов некоторого множества, называется отношением на этом множестве. Например, множество пар {(1,1), (1,2), (2,1)} – на множестве {1,2}.
Отношение называется отношением частичного порядка, если оно имеет такие свойства:
1. Для каждого элемента a множества в отношении есть пара (a, a).
2. Если в отношении есть пара (a, b) с различными элементами a и b, то пары (b, a) там нет. При этом мы говорим, что а меньше b. Во множестве могут быть и несравнимые элементы, которые друг с другом пары не образуют.
3. Если а меньше b, а b меньше c, то a меньше c. Впрочем, элементов a, b, c таких, что a меньше b, а b меньше с, во множестве может и не быть – при выполнении свойств (1) и (2) отношение будет отношением частичного порядка.
Множество с заданным на нём отношением частичного порядка называется частично упорядоченным. Элемент частично упорядоченного множества называется минимальным, если во множестве нет элементов, меньших его.
Очевидно, что в примере 1 каждые два элемента множества {1, 2, 6,…} сравнимы между собою, а минимальным является 1. В примере 2 один идентификатор меньше другого, если тот образуется из него дописыванием символов в конце. Так, а меньше а1 и ааа, но а1 и аа несравнимы. Идентификатор а – минимальный. В примере 3 одно выражение меньше другого, если оно является его частью. Так, 1 и 2 меньше, чем (1)+(2), а (1)+(2) меньше, чем ((1)+(2))+(1); минимальными элементами являются все возможные константы, между собою несравнимые.
По правилам языка Паскаль, задающим область действия определений, тело подпрограммы может содержать вызовы подпрограмм, заголовки которых записаны выше в тексте программы. Отсюда вытекает, что подпрограмма может содержать вызовы самой себя – рекурсивные вызовы. Выполнение такого вызова ничем не отличается от выполнения вызова любой другой подпрограммы. Подпрограмма с рекурсивными вызовами называется рекурсивной.
Пример 6
Напишем рекурсивную функцию f по такому определению функции факториал: n!=n*(n-1)! при n>1, 1!=1 (считается, что n>0).
function f(n:integer):integer;
begin
if n=1 then f:=1
else f:=n*f(n-1)
end;
При имитации выполнения вызовов рекурсивных подпрограмм их локальные переменные обозначают следующим образом. Если подпрограмма F вызвана из программы, то её локальная переменная Хобозначается F.X. При выполнении каждого рекурсивного вызова подпрограммы F, указанного в её теле, появляется новая переменная Х. Она обозначается добавлением префикса F. к обозначению переменной Х в предыдущем вызове: F.F.X, F.F.F.X и т.п.
Пример 7
Имитацию выполнения вызова f(2) функции из примера 6 можно представить в виде таблицы:
|
Что выполняется |
Состояние памяти |
|
|
Вызов f(2) |
f.n f.f |
|
|
|
2 ? |
|
|
Вычисление n=1: false |
2 ? |
|
|
начало f:=n*f(1) |
2 ? |
|
|
Вызов f(1) |
2 ? |
f.f.n f.f.f |
|
|
2 ? |
1 ? |
|
Вычисление n=1: true |
2 ? |
1 ? |
|
f:=1 |
2 ? |
1 1 |
|
Возвращение из вызова f(1) |
2 ? |
|
|
Окончание f:=n*f(1) |
2 2 |
Пример 8
Наибольший общий делитель НОД(a, b) натуральных чисел a и b можно вычислить рекурсивно на основании таких равенств:
§ если b=0, то НОД(a, b)=a;
§ если а mod b=0, то НОД(a, b)=b;
§ если а mod b>0, то НОД(a, b)= НОД(b, а mod b).
Этому определению соответствует следующая рекурсивная функция вычисления НОД:
function GCD(a, b:integer):integer;
(Greatest Common Divisor – Наибольший Общий Делитель)
begin
if b=0 then GCD:=a else
if a mod b=0 then GCD:=b
else GCD:=GCD(b, a mod b)
end;
С рекурсивными подпрограммами связаны два важных понятия – глубина рекурсии и общее количество вызовов, порожденных вызовом рекурсивной подпрограммы.
Рассмотрим первое из них. В примере 6 приведена функция вычисления n!. Очевидно, что её вызов с аргументом, например 4, заканчивается лишь по окончании вызова с аргументом 3, а тот, в свою очередь, после вызова с аргументом 2 и т.д. Такие вызовы называются вложенными. Таким образом, вызов с аргументом 4 порождает ещё три вложенных вызова. Вообще, при вызове этой функции с аргументом nпорождается ещё n-1 вызов, и общее количество незаконченных вызовов достигает n. Таким образом,глубиной рекурсии вызова подпрограммы называется максимальное количество незаконченных рекурсивных вызовов при выполнении её вызова.
При выполнении вызова с глубиной рекурсии т одновременно существует т экземпляров локальной памяти. Каждый экземпляр имеет определённый размер, и если глубина будет чересчур большой, то автоматической памяти, предоставленной процессу выполнения программы, может не хватить.
Второе понятие можно назвать общим количеством вложенных вызовов, порождённых вызовом рекурсивной подпрограммы. Это количество влияет на время выполнения вызова.
Пример 9
По свойствам треугольника Паскаля, биномиальный коэффициент C(m, n)=1 при т<1 или n=0, или n=m; в противном случае C(m, n)= C(m-1, n-1)+C(m-1, n).
В соответствии с этим равенством напишем рекурсивную функцию вычисления биномиального коэффициентаC(m, n) по m, n, где 0<n<m:
function C(m, n:integer):integer;
begin
if (m<=1) or (n=0) or (n=m) then C:=1
else C:=C(m-1, n-1)+C(m-1, n)
end;
Как видим, каждый вызов, в котором значения аргументов m>1, 0<n<m, порождает два вложенных вызова. В результате происходит повторное вычисление одних и тех же величин. Например, выполнение вызова с аргументом (5,2) ведёт к тому, что вызов с аргументами (3,1) выполняется дважды, вызовы с аргументами (2,1), (1,0) и (1,1) – трижды, а общее количество вложенных вызовов достигает 18.
Нетрудно понять, что чем больше т и чем ближе n к т/2, тем большим будет общее количество вложенных вызовов. Мы не будем точно определять его зависимость от аргументов. Скажем лишь, что при n=m div 2 илиn=m div 2+1 оно больше, чем 2т/2. Например, при т=60 это 230, или примерно 109. Если даже предположить, что за секунду можно выполнить 106 вызовов, то нужно больше 1000 секунд, т.е. более четверти часа. Однако нетрудно написать рекурсивную функцию, вызов которой с аргументом т порождает не более т/2 вложенных вызовов.
Таким образом, употребление рекурсивных подпрограмм требует осторожности и умения оценить возможную глубину рекурсии и общее количество вызовов. Не всегда стоит писать рекурсивные подпрограммы непосредственно по рекурсивному определению. По крайней мере, для вычисления биномиальных коэффициентов вообще лучше воспользоваться циклом. Дело в том, что выполнение каждого вызова подпрограммы требует дополнительных действий компьютера. Поэтому циклический вариант описания вычислений выполняется, как правило, быстрее рекурсивного. Также не следует употреблять рекурсию для вычисления элементов рекуррентных последовательностей. При большой глубине рекурсии это вообще может привести к исчерпанию автоматической памяти и аварийному завершению программы.
Рекурсивный вызов может быть косвенным. В этом случае подпрограмма обращается сама к себе опосредованно, путём вызова другой подпрограммы, в которой обращение к первой, например:
Procedure A(i: Byte);
Begin
...
B(i);
...
end;
procedure B(j: Byte);
...
begin
...
A(j);
...
end;
Если строго следовать правилу, согласно которому каждый идентификатор перед употреблением должен быть описан, то такую программную конструкцию использовать нельзя. Для того, чтобы такого рода вызовы стали возможны, вводится опережающее описание:
Procedure B(j: Byte); forward;
Procedure A(i: Byte);
Begin
...
B(i);
...
end;
procedure B;
begin
...
A(j);
...
end;
Как видим, опережающее описание заключается в том, что объявляется лишь заголовок процедуры В, а её тело заменяется стандартной директивой FORWARD. Теперь в процедуре А можно использовать обращение к процедуре В – ведь она уже описана, точнее, известны её формальные параметры, и компилятор может правильным образом организовать её вызов. Обратим внимание: тело процедуры В начинается заголовком, в котором уже не указываются описанные ранее формальные параметры.
Список относится к особой группе структур - это так называемые рекурсивные структуры.
Приведем рекурсивное определение списка: Списком называется совокупность связанных элементов, из которых один является особым элементом (первым, "головой"), а все остальные образуют список. Рекурсивные структуры в программировании замечательны тем, что многие операции по их обработке можно эффективно реализовать с использованием рекурсивных процедур, которые отличаются большой лаконичностью и наглядностью. В качестве примера приведём процедуру проверки, является ли Н1 подсписком списка Н:
TYPE Указатель = POINTER TO Элемент;
Элемент = RECORD
INFO : Инфоpмация;
LINK : Указатель;
END
PROCEDURE Проверка (Н,Н1 : Указатель) : BOOLEAN;
BEGIN
IF H # NIL THEN
RETURN (Н = Н1) OR Проверка (Н^.LINK, Н1)
ELSE RETURN (Н = Н1)
END
END Проверка.
Проверка (H # NIL) в этом примере нужна только для того, чтобы предотвратить попытку интерпретировать пустую ссылку как элемент списка при вызове Проверка (H^.LINK, H1). Ситуация (H=H1=NIL) рассматривается как положительный результат проверки.
1.4.2. Набор
Другим примером рекурсивной структуры является структура набора, которая определяется следующим образом: Набором называется совокупность связанных элементов, каждый из которых может быть либо атомом, либо набором. Атом определяет "неделимый" элемент набора, предназначенный для хранения элементарной порции информации. Реализация наборов основана на использовании разнородных списков. Например, ниже приведена (см. рис. 1) одна из возможных структур наборов. В этой структуре H1 - набор из четырех элементов (a, b, H2, c), из них H2 - набор, остальные - атомы. H2 состоит в свою очередь из тpех элементов - атома c и двух наборов H3 и H4, причем набор H3 - пуст (не содержит элементов), а H4 содержит два атома (d и f).
Элементы H2, H3, H4 определяют "головы" новых наборов и одновременно являются членами наборов "верхнего уровня" - при этом структура набора оказывается адекватной для реализации динамических "вложенных" понятий предметной области. Например, в ассоциацию H1-"Акционеры" могут входить как отдельные частные лица, так и коллективы - организации, которые являются ассоциациями собственных акционеров.
Элементы H2, H3, H4 на приведенной иллюстрации участвуют в двух связях - горизонтальной (связь между членами одного набора) и вертикальной (связь с членами "своего собственного" набора). Эта терминология часто используется для организации так называемых ортогональных списков, моделирующих структуры динамически изменяющегося плоского "игрового поля": "разреженных" матриц, "кроссвордов", цепей "домино" и т.д. Понятие "игрового поля", разумеется, не означает, что ортогональные списки используются лишь в игровых задачах.
1.4.3. Дерево
Еще один пример рекурсивной структуры, широко использующейся в программировании - структура дерева. Деревом называется совокупность связанных элементов - вершин дерева, включающая в себя один особый элемент - корень, при этом все остальные элементы образуют поддеревья. Наиболее широко используется структура бинарного дерева, все множество вершин которого делится (по отношению к корню) на два подмножества - два поддерева (левое и правое). Любая вершина бинарного дерева реализуется на связанной памяти элементом с двумя связями: с левым поддеревом и с правым.
На этой иллюстрации изображена структура бинарного дерева на связанной памяти, здесь К – корень; Л1,Л2,Л3 – "листья" – вершины с "пустыми" связями ("не выросшими" поддеревьями).
Заметим, что в этой интерпретации дерево реализуется на однородных списках (в отличие от набора). Особое положение корня определяется единственным свойством – отсутствием вершин-предков, любой лист дерева характеризуется полным отсутствием вершин-потомков. Поскольку любая вершина в связанной структуре дерева открывает доступ только "вниз" (только к своим поддеревьям), она может интерпретироваться как корень соответствующего поддерева. В этом смысле лист является корнем "не выросшего" дерева и определяет его своеобразную "точку роста". Включение в дерево новой вершины и удаление старой не должно нарушать общего отношения порядка на множестве вершин.
Примером такого отношения может служить отношение "больше- меньше", определяющее структуру бинарного дихотомического дерева. В таком дереве все вершины любого правого поддерева имеют значение информационного поля большее, чем значение такого же поля у корня, а веpшины соответствующего левого поддерева – меньшее. Например, конструирование дихотомического дерева по последовательности целых чисел 30, 70, 80, 21, 25, 17, 4, начиная с 30, должно приводить к созданию следующей структуры:
Нетрудно заметить, что процесс конструирования такого дерева происходит сверху вниз, начиная с корня, путем последовательного сравнения числовых значений, размещаемых в вершинах, с целью определения места размещения соответствующей вершины в структуре дерева. Любая модификация дихотомического дерева (удаление вершины, вставка новой веpшины) не должна нарушать дихотомической структуры в целом.
В общем случае трансформация произвольной информационной строки (последовательности объектов) в структуру дерева и обратно основана на использовании глубоких структурных межобъектных отношений в исходной строке. Такая трансформация позволяет наглядно представить подобные отношения в форме дерева. В программировании дерево во многом рассматривается как формальная структура, наполняемая различным семантическим содержанием. Такой подход позволяет формально реализовать многие преобразования данных на основе унифицированных процедур обхода деревьев.
Например, в теории трансляции широко используется понятие Польской инверсной записи (ПОЛИЗ) – особой системы представления математических выражений символьными последовательностями. Так, например, выражение " a + b * c " будет представлено в ПОЛИЗЕ строкой " a b c * + ". Если представить исходное выражение в естественной иерархической форме бинарного дерева :
то его восходящий обход (пунктир на рис. 4) приведет к строке " a b c * + ", определяющей "польский" эквивалент исходной строки. Формула восходящего обхода "Левый–Правый–Корень" (ЛПК) определяет правило обхода бинарного дерева: восходящий обход связан с обходом его левого поддерева, затем правого поддерева, затем корня. Поскольку каждая вершина дерева может интерпретироваться как корень "вырастающего из нее" поддерева, это правило применяется рекурсивно к каждой вершине обходимого дерева. Правило ЛКП (Левый–Корень–Правый) определяет так называемый смешанный обход, правило КЛП – нисходящий обход и т.д. Нетрудно заметить, что смешанный обход дерева дихотомии по правилу ЛКП приведет к формированию строки чисел (хранящихся в вершинах этого дерева), упорядоченной по возрастанию, а такой же обход по правилу ПКЛ – к формированию строки, упорядоченной по убыванию соответствующих чисел. Таким образом, между структурой дерева, отношением порядка на множестве информационных компонент его вершин и видом обхода существует глубокая связь, определяемая рекурсивной природой структуры дерева. Рекурсивные процедуры обхода бинарных деревьев пишутся прямо по формуле обхода с учетом спецификации представления вершин дерева. Например, ниже приведена процедура смешанного обхода бинарного дерева дихотомии, реализующего формулу ЛКП.
TYPE Вершина = POINTER TO Элемент ;
Элемент = RECORD
Info : CARDINAL ;
LLink,RLink : Вершина
END ;
PROCEDURE Смеш_Обход (K : Вершина);
BEGIN
IF K # NIL THEN
Смеш_Обход (K^.LLink); (* Обход левого поддерева *)
WriteCard (K^.Info); (* Обработка корня *)
Смеш_Обход (K^.RLink); (* Обход правого поддерева *)
END
END Смеш_Обход.
В традиционном программировании рекурсия часто рассматривается как некоторый заменитель итерации. Причем в качестве примеров рассматривается вычисление рекуррентных последовательностей, которые могут быть легко сформированы и обычными итераторами (циклами WHILE, REPEAT и т.п.). Природа рекурсии значительно глубже, чем механизм итерации, поэтому ее использование практически не имеет альтернатив в виде итераторов только тогда, когда решение задач проводится на рекурсивных структурах. Попробуйте написать процедуру Смеш-Обход без использования рекурсии, только на основе циклов и, если Вам это удастся, сравните ее с приведенным выше вариантом рекурсивной процедуры по наглядности, лаконичности, выразительности.
При написании рекурсивных программ, следует помнить, что при рекурсивном вызове процедурой самой себя или другой процедуры следует соблюдать определённые “правила предосторожности”. Рекомендуется компилировать программу с директивой {$S+}. Эта директива включает проверку переполнения стека (области памяти, в которой хранится состояние вызывающей подпрограммы). Если в процессе выполнения программы происходит переполнение стека, вызов процедуры или функции, откомпилированной с опцией {$S+}, приводит к завершению работы программы, а на дисплей выдаётся сообщение об ошибке. Полезно также использовать директиву {$R+}, включающую проверку диапазона переменных. В начале каждой процедуры (функции), вызываемой рекурсивно, можно разместить строку if keypressed then Halt. В этом случае при зависании программы вместо перезагрузки будет достаточно нажать любую клавишу.
Количество рекурсивных вызовов называется глубиной рекурсии. Глубина рекурсии должна быть конечной. Позаботиться об этом должен программист, выбирающий или разрабатывающий рекурсивный алгоритм.
Рассмотрим пример. Правила головоломки “Ханойская башня” таковы. Имеется доска с тремя колышками. На первом из них нанизано несколько дисков убывающего диаметра (самый большой находится внизу – рис. 5).
Требуется расположить диски в том же порядке на третьем колышке, причём диски разрешается перекладывать только по одному, а класть большой диск на меньший нельзя. Один колышек используется в качестве вспомогательного. Ответим на вопрос – сколько перемещений дисков следует выполнить?
Алгоритм решения головоломки следующий:
1. Переместить верхние n-1 дисков на второй колышек.
2. Нижний диск с первого колышка переместить на третий.
3. Переместить n-1 дисков на третий колышек, используя первый в качестве вспомогательного.
4. Повторять, пока на третьем колышке не будет сформирована новая пирамида.
Исходная задача сводится, таким образом, к двум задачам о переносе n-1 диска и одной задаче о переносе одного диска. Для n-1 требуется одно перемещение. Исходный текст программы для вычисления количества ходов приведён ниже (Листинг 1). Количество ходов здесь может быть вычислено как с применением рекурсии (функция hanoi1), так и без неё (функция hanoi2). В первом случае исходный текст функции короче.
Листинг 1. Программа “Ханойская башня”
{$S+}
program hanoi_moves;
function hanoi1(n: Word): LongInt;
begin
if n=1 then hanoi1:=1
else hanoi1:=2*hanoi1(n-1)+1;
end;
function hanoi2(n: Word): LongInt;
var j: LongInt; k: Word;
begin
if n=1 then hanoi2:=1
else
begin
j:=1;
for k:=2 to n do j:=2*j+1;
hanoi2:=j;
end;
end;
writeln(hanoi1(20));
writeln(hanoi2(20));
end.
1.5.2. Двумерное множество Кантора
Ещё один пример использования рекурсии приводится в программе Cantor (Листинг 2), которая строит двумерное множество Кантора. Множество строится следующим образом. Имеется квадрат, внутренняя часть которого закрашена каким-то цветом. Этот квадрат делится на 16 равных частей (тоже квадратных). Затем удаляются 4 средних квадрата, причём изображения их границ остаются. Далее процедура повторяется для каждого оставшегося квадрата. Алгоритм построения квадратного множества Кантора следующий:
1. Построить квадрат размером L.
2. Вырезать расположенный в центре квадрат размером L/2.
3. Разделить исходный квадрат на четыре равные части размером L/2.
4. Для каждого из четырёх квадратов повторить шаги 2 и 3.
В результате получается самоподобное множество – фрактал. В программе Cantor сохраняется изображение границы вырезанного квадрата, а построение множества идёт не от большего квадрата к меньшим, а наоборот.
Процедура SetWriteMode модуля Graph устанавливает режим вывода линии. Режим задаётся с помощью логической операции. В нашем примере используется операция “исключающее ИЛИ” (ей соответствует константа xorput), поэтому изображение линии комбинируется с изображением, уже выведенным на экран.
Листинг 2. Программа “Двумерное множество Кантора”
{$S+}
program Cantor;
uses Crt, Graph, graphs;
var ch: Char;
const min_size=1;
procedure draw(x,y: integer; size: Word);
var s: Word;
begin
if size>min_size then
begin
s:=size div 2;
draw(x-size, y+size, s);
draw(x-size, y-size, s);
draw(x+size, y+size, s);
draw(x+size, y-size, s);
end;
rectangle(x-size, y-size, x+size, y+size,);
bar(x-size+1, y-size+1, x+size-1, y+size-1);
end;
begin
open_graph;
SetFillStyle(solidfill, black);
SetColor(White);
draw(GetMaxX div 2, GetMaxY div 2, GetMaxY div 4);
OutTextXY(265, 235, ‘Press <Space>’);
ch:=ReadKey;
SetColor(Black);
SetWriteMode(xorput);
draw(getmaxx div 2, getmaxy div 2, getmaxy div 4);
SetColor(White);
OutTextXY(265, 235, ‘Press <Space>’);
ch:=ReadKey;
close_graph;
end.
1.5.3. “Индийский алгоритм” возведения в степень
Этот алгоритм вычисления натуральной n-й (n>1) степени целого числа х выглядит совсем просто:
§ при n=1 xn=x;
§ при n>1 xn= xn mod 2(xn div 2)2.
Основная цель этого алгоритма – сократить количество умножений при возведении в степень. Например, по этому алгоритму х5=х*(х2)2, т.е. достаточно трёх умножений вместо четырёх: х*х*х*х*х. Одно умножение экономится за счёт того, что х2 хранится как промежуточное значение и умножается само на себя. Точно так же х10=1*(х5)2=(х5)2, что требует лишь четырёх умножений (три из них для вычисления х5) вместо девяти “лобовых”. Но здесь придётся хранить сначала х2, а потом х5.
Очевидно, что вычисление хn сводится к вычислению хn div 2, запоминанию результата, возведению в квадрат и умножению его на х при нечётном n. Итак, вычисление xn описывается рекурсивной функцией:
function pow(x,n:integer):integer;
var t:integer;
begin
if odd(n) then t:=x else t:=1;
if n=1 then pow:=x else pow:=t*sqr(pow(x,n div 2))
end;
Как видим, промежуточные сомножители хранятся в локальной памяти процессов выполнения вызовов функции, а именно, в переменных, поставленных в соответствие её имени.
Теперь опишем зависимость глубины рекурсии вызовов функции от значения аргумента. В каждом следующем вложенном вызове значение аргумента n меньше предыдущего значения, по крайней мере, вдвое. Поскольку при n=1 происходит возвращение из вызова, то таких уменьшений значения аргумента n не может быть больше чем log2n. Следовательно, глубина рекурсии вызова с аргументом n не превышает log2n.
Такую глубину можно считать хорошим свойством алгоритма. При каждом выполнении вызова происходит не более одного деления, возведения в квадрат и умножения, поэтому общее количество арифметических операций не больше 3log2n. При больших значениях n это существенно меньше “лобовых” n-1 умножений. Например, при n=1000 это примерно 30.
Отметим, что при некоторых значениях n приведённый алгоритм не даёт наименьшего количества умножений, необходимых для вычисления n-й степени. Например, при n=15 по этому алгоритму необходимо выполнить 6 умножений, хотя можно с помощью 3-х умножений вычислить х5, после чего помножить его на себя дважды (всего 5 умножений). Однако написать алгоритм, который задаёт вычисление произвольной степени с минимальным количеством умножений, – не совсем простая задача.
Построим нерекурсивный аналог приведённого алгоритма. Представим вычисление по рекурсивному алгоритму в таком виде:
х13=(х6)2*х1=((х3)2*х0)2*х1=(((х1)2*х1)2*х0)2*х1
Этому соответствует следующая обработка вычисляемых показателей степеней:
13=6*2+1=(3*2+0)*2+1=((1*2+1)*2+0)*2+1
Как видим, вычислению степеней соответствует вычисление значения 13, представленного полиномом относительно 2. Коэффициентами его являются цифры двоичного разложения числа 13. Нетрудно убедится, что вычислению степени с произвольным показателем n точно так же соответствует вычисление числа n, представленного двоичным разложением. Причём это разложение-полином записано по схеме Горнера. Раскроем в нём скобки:
1*23+1*22+0*21+1*20
Коэффициент при 20, 21, 22 и т.д. – это последовательные остатки от деления на 2 чисел:
n, n div 2, (n div 2) div 2 и т.д.
причём остатку 1 соответствует в рекурсивном алгоритме присваивание t:=x, а 0 – присваивание t:=1. Таким образом, двоичное разложение, например, числа 13 по степеням двойки соответствует такому представлению х13:
х2^3*x2^2*1*x2^0
Итак, достаточно вычислять степени:
x2^0= x, x2^1= x2, x2^2= (x2)2, x2^3= (x2^2)2 и т.д.
и соответствующие им остатки от деления на 2 показателей:
n, n div 2, (n div 2) div 2, ((n div 2) div 2) div 2 и т.д.
накапливая в произведении лишь те степени двойки, которые соответствуют остаткам 1. В следующем алгоритме произведение степеней накапливается в переменной t, а степени двойки – в переменной х:
function pow(x,n:integer):integer;
var t:integer; notfin:boolean;
begin
t:=1; notfin:=true;
while notfin do
begin
if odd(n) then t:=t*x;
n:=n div 2;
if n>0 then x:=x*x else notfin:=false
end;
pow:=t
end.
1.5.4. Вычисление факториала
Программируя формулы из комбинаторной математики, часто приходится использовать рекурсию. В качестве примера применения рекурсии в комбинаторике приведём, рассмотренную ранее, программу вычисления факториала (Листинг 3). Программа вводит с клавиатуры целое число N и выводит на экран значение N!, которое вычисляется с помощью рекурсивной функции FAC. Для выхода из программы необходимо либо ввести достаточно большое целое число, чтобы вызвать переполнение при умножении чисел с плавающей запятой, либо нажать Ctrl-Z и Enter.
При выполнении правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В приведённой ниже программе решение при N=0 тривиально и используется для остановки рекурсии.
Листинг 3. Программа вычисления факториала.
Program Factorial;
{$S+} {Включаем контроль переполнения стека}
var n: Integer;
function Fac (n: Integer): Real;
{Рекурсивная функция, вычисляющая n!}
begin
if n<0 then
writeln (‘Ошибка в задании N’)
else
if n=0 then
Fac:=1
else Fac:=n*Fac(n-1)
end {Fac};
{----------}
begin {main}
repeat
ReadLn(n);
WriteLn(‘n! = ’,Fac(n))
until EOF
end {main}.
Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и даёт более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека (при каждом входе в программу её локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком). Переполнение стека особенно ощутимо сказывается при работе с сопроцессором: если программа использует арифметический сопроцессор, результат любой вещественной функции возвращается через аппаратный стек сопроцессора, рассчитанный всего на 8 уровней. Если, например, попытаться заменить тип REAL функции FAC (см. листинг 3) на EXTENDED, программа перестанет работать уже при N=8. Чтобы избежать переполнения стека сопроцессора, следует размещать промежуточные результаты во вспомогательной переменной. Вот правильный вариант для работы с типом EXTENDED:
Program Factorial;
{$S+,N+,E+} {Включаем контроль стека и работу сопроцессора}
var n: Integer;
function Fac (n: Integer): extended;
var F: extended; {Буферная переменная
для разгрузки стека сопроцессора}
{Рекурсивная функция, вычисляющая n!}
begin {Fac}
if n<0 then
writeln (‘Ошибка в задании N’)
else
if n=0 then
Fac:=1
else
begin
F:=Fac(n-1);
Fac:=F*n
end;
end {Fac};
{----------}
begin {main}
repeat
ReadLn(n);
WriteLn(‘n! = ’,Fac(n))
until EOF
end {main}.
Архитектура стека непосредственно поддерживает рекурсию, поскольку каждый вызов процедуры автоматически размещает новую копию локальных переменных. Например, при каждом рекурсивном вызове функции факториала требуется одно слово памяти для параметра и одно слово памяти для адреса возврата. То, что издержки на рекурсию больше, чем на итерацию, связано с дополнительными командами, затраченными на вход в процедуру и выход из неё. Некоторые компиляторы пытаются выполнить оптимизацию, называемую оптимизацией хвостовой рекурсии (tail-recursion) или оптимизацией последнего вызова (last-call). Если единственный рекурсивный вызов в процедуре – последний оператор процедуры, то можно автоматически перевести рекурсию в итерацию.
С идейной точки зрения рекурсия аналогична методу математической индукции. Базе индукции соответствует база рекурсии. Предположению индукции соответствует предположение о том, что нужная процедура уже написана. Наконец, шагу индукции соответствует вызов создаваемой рекурсивной процедуры. В любой рекурсии необходимо предусмотреть условие завершения процесса, т.е. когда вызова больше не происходит.
Рассмотрим ещё один пример использования рекурсии – вычисление N-ого по счёту числа Фибоначчи. Числа Фибоначчи составляют последовательность, очередной элемент которой вычисляется по двум предыдущим значениям:
Fn=Fn-1 + Fn-2 .
Нулевое и первое значения должны быть заданы, их значения равны единице. Последовательности такого рода применяются, например, в программах генераторах случайных чисел. Вычисление 20-ого числа Фибоначчи реализовано в программе Fibonacci (Листинг 4). Впрочем, номер числа можно изменить, задав в описании константы другое значение.
Листинг 4. Программа вычисления 20-ого числа Фибоначчи.
program Fibonacci;
uses Crt;
const n=20;
function F(n: word): longint;
begin
if keypressed then
halt;
if (n=0) or (n=1) then
F:=1
else F:=F(n-1)+F(n-2); {рекурсивный вызов}
end;
function G(n: word): longint;
var x,y,t: longint; k: word;
begin
x:=1;
y:=1;
for k:=2 to n do
begin
t:=y;
y:=x+y;
x:=t;
end;
G:=y;
end;
begin
clrscr;
textcolor(lightgray +128);
write(‘Считаю...’);
textcolor(lightgray);
writeln(‘—Ждите ответа--’);
writeln;
writeln(‘Рекурсивный алгоритм : F(‘, n, ’)= ’, F(n));
writeln;
writeln(‘Итерационный алгоритм : F(‘, n, ’)= ’, G(n));
gotoxy(1,1);
clreol;
gotoxy(1,7);
write(‘Нажмите <Enter>’);
end.
В этой программе реализованы два метода решения задачи вычисления числа Фибоначчи. Один назовём итерационным методом – он заключается в прямом программировании итерационной формулы для чисел Фибоначчи. В функции G для этого используются три вспомогательные переменные типа LongInt.
Решение с использованием рекурсивных вызовов запрограммировано с помощью функции F. Оператор, вычисляющий её значение, два раза вызывает саму эту функцию. Текст рекурсивной функции короче, лаконичнее итерационной функции. Процедура ClrEol из модуля Crt удаляет все символы строки от текущего положения курсора до её конца.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ:
1. Бен-Ари М. Языки программирования. Практический сравнительный анализ: Пер. с англ. – М.: Мир, 2000. – 366 с., ил.
2. Зуев Е.А. Turbo Pascal. Практическое программирование. – М.: Приор, 1997. – 336с.
3. Кнут Д. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. – М.: Издательский дом "Вильямс", 2000. – 720 с.
4. Немнюгин С.А. Turbo Pascal. – СПб.: Издательство “Питер”, 2000. – 496 с., ил.
5. Немнюгин С.А. Turbo Pascal: практикум – СПб.: Питер, 2001. – 256 с., ил.
6. Рубенкинг Н.Дж. Турбо Паскаль для Windows: в 2-х томах. Т.1. Пер. с англ. - М.: Мир, 1993. – 536 с., ил.
7. Рубенкинг Н.Дж. Турбо Паскаль для Windows: в 2-х томах. Т.2. Пер. с англ. - М.: Мир, 1993. – 536 с., ил.
8. Ставровский А.Б. Турбо Паскаль 7.0. Учебник. – К.: Издательская группа BHV, 2000. – 400 с.
9. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие. Издание 7-е, переработанное. – М.: «Нолидж», 2000. – 576 с., ил.
10. Фаронов В.В. Турбо Паскаль 7.0. Практика программирования. Учебное пособие. Издание 7-е, переработанное. – М.: «Нолидж», 2000, - 416 с., ил.
11. Шелест В.Д. Программирование. – СПб.: БХВ – Петербург, 2001. – 592 с., ил.