Algorithme de construction du triangle de Sierpinski. Le concept de dimension fractale. Et alors

13.11.2020

Nous prenons un triangle ordinaire.
Découpez-y un triangle dont les sommets se trouvent au milieu des côtés de l'original. En conséquence, nous obtenons trois triangles sur le plan, dont l'aire de chacun est quatre fois inférieure à l'aire de l'original.
Nous faisons les manipulations précédentes avec les triangles résultants.

Le processus ressemble à ceci:

Il est intéressant de noter que si dans le triangle de Pascal tous les nombres impairs sont colorés dans une couleur et les nombres pairs dans une autre, alors le triangle de Sierpinski se forme.

Nous utiliserons ce fait. Seulement dans Excel, il est plus pratique d'utiliser non pas la forme classique (ligne par ligne) du triangle de Pascal, mais ceci:

Ici, les coefficients binomiaux sont écrits en diagonale, dans la première ligne remplie et la première colonne remplie, les unités et dans le reste la somme des éléments du haut et de gauche.

Passons à la construction. Il nous suffit d'écrire non pas les coefficients, mais seulement leur parité.

Commençons par définir la taille de la cellule dans Excel, par exemple 7 sur 7 pixels.

Restons dans la cellule B2, puis sélectionnez la zone B2: DY129 - pour ce faire, appuyez sur Ctrl + G et écrivez B2: DY129 dans le champ de lien.

Maintenant, dans la barre de formule, nous écrivons \u003d SI (OU (RANG () \u003d 2, COLONNE () \u003d 2), 1, REPOS (A2 + B1,2))
et appuyez sur Ctrl + Entrée pour remplir toute la sélection avec une formule similaire.

Va dans Menu - Mise en forme conditionnelle et pour la valeur 1, nous spécifions la couleur de la cellule.

En conséquence, nous obtenons:

Il convient de noter que le triangle de Sierpinski est obtenu pour une sorte de marche aléatoire dans l'avion. À savoir:

Nous fixons 3 sommets du triangle sur le plan et prenons un point de plus.
Le premier point est obtenu comme point médian du segment entre accidentellement sommet et point sélectionnés à partir de l'élément 1.
Le deuxième point est obtenu comme le point médian du segment entre accidentellement le sommet sélectionné et le premier point.
Nous répétons le processus plusieurs fois.

Vous pouvez utiliser la macro suivante:

Sous-macro publique ()

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

Définissez arRange (1) \u003d Cells (1, 1)
Définissez arRange (2) \u003d Cells (50, 250)
Définissez arRange (3) \u003d Cells (200, 20)

Cellules claires

Pour i \u003d 1 à 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)
Cellules (tekRow, tekColumn) .Interior.ColorIndex \u003d 5
Suivant

End Sub

Cette fractale a été décrite en 1915 par le mathématicien polonais Vaclav Sierpinski. Pour l'obtenir, vous devez prendre un triangle (équilatéral) avec un intérieur, dessiner des lignes médianes et jeter le triangle central des quatre petits triangles formés. Ensuite, les mêmes étapes doivent être répétées avec chacun des trois triangles restants, etc. La figure montre les trois premières étapes.

Jeter les triangles centraux n'est pas le seul moyen de se retrouver avec le triangle de Sierpinski. Vous pouvez vous déplacer "dans la direction opposée": prenez un triangle initialement "vide", puis construisez un triangle formé par les lignes médianes, puis faites de même dans chacun des trois triangles d'angle, et ainsi de suite. Au fur et à mesure que le nombre d'itérations augmente, ils se ressembleront de plus en plus et coïncideront à la limite.

La prochaine façon d'obtenir le triangle de Sierpinski est encore plus similaire au schéma habituel de construction de fractales géométriques en remplaçant des parties de l'itération suivante par un fragment mis à l'échelle. Ici, à chaque étape, les segments qui composent la polyligne sont remplacés par une polyligne de trois liens (elle est obtenue elle-même dans la première itération). Vous devez reporter cette ligne brisée en alternance vers la droite puis vers la gauche. On peut voir que déjà la huitième itération est très proche de la fractale, et plus la ligne se rapproche d'elle.

Mais ce n'est pas tout. Il s'avère que le triangle de Sierpinski est obtenu à la suite de l'une des variétés de la marche aléatoire d'un point sur le plan. Cette méthode s'appelle le «jeu du chaos». Certaines autres fractales peuvent être construites avec.

