Algorithmes de type "Diviser pour régner"
I. Définition, principes, cas d'utilisation
A. Définition
Un algorithme de type "diviser pour régner" est un algorithme qui, pour résoudre un problème de taille n, utilise la résolution d'un ou plusieurs problèmes de tailles inférieures à n. Il s'agit donc souvent d'algorithmes récursifs.
B. Caractéristiques générales
Ces algorithmes présentent en général les caractéristiques suivantes :
- Un algorithme récursif peut mener à un débordement de pile ;
- Ces algorithmes peuvent souvent s'avérer plutôt efficaces, mais cela peut fortement varier selon la décomposition qui est faite ;
- Ces algorithmes se prêtent souvent bien à la parallélisation.
II. Quelques exemples classiques
A. Exemples simples
Pour déterminer le maximum de 4 nombres, on peut passer par le maximum de 2 nombres, selon différentes façons d'ailleurs :
max(a, b, c, d) = max(max(a, b), max(c, d))max(a, b, c, d) = max (a, max(b, max (c,d)))
Pour déterminer le maximum d'une liste de taille n, on peut passer par le maximum d'une liste de taille n-1 :
max([a1, a2, ... an]) = max (a1, max([a2, ... an]))
B. Exemples plus complexes
Le problème des tours de Hanoi est un problème typique des problèmes avec une résolution récursive :
deplacer(n, A, B, C):
deplacer(n-1, A, C, B)
deplacer(1, A, B, C)
deplacer(n-1, C, B, A)
Exercice 1 : écrire un programme donnant la solution au problème des tours de Hanoi à n disques.
from sys import argv
def hanoi(n, depart, arrivee, intermediaire):
if n < 0 :
raise "Nombre de disque négatif !"
if n == 0 :
return
elif n == 1:
print("déplacer 1 disque de", depart, "à", arrivee)
else:
hanoi(n-1,depart, intermediaire, arrivee)
hanoi(1, depart, arrivee, intermediaire)
hanoi(n-1, intermediaire, arrivee, depart)
hanoi(int(argv[1]), "A", "B", "C")
D'autres algorithmes classiques reposent sur le principe "Diviser pour Régner" :
- Recherche par dichotomie dans une liste triée
- Certains algorithmes de tri (tri rapide, tri fusion)
Exercice 2 : écrire un programme de recherche dichotomique dans une liste triée
from sys import argv
def recherche(liste, valeur, debutZoneRecherche, finZoneRecherche):
"""
Fonction renvoyant l'indice d'une valeur si elle est présente dans liste,
et renvoyant -1 sinon
"""
if len(liste) == 0:
return -1
indiceMilieu = int((debutZoneRecherche+finZoneRecherche)/2)
valeurMediane = liste[indiceMilieu]
if valeurMediane == valeur:
return indiceMilieu
elif valeur < valeurMediane and indiceMilieu > debutZoneRecherche:
return recherche(liste, valeur, debutZoneRecherche, indiceMilieu-1)
elif valeur > valeurMediane and indiceMilieu < finZoneRecherche:
return recherche(liste, valeur, indiceMilieu+1, finZoneRecherche)
else:
return -1
listeTest = [1, 2, 4, 6, 7, 9, 10, 12, 16, 20]
print(listeTest)
print(recherche(listeTest, int(argv[1]), 0, len(listeTest)-1))
Exercice 3 : écrire un programme implantant un algorithme de tri rapide sur une liste
from random import randint
liste = []
for i in range(0, 30):
liste.append(randint(1,100))
print(liste)
def triRapide(liste):
"""
fonction qui initialise la fonction récursive de tri rapide d'une liste.
"""
trier(liste, 0, len(liste+1))
def trier(liste, indiceDebut, indiceFin):
"""
fonction récursive qui trie une liste en utilisant la méthode trie rapide.
"""
if (indiceFin <= indiceDebut):
return
indicePivot = randint(indiceDebut, indiceFin)
pivot = liste[indicePivot]
indicePivot = partitionner(liste, pivot, indiceDebut, indicePivot, indiceFin)
trier(liste, indiceDebut, indicePivot-1)
trier(liste, indicePivot+1, indiceFin)
def partitionner(liste, pivot, indiceDebut, indicePivot, indiceFin):
"""
fonction qui partitionne une liste en fonction d'un pivot en mettant à gauche
du pivot les éléments plus petits que le pivot et à droite les éléments plus
grand. L'indice du pivot est susceptible d'être modifié au cours du traitement ;
il est donc renvoyé par cette fonction.
"""
termine = False
indiceCourant = indiceDebut
while indiceCourant <= indiceFin:
if liste[indiceCourant] > pivot and indiceCourant < indicePivot:
liste[indicePivot] = liste[indiceCourant]
liste[indiceCourant] = liste[indicePivot-1]
liste[indicePivot-1] = pivot
indicePivot = indicePivot - 1
elif liste[indiceCourant] < pivot and indiceCourant > indicePivot:
liste[indicePivot] = liste[indiceCourant]
liste[indiceCourant] = liste[indicePivot+1]
liste[indicePivot+1] = pivot
indicePivot = indicePivot + 1
else:
indiceCourant = indiceCourant + 1
return indicePivot
triRapide(liste)
print(liste)
Exercice 4 : écrire un programme implantant un algorithme de tri fusion sur une liste
from random import randint
liste = []
for i in range(0, 30):
liste.append(randint(1,100))
print(liste)
def trier(liste):
"""
renvoie une version triée d'une liste en utilisant la méthode du tri fusion.
"""
taille = len(liste)
if taille <= 1:
return liste
milieu = int(taille/2)
return fusionner(trier(liste[:milieu]), trier(liste[milieu:]))
def fusionner(listeA, listeB):
"""
fonction qui fusionne 2 listes triées
"""
fusion = []
teteA = listeA[0]
teteB = listeB[0]
while (len(listeA) > 0 and len(listeB) > 0):
if teteA < teteB:
fusion.append(teteA)
listeA.pop(0)
if len(listeA) > 0:
teteA = listeA[0]
else:
fusion.append(teteB)
listeB.pop(0)
if len(listeB) > 0:
teteB = listeB[0]
fusion = fusion + listeA + listeB
return fusion
resultat = trier(liste)
print(resultat)