Le tracé de Sierpinski

Fonctions récursives · niveau 2

Énoncé

Le triangle de Sierpinski de niveau $n$ est constitué de 3 triangles de Sierpinski de niveau $n - 1$ disposés en triangle. Implémenter ce tracé à l'aide du module turtle (cas de base : tracé d'un triangle équilatéral). Compter le nombre de triangles dessinés et le nombre d'appels.

Corrigé

Le point critique est d'assurer la restauration de la position et de l'orientation de la tortue après chaque appel :

import turtle

def sierpinski(longueur: float, n: int) -> None:
    if n == 0:
        for _ in range(3):
            turtle.forward(longueur)
            turtle.left(120)
        return
    sierpinski(longueur / 2, n - 1)      # Triangle en bas à gauche
    turtle.forward(longueur / 2)
    sierpinski(longueur / 2, n - 1)      # Triangle en bas à droite
    turtle.backward(longueur / 2)
    turtle.left(60)
    turtle.forward(longueur / 2)
    turtle.right(60)
    sierpinski(longueur / 2, n - 1)      # Triangle du haut
    turtle.left(60)
    turtle.backward(longueur / 2)
    turtle.right(60)

Le nombre de triangles élémentaires tracés est de $3^{n}$ , et le nombre total d'appels vaut $\frac{3 ^{n + 1} - 1}{2}$ . La complexité temporelle est exponentielle, mais la profondeur de pile n'est que de $n + 1$ .

Énoncé

Corrigé

Exercices semblables