Треугольник серпинского задание явными формулами. Понятие о фрактальной размерности

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

Основными представителями этой группы фракталов являются такие объекты, как: кривая Пеано , снежинка Коха , треугольник Серпинского, пыль Кантора, «дракон» Хартера-Хейтуэя. .. Все они получены путем повторений определенной последовательности геометрических построений с использованием точек и линий. Кантор с помощью простой рекурсивной процедуры «превратил» линию в набор несвязных точек: брал линию и выносил её центральную треть на определенное расстояние, затем повторял эту процедуру с остальными отрезками. Джузеппе Пеано нарисовал особую линию, используя довольно простой алгоритм: он брал прямую линию, затем заменял её девятью отрезками, каждый из которых затем вновь подвергал этой процедуре и т.д.

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

Снежинка Коха

Из геометрических фракталов очень интересным и довольно знаменитым является фрактал "Снежинка Коха". Строится она на основе равностороннего треугольника.
Пусть сторона исходного треугольника равна 1. Его площадь также равна 1.

Каждая сторона делится на три части каждая длиной в 1/3 исходной стороны. Затем пририсовывются три меньших равносторонних треугольника по одному на каждой стороне (на стредней трети). На каждой из полученных 12 сторон пририсовываются по одному ещё меньшему треугольнику (снова на средней трети стороны).

Таким образом, с каждой итерацией длина кривой увеличивается на треть.

Каждый раз число сторон учетверяется. Число сторон можно выразить такой последовательностью:

3, 3*4, 3*4*4, 3* 4*4*4, 3* 4*4*4*4....

Убеждаемся, что число сторон снежинки бесконечно велико.

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

Площадь первоначального треугольника была равна 1. Площадь каждого нового треугольника равна 1/9 от плошади предыдущего. Площадь первоначального треугольника была равна 1.. После добавления трёх треугольников площадь увеличивается на 3/9=1/3. Затем каждый раз будет добавляться вчетверо больше треугольников, чем на предыдущем этапе. Следовательно, площадь, добавляемая на каждом этапе, будет составлять 4/9 от площади, добвледущнной на предыдущем этапе.

Общую площадь снежинки можно выразить геометрическим рядом

1+ 1/3 + (1/3) * (4/9) + (1/3) * (4/9)*(4/9) + (1/3) * (4/9)*(4/9)*(4/9) + ...
Сумма этого ряда конечна и равна 1,6.

При этом периметр снежинки, напротив, бесконечен.

