Triangle de Sierpiński⚓︎

Le triangle de Sierpiński¹ est un exemple simple de fractale :

On part d'un carré de côté 1.
On colle deux copies, une à droite, une en bas ; on obtient un triangle de pixels.
On colle deux copies de triangle, une à droite, une en bas.
On répète le processus de construction.
La largeur et la hauteur de chaque étape est une puissance de deux.

Exercice

Écrire une fonction récursive telle que sierpinski(h) renvoie une liste de h lignes de pixels formant un triangle de Sierpiński. h sera un entier, une puissance de deux.

###

def sierpinski(n):bksl-nl ...bksl-nl bksl-nl bksl-nlassert sierpinski(1) == [bksl-nl "#",bksl-nl]bksl-nlbksl-nlassert sierpinski(2) == [bksl-nl "##",bksl-nl "#",bksl-nl]bksl-nlbksl-nlassert sierpinski(8) == [bksl-nl "########",bksl-nl "# # # #",bksl-nl "## ##",bksl-nl "# #",bksl-nl "####",bksl-nl "# #",bksl-nl "##",bksl-nl "#",bksl-nl]bksl-nlbksl-nlbksl-nl

Réponse

Le cas de base étant écrit, on réfléchit au cas général :

On demande par récursivité la base de hauteur h = n // 2.
On construit h premières lignes avec une ligne de la base, des espaces, et une autre copie de la ligne de base. Il y a 0 espaces au premier tour, puis 1, puis 2, ...
On construit les h lignes suivantes, simplement en ajoutant les lignes de la base.

🐍 Script Python

def sierpinski(n):
    """Renvoie une liste de ligne, un triangle de Sierpiński de hauteur n"""
    if n == 1:
        return ["#"]
    else:
        h = n // 2
        base = sierpinski(h)
        triangle = []
        for i in range(h):
            triangle.append(base[i] + " " * i + base[i])
        for i in range(h):
            triangle.append(base[i])
        return triangle

Triangle de Sierpiński ↩