4.1 Рекурсивные объекты и фрактальные узоры.

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

Рисование рекурсивных объектов.

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

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

Мы приведем три простых примера фракталов.

Задача.

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

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

Кривая Коха первого и второго порядка.

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

Салфетка Серпинского первого и второго порядка.

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