Рейтинг@Mail.ru

Изучение темы "Рекурсивные графические алгоритмы"

Разделы: Информатика


У попа была собака, он ее любил.
Она съела кусок мяса, он ее убил.
Камнем придавил, и на камне написал:
“У попа была собака...””

Детская считалка

Понятие рекурсии. Виды рекурсии.

Рекурсией называется ситуации, когда процедура или функция обращается к себе самой прямо или косвенно. Соответственно говорят о прямой ли косвенной рекурсии. При прямой рекурсии процедура содержит вызов себя в собственном теле, например:

ЭТО процедура 1

….

ЕСЛИ … ТО процедура 1

….

КОНЕЦ

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

ЭТО процедура_1

….

… процедура_2

….

КОНЕЦ

ЭТО процедура_2

….

… процедура_3

….

КОНЕЦ

ЭТО процедура_3

….

… процедура_1

КОНЕЦ

В данном примере “процедура_1” является рекурсивной, так как вызывает сама себя. Правда этот вызов не прямой, а косвенный, через обращение к процедурам “процедура_2” и “процедура_3”. Понятно, что каждая из процедур рекурсивной цепочки является рекурсивной.

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

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

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

Приведем примеры рекурсивных определений.

Пример 1. Классический пример, без которого не обходятся ни в одном рассказе о рекурсии, - определение факториала. С одной стороны, факториал определяется так:

n! = 1*2*3*…*n.

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

Граничным условием в данном примере является n < 1.

Пример 2. Определим функцию K(n), которая возвращает количество цифр в заданном натуральном числе n.

 

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

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

Реализуем приведенные выше рекурсивные определения в виде функций и процедур на языке Pascal.

Пример 1.

Пример программы с функцией

uses crt;

var f: longint: n: integer;

function factorial(n: integer):longint;

begin

if (n=0) or (n=1)

then factorial:=1

else factorial:= factorial(n-1)*n;

end;

begin

clrscr;

write(‘n=’); readln(n);

f:=factorial(n);

writeln (n,’! = ‘, f);

readln;

end.

Пример программы с процедурой

uses crt;

var f: longint: n: integer;

procedure factorial(n: integer; var f: longint);

begin

if (n=0) or (n=1)

then f:=1

else factorial (n-1, f);

f:=f*n;

end;

begin

clrscr;

write(‘n=’); readln(n);

factorial (n, f);

writeln (n,’! = ‘, f);

readln;

end.

Пример 2.

Функция

function K(n: longint):byte;

begin

if n<10

then K:=1

else K:=K(n div 10) +1;

end;

Процедура

procedure K(n: longint; var s: byte);

begin

if n<10 then s:=1

else K( n div 10, s);

s:=s+1;

end;

В приведенных выше примерах программ действия выполняются на рекурсивном подъеме (прямая рекурсия).

А теперь рассмотрим рекурсивные графические алгоритмы, проведем анализ их сложности и эффективности.

Пример 3. Напишите программу построения изображения, представленного на рис.1.

Анализ изображения:

Самостоятельная работа №1.

Задание 1. По аналогии прим. 2 определите функцию S(n), вычисляющую сумму цифр заданного натурального числа.

Задание 2. Реализуйте в виде процедуры и функции рекурсивное определение примера задания №1.

Задание 3. Напишите программу построения изображения, представленного на рис. 2 и 3.

Фрактальные кривые.

Понятие фрактала. Многие объекты окружающего мира обладают свойством “самоподобия”. Так, строение Вселенной от метагалактики до атома описывается сходными моделями типа “ядро – спутники”; строение гористой поверхности или изрезанность морского берега выглядят примерно одинаково и с космической высоты, и с высоты птичьего полета, и с уровня человеческого роста. Все отличие лишь в разрешающей способности восприятия изображения. Вообразим съемку береговой линии кинокамерой с трансфокатором, имеющим регулируемое, но конечное угловое разрешение. При “наезде” камеры на объект взору открываются неразличимые ранее фрагменты, сходные по структуре с фрагментами предыдущего уровня. Такой процесс укрупнения масштаба изображения принципиально отличается от увеличения фотографии по е негативу или от растяжения выделенного фрагмента растровой картинки, при которых увеличивается зернистость без появления новых более мелких фрагментов.

