Трикутник Серпінського алгоритм побудови. Поняття про фрактальної розмірності. І що з того

13.11.2020

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

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

Цікаво, що якщо в трикутнику Паскаля всі непарні числа пофарбувати в один колір, а парні в інший, то утворюється трикутник Серпінського.

Цим фактом і скористаємося. Тільки в Excel зручніше використовувати не класичний (порядковий) вид трикутника Паскаля, а такий:

Тут біноміальні коефіцієнти виписані по діагоналі, в першій заповненої рядку і першому заповненому стовпці одиниці, а в інших сума вехньої і лівого елемента.

Перейдемо до побудови. Для нас досить виписувати НЕ коефіцієнти, а тільки їх парність.

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

Станом в клітинку B2, потім виділимо область B2: DY129 - для цього натискаємо Ctrl + G і в поле посилання пишемо B2: DY129.

Тепер в рядку формул пишемо \u003d ЕСЛИ (ИЛИ (СТРОКА () \u003d 2; стовпець () \u003d 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 \u003d Int (1000 * Rnd) + 1
tekColumn \u003d Int (200 * Rnd) + 1

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

Cells.Clear

For i \u003d 1 To 20000
iT \u003d (Int (1000 * Rnd) Mod 3) + 1
tekRow \u003d Int ((tekRow + arRange (iT) .Row) / 2)
tekColumn \u003d Int ((tekColumn + arRange (iT) .Column) / 2)
Cells (tekRow, tekColumn) .Interior.ColorIndex \u003d 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 \u003d" center "/\u003e

деякі властивості

фрактальна розмірність log 2 3 ≈ 1,584962.... Трикутник Серпінського складається з трьох копій самого себе, кожна в два рази менше. Взаємне розташування їх таке, що якщо зменшити клітинки сітки в два рази, то число квадратиків, що перетинаються з фракталом, потроїться. Тобто N (δ / 2) \u003d 3N (δ). Якщо спочатку розмір клітин був 1, а з фракталом зустрічалося N 0 з них (N (1) \u003d N 0), то N (1/2) \u003d 3N 0, N (1/4) \u003d 32N 0, ..., N (1 / 2k) \u003d 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 ), Але при цьому нескінченно велика площа.

Л
оманной лінії:

N- кількість відрізків, розміром а.

D - «ступінь згинання»

N \u003d (1 / a) D; S \u003d N * a; S \u003d (1 / a) D-1

До
рівая Коха

2) N \u003d 4L \u003d 1 / 3S (4) \u003d 4/3

N \u003d 16 L \u003d 1 / 9S (16) \u003d 16/9

Фрактальна розмірність:

D \u003d lg4 /lg3\u003d1.26...

Фрактальна розмірність безлічі

Обсяг фрактала в своєму просторі вкладеннязавжди дорівнює нулю. Він, однак, може бути відмінний від нуля в просторі меншої розмірності. Щоб визначити розмірність цього простору D, Розіб'ємо всі n-мірним простір на малі кубики з довжиною ребра ε і об'ємом ε n - рис.1. нехай N(ε ) - мінімальне число кубиків, які в сукупності повністю покривають фрактальное безліч, тоді по визначенню

Існування цієї межі означає кінцівку обсягу фрактала в Dвимірному просторі: при малому ε

і на відміну від звичної розмірності Dможе бути дробової величиною, якою вона найчастіше і є для фрактальних множин.

Очевидно, що для звичайних множин це визначення призводить до добре відомих результатів. Так для безлічі Nізольованих точок маємо N(ε ) =Nі тому

Для відрізка досить гладкою лінії довжини L:N(ε ) =L/ε і тому D\u003d 1. Для майданчики Sдвовимірної поверхні: N(ε ) =S/ε 2 і D\u003d 2 і т.д ..

Рекурсивний алгоритм побудови конструктивних фракталів.

трикутник Серпінського

трикутник Серпінського

трикутник Серпінського - фрактал, один з двовимірних аналогів безлічі Кантора запропонований польським математиком Серпінським в 1915 році. Також відомий як «решітка» або «серветка» Серпінського.

побудова

Береться суцільний рівносторонній трикутник, на першому кроці з центру віддаляється внутрішність серединного трикутника. На другому кроці видаляється три серединних трикутника з трьох, що залишилися трикутників і т. Д. Після нескінченного повторення цієї процедури, від суцільного трикутника залишається підмножина - трикутник Серпінського.

Побудова трикутника Серпінського

Трикутник Серпінського можна також отримати за наступним алгоритмом:

Взяти три точки на площині, і намалювати трикутник.

Випадково вибрати будь-яку точку всередині трикутника, і просунутися на половину відстані від цієї точки до будь-якої з трьох вершин трикутника.

Відзначити поточну позицію.

Повторити з кроку 2.

трикутник Серпінського

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

трикутник Паскаля

Трикутник Паскаля - нескінченна таблиця біноміальних коефіцієнтів, що має трикутну форму. У цьому трикутнику на вершині і з боків стоять одиниці. Кожне число дорівнює сумі двох розташованих над ним чисел. Рядки трикутника симетричні щодо вертикальної осі.

І що з того?

Є в трикутнику Паскаля цікава особливість. Він відображає вищезгаданий фрактал своїми числами. Якщо довго вдивлятися в безодню, безодня починає вдивлятися в тебе значення, то можна побачити, що парні і непарні числа розташовуються групами, бо є одне негласне всім відоме правило: парне + непарне \u003d непарне, парне + парне \u003d парне, непарне + непарне \u003d парне .

Що ж, менше слів, більше діла. Зробимо висновок трохи наочніше. Людям, які не цікавляться програмною реалізацією наступний абзац буде нецікавий.

Я взяв старий алгоритм розрахунку-виведення трикутника Паскаля і перетворив його таким чином, що замість значення чисел виводиться залишок від його ділення на 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," \u003e\u003e 1.html "); # || die" Can "t open STREAM_OUT \\ n"; $ Ss \u003d "
"; While ($ curr \u003d ) (Chomp ($ curr); $ curr \u003d ~ s / 1 / O<\/font>/ G; $ Curr \u003d ~ s / 0 / O<\/font>/ G; $ Curr \u003d ~ s / - // g; $ Out \u003d $ curr. $ Ss; print (STREAM_OUT $ out); ); close STREAM_IN; close STREAM_OUT;
З исходника видно, що дивитися ми будемо html. Чому? З міркувань простоти. Тільки дерево DOM невірне виходить. Виправимо це скриптом на BASH і автоматизуємо все вищеописане:
#! / Bin / bash g ++ ~ / serp.cpp; ~ / A.out\u003e ~ / 1.txt; echo " TRIANGLE

"\u003e ~ / 1.html; perl ~ / s.pl; echo" "\u003e\u003e ~ / 1.html
Отже, ми компілюємо исходник на плюсах, його висновок йде в текстовічок, баш «ехает» в html на перезапис початком дерева DOM, після чого текстовічок бере перл-скрипт, переробляє його в різнокольорову html-версію, доповнює htmlку, після чого люб'язний БАШ знову завершує формування дерева. Запускаємо, дивимося:

Підкреслимо і порівняємо з оригіналом

PROFIT

Схожі статті