Python, turtle et un arbre fractal

  • Dernière modification de la publication :6 septembre 2020
  • Temps de lecture :7 min de lecture
  • Commentaires de la publication :1 commentaire

Loading

Utiliser Python, notamment module turtle, pour construire un arbre fractal, c’est possible ! Je ne suis pas trop fan de ce module (car très lent), mais il faut bien avouer que le résultats est sympatoche… comme disent les jeunes !

Je me suis donc mis à la recherche d’un code donnant un tel schéma pour tenter de me familiariser avec le module. J’avais une idée bien précise : celle d’un arbre fractal, que j’avais vu quelque part.

Après quelques recherches, je suis enfin tombé sur le code suivant (que je me suis permis de commenter):

from turtle import *

angle = 30
color('#3f1905')

def arbre(n,longueur):
    if n==0:
        color('green')
        forward(longueur) # avance
        backward(longueur) # recule
        color('#3f1905')
    else:
        width(n)
        forward(longueur/3) #avance
        left(angle) # tourne vers la gauche de angle degrés
        arbre(n-1,longueur*2/3)
        right(2*angle) # tourne vers la droite de angle degrés
        arbre(n-1,longueur*2/3)
        left(angle) # tourne vers la gauche de angle degrés
        backward(longueur/3) # recule

hideturtle() # cache la tortue
up() # lève le stylo
right(90) # tourne de 90 degrés vers la droite 
forward(300) # avance de 300 pixels
left(180) # fait un demi-tour
down() # pose le stylo
arbre(11,700) # exécute la macro
showturtle() # affiche la tortue
mainloop()

qui donne ceci:

python turtle arbre fractal
Arbre fractal réalisé avec Python avec un angle de 30°

Mais attention… Ce magnifique dessin Python obtenu avec turtle représentant un arbre fractal met un certain temps avant d’être fini (par exemple, sur mon ordinateur 16 Mo de RAM, processeur Intel Core i5, il met une vingtaine de minutes… arf !).

Si on modifie l’angle (disons pour le mettre à 50°), on obtient ceci:

python turtle arbre fractal
Arbre fractal réalisé avec Python avec un angle de 50°

Et avec un angle de 110° :

python turtle arbre fractal
Arbre fractal réalisé avec Python avec un angle de 110°

N’est-il pas choupinou ? 🙂

Vous pouvez remarquer dans le code la fonction récursive : c’est une notion que l’on verra en NSI (nouveau lycée)… mais prévue en cycle de maturité (en Terminale quoi !)… même si je n’ai pas pu résister à l’envie d’en mettre dans mon livre d’exercices corrigés qui sortira en version papier pour la rentrée 2019.

Une fonction récursive est une fonction qui fait appel à elle-même dans sa définition. On retrouve ce genre de fonction par exemple pour calculer le pgcd de deux nombres:

def pgcd(a,b):
    if b==0:
        return a
    else:
        r=a%b
        return pgcd(b,r)
 
print(pgcd(56,42))

Ici, la récursivité s’appuie sur la propriété du pgcd qui stipule que:$$\text{pgcd}(a,b)=\text{pgcd}(b,r)$$où \(a = bq + r,\ 0\leq r < b\).

Les mathématiques sont donc très importantes pour construire des algorithmes (et par suite des programmes) performants. En effet, on aurait très bien pu calculer le pgcd de la manière suivante:

def pgcd(a,b):
    while b<>0:
        r=a%b
        a,b=b,r
    return a
 
print(pgcd(56,42))

Pour comparer deux algorithmes, on parle souvent de complexité. Cet article ne parle pas de cette notion, mais sachez tout de même que la complexité d’une fonction récursive est donnée par une suite arithmético-géométrique. Dans la fonction pgcd, il y a 2 instructions élémentaires (le test sur b et l’affectation de r). La complexité \(C_n\) est donc égale à \(2+C_{n-1}\), où \(C_{n-1}\) est celle de la fonction pgcd(b,r). On démontre alors que la complexité de la fonction récursive est de l’ordre de O(n) [complexité linéaire]. En fait, la complexité est linaire dans le pire des cas (quand a et b sont deux nombres successifs de la suite de Fibonacci), car dans les autres cas, la complexité est logarithmique [O(ln(n))].

L’évaluation moyenne de la complexité de l’algorithme d’Euclide version récursive est assez compliquée. Le nombre d’appels moyen de la fonction pgcd est:$$\frac{12\ln(2\ln n)}{\pi^2}+1,47.$$

http://imss-www.upmf-grenoble.fr/prevert/Prog/Complexite/euclide.html

La complexité de l’algorithme non récursif est quasi-identique à sa version récursive.


La version récursive de l’algorithme d’Euclide est peut-être un peu plus facile à écrire que la version itérative. Les deux versions ont fondamentalement la même complexité, avec un petit avantage à la version itérative, car l’appel d’une fonction n’est pas gratuit.

https://www.labri.fr/perso/betrema/deug/poly/euclide.html

Mais là, je m’égare… Saint-Lazare !

0 0 votes
Évaluation de l'article
S’abonner
Notification pour
guest
1 Commentaire
Le plus ancien
Le plus récent Le plus populaire
Commentaires en ligne
Afficher tous les commentaires
Nicolas Patrois

Pour la tortue qui dessine des approximations de fractales, j’utilise une autre approche : les L-systèmes.
On va prendre comme exemple le triangle de Sierpinski.
On part d’une chaîne de caractères, par exemple « A » et de règles de substitutions.
Ainsi, on remplace « A » par « B-A-B », »-« : »- » et « B » par « A+B+A », »+ »: »+ ». On obtient successivement « B-A-B » puis « A+B+A-B-A-B-A+B+A », etc.
Ensuite, on donne une signification à chaque lettre, par exemple « A » veut dire avancer, « B » aussi, « + » veut dire tourner de 60° à gauche et « – » tourner à droite de 60°… et ne pas oublier de diminuer la taille du segment tracé.
Le script contient d’autres exemples.

from turtle import *

def remplace(chaine,regles):
  return ''.join(regles[caractere] for caractere in chaine)

def dessin(position=(0,0),rang=5,
           longueur=100,angle=0,
           couleur=(0,0,0),
           vitesse=10):
  reset()
  speed(vitesse)
  penup()
  color(couleur)
  goto(*position)
  left(angle)
  pendown()

# Courbe du C
#  regles={"F":"+F-F+",
#          "+":"+","-":"-"}
#  red=0.5**.05
#  longueur*=red**rang
#  mouvements={"F":"forward(%f)"%longueur,
#              "+":"left(45)",
#              "-":"right(90)"}
#  chaine="F"

# Courbe de Peano
#  regles={"F":"F-F+F+F+F-F-F-F+F",
#          "+":"+","-":"-"}
#  red=1/3
#  longueur*=red**rang
#  mouvements={"F":"forward(%f)"%longueur,
#              "+":"left(90)",
#              "-":"right(90)"}
#  chaine="F"

# Courbe de Von Koch
#  regles={"A":"A+A-A+A",
#          "+":"+","-":"-"}
#  red=1/3
#  longueur*=red**rang
#  chaine="A"
#  mouvements={"A":"forward(%f)"%longueur,
#              "+":"right(60)",
#              "-":"left(120)"}

# Courbe de Sierpinski
  regles={"A":"B-A-B","-":"-",
          "B":"A+B+A","+":"+"}
  red=0.5
  longueur*=red**rang
  chaine="A"
  mouvements={"A":"forward(%f)"%longueur,
              "B":"forward(%f)"%longueur,
              "+":"left(60)",
              "-":"right(60)"}

# Courbe du dragon
#  regles={"A":"AGB","B":"CGB",
#        "C":"AGD","D":"CGD",
#        "G":"G"}
#  chaine="A"
#  red=0.5**0.5
#  longueur*=red**rang

#  mouvements={"A":"right(90)",
#            "B":"right(90)",
#            "C":"left(90)",
#            "D":"left(90)",
#            "G":"forward(%f)"%longueur}
# forward(longueur) se plaint que longueur est inexistant

  for _ in range(rang):
    chaine=remplace(chaine,regles)

  for mot in chaine:
    exec(mouvements[mot])
  mainloop()

Ce script fonctionne sur une Numworks.