Как сделать фрактал в паскале

Обновлено: 03.07.2024

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

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

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

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

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

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

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

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

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

нарисовать прямолинейный отрезок заданной длины;
повернуть на +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 ветвей.

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

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

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

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

Методы исследования : сравнительный анализ, синтез, моделирование.

фрактал фрактальная геометрия программирование

Цель: исследовать фракталы в природе и математике и составить программы моделирования фракталов.

узнать, что такое фракталы;

изучить историю возникновения и развития фрактальной геометрии;

ознакомиться с биографией создателя фракталов - Бенуа Мандельброта;

смоделировать фракталы на языке программирования Pasca l АВС и в графическом редактор GIMP .

Актуальность : Интерес к проблеме обусловлен интересом к компьютерной графики

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

Первый раз, услышав о фракталах, задаёшься вопросом, что это такое?

Это понятие завораживает своей красотой и таинственностью, проявляясь в самых неожиданных областях: метеорологии, философии, географии, биологии, механике и даже истории

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

2. Виды компьютерной графики

Понятие компьютерной графики не ограничивается такими ее видами как, растровая и векторная.

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

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

Векторная графика. Векторные графические изображения являются оптимальным средством хранения высокоточных графических объектов (чертежи, схемы и пр.), для которых имеет значение сохранение четких и ясных контуров. С векторной графикой мы сталкиваемся, когда работаем с системами компьютерного черчения и автоматизированного проектирования (САПР), программами обработки трехмерной графики и др.

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

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

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

Фрактальная графика, как векторная, является вычисляемой. Но, в отличие от векторной графики, основное внимание уделяется не заданию изображения в виде совокупности простых геометрических фигур (прямых, многоугольников, окружностей, многогранников и пр.), а описанию алгоритма построения изображения – фрактальное изображение строится по уравнению или системе уравнений, и никакие объекты в памяти компьютера не хранятся.

3. Графический режим Паскаль АВС

Для работы в графическом режиме необходимо подключение модуля uses GraphABC.

Графический режим Графический экран PasсalABC (по умолчанию) содержит 640 точек по горизонтали и 400 точек по вертикали.

1. Управление экраном SetWindowWidth(w) -устанавливает ширину графического окна;

SetWindowHeight(h) -устанавливает высоту графического окна;

2. Точка SetPixel(x,y,color) – закрашивает один пиксел с координатами (x,y) цветом color

3. Линии Line(x1,y1,x2,y2) - рисует отрезок с началом в точке (x1,y1) и концом в точке (x2,y2).

Запуск кода:
Для того чтобы запустить код нужно открыть приложение PascalABC.NET. Далее нужно скопировать код в рабочую зону и нажать на кнопку "Выполнить". После чего произойдет компиляция кода и с помощью модуля GraphABC появится окно в котором уже и будет построен фрактал.

Метод наименьших квадратов

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

Кривая Дракона

Работа с кодом :
Чтобы запустить наш код нам понадобится открыть приложение PascalABC.NET. Мы должны скопировать код и нажать на кнопку "Выполнить". После чего произойдет компиляция кода и помощью модуля GraphABC появится окно в котором уже и будет построен фрактал.

Дерево Пифагора

Кривая Минского

Отсечение отрезка

В программе используется алгоритм Алгоритм Сазерленда-Коэна отсечения отрезка.

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

Алгоритм Брезенхема для генерации эллипса

Задача : построить (растеризовать) эллипс, зная координаты его центра и длины меньшей и большей полуосей a и b соответственно.
Суть алгоритма : использование модифицированного алгоритма Брезенхема для построение окружности . Как и в оригинальном алгоритме Брезенхема, выбор ближайшей точки основан на анализе знаков управляющих
В поля "X" и "Y" вводятся координаты центра окружности, в поля "a" и "b" — длины соответствующих полуосей.

Алгоритм заполнения окружностей

Задача: зарисовать (заполнить) окружность, зная координаты её центра и радиус.
Суть алгоритма: используя свойства вписанной в квадрата окружности, можно утверждать, что все точки окружности и круга, ограниченного этой окружностью, лежат в квадрате,описанном вокруг данной окружности. Перебирая все точки двойным циклом (по OX и OY) и проверяя их удовлетворение неравенству (X-текущийX) 2 +(Y-текущийY) 2 ≤Радиус 2 строится сама окружность и эта же окружность заполняется

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

Мандельброт предложил следующее определение фрактала:

Фрактал – это структура, состоящая из частей, которые в каком-то смысле подобны целому.

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

