Sierpinski-Dreieckkonstruktionsalgorithmus. Das Konzept der fraktalen Dimension. Na und

13.11.2020

Wir nehmen ein gewöhnliches Dreieck.
Schneiden Sie daraus ein Dreieck aus, dessen Eckpunkte an den Mittelpunkten der Seiten des Originals liegen. Als Ergebnis erhalten wir drei Dreiecke in der Ebene, deren Fläche jeweils viermal kleiner ist als die Fläche des ursprünglichen Dreiecks.
Wir machen die vorherigen Manipulationen mit den resultierenden Dreiecken.

Der Prozess sieht folgendermaßen aus:

Es ist interessant, dass, wenn in Pascals Dreieck alle ungeraden Zahlen in einer Farbe und gerade Zahlen in einer anderen Farbe gefärbt sind, das Sierpinski-Dreieck gebildet wird.

Wir werden diese Tatsache nutzen. Nur in Excel ist es bequemer, nicht die klassische (zeilenweise) Form des Pascalschen Dreiecks zu verwenden, sondern Folgendes:

Hier werden die Binomialkoeffizienten diagonal in der ersten gefüllten Zeile und der ersten gefüllten Spalte Einheiten und im Rest die Summe der oberen und linken Elemente ausgeschrieben.

Fahren wir mit der Konstruktion fort. Für uns reicht es aus, nicht die Koeffizienten, sondern nur deren Parität aufzuschreiben.

Lassen Sie uns zunächst die Größe der Zellen in Excel auf 7 x 7 Pixel festlegen.

Lassen Sie uns in Zelle B2 stehen und dann den Bereich B2: DY129 auswählen - drücken Sie dazu Strg + G und schreiben Sie B2: DY129 in das Verknüpfungsfeld.

Jetzt schreiben wir in die Formelleiste \u003d IF (OR (ROW () \u003d 2, COLUMN () \u003d 2), 1, REM (A2 + B1,2))
und drücken Sie Strg + Eingabetaste, um die gesamte Auswahl mit einer ähnlichen Formel zu füllen.

Hineingehen Speisekarte - Bedingte Formatierung und für den Wert 1 geben wir die Zellenfarbe an.

Als Ergebnis erhalten wir:

Es sollte beachtet werden, dass das Sierpinski-Dreieck für eine Art zufälligen Spaziergang im Flugzeug erhalten wird. Nämlich:

Wir fixieren 3 Eckpunkte des Dreiecks in der Ebene und nehmen einen weiteren Punkt.
Der erste Punkt wird als Mittelpunkt des Segments zwischen erhalten versehentlich Ausgewählter Scheitelpunkt und Punkt aus Punkt 1.
Der zweite Punkt wird als Mittelpunkt des Segments zwischen erhalten versehentlich der ausgewählte Scheitelpunkt und der erste Punkt.
Wir wiederholen den Vorgang viele Male.

Sie können das folgende Makro verwenden:

Öffentliches Submakro ()

Dim arRange (1 bis 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

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

Cells.Clear

Für i \u003d 1 bis 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)
Zellen (tekRow, tekColumn) .Interior.ColorIndex \u003d 5
Nächster

End Sub

Dieses Fraktal wurde 1915 vom polnischen Mathematiker Vaclav Sierpinski beschrieben. Um es zu bekommen, müssen Sie ein (gleichseitiges) Dreieck mit einem Innenraum nehmen, Mittellinien darin zeichnen und das mittlere der vier gebildeten kleinen Dreiecke wegwerfen. Dann müssen die gleichen Schritte mit jedem der verbleibenden drei Dreiecke usw. wiederholt werden. Die Abbildung zeigt die ersten drei Schritte.

Das Herauswerfen der mittleren Dreiecke ist nicht die einzige Möglichkeit, das Sierpinski-Dreieck zu erhalten. Sie können sich "in die entgegengesetzte Richtung" bewegen: Nehmen Sie ein anfänglich "leeres" Dreieck, bauen Sie dann ein Dreieck, das aus den Mittellinien besteht, und machen Sie dasselbe in jedem der drei Eckdreiecke usw. Zuerst werden die Figuren sehr unterschiedlich sein, aber mit Wenn die Iterationszahl wächst, werden sie sich immer mehr ähneln und im Grenzfall zusammenfallen.

Der nächste Weg, um das Sierpinski-Dreieck zu erhalten, ist dem üblichen Schema zum Konstruieren geometrischer Fraktale noch ähnlicher, indem Teile der nächsten Iteration durch ein skaliertes Fragment ersetzt werden. Hier werden bei jedem Schritt die Segmente, aus denen die Polylinie besteht, durch eine Polylinie mit drei Verknüpfungen ersetzt (sie wird selbst in der ersten Iteration erhalten). Sie müssen diese gestrichelte Linie abwechselnd nach rechts und links verschieben. Es ist ersichtlich, dass bereits die achte Iteration sehr nahe am Fraktal liegt, und je weiter, desto näher wird die Linie daran sein.

Aber das ist nicht alles. Es stellt sich heraus, dass das Sierpinski-Dreieck als Ergebnis einer der Varianten des zufälligen Gehens eines Punktes in der Ebene erhalten wird. Diese Methode wird als "Chaos-Spiel" bezeichnet. Einige andere Fraktale können damit erstellt werden.

Das Wesen des "Spiels" ist wie folgt. In der Ebene A 1 A 2 A 3 ist ein regelmäßiges Dreieck fixiert. Jeder Startpunkt B 0 ist markiert. Dann wird einer der drei Eckpunkte des Dreiecks zufällig ausgewählt und Punkt B 1 markiert - die Mitte des Segments mit Enden an diesem Scheitelpunkt und an B 0 (in der Abbildung rechts wurde der Scheitelpunkt A 1 zufällig ausgewählt). Das gleiche wird mit Punkt B 1 wiederholt, um B 2 zu erhalten. Dann werden die Punkte B 3, B 4 usw. erhalten. Es ist wichtig, dass der Punkt zufällig "springt", dh jedes Mal, wenn der Scheitelpunkt des Dreiecks zufällig ausgewählt wird, unabhängig davon, was in den vorherigen Schritten ausgewählt wurde. Es ist überraschend, dass, wenn Sie Punkte aus der Sequenz B i markieren, bald das Sierpinski-Dreieck erscheint. Unten sehen Sie, was passiert, wenn es aktiviert ist 100 , 500 und 2500 Punkte.

100, 500 und 2500 Punkte "align \u003d" center "/\u003e

Einige Eigenschaften

Fraktale Dimension log 2 3 ≈ 1,584962.... Das Sierpinski-Dreieck besteht aus drei Kopien von sich, die jeweils halb so klein sind. Ihre relative Position ist so, dass sich die Anzahl der Quadrate, die sich mit dem Fraktal schneiden, verdreifacht, wenn die Gitterzellen halbiert werden. Also N (δ / 2) \u003d 3N (δ)... Wenn zuerst die Größe der Zellen 1 war und sich das Fraktal schnitt N 0 Aus ihnen (N (1) \u003d N 0)dann N (1/2) \u003d 3N 0, N (1/4) \u003d 32N 0, ..., N (1 / 2k) \u003d 3kN0... Daher stellt sich heraus, dass N (δ) proportional und per Definition der fraktalen Dimension ist es gleich gerecht log 2 3.
Das Sierpinski-Dreieck hat die Fläche Null. Dies bedeutet, dass kein einziger, auch nur ein sehr kleiner Kreis in das Fraktal passt. Das heißt, wenn wir zunächst mit der Konstruktion beginnen, wurde das gesamte Innere aus dem Dreieck „herausgenommen“: Nach jeder Iteration wird die Fläche des verbleibenden Teils mit multipliziert 3/4 das heißt, es wird immer weniger und neigt dazu 0 ... Dies ist kein strenger Beweis, aber andere Konstruktionsmethoden können nur das Vertrauen erhöhen, dass diese Eigenschaft immer noch wahr ist.
Eine unerwartete Verbindung mit der Kombinatorik. Wenn in Pascals Dreieck mit 2n Färben Sie alle geraden Zahlen mit weißen Linien und alle ungeraden Zahlen mit Schwarz, dann bilden die sichtbaren Zahlen ein Sierpinski-Dreieck (in gewisser Annäherung).

Optionen Teppich (quadratisch, Serviette) Sierpinski.

Die quadratische Version wurde 1916 von Vaclav Sierpinski beschrieben. Es gelang ihm zu beweisen, dass jede Kurve, die auf einer Ebene ohne Selbstschnittpunkte gezeichnet werden kann, homöomorph zu einer Teilmenge dieses Lochquadrats ist. Wie ein Dreieck kann ein Quadrat aus verschiedenen Designs erhalten werden. Rechts ist die klassische Methode: Teilen Sie das Quadrat in 9 Teile und werfen Sie den Mittelteil heraus. Dann wird dasselbe für die verbleibenden 8 Quadrate wiederholt und so weiter.

Wie ein Dreieck hat ein Quadrat eine Fläche von Null. Die fraktale Dimension des Sierpinski-Teppichs ist log 3 8wird ähnlich wie die Abmessung eines Dreiecks berechnet.

Sierpinski-Pyramide.

Eines der dreidimensionalen Analoga des Sierpinski-Dreiecks. Es ist ähnlich aufgebaut und berücksichtigt die Dreidimensionalität des Geschehens: 5 Kopien der ursprünglichen Pyramide, die zweimal komprimiert wurden, bilden die erste Iteration, ihre 5 Kopien bilden die zweite Iteration und so weiter. Die fraktale Dimension ist log 2 5... Die Figur hat ein Volumen von Null (bei jedem Schritt wird die Hälfte des Volumens weggeworfen), aber die Oberfläche bleibt von Iteration zu Iteration erhalten, und für das Fraktal ist sie dieselbe wie für die anfängliche Pyramide.

Mengers Schwamm.

Verallgemeinerung des Sierpinski-Teppichs in den dreidimensionalen Raum. Um einen Schwamm zu bauen, müssen Sie den Vorgang endlos wiederholen: Jeder der Würfel, aus denen sich die Iteration zusammensetzt, ist in 27 dreimal kleinere Würfel unterteilt, aus denen der zentrale und seine 6 Nachbarn herausgeworfen werden. Das heißt, jeder Würfel bringt 20 neue hervor, dreimal weniger. Daher ist die fraktale Dimension log 3 20... Dieses Fraktal ist eine universelle Kurve: Jede Kurve im dreidimensionalen Raum ist homöomorph zu einer Teilmenge des Schwamms. Der Schwamm hat ein Volumen von Null (da er bei jedem Schritt mit multipliziert wird 20/27 ), aber gleichzeitig eine unendlich große Fläche.

L.
omana Linie:

N - Anzahl der Segmente, Größe und.

D - "Biegungsgrad"

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

ZU
rivai Koha

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

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

Fraktale Dimension:

D \u003d lg4 / lg3 \u003d 1,26 ...

Fraktale Dimension einer Menge

Fraktales Volumen in seiner nistplatzist immer Null. Es kann jedoch in einem Raum mit geringerer Dimension ungleich Null sein. Um die Dimension dieses Raums zu bestimmen D.Lass uns alles kaputt machen n-dimensionaler Raum in kleine Würfel mit Kantenlänge ε und Volumen ε n - Abb. 1. Lassen N.(ε ) ist die minimale Anzahl von Würfeln, die zusammen die fraktale Menge vollständig abdecken, dann per Definition

Das Vorhandensein dieser Grenze bedeutet das endliche Volumen des Fraktals in D.-dimensionaler Raum: klein ε

und anders als die übliche Dimension D.kann eine gebrochene Größe sein, die am häufigsten für fraktale Mengen verwendet wird.

Offensichtlich führt diese Definition für gewöhnliche Mengen zu bekannten Ergebnissen. So viele N.isolierte Punkte haben wir N.(ε ) =N.und deswegen

Eine glatte Längenlinie reicht für einen Schnitt aus L.:N.(ε ) =L./ε und deswegen D.\u003d 1. Für die Site S.zweidimensionale Oberfläche: N.(ε ) =S./ε 2 und D.\u003d 2 usw.

Rekursiver Algorithmus zum Konstruieren konstruktiver Fraktale.

Sierpinski-Dreieck

Sierpinski-Dreieck

Sierpinski-Dreieck ist ein Fraktal, eines der zweidimensionalen Analoga der Cantor-Menge, das der polnische Mathematiker Sierpinski 1915 vorgeschlagen hat. Auch als Sierpinski "Gitter" oder "Serviette" bekannt.

Gebäude

Nehmen Sie ein festes gleichseitiges Dreieck. Im ersten Schritt wird das Innere des mittleren Dreiecks von der Mitte entfernt. Im zweiten Schritt werden drei mittlere Dreiecke von den drei verbleibenden Dreiecken usw. entfernt. Nach einer endlosen Wiederholung dieses Vorgangs verbleibt eine Teilmenge des durchgezogenen Dreiecks - des Sierpinski-Dreiecks.

Bau des Sierpinski-Dreiecks

Das Sierpinski-Dreieck kann auch mit dem folgenden Algorithmus erhalten werden:

Nehmen Sie drei Punkte in der Ebene und zeichnen Sie ein Dreieck.

Wählen Sie zufällig einen beliebigen Punkt innerhalb des Dreiecks aus und bewegen Sie den halben Abstand von diesem Punkt zu einem der drei Eckpunkte des Dreiecks.

Markieren Sie die aktuelle Position.

Wiederholen Sie ab Schritt 2.

Sierpinski-Dreieck

Das Sierpinski-Dreieck ist eines der bekanntesten Fraktale. Seine Konstruktion ist eine der ersten Laborarbeiten zur Rekursion in den relevanten Disziplinen vieler Universitäten. Das Fraktal sieht so aus:

Pascals Dreieck

Pascals Dreieck ist eine unendliche Tabelle von Binomialkoeffizienten mit dreieckiger Form. In diesem Dreieck gibt es oben und an den Seiten. Jede Zahl ist gleich der Summe der beiden Zahlen darüber. Die Linien des Dreiecks sind symmetrisch zur vertikalen Achse.

Na und?

Es gibt ein interessantes Merkmal in Pascals Dreieck. Es zeigt das obige Fraktal mit seinen Zahlen an. Wenn Sie für eine lange Zeit in den Abgrund blicken, beginnt der Abgrund in Ihre Bedeutungen zu blicken, dann können Sie sehen, dass gerade und ungerade Zahlen in Gruppen angeordnet sind, da jedem eine unausgesprochene Regel bekannt ist: gerade + ungerade \u003d ungerade, gerade + gerade \u003d gerade, ungerade + ungerade \u003d gerade ...

Nun, weniger Worte, mehr Action. Lassen Sie uns die Schlussfolgerung etwas klarer machen. Personen, die nicht an der Implementierung von Software interessiert sind, werden am nächsten Absatz nicht interessiert sein.

Ich habe den alten Algorithmus zur Berechnung der Inferenz des Pascalschen Dreiecks verwendet und ihn so transformiert, dass anstelle des Werts von Zahlen der Rest seiner Division durch 2 angezeigt wird. Daher sind gerade Zahlen jetzt Nullen, ungerade Einsen Einsen. Ich füge den Code unten hinzu
#einschließen Verwenden des Namespace std; doppeltes Cnk (int N, int K) (return ((N. (Cnk (j, i))% 2<<" "; cout<<"\n"; } return 0; }
Zur besseren Übersicht habe ich die Ausgabe folgendermaßen dekoriert: Die Ausgabe des Programms wird in eine Datei umgeleitet, von der aus die Perle nach Abschluss der ersten Ausführung die Einheiten durch rote Buchstaben O, Nullen durch blaue durch ihre regulären Ausdrücke ersetzt. Der Skriptcode ist unten:
#! perl -w open (STREAM_IN, "1.txt"); # || die "Kann STREAM_IN nicht öffnen \\ n"; open (STREAM_OUT, "\u003e\u003e 1.html"); # || die "Kann STREAM_OUT nicht öffnen \\ n"; $ ss \u003d "
"; while ($ curr \u003d ) (chomp ($ curr); $ curr \u003d ~ s / 1 / Ö<\/font>/ g; $ curr \u003d ~ s / 0 / Ö<\/font>/ g; $ curr \u003d ~ s / - // g; $ out \u003d $ curr. $ ss; print (STREAM_OUT $ out); ); schließen Sie STREAM_IN; close STREAM_OUT;
Aus der Quelle können Sie sehen, dass wir uns mit HTML befassen werden. Warum? Aus Gründen der Einfachheit. Nur der DOM-Baum ist falsch. Beheben wir dies mit einem BASH-Skript und automatisieren alles, was oben beschrieben wurde:
#! / bin / bash g ++ ~ / serp.cpp; ~ / a.out\u003e ~ / 1.txt; Echo " DREIECK

"\u003e ~ / 1.html; perl ~ / s.pl; echo" "\u003e\u003e ~ / 1.html
Also kompilieren wir den Quellcode auf den Pluspunkten, seine Ausgabe geht in einen Texteditor, der Bash "hallt" in HTML zum Umschreiben am Anfang des DOM-Baums, danach nimmt der Texteditor ein Perlenskript, konvertiert es in eine mehrfarbige HTML-Version, ergänzt das HTML, wonach das liebe BASH erneut vervollständigt die Bildung des Baumes. Starten Sie, schauen Sie:

Lassen Sie uns das Original hervorheben und vergleichen

PROFITIEREN