Визуализация рекурсивных алгоритмов, построение фракталов

им. Первого Президента России Б. Н. Ельцина»

Факультет информационно-математических технологий и экономического моделирования

Кафедра интеллектуальных информационных технологий

Пояснительная записка

к курсовому проекту

по дисциплине Алгоритмы и анализ сложности

на тему: Визуализация рекурсивных алгоритмов, построение фракталов

Руководитель: Макрушин А.А

Выполнил: студент группы ИМ-37041

Михеева Я. С.

Екатеринбург 2010Постановка задачи

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

Известными рекурсивными подпрограммами являются вычисление факториала, решение задачи о Ханойских башнях, быстрая сортировка К. Хоара, подпрограммы работы с динамическими структурами данных, подпрограммы построения фракталов и многие другие.

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

Введение

Понятия фрактал и фрактальная геометрия, появившиеся в конце 70-х, с середины 80-х прочно вошли в обиход математиков и программистов. Слово фрактал образовано от латинского fractus и в переводе означает состоящий из фрагментов. Оно было предложено Бенуа Мандельбротом в 1975 году для обозначения нерегулярных, но самоподобных структур, которыми он занимался. Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта «The Fractal Geometry of Nature». В его работах использованы научные результаты других ученых, работавших в период 1875-1925 годов в той же области (Пуанкаре, Фату, Жюлиа, Кантор, Хаусдорф). Но только в наше время удалось объединить их работы в единую систему.

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

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

Определение фрактала, данное Мандельбротом, звучит так: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому".

Фракталы делятся на группы. Самые большие группы это: геометрические фракталы, алгебраические фракталы, системы итерируемых функций, стохастические фракталы.

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

Ход решения

Рассмотрим алгоритм построения. Для его построения из центра треугольника мысленно вырежем кусок треугольной формы, который своими вершинами будет упираться в середины сторон исходного треугольника. Повторим эту же процедуру для трех образовавшихся треугольников (за исключением центрального) и так до бесконечности. Если мы теперь возьмем любой из образовавшихся треугольников и увеличим его - получим точную копию целого. В данном случае мы имеем дело с полным самоподобием. Другими словами рисуется равносторонний треугольник. Каждая сторона делится пополам и соединяется линиями. Центральный треугольник отбрасываем. А из получившихся трех маленьких треугольников снова находим середины. И так далее.

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

Вывод

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

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