Выяснилось, что дробную размерность имеют многие ранее изучавшиеся в математике объекты – канторово множество, кривая Вейерштрасса, кривая Кох и т.д. Дробная размерность множества выражается не целым числом, а дробью: одна целая и четыре десятых, две целых и шесть десятых и т.п. Как такое возможно? Математика исходит из постулата о бесконечной делимости всего. Математическая точка не имеет размеров, тем не менее, бесконечно много бесконечно малых точек в пределе образуют вполне конечные тела. Так выяснилось, что созданное по определенному рецепту тело – это что-то среднее между не имеющей толщины и площади линией и имеющим площадь куском плоскости, или же между не имеющей толщины и объема плоской фигурой и имеющим объем пространственным телом. В этих объектах стерта грань между измерениями. Это одно из поразительных свойств фракталов.

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

Запустите программу paporot . pas .

Этот рисунок получен по строго математическому правилу "почкования".

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

Рассмотрим теперь комплексную плоскость. Напомним, что комплексное число состоит из реальной и мнимой частей. Мнимая часть содержит квадратный корень из - 1: i = Ö- 1. Разработаны правила действий с комплексными числами, основанные на том, что i 2 = - 1. Комплексные числа имеют значение во многих областях науки, являются основным аппаратом для расчетов в электротехнике и связи. Если на плоскости по горизонтальной оси откладывать реальные числа, а по вертикальной мнимые, то каждому комплексному числу будет соответствовать точка на этой плоскости. В нашем случае каждому элементу последовательности также будет соответствовать точка комплексной плоскости. В зависимости от начального числа могут быть три варианта: число быстро растет и уходит из поля зрения; число быстро уменьшается и исчезает; числа группируются внутри некоторой области, а при отображении их на плоскости появляются невероятные, поразительные изображения. Это группирование возводимых в квадрат комплексных чисел впервые подметил и описал Жюлиа в 1916 г. И это так называемое множество Жюлиа послужило отправной точкой для Бенуа Мандельброта, а некую сложную фигуру, которая получилась на комплексной плоскости в результате описанных действий, назвали множеством Мандельброта.

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

2. Классификация фракталов.

2.1 Геометрические фракталы

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

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

2.2 Алгебраические фракталы

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

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

Множество Мандельброта относится к алгебраическим фракталам.

2.3 Стохастические фракталы

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

Существуют и другие классификации фракталов, например деление фракталов на детерминированные (алгебраические и геометрические) и недетерминированные (стохастические).

3. Примеры.

Рассмотрим примеры программ, написанных на языке Паскаль. Каждая программа строит фрактальный объект. При этом, программа tree . pas использует аффинные преобразования, позволяющие переносить, поворачивать и изменять масштаб участков изображения, которые служат компоновочными блоками остальной части картинки. Программы fractal * .pas используют действия над комплексными числами.

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

Алгоритм:
1. Создаём структуру , которая будет содержать координаты центров квадратов (Spoint).
2. По таймеру вызывается процедура Draw.
3. В процедуре Draw происходит рисование квадратов,центр которых - это точки, параметр draw которых равен true.
4. Увеличиваем счётчик num отвечающий за количество квадратов, которые будут построены на следующем шаге. num изменяется по степеням четвёрки.
5. В цикле “while k меньше num” добавляются вершины построеных квадратов в массив точек.При этом если вершины принадлежат квадратам,которые не были нарисованы, то добавляемая точка будет иметь в параметре draw значение false.
Рассмотрим значение flag.Оно изменяется от 1 до 4. Если flag=1, тогда центр построенного при данном вызове процедуры Draw квадрата - это левая верхняя вершина квадрата построенного при предыдущем вызове процедуры Draw, если flag=2 - правая верхняя, flag=3 - правая нижняя, flag=4 - левая нижняя.
6. При добавлении в массив точки, которая является ЛЕВОЙ ВЕРХНЕЙ вершиной квадрата, проверяем , построенли этот квадрат "вокруг" ПРАВОЙ НИЖНЕЙ вершины квадрата, строившегося на предыдущем шаге процедуры Draw.Если да (т.е. flag=3), то парметр draw у добавляемой точки принимает занчение false.
7. При добавлении в массив точки, которая является ПРАВОЙ ВЕРХНЕЙ вершиной квадрата, проверяем , построенли этот квадрат "вокруг" ЛЕВОЙ НИЖНЕЙ вершины квадрата, строившегося на предыдущем шаге процедуры Draw.Если да (т.е. flag=4), то парметр draw у добавляемой точки принимает занчение false.
8. При добавлении в массив точки, которая является ПРАВОЙ НИЖНЕЙ вершиной квадрата, проверяем , построенли этот квадрат "вокруг" ЛЕВОЙ ВЕРХНЕЙ вершины квадрата, строившегося на предыдущем шаге процедуры Draw.Если да (т.е. flag=1), то парметр draw у добавляемой точки принимает занчение false.
9. При добавлении в массив точки, которая является ЛЕВОЙ НИЖНЕЙ вершиной квадрата, проверяем , построенли этот квадрат "вокруг" ПРАВОЙ ВЕРХНЕЙ вершины квадрата, строившегося на предыдущем шаге процедуры Draw.Если да (т.е. flag=2), то парметр draw у добавляемой точки принимает занчение false.

Читайте также: