Correction : Applications la récursivité

Dessin de fractales

La courbe de Koch

Le motif de base

from turtle import *

def motif_koch(c: int)->None:
    down()
    forward(c)
    left(60)
    forward(c)
    right(120)
    forward(c)
    left(60)
    forward(c)

up()
backward(250)
motif_koch(300)
done()
			

La courbe de Koch

• cas général : on remplace le tracé d'un segment par le dessin ( = appels récursifs sur ce segment ) du motif de base
• cas de base : on trace simplement un segment !

from turtle import *

def courbe_koch(c: int, n: int)->None:

    if n == 0: # cas de base : on trace un segment
        down()
        forward(c)
    else : # ca général : on dessine récursivement le motif
        courbe_koch(c//3, n-1)
        left(60)
        courbe_koch(c//3, n-1)
        right(120)
        courbe_koch(c//3, n-1)
        left(60)
        courbe_koch(c//3, n-1)


speed(0)
n = 4

up()
backward(250)
courbe_koch(300, n)
done()
			

Le triangle de Sierpinski

Tracé d'un triangle

from turtle import *

def triangle_equi(c) :
    down()
    right(60)
    forward(c)
    right(120)
    forward(c)
    right(120)
    forward(c)
    right(60)
    
triangle_equi(200)
done()
			

Tracé du motif

Après avoir tracé les trois triangles ( en utilisant la fonction précédente ), il faut penser à replacer la tortue à son point et dans son orientation de départ :

from turtle import *

def triangle_equi(c) :
    down()
    right(60)
    forward(c)
    right(120)
    forward(c)
    right(120)
    forward(c)
    right(60)

def motif_sierpinski(c):
    triangle_equi(c//2)
    right(60)
    forward(c//2)
    left(60)
    triangle_equi(c//2)
    backward(c//2)
    triangle_equi(c//2)
    left(60)
    forward(c//2)
    right(60)

motif_sierpinski(200)
done()
			

Tracé du triangle de Sierpinski

Même principe que pour la courbe de Koch : dans le dessin du motif, on remplace le tracé d'un triangle par un appel récursif, dont le cas de base sera le tracé d'un triangle :

from turtle import *

def triangle_equi(c) :
    down()
    right(60)
    forward(c)
    right(120)
    forward(c)
    right(120)
    forward(c)
    right(60)
    done()

def triangle_sierpinski(c, n):

    if n == 0:
        triangle_equi(c)
    else :
        triangle_sierpinski(c//2, n-1)
        right(60)
        forward(c//2)
        left(60)
        triangle_sierpinski(c//2, n-1)
        backward(c//2)
        triangle_sierpinski(c//2, n-1)
        left(60)
        forward(c//2)
        right(60)

speed(0)
n = 3

triangle_sierpinski(200, 4)
done()
			

Le flocon de Koch

On reprend le tracé de la courbe de Koch, appliquée aux 4 côtés d'un carré :

from turtle import *

def courbe_koch(c: int, n: int)->None:

    if n == 0 :
        down()
        forward(c)
    else :
        courbe_koch(c//3, n-1)
        left(60)
        courbe_koch(c//3, n-1)
        right(120)
        courbe_koch(c//3, n-1)
        left(60)
        courbe_koch(c//3, n-1)

speed(0)
n = 4
up()
backward(250)

courbe_koch(200, n)
right(90)
courbe_koch(200, n)
right(90)
courbe_koch(200, n)
right(90)
courbe_koch(200, n)
right(90)
done()
			

Coloriage automatique

Remplissage d'un tableau

def remplit_recurs(t: list, x: int, y: int)->list:
    if (x-1 >= 0 and x+1 < 10 and y-1 >= 0 and y+1 < 10 and t[y][x] == 0):
        t[y][x] = 2
        remplit_recurs(t, x-1, y)
        remplit_recurs(t, x+1, y)
        remplit_recurs(t, x, y-1)
        remplit_recurs(t, x, y+1)

pixels = [[0,0,0,0,0,0,0,0,0,0],
    [0,0,1,1,1,0,0,0,0,0],
    [0,1,0,0,0,1,0,0,0,0],
    [0,1,0,0,0,1,0,0,0,0],
    [0,1,0,0,0,1,0,0,0,0],
    [0,1,0,0,0,0,1,0,0,0],
    [0,0,1,0,0,0,1,0,0,0],
    [0,0,1,0,0,0,1,0,0,0],
    [0,0,0,1,1,1,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0]]

remplit_recurs(pixels, 3, 4)
			

Attention aux indices dans un tableau de tableaux : l'abscisse x correspond au numéro de colonne ( 2^ème indice ), l'ordonnée y au numéro de ligne ( 1^er indice ).

Remplissage dans une image

from PIL import Image		

def colorie_recurs(t, x, y):
    largeur = len(t[0])
    hauteur = len(t)

    if (x-1 >= 0 and x+1 < largeur and y-1 >= 0 and y+1 < hauteur and t[y][x] >= 250):
        t[y][x] = 100
        colorie_recurs(t, x-1, y)
        colorie_recurs(t, x+1, y)
        colorie_recurs(t, x, y-1)
        colorie_recurs(t, x, y+1)
    
## Ouverture du fichier, et construction de la matrice des pixels
img = Image.open("minion.jpg")
pixels = list(img.getdata())
width, height = img.size
data = [pixels[i * width:(i + 1) * width] for i in range(height)]

## Remplissage récursif
colorie_recurs(data, 50, 100) # coordonnées de la 'graine" à expérimenter !

## Construction de l'image
img = Image.new("L" ,(len(data[0]), len(data))) 
data = [pixel for ligne in data for pixel in ligne]
img.putdata(data)

## Affichage
img.show(img)