Треугольник Серпинского ( http://elementy.ru/posters/fractals/Sierpinski)

Этот фрактал описал в 1915 году польский математик Вацлав Серпинский . Чтобы его получить, нужно взять (равносторонний) треугольник с внутренностью, провести в нём средние линии и выкинуть центральный из четырех образовавшихся маленьких треугольников. Дальше эти же действия нужно повторить с каждым из оставшихся трех треугольников, и т. д. На рисунке показаны первые три шага, а на флэш-демонстрации вы можете потренироваться и получить шаги вплоть до десятого.
Выкидывание центральных треугольников — не единственный способ получить в итоге треугольник Серпинского. Можно двигаться «в обратном направлении»: взять изначально «пустой» треугольник, затем достроить в нём треугольник, образованный средними линиями, затем в каждом из трех угловых треугольников сделать то же самое, и т. д. Поначалу фигуры будут сильно отличаться, но с ростом номера итерации они будут всё больше походить друг на друга, а в пределе совпадут.

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

Вторая большая группа фракталов - алгебраические. Свое название они получили за то, что их строят, на основе алгебраических формул иногда весьма простых. Методов получения алгебраических фракталов несколько. Один из методов представляет собой многократный (итерационный) расчет функции Zn+1=f(Zn), где Z - комплексное число, а f некая функция. Расчет данной функции продолжается до выполнения определенного условия. И когда это условие выполнится, на экран выводится точка.

При этом значения функции для разных точек комплексной плоскости может иметь разное поведение:

С течением времени стремится к бесконечности.

Стремится к нулю.

Принимает несколько фиксированных значений и не выходит за их пределы.

Поведение хаотично, без каких либо тенденций.

Фракталы Пьера Фату

К алгебраическим фракталам относят фракталы Фату.
Фату изучал рекурсивные процессы вида

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

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

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

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

Множество Мандельброта

Фракталы были описаны Мандельбротом в 1975 году в его книге «Les Objets Fractals: Forme, Hasard et Dimension» (« Фрактальные объекты: форма, случайность и размерность »). В этой книге Мандельброт впервые использовал термин «фрактал» для обозначения математического феномена, демонстрирующего столь непредсказуемое и удивительное поведение. Эти феномены рождались при использовании рекурсивного алгоритма для получения какой-либо кривой или множества. Множество Мандельброта — один из таких феноменов, названный по имени своего исследователя. Википедия
Множество Мандельброта — классический образец фрактала.

Множество Мандельброта — это множество таких точек С на комплексной плоскости :

Треугольник Серпинского

Треугольник Серпинского - один из известнейших фракталов, его построение - одна из первых лабораторных работ на рекурсию по соответствующим дисциплинам во многих ВУЗах. Выглядит фрактал следующим образом:

Треугольник Паскаля

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

И что с того?

Есть в треугольнике Паскаля интересная особенность. Он отображает вышеупомянутый фрактал своими числами. Если долго всматриваться в бездну, бездна начинает всматриваться в тебя значения, то можно увидеть, что чётные и нечетные числа располагаются группами, ибо есть одно негласное всем известное правило: четное+нечетное=нечетное, четное+четное=четное, нечетное+нечетное=четное.

Что ж, меньше слов, больше дела. Сделаем вывод немного нагляднее. Людям, не интересующимся программной реализацией следующий абзац будет неинтересен.

Я взял старый алгоритм расчета-вывода треугольника Паскаля и преобразовал его таким образом, что вместо значения чисел выводится остаток от его деления на 2. Стало быть, четные теперь стали нулями, нечетные - единицами. Сам код прилагаю ниже
#include using namespace std; double Cnk(int N,int K) { return ((N(Cnk(j,i)))%2<<" "; cout<<"\n"; } return 0; }
Для пущей наглядности я разукрасил вывод следующим способом: вывод программы перенаправляется в файл, откуда по завершению выполнения первой, перл своими регэкспами заменяет единицы на красные буквы О, нули - на синие. Код скрипта ниже:
#! perl -w open (STREAM_IN, "1.txt");# || die "Can"t open STREAM_IN\n"; open (STREAM_OUT, ">> 1.html");# || die "Can"t open STREAM_OUT\n"; $ss="
"; while ($curr = ) { chomp($curr); $curr=~s/1/O<\/font>/g; $curr=~s/0/O<\/font>/g; $curr=~s/-//g; $out = $curr.$ss; print (STREAM_OUT $out); }; close STREAM_IN; close STREAM_OUT;
Из исходника видно, что смотреть мы будем html. Почему? Из соображений простоты. Только дерево DOM неверное получается. Исправим это скриптом на BASH и автоматизируем всё вышеописанное:
#!/bin/bash g++ ~/serp.cpp; ~/a.out > ~/1.txt; echo " TRIANGLE

" > ~/1.html; perl ~/s.pl; echo " " >> ~/1.html
Итак, мы компилируем исходник на плюсах, его вывод уходит в текстовичок, баш «эхает» в html на перезапись началом дерева DOM, после чего текстовичок берет перл-скрипт, переделывает его в разноцветную html-версию, дополняет htmlку, после чего любезный БАШ снова завершает формирование дерева. Запускаем, смотрим:

Подчеркнем и сравним с оригиналом

PROFIT

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

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

Но и на этом не всё. Оказывается, треугольник Серпинского получается в результате одной из разновидностей случайного блуждания точки на плоскости. Этот способ называется «игрой Хаос». С его помощью можно построить и некоторые другие фракталы.

Суть «игры» такова. На плоскости зафиксирован правильный треугольник A 1 A 2 A 3 . Отмечают любую начальную точку B 0 . Затем случайным образом выбирают одну из трех вершин треугольника и отмечают точку B 1 - середину отрезка с концами в этой вершине и в B 0 (на рисунке справа случайно выбралась вершина A 1). То же самое повторяют с точкой B 1 , чтобы получить B 2 . Потом получают точки B 3 , B 4 , и т. д. Важно, чтобы точка «прыгала» случайным образом, то есть чтобы каждый раз вершина треугольника выбиралась случайно, независимо от того, что было выбрано в предыдущие шаги. Удивительно, что если отмечать точки из последовательности B i , то вскоре начнет проступать треугольник Серпинского. Ниже изображено, что получается, когда отмечено 100, 500 и 2500 точек.

Некоторые свойства

Варианты

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

Как и у треугольника, у квадрата нулевая площадь. Фрактальная размерность ковра Серпинского равна log 3 8, вычисляется аналогично размерности треугольника.

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

Губка Менгера. Обобщение ковра Серпинского в трехмерное пространство. Чтобы построить губку, нужно бесконечное повторение процедуры: каждый из кубиков, из которых состоит итерация, делится на 27 втрое меньших кубиков, из которых выбрасывают центральный и его 6 соседей. То есть каждый кубик порождает 20 новых, в три раза меньших. Поэтому фрактальная размерность равна log 3 20. Этот фрактал является универсальной кривой: любая кривая в трехмерном пространстве гомеоморфна некоторому подмножеству губки. У губки нулевой объем (так как на каждом шаге он умножается на 20/27), но при этом бесконечно большая площадь.

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

Выглядит процесс так:

Интересно, что если в треугольнике Паскаля все нечетные числа окрасить в один цвет, а четные в другой, то образуется треугольник Серпинского.

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

Здесь биномиальные коэффициенты выписаны по диагонали, в первой заполненной строке и первом заполненном столбце единицы, а в остальных сумма вехнего и левого элемента.

Перейдем к построению. Для нас достаточно выписывать не коэффициенты, а только их четность.

Для начала сделаем размер ячеек в Excel, к примеру 7 на 7 пикселей.

Станем в ячейку B2 , затем выделим область B2:DY129 - для этого нажимаем Ctrl + G и в поле ссылка пишем B2:DY129 .

Теперь в строке формул пишем =ЕСЛИ(ИЛИ(СТРОКА()=2;СТОЛБЕЦ()=2);1;ОСТАТ(A2+B1;2))
и нажимаем Ctrl + Enter, чтобы заполнить подобной формулой всю выделенную область.

Заходим Меню - Условное форматирование и для значения 1 указываем цвет ячейки.

В итоге получаем:

Следует отметить, что треугольник Серпинского получается при некоторой разновидности случайного блуждания на плоскости. А именно:

Зафиксируем на плоскости 3 вершины треугольника и возьмем еще одну точку.
Первую точку получим как середину отрезка между случайно выбранной вершиной и точкой из п.1.
Вторую точку получим как середину отрезка между случайно выбранной вершиной и первой точкой.
Повторяем процесс много раз.

Можно ипользовать такой макрос:

Public Sub Макрос()

Dim arRange(1 To 3) As Range
Dim tekRow As Integer
Dim tekColumn As Integer
Dim i As Integer
Dim iT As Integer

tekRow = Int(1000 * Rnd) + 1
tekColumn = Int(200 * Rnd) + 1

Set arRange(1) = Cells(1, 1)
Set arRange(2) = Cells(50, 250)
Set arRange(3) = Cells(200, 20)

Cells.Clear

For i = 1 To 20000
iT = (Int(1000 * Rnd) Mod 3) + 1
tekRow = Int((tekRow + arRange(iT).Row) / 2)
tekColumn = Int((tekColumn + arRange(iT).Column) / 2)
Cells(tekRow, tekColumn).Interior.ColorIndex = 5
Next

End Sub

Этот фрактал описал в 1915 году польский математик Вацлав Серпинский. Чтобы его получить, нужно взять (равносторонний) треугольник с внутренностью, провести в нём средние линии и выкинуть центральный из четырех образовавшихся маленьких треугольников. Дальше эти же действия нужно повторить с каждым из оставшихся трех треугольников, и т. д. На рисунке показаны первые три шага.

Выкидывание центральных треугольников - не единственный способ получить в итоге треугольник Серпинского. Можно двигаться «в обратном направлении»: взять изначально «пустой» треугольник, затем достроить в нём треугольник, образованный средними линиями, затем в каждом из трех угловых треугольников сделать то же самое, и т. д. Поначалу фигуры будут сильно отличаться, но с ростом номера итерации они будут всё больше походить друг на друга, а в пределе совпадут.

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

Но и на этом не всё. Оказывается, треугольник Серпинского получается в результате одной из разновидностей случайного блуждания точки на плоскости. Этот способ называется «игрой Хаос». С его помощью можно построить и некоторые другие фракталы.

Суть «игры» такова. На плоскости зафиксирован правильный треугольник A 1 A 2 A 3 . Отмечают любую начальную точку B 0 . Затем случайным образом выбирают одну из трех вершин треугольника и отмечают точку B 1 - середину отрезка с концами в этой вершине и в B 0 (на рисунке справа случайно выбралась вершина A 1). То же самое повторяют с точкой B 1 , чтобы получить B 2 . Потом получают точки B 3 , B 4 , и т. д. Важно, чтобы точка «прыгала» случайным образом, то есть чтобы каждый раз вершина треугольника выбиралась случайно, независимо от того, что было выбрано в предыдущие шаги. Удивительно, что если отмечать точки из последовательности B i , то вскоре начнет проступать треугольник Серпинского. Ниже изображено, что получается, когда отмечено 100 , 500 и 2500 точек.

100, 500 и 2500 точек" align="center" />

Некоторые свойства

Фрактальная размерность log 2 3 ≈ 1,584962 ... . Треугольник Серпинского состоит из трех копий самого себя, каждая в два раза меньше. Взаимное расположение их таково, что если уменьшить клеточки сетки в два раза, то число квадратиков, пересекающихся с фракталом, утроится. То есть N (δ/2) = 3N (δ) . Если сначала размер клеток был 1, а с фракталом пересекалось N 0 из них (N (1) = N 0) , то N(1/2) = 3N 0 , N (1/4) = 32N 0 , ..., N (1/2k) = 3kN0 . Отсюда получается, что N (δ) пропорционально, и по определению фрактальной размерности она равна как раз log 2 3 .
Треугольник Серпинского имеет нулевую площадь. Это означает, что в фрактал не влезет ни один, даже очень маленький, кружок. То есть, если отталкиваться от построения первым способом, из треугольника «вынули» всю внутренность: после каждой итерации площадь того, что остается, умножается на 3/4 , то есть становится всё меньше и стремится к 0 . Это не строгое доказательство, но другие способы построения могут только усилить уверенность, что это свойство всё-таки верно.
Неожиданная связь с комбинаторикой. Если в треугольнике Паскаля с 2n строками покрасить все четные числа белым, а нечетные - черным, то видимые числа образуют треугольник Серпинского (в некотором приближении).

Варианты Ковер (квадрат, салфетка) Серпинского.

Квадратная версия была описана Вацлавом Серпинским в 1916 году. Ему удалось доказать, что любая кривая, которую можно нарисовать на плоскости без самопересечений, гомеоморфна какому-то подмножеству этого дырявого квадрата. Как и треугольник, квадрат можно получить из разных конструкций. Справа изображен классический способ: разделение квадрата на 9 частей и выбрасывание центральной части. Затем то же повторяется для оставшихся 8 квадратов, и т. д.

Как и у треугольника, у квадрата нулевая площадь. Фрактальная размерность ковра Серпинского равна log 3 8 , вычисляется аналогично размерности треугольника.

Пирамида Серпинского.

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

Губка Менгера.

Обобщение ковра Серпинского в трехмерное пространство. Чтобы построить губку, нужно бесконечное повторение процедуры: каждый из кубиков, из которых состоит итерация, делится на 27 втрое меньших кубиков, из которых выбрасывают центральный и его 6 соседей. То есть каждый кубик порождает 20 новых, в три раза меньших. Поэтому фрактальная размерность равна log 3 20 . Этот фрактал является универсальной кривой: любая кривая в трехмерном пространстве гомеоморфна некоторому подмножеству губки. У губки нулевой объем (так как на каждом шаге он умножается на 20/27 ), но при этом бесконечно большая площадь.