Математическое описание бесконечно дробимых объектов уравнениями линий или поверхностей чрезвычайно громоздко из-за необъятного количества мельчайших объектов. Для преодоления этой трудности математиком Исследовательского центра корпорации IBM Бенуа Мандельбротом в 1975 году был введен термин “фрактал” (от латинского fractus – раздробленный, разбитый, состоящий из фрагментов), а в 1982 году опубликована основополагающая книга “Фрактальная геометрия природы”, где описаны фрактальные множества, их свойства, методы получения и изображения.

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

Ниже рассмотрим некоторые из этих фрактальных множеств.

Итак, займемся построением геометрических узоров. Программы, описываемые здесь, основаны на идеях “черепашьей графики”. “Черепаха” - это вектор с началом в текущем указателе, показывающий направление очередного перемещения из текущей точки и оставляющий при перемещении позади себя след. Что можно делать с “черепахой”? Ее можно поворачивать на заданный угол и перемещать на заданное расстояние.

Пример 4. Начнем с рекурсивной программы рисования кривой Коха.

Процесс формирования кривой Коха состоит в следующем – отрезок разбивается на три равные части, и на средней части отрезка строится, например, квадрат (см. рис. 4) или равносторонний треугольник. Для простоты рассмотрим кривую Коха с квадратом. На рис. 4 изображены кривые Коха первого и второго порядка. Для рисования кривой Коха используются только повороты на +90° и -90° и смещения вдоль прямолинейных отрезков. Алгоритм рисования кривой Коха можно записать следующим образом:

  • нарисовать прямолинейный отрезок заданной длины;
  • повернуть на +90°;
  • нарисовать прямолинейный отрезок заданной длины;
  • повернуть на -90°;
  • нарисовать прямолинейный отрезок заданной длины;
  • повернуть на -90°;
  • нарисовать прямолинейный отрезок заданной длины.

Затем эта последовательность вновь применяется к каждому прямолинейному участку построенной ломаной линии. Интересной особенностью фрактальных объектов является повторение особенностей их структуры при переходе к любому масштабу.

Программу, реализующую кривую Коха см. в файле Primer_4. pas.

Прямолинейные отрезки, начинающиеся из текущей точки и оканчивающиеся в точке с заданными координатами, в программе рисуются процедурой Linerel модуля Graf. Процедура draw (x,y: integer; dlina:word) является рекурсивной, она строит кривую Коха. Параметрами этой процедуры являются x и y (эти два числа задают единичный вектор в направлении очередного смещения) и величина смещения dlina.

Пример 5. “Множество Кантора”. На первый взгляд, кажется, что “множество Кантора” (см. рис. 5) состоит из большого квадрата и квадратов, нарисованных с помощью множества операторов Line.

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

Алгоритм рисования “множества Кантора”:

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

Программу, реализующую множество Кантора см. в файле primer_5. pas.

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

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

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

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

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

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

На рис. 6 представлено изображение, состоящее из трех уровней, а данная программа позволяет рисовать изображение в зависимости от введённого пользователем n уровней.

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

Самостоятельная работа №2.

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

Задание 4. а) Разработайте программу построения изображения “Спираль”, представленного на рис. 7.

Примечание.

В изображении можно заметить ряд закономерностей:

  • построение начинается из “середины” рисунка;
  • каждый следующий отрезок увеличивается на определённую величину;
  • все отрезки либо вертикальные, либо горизонтальные;
  • при рисовании происходит последовательное построение сходных элементов с изменяющимися параметрами следовательно, данный рисунок можно построить с использованием рекурсии, вместо отрезков в программе строятся векторы.