L'essence du «jeu» est la suivante. Un triangle régulier est fixé sur le plan A 1 A 2 A 3. Tout point de départ B 0 est marqué. Ensuite, l'un des trois sommets du triangle est sélectionné au hasard et le point B 1 est marqué - le milieu du segment avec des extrémités à ce sommet et à B 0 (sur la figure de droite, le sommet A 1 a été sélectionné au hasard). La même chose est répétée avec le point B 1 pour obtenir B 2. On obtient alors les points B 3, B 4, etc. Il est important que le point "saute" au hasard, c'est-à-dire qu'à chaque fois le sommet du triangle soit choisi au hasard, indépendamment de ce qui a été sélectionné dans les étapes précédentes. Il est surprenant que si vous marquez les points de la séquence B i, alors le triangle de Sierpinski commencera bientôt à apparaître. Ci-dessous, ce qui se passe une fois coché 100 , 500 et 2500 points.

100, 500 et 2500 points "align \u003d" center "/\u003e

Quelques propriétés

Dimension fractale log 2 3 ≈ 1,584962.... Le triangle de Sierpinski se compose de trois copies de lui-même, chaque moitié aussi petite. Leur position relative est telle que si les cellules de la grille sont divisées par deux, le nombre de carrés coupant la fractale triplera. C'est à dire N (δ / 2) \u003d 3N (δ)... Si au début la taille des cellules était de 1 et que la fractale se croisait N 0 d'eux (N (1) \u003d N 0)puis N (1/2) \u003d 3N 0, N (1/4) \u003d 32N 0, ..., N (1 / 2k) \u003d 3kN0... Par conséquent, il s'avère que N (δ) proportionnellement, et par définition de dimension fractale, il est égal à juste journal 2 3.
Le triangle de Sierpinski a une aire zéro. Cela signifie qu'aucun cercle, même très petit, ne rentrera dans la fractale. Autrement dit, si nous partons de la construction de la première manière, tout l'intérieur a été «sorti» du triangle: après chaque itération, l'aire de ce qui reste est multipliée par 3/4 , c'est-à-dire qu'il devient de moins en moins et tend à 0 ... Ce n'est pas une preuve rigoureuse, mais d'autres méthodes de construction ne peuvent qu'accroître la confiance que cette propriété est toujours vraie.
Une connexion inattendue avec la combinatoire. Si dans le triangle de Pascal avec 2n colorie tous les nombres pairs avec des lignes blanches et les nombres impairs avec du noir, puis les nombres visibles forment un triangle de Sierpinski (dans une certaine approximation).

Options Tapis (carré, serviette) Sierpinski.

La version carrée a été décrite par Vaclav Sierpinski en 1916. Il a réussi à prouver que toute courbe qui peut être dessinée sur un plan sans auto-intersections est homéomorphe à un sous-ensemble de ce carré qui fuit. Comme un triangle, un carré peut être obtenu à partir de différents modèles. À droite, la méthode classique: diviser le carré en 9 parties et jeter la partie centrale. Ensuite, la même chose est répétée pour les 8 carrés restants, et ainsi de suite.

Comme un triangle, un carré a une aire nulle. La dimension fractale du tapis Sierpinski est log 3 8, est calculé de la même manière que la dimension d'un triangle.

Pyramide de Sierpinski.

Un des analogues tridimensionnels du triangle de Sierpinski. Il est construit de la même manière, en tenant compte de la tridimensionnalité de ce qui se passe: 5 des copies de la pyramide initiale, compressées par deux, constituent la première itération, son 5 copies constitueront la deuxième itération, et ainsi de suite. La dimension fractale est log 2 5... La figure a un volume nul (à chaque pas, la moitié du volume est jetée), mais la surface est préservée d'itération en itération, et pour la fractale c'est la même que pour la pyramide initiale.

L'éponge de Menger.

Généralisation du tapis de Sierpinski dans un espace tridimensionnel. Pour construire une éponge, vous avez besoin d'une répétition sans fin de la procédure: chacun des cubes qui composent l'itération est divisé en 27 cubes trois fois plus petits, dont le central et ses 6 voisins sont jetés. Autrement dit, chaque cube en génère 20 nouveaux, trois fois moins. Par conséquent, la dimension fractale est journal 3 20... Cette fractale est une courbe universelle: toute courbe dans l'espace tridimensionnel est homéomorphe à un sous-ensemble de l'éponge. L'éponge a un volume nul (puisqu'à chaque étape, elle est multipliée par 20/27 ), mais en même temps une zone infiniment grande.

L
ligne Omana:

N - nombre de segments, taille et.

D - "degré de flexion"

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

À
rivai Koha

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

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

Dimension fractale:

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

Dimension fractale d'un ensemble

Volume fractal dans son espace de nidificationest toujours zéro. Cependant, il peut être différent de zéro dans un espace de moindre dimension. Pour déterminer la dimension de cet espace ré, cassons tout n-espace dimensionnel en petits cubes avec une longueur de bord ε et volume ε n - Fig. 1. Laisser être N(ε ) est le nombre minimum de cubes qui, ensemble, couvrent complètement l'ensemble fractal, alors par définition

L'existence de cette limite signifie le volume fini de la fractale en ré-espace dimensionnel: au petit ε

