Diviser pour régner

La technique de programmation « diviser pour régner » consiste à diviser un problème complexe en plusieurs problèmes simples.

Les algorithmes utilisant cette méthode, s’écrivent naturellement de manière récursive.

Paradigme « diviser pour régner » en 3 étapes :

1. Diviser : on divise les données initiales en plusieurs sous-parties,
2. Régner : on résout récursivement chacun des sous-problèmes associés,
   (chaque sous-problème étant plus facile à résoudre que le problème précédent/source/parent)
3. Combiner : les solutions des sous-problèmes sont combinées afin d’obtenir la solution du problème d’origine.

Exemple : l’exponentiation rapide

La première façon de calculer une puissance \(x^n\) est de multiplier \(x\) par lui-même \(n\) fois. Cependant, il existe des méthodes bien plus efficaces :

Si on écrit \(n\) en base 2 :

\(n=a_02^0+a_12^1+\cdots+a_d2^d=\displaystyle\sum_{i=0}^d a_i2^i\)

avec \(a_i\in\left\{0,1\right\}\)

On a alors :

\(\Large{x^n=\displaystyle\prod_{i=0}^d (x^{2^i})^{a_i}}\)

Tri fusion

Le tri fusion d’une liste est basé sur le principe suivant : « plus une liste est petite, plus elle est facile à trier ».

La liste la plus facile à trier est la liste de taille 1, puisqu’elle est déjà triée !

Ainsi on divise la liste initiale jusqu’à ce que chaque sous-partie soit de taille 1,

puis on combine les listes 2 par 2 en les interclassant : on remplit une nouvelle liste en sélectionnant les éléments dans les deux premières, dans l’ordre croissant :

Activité

Écrire en Python une fonction fusion qui prend en paramètres une liste l, et 2 listes triées l1 et l2, la taille de l étant égale à la somme des tailles de l1 et l2. La fonction fusion modifie en place la liste l.

Aide

Correction

def fusion(l, l1, l2):
    i1 = i2 = 0
    for i in range(len(l)):
        if i1 <= len(l1)-1 and (i2 >= len(l2) or l1[i1] <= l2[i2]):
            l[i] = l1[i1]
            i1 += 1
        else:
            l[i] = l2[i2]
            i2 += 1

Compléter la fonction (récursive) tri_fusion proposée ci-dessous.

def tri_fusion(l):
    ...

    l1 = ...
    tri_fusion(l1)
    l2 = ...
    tri_fusion(l2)

    fusion(l, l1, l2)

Rotation  en place d’une image

Voir exercice Rotation d’une image