б*) разработайте программу, в которой, кроме стороны, задан еще и угол витков спирали, при увеличении угла можно получить довольно интересные изображения (см. файл Приложение_1.doc).

Решение олимпиадных задач

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

При изучении этого материала можно пойти двумя путями: 1) внимательно изучить предложенный ниже материал, а затем, посмотрев программы для демонстрации, выполнить задания самостоятельной работы №3; 2) попытаться самим придумать и реализовать в Паскале алгоритмы предложенных заданий.

Пример 7.Снежинка”. Разработайте программу, которая обеспечивает рисование снежинки (рис. 8), количество звеньев и ветвей, коэффициент уменьшения каждого звена ветви задаются пользователем.

На рисунке изображена снежинка, состоящая из 3 звеньев и 6 ветвей.

Алгоритм работы над задачей:

  • Определим, какие данные нужны для рисования снежинки и введем обозначения: n – количество звеньев снежинки, p – количество ветвей снежинки, l – длину (в точках) ветви внутреннего звена, t - коэффициент уменьшения каждого звена.
  • Центр снежинки расположим в центре экрана монитора (320, 240).
  • Начинаем рисовать из центра снежинки: рисуем первый (длины l) отрезок, далее, если это не последнее звено, то рисуем отрезок длины l*t следующего звена, и так до тех пор, пока не нарисуем отрезок последнего звена (l*tn-1).
  • На последнем звене дорисовываем самую маленькую снежинку.
  • Возвращаемся на предпоследний отрезок и дорисовываем самое маленькое звено со снежинкой.
  • И так продолжаем до тех пор, пока не нарисуем всю снежинку. Эта логика рисования легко реализуется с помощь рекурсии.

Программу, реализующую “Снежинку” см. в файле primer_7.pas. В данной программе предложено два уровня работы: Demo – выводит на экран монитора снежинку с уже заданными параметрами; во втором варианте необходимо сначала ввести параметры (при работе с данной программой обратите внимание на ограничения, накладываемые на ввод данных).

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

Алгоритм работы над задачей:

  • Введем обозначения: n – количество звеньев ветки, длина первоначального (вертикального) отрезка ветки (в точках) - dl, коэффициент уменьшения каждого звена - t .
  • Начинаем рисовать с первоначального (вертикального) отрезка, далее, если это не последнее звено, просчитывается длина следующего отрезка и строится этот отрезок; так продолжается до тех пор, пока не прорисуются все n звеньев (см. рис. 10 – красная часть рисунка).
  • Далее аналогично рисованию снежинки – прорисовывается левая часть ветви, а затем правая.

Программу, реализующую “Ветку” см. в файле primer_8.pas.

При работе с данной программой обратите внимание на ограничения, накладываемые на ввод данных: n - количество звеньев (>1); dl - длина первоначального отрезка в точках, брать 10 точек …(начните со 100); 0<m<1.

Самостоятельная работа №3

Задание 5. Разработайте программы построения изображений, представленных на рис. 10 и 11 с использованием рекурсии и без нее. Укажите достоинства и недостатки каждой из программ.

Важно:

1) При выполнении программ на своем компьютере обратите внимание на строку программы, где происходит инициализация графики. Возможно, папка BGI у Вас находится в другом месте.

2) Некоторые “правила предосторожности” при работе с рекурсивными функциями и процедурами:

  • Рекомендуется компилировать программу с директивой {$S+}. Эта директива включает проверку переполнения стека. Если в процессе выполнения программы происходит переполнение стека, вызов процедуры или функции, откомпилированной с опцией {$S+}, приводит к завершению работы программы, а на дисплей выдается сообщение об ошибке.
  • Полезно также использовать директиву {$R+}, включающую проверку диапазона переменных.
  • В начале каждой процедуры (функции), вызываемой рекурсивно, можно поместить строку if keypressed then halt. В этом случае при зависании программы вместо перезагрузки будет достаточно нажать любую клавишу.

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

Итоги:

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

Приложение 1

Приложение 2