Feuille d’exercices 4 – avancé

Contenu

Feuille d’exercices 4 – avancé#

Avertissement

Ces exercices sont prévus pour les étudiant·e·s ayant déjà réussi la feuille d’exercices « classiques ».

Exercice 5 : décomposition en binaire#

Question 1 : Exécuter les instructions bin(2) et bin(11). Quel type d’objet obtient-on ? Que contient-il ?

print(bin(2))
bin(11)

0b10

'0b1011'

On obtient une chaîne de caractères commençant par '0b', et terminant par les coefficients de la décomposition de ces entiers en base \(2\), dans l’ordre décroissant de poids.

Question 2 : Stocker dans une variable x la valeur de bin(11), puis entrer la commande int(x, 2). Qu’obtient-on ?

x = bin(11)
int(x, 2)

On retrouve l’entier donné en paramètre de bin.

Question 3 : Écrire une fonction decomposition(n) qui prend en entrée un entier n positif ou nul, et qui retourne une liste formée des coefficients de la décomposition de n en base \(2\).

Par exemple, pour l’entier \(n = 13\) qui s’écrit \(n = 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0\), la fonction retournera la liste [1, 1, 0, 1].

def decomposition(n):
    if n < 2:
        return [n]
    L = decomposition(n//2)
    L.append(n%2)
    return L
    
decomposition(13)

[1, 1, 0, 1]

Question 4 : Écrire une fonction my_bin(n) qui copie le fonctionnement de bin. Puis, vérifiez qu’elle est correcte en testant si my_bin(n) égale bin(n) pour les \(1000\) premiers entiers naturels n.

def my_bin(n):
    res = "0b"
    L = decomposition(n)
    for d in L:
        if d == 0:
            res += "0"
        else:
            res += "1"
    return res

all(my_bin(n) == bin(n) for n in range(1000))

True

Exercice 6 : flocon de Koch#

Le but de cet exercice est de programmer une fonction qui dessine le flocon de Koch, comme sur l’image ci-dessous.

Le flocon de Koch est une fractale, c’est-à-dire une figure similaire à elle-même à n’importe quelle échelle. On peut le construire de manière itérative, comme l’illustre par la série d’images suivantes :

Les images précédentes représentent des parties d’un flocon de Koch d’ordre \(0\), \(1\), \(2\) et \(3\). L’ordre correspond au nombre d’itérations dans la construction de la figure.

Pour obtenir le flocon d’ordre \(n\) à partir du flocon d’ordre \(n-1\), l’idée est d’opérer une floraison sur chacun des segments du flocon d’ordre \(n-1\). On fait fleurir un segment par le procédé suivant :

on partage le segment en 3 parties de longueur égale ;
on préserve à l’identique les deux sous-segments extérieurs ;
on supprime le sous-segment central, que l’on remplace par deux segments qui auraient formé un triangle équilatéral avec le sous-segment supprimé.

Mathématiquement, si le segment de base a pour extrémités \(A\) et \(B\), alors la forme obtenue après floraison est définie par les \(5\) points suivants :

\(A\)
\(M_1 = A + \frac{1}{3} \overrightarrow{AB}\)
\(M_2 = A + \frac{1}{2} \overrightarrow{AB} + \frac{\sqrt{3}}{6} {\rm rot}(\overrightarrow{AB})\)
\(M_3 = A + \frac{2}{3} \overrightarrow{AB}\)
\(B\)

où \({\rm rot}(\overrightarrow{AB})\) est la rotation de \(+ 90°\) du vecteur \(\overrightarrow{AB}\).

L’objectif des premières questions de cet exercice est d’écrire les fonctions auxiliaires qui permettront ensuite de construire le flocon. Dans tout l’exercice, on représentera les points du plan par leurs coordonnées cartésiennes. Un point du plan sera donc un couple \([x, y]\) de nombres.

Question 1 : Écrire une fonction vecteur(A, B) qui prend en entrée deux points du plan A et B et qui retourne les coordonnées du vecteur \(\overrightarrow{AB}\).

Par exemple, vecteur([1, 0], [3, -1]) doit retourner la liste [2, -1].

def vecteur(A, B):
    return [ B[0]-A[0], B[1]-A[1] ]

print(vecteur([1, 0], [3, -1]))

[2, -1]

Question 2 : Écrire une fonction rotation(u) qui prend en entrée un vecteur u et qui retourne le vecteur obtenu par la rotation de \(+90\) degrés de u autour de l’origine.

Par exemple, rotation([2, 3]) doit retourner la liste [-3, 2].

def rotation(u):
    return [-u[1], u[0]]

print(rotation([2, 3]))

[-3, 2]

Question 3 : Écrire une fonction translation(A, u, x) qui prend en entrée un point A, un vecteur directeur u et un nombre flottant x et qui retourne les coordonnées du point \(A + x u\).

Par exemple, translation([2, 3], [-1,1], 2) doit retourner la liste [0, 5].

def translation(A, u, x):
    return [A[0] + x*u[0], A[1] + x*u[1]]

print(translation([2, 3], [-1,1], 2))

[0, 5]

Question 4 : Écrire une fonction etape_floraison(A, B) qui prend en entrée deux points du plan A et B, et qui calcule la liste des \(5\) points correspondant à une étape de floraison du flocon de Koch entre les points A et B.

Par exemple, pour \(A = (0, 0)\) et \(B = (1, 1)\), on doit obtenir une liste avec des valeurs approchées suivantes :

[ [0,0], [0.3333, 0.3333], [0.2113, 0.7886], [0.6666, 0.6666], [1,1] ]

from math import sqrt

def etape_floraison(A, B):
    u = vecteur(A, B)
    v = rotation(u)
    return [A, translation(A, u, 1.0/3), translation(translation(A, u, 1.0/2), v, sqrt(3)/6), translation(A, u, 2.0/3), B]
    
etape_floraison([0,0], [1,1])

[[0, 0],
 [0.3333333333333333, 0.3333333333333333],
 [0.21132486540518713, 0.7886751345948129],
 [0.6666666666666666, 0.6666666666666666],
 [1, 1]]

Question 5 : Écrire une fonction flocon_koch(N, L) qui prend en entrée un ordre N et une liste de points initiaux L, et qui retourne la liste des coordonnées des points du flocon de Koch à l’ordre \(N\). Dans l’exemple donné au début de l’exercice, la liste \(L\) correspond aux points du premier segment (typiquement, \([ (0,0), (1,0) ]\)).

Par exemple, pour \(N = 2\) et \(L = [ (0,0), (1,0) ]\), on doit obtenir la liste avec les valeurs approchées suivantes :

[
 [0,0], [0.1111, 0.0], [0.1666, 0.0962], [0.3333, 0.0], [0.3333, 0.0],
 [0.3888, 0.0962], [0.3333, 0.1925], [0.4444, 0.1925], [0.5, 0.2886],
 [0.5555, 0.1925], [0.6666, 0.1925], [0.6111, 0.0962], [0.6666, 0.0],
 [0.7777, 0.0], [0.8333, 0.0962], [0.8888, 0.0], [1.0, 0.0]
]

def flocon_koch(N, L):
    for j in range(N):
        R = []
        n = len(L)
        for i in range(n-1):
            R += etape_floraison(L[i], L[i+1])
            R.pop()
        L = R + [L[n-1]]
    return L

segment = [ [0,0], [1,0] ]
flocon_koch(2, segment)

[[0, 0],
 [0.1111111111111111, 0.0],
 [0.16666666666666666, 0.09622504486493762],
 [0.2222222222222222, 0.0],
 [0.3333333333333333, 0.0],
 [0.3888888888888889, 0.09622504486493762],
 [0.3333333333333333, 0.19245008972987526],
 [0.4444444444444444, 0.19245008972987523],
 [0.5, 0.28867513459481287],
 [0.5555555555555556, 0.19245008972987526],
 [0.6666666666666666, 0.19245008972987523],
 [0.611111111111111, 0.09622504486493763],
 [0.6666666666666666, 0.0],
 [0.7777777777777778, 0.0],
 [0.8333333333333333, 0.09622504486493763],
 [0.8888888888888888, 0.0],
 [1, 0]]

Question 6 : Afficher le flocon de Koch d’ordre \(6\), dans un graphe sans axe (grâce à la commande plt.axis('off')) et sans dilatation des axes (grâce à la commande plt.axis('equal')).

Pour afficher le flocon on pourra :

ou bien partir du segment L = [ [0,0], [1,0] ] comme dans la question précédente
ou bien construire le flocon complet, en choisissant comme points initiaux la liste

triangle = [ [0,0], [1,0], [0.5, -sqrt(3)/2], [0,0] ]

import matplotlib.pyplot as plt

triangle = [ [0,0], [1,0], [0.5, -sqrt(3)/2], [0,0] ]
R = flocon_koch(6, triangle)
X = [m[0] for m in R]
Y = [m[1] for m in R]

plt.plot(X, Y, color='red', linewidth=0.5)
plt.axis('off')
plt.axis('equal')
plt.show()

../_images/246076dc14944e9395e3de17417c649bc541d56af3cebbcf4174eff7d9227091.png