Le tracé de Sierpinski

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 6 — Fonctions récursives

É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$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.