et contrairement à la dimension habituelle répeut être une quantité fractionnelle, ce qui est le plus souvent pour les ensembles fractals.

Evidemment, pour les ensembles ordinaires, cette définition conduit à des résultats bien connus. Tant Npoints isolés que nous avons N(ε ) =Net donc

Une ligne de longueur lisse suffit pour une coupe L:N(ε ) =L/ε et donc ré\u003d 1. Pour le site Ssurface bidimensionnelle: N(ε ) =S/ε 2 et ré\u003d 2, etc.

Algorithme récursif pour la construction de fractales constructives.

Triangle de Sierpinski

Triangle de Sierpinski

Triangle de Sierpinski est une fractale, l'un des analogues bidimensionnels de l'ensemble Cantor, proposé par le mathématicien polonais Sierpinski en 1915. Aussi connu sous le nom de "treillis" ou "serviette" de Sierpinski.

Bâtiment

Prenez un triangle équilatéral solide, à la première étape, l'intérieur du triangle du milieu est retiré du centre. À la deuxième étape, trois triangles du milieu sont supprimés des trois triangles restants, etc. Après une répétition sans fin de cette procédure, il reste un sous-ensemble du triangle solide - le triangle de Sierpinski.

Construction du triangle Sierpinski

Le triangle de Sierpinski peut également être obtenu en utilisant l'algorithme suivant:

Prenez trois points sur le plan et dessinez un triangle.

Sélectionnez au hasard n'importe quel point à l'intérieur du triangle et déplacez la moitié de la distance de ce point vers l'un des trois sommets du triangle.

Marquez la position actuelle.

Répétez à partir de l'étape 2.

Triangle de Sierpinski

Le triangle de Sierpinski est l'une des fractales les plus connues, sa construction est l'un des premiers travaux de laboratoire sur la récursivité dans les disciplines concernées dans de nombreuses universités. La fractale ressemble à ceci:

Triangle de Pascal

Le triangle de Pascal est une table infinie de coefficients binomiaux qui a une forme triangulaire. Dans ce triangle, il y en a en haut et sur les côtés. Chaque nombre est égal à la somme des deux nombres au-dessus. Les lignes du triangle sont symétriques par rapport à l'axe vertical.

Et alors?

Il y a une caractéristique intéressante dans le triangle de Pascal. Il affiche la fractale ci-dessus avec ses numéros. Si vous regardez dans l'abîme pendant une longue période, l'abîme commence à scruter vos significations, alors vous pouvez voir que les nombres pairs et impairs sont disposés en groupes, car il y a une règle tacite connue de tout le monde: pair + impair \u003d impair, pair + pair \u003d pair, impair + impair \u003d pair ...

Eh bien, moins de mots, plus d'action. Faisons la conclusion un peu plus claire. Les personnes qui ne sont pas intéressées par la mise en œuvre de logiciels ne seront pas intéressées par le paragraphe suivant.

J'ai pris l'ancien algorithme de calcul-inférence du triangle de Pascal et je l'ai transformé de telle manière qu'au lieu de la valeur des nombres, le reste de sa division par 2 est affiché. Par conséquent, les pairs sont maintenant des zéros, les impairs sont des uns. Je joins le code ci-dessous
#comprendre en utilisant l'espace de noms std; double Cnk (int N, int K) (retourne ((N (Cnk (j, i)))% 2<<" "; cout<<"\n"; } return 0; }
Pour plus de clarté, j'ai coloré la sortie de la manière suivante: la sortie du programme est redirigée vers un fichier, d'où, à la fin de la première exécution, la perle avec son expression rationnelle remplace celles avec des lettres rouges O, des zéros avec des bleus. Le code de script est ci-dessous:
#! perl -w ouvert (STREAM_IN, "1.txt"); # || die "Impossible" d'ouvrir STREAM_IN \\ n "; open (STREAM_OUT," \u003e\u003e 1.html "); # || die" Impossible "d'ouvrir 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; impression (STREAM_OUT $ out); ); fermer STREAM_IN; fermer STREAM_OUT;
De la source, vous pouvez voir que nous allons examiner html. Pourquoi? Pour des raisons de simplicité. Seul l'arborescence DOM est erronée. Corrigeons cela avec un script en BASH et automatisons tout ce qui est décrit ci-dessus:
#! / bin / bash g ++ ~ / serp.cpp; ~ / a.out\u003e ~ / 1.txt; écho " TRIANGLE

"\u003e ~ / 1.html; perl ~ / s.pl; echo" "\u003e\u003e ~ / 1.html
Donc, on compile le code source sur les plus, sa sortie va dans un éditeur de texte, le bash "écho" en html pour la réécriture au début de l'arbre DOM, après quoi l'éditeur de texte prend un script perle, le convertit en une version html multicolore, complète le html, après quoi le cher BASH à nouveau achève la formation de l'arbre. Lancez, regardez:

Soulignons et comparons avec l'original

PROFIT