Diviser pour régner

Trois questions à poser au problème

Comment découper l’entrée ? Comment résoudre chaque morceau ? Comment reconstruire la réponse globale ? Pour trier une liste, on peut la couper en deux, trier les moitiés puis les fusionner. Les sous-problèmes appartiennent au même type de tâche, mais portent sur des entrées plus petites.

Le cas de base doit être directement résolu : une liste vide ou contenant un seul élément est déjà triée. La réduction garantit que les appels atteignent ces bases. La combinaison n’est pas toujours une simple concaténation ; dans un tri, deux moitiés triées doivent être entrelacées selon leurs valeurs.

Voir le découpage dans une image

Une image carrée peut être représentée par une matrice de pixels. Pour une rotation d’un quart de tour horaire, le pixel situé en ligne i, colonne j devient celui de ligne j, colonne n-1-i. Sur une matrice 2×2 dont les lignes sont A B puis C D, on obtient C A puis D B.

On peut aussi découper une image de côté puissance de deux en quatre quadrants. Chaque quadrant doit tourner intérieurement ; les quadrants changent ensuite de position : bas gauche vers haut gauche, haut gauche vers haut droite, haut droite vers bas droite, bas droite vers bas gauche. Déplacer les quadrants sans tourner leur contenu ne suffit pas.

Pour visualiser le déplacement, gardez les indices à partir de zéro et choisissez d’abord les quatre coins. Le coin supérieur gauche (0,0) va en (0,n-1), le supérieur droit en (n-1,n-1). Ce repère distingue rotation horaire, rotation antihoraire et simple transposition.

Écrire une transformation de référence

Une version simple construit une nouvelle matrice. Elle permet de vérifier facilement les coordonnées attendues et de servir de référence à une version plus élaborée.

def tourner(image):
    n = len(image)
    resultat = [[None for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            resultat[j][n - 1 - i] = image[i][j]
    return resultat

Cette implémentation est itérative et utilise une mémoire supplémentaire proportionnelle au nombre de pixels. Elle illustre la transformation, pas à elle seule une implémentation récursive de diviser pour régner. Pour une version récursive, il faut rendre explicites les régions, les sous-appels et la combinaison.

Écrire une division récursive complète

Voici une fonction complète qui cherche le maximum d’une liste non vide de nombres. Chaque appel traite l’intervalle semi-ouvert [debut, fin[ ; ses deux moitiés sont strictement plus petites tant que leur longueur dépasse un. La combinaison compare les deux maxima.

def maximum(valeurs):
    assert len(valeurs) > 0

    def chercher(debut, fin):
        if fin - debut == 1:
            return valeurs[debut]
        milieu = (debut + fin) // 2
        gauche = chercher(debut, milieu)
        droite = chercher(milieu, fin)
        return max(gauche, droite)

    return chercher(0, len(valeurs))

Sur [4,9,2,7], les maxima des deux moitiés valent neuf et sept ; leur maximum vaut neuf. La méthode est récursive et divise réellement le problème, mais elle conserve un coût linéaire : chaque valeur doit être examinée. Une meilleure organisation n’implique donc pas toujours un meilleur ordre de coût.

Découper n’assure pas automatiquement une amélioration. Si chaque combinaison recopie beaucoup de données ou résout de nouveau le problème entier, le coût peut rester élevé. Le tri fusion réalise des fusions linéaires à chaque niveau ; cette structure explique son coût en n log n.

Pour la rotation, des échanges cycliques de quatre pixels permettent aussi une réalisation en place avec quelques variables temporaires. Le programme officiel évoque la rotation avec faible mémoire comme exemple ; il faut préciser si l’on compte la mémoire de la pile récursive. Un traitement en place n’implique pas automatiquement une mémoire auxiliaire totale constante lorsque la récursion conserve plusieurs niveaux d’appels.

Exemple suivi : deux niveaux de découpage

Dans une image 4×4 numérotée ligne par ligne de 1 à 16, le quadrant supérieur gauche contient [1,2] puis [5,6]. Sa rotation interne produit [5,1] puis [6,2]. Ce quadrant se déplace ensuite en haut à droite. Le quadrant inférieur gauche contient [9,10] puis [13,14] ; il devient [13,9] puis [14,10] et se déplace en haut à gauche. Les deux premières lignes complètes deviennent donc [13,9,5,1] et [14,10,6,2].

Ce calcul montre les deux responsabilités de la combinaison : déplacer les régions et préserver leur orientation correcte. Si les quadrants étaient déplacés sans tourner intérieurement, le pixel 13 n’arriverait pas au coin supérieur gauche. Pour une taille puissance de deux, on peut recommencer la subdivision jusqu’aux pixels seuls, dont la rotation interne ne change rien. La formule globale des coordonnées fournit un contrôle indépendant de cette récursion.

Exemple suivi : analyser le maximum divisé

Pour [4,9,2,7,5], l’intervalle [0,5[ se coupe en [0,2[ et [2,5[. Le premier maximum vaut 9 ; le second, calculé à partir de [2] et [7,5], vaut 7. Leur comparaison fournit 9. Une feuille de la décomposition contient exactement une valeur ; elle n’a pas besoin de comparaison pour donner son maximum.

Si deux parties contiennent a et b valeurs, leurs calculs demandent respectivement a-1 et b-1 comparaisons, puis la combinaison en ajoute une : a+b-1. On retrouve n-1 comparaisons pour n valeurs, comme une recherche séquentielle bien écrite. La division réduit la profondeur des appels par rapport à une récursion qui enlève une seule valeur, mais elle ne peut éviter d’examiner tous les candidats. Cette analyse apprend à séparer forme de la récursion et quantité de travail.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Confondre récursion et diviser pour régner.

La récursion est un mécanisme ; la méthode décrit une décomposition et une combinaison du problème.

Oublier de tourner l’intérieur des quadrants.

Le déplacement global des régions ne transforme pas leurs coordonnées internes.

Le prochain pas

• Le tri fusion
• La programmation dynamique

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.