A3 : Méthode Diviser pour Régner
Tri-Fusion
B. Tri-Fusion
5. Implémentation en Python
🐍 Script Python
def diviser(l):
"""
Fonction retournant les 2 moitiés de même longueur (+/- 1) d'une liste l
"""
long = len(l)
return l[:long//2], l[l//2:]
🐍 Script Python
def combiner(gauche,droite):
"""
Combine 2 listes triées gauche et droite en une liste triée.
"""
resultat = []
while len(gauche) > 0 and len(droite) > 0: # Tant que les listes gauche et droite ne sont pas vides
if gauche[0] < droite[0]: # Comparaison de la 1ère valeur de chaque liste
resultat.append(gauche[0]) # Et ajout au résultat de la plus petite
gauche = gauche[1:] # Suppression de la valeur ajoutée
else:
resultat.append(droite[0])
droite = droite[1:]
if len(gauche) == 0: # Dans le cas où
resultat = resultat + droite
else:
resultat = resultat + gauche
return resultat
🐍 Script Python
def tri_fusion(l):
if len(l)<=1:
return l
else:
gauche,droite = diviser(l)
return combiner(tri_fusion(gauche), tri_fusion(droite))
C. Rotation d'une image
🐍 Script Python
import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
def rotate(image):
n = len(image)
if n > 1:
temp = np.copy(image[n//2:, :n//2])
image[n//2:, :n//2] = rotate(image[n//2:, n//2:])
image[n//2:, n//2:] = rotate(image[:n//2, n//2:])
image[:n//2, n//2:] = rotate(image[:n//2, :n//2])
image[:n//2, :n//2] = rotate(temp)
return image
image = np.array(Image.open('R2D2.jpg'))
image = rotate(image)
plt.imshow(image)
En itératif
🐍 Script Python
import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
def rotate(image):
n = len(image)
result = np.copy(image)
for i in range(n//2):
for j in range(n//2):
# partie à compléter pour déplacer
# les pixels des quatre quadrants
return result
image = np.array(Image.open('vador.jpg'))
image = rotate(image)
plt.imshow(image)
