Fractali prin divide et impera

Un fractal se construiește repetând aceeași regulă la scări tot mai mici. La curba Koch, fiecare segment se înlocuiește cu patru segmente, fiecare de trei ori mai scurt. La triunghiul Sierpinski, fiecare triunghi rămas este înlocuit cu trei triunghiuri mai mici, după eliminarea celui central. Figurile arată autosimilaritate: o parte seamănă cu întregul.

Metoda divide et impera împarte problema „desenează nivelul $n$” în subprobleme „desenează nivelul $n-1$”. Este necesar un caz de bază, altfel recursia nu se oprește. La nivelul $0$ al curbei Koch există un segment; la nivelul $1$ sunt $4$, iar la nivelul $2$ sunt $16$.

Un fractal este o figură autosimilară: fiecare parte a lui seamănă cu întregul. Construcția recursivă (divide et impera) reduce problema „desenează nivelul $n$” la problema „desenează nivelul $n-1$” de mai multe ori, la o scară mai mică. Fără un caz de bază, recursia nu se oprește, de aceea nivelul 0 este tratat direct: la curba Koch este un segment, la triunghiul Sierpinski este un triunghi. Curba Koch înlocuiește fiecare segment cu patru segmente, fiecare de trei ori mai scurt decât cel înlocuit. După $n$ pași numărul de segmente este $4^n$, un segment are lungimea $L_0/3^n$, iar lungimea totală este $L_n=L_0{\left(\frac{4}{3}\right)}^n$. Triunghiul Sierpinski se obține înlocuind fiecare triunghi cu trei triunghiuri de latură jumătate, după eliminarea triunghiului central. După $n$ pași sunt $3^n$ triunghiuri păstrate, iar aria lor totală este $A_n=A_0{\left(\frac{3}{4}\right)}^n$.

Exemplul 1 — numărarea segmentelor Koch. Numărul de segmente de la nivelul $n$ este de patru ori numărul de la nivelul $n-1$, cu un segment la nivelul 0.

#include <iostream>
using namespace std;
long long segmente(int nivel) {
    if (nivel == 0) return 1;
    return 4 * segmente(nivel - 1);
}
int main() {
    for (int i = 0; i <= 4; ++i)
        cout << segmente(i) << " ";
    return 0;
}

Programul afișează 1 4 16 64 256 . Pentru segmente(2) apelurile dau $1\to 4\to 16$. Recursia simplă are timp proporțional cu $n$ pentru numărare, dar desenarea tuturor segmentelor de nivel $n$ cere $O(4^n)$ operații, deoarece fiecare segment este produs separat. Tipul long long se depășește la niveluri suficient de mari, în jur de $n=31$, unde $4^{31}$ ajunge la limita tipului.

Exemplul 2 — curba Koch la nivelul 3. Pentru un segment inițial de lungime $L_0$ și $n=3$: sunt $4^3=64$ de segmente, fiecare cu lungimea $L_0/27$, deci lungimea totală este $64L_0/27\approx 2,37L_0$. La nivelurile 0, 1, 2, 3 lungimea totală este $L_0$, $\frac{4}{3}{L}_0$, $\frac{16}{9}{L}_0$ și $\frac{64}{27}{L}_0$: crește cu un factor de $4/3$ la fiecare pas și nu are limită superioară, deși figura încape într-o zonă de mărime finită.

Exemplul 3 — triunghiul Sierpinski la nivelul 3. Sunt $3^3=27$ de triunghiuri păstrate, fiecare cu latura de opt ori mai mică decât a celui inițial. Aria totală este ${\left(\frac{3}{4}\right)}^3{A}_0=\frac{27}{64}{A}_0\approx 0,42A_0$, deci aproape 58% din aria inițială a fost eliminată. Din același motiv, la fiecare pas rămân $\frac{3}{4}$ din aria precedentă, iar aria tinde spre 0 când $n$ crește, deși numărul de triunghiuri crește.

Cum se desenează. Pentru curba Koch, o procedură recursivă koch(lungime, nivel) desenează un segment dacă nivel este 0; altfel apelează de patru ori koch(lungime / 3, nivel - 1), cu rotiri de 60 de grade la stânga, 120 de grade la dreapta și 60 de grade la stânga între apeluri, astfel încât cele patru segmente să alcătuiască „vârful” curbei. Procedura are un singur parametru care scade, nivel, deci numărul apelurilor la nivelul $n$ este $1+4+4^2+\dots +4^n$.

Exemplul 4 — fulgul lui Koch. Pornind de la un triunghi echilateral cu latura $a=9$ și aplicând regula pe fiecare latură, perimetrele sunt $27$, $36$ și $48$ la nivelurile 0, 1 și 2: la nivelul 2 sunt $3\cdot 4^2=48$ de segmente de lungime 1.

Greșeli frecvente

• Greșit: la fractali recursia nu are nevoie de caz de bază.
  Corect: fără nivelul 0 apelurile nu se mai opresc.
• Greșit: la curba Koch numărul segmentelor se dublează la fiecare pas.
  Corect: se înmulțește cu 4, fiind $4^n$.
• Greșit: lungimea curbei Koch rămâne aceeași la toate nivelurile.
  Corect: se înmulțește cu $4/3$ la fiecare pas.

Înainte și după