⌂  Menu général
Support des 3 séances du chapitre « Diviser pour régner ». Il sert à la fois de support de projection en classe et de support de révision à la maison : cliquez sur « Voir la réponse » sous chaque exercice pour afficher le corrigé.
Le principe : DIVISER (scinder le problème en sous-problèmes plus petits, de même nature) → RÉGNER (résoudre chaque sous-problème, souvent récursivement) → COMBINER (assembler les solutions des sous-problèmes pour construire la solution finale).

Séance 1 — Comprendre le principe

Deux exemples simples, puis retour sur la dichotomie récursive

Durée : 2hDiviser / Régner / Combiner

1 recherche_max(tableau, g, d)

Retourne la valeur maximale de tableau[g..d], en le coupant en deux à chaque étape.

Voir la réponse 
def recherche_max(tableau, g, d):
    if g == d:
        return tableau[g]
    m = (g + d) // 2
    max_gauche = recherche_max(tableau, g, m)
    max_droite = recherche_max(tableau, m + 1, d)
    return max(max_gauche, max_droite)

2 puissance_rapide(x, n)

Calcule x^n avec un seul sous-problème deux fois plus petit à chaque étape paire.

Voir la réponse 
def puissance_rapide(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        moitie = puissance_rapide(x, n // 2)
        return moitie * moitie
    else:
        return x * puissance_rapide(x, n - 1)
puissance_rapide(2, 1024) ne nécessite que 10 appels (2^10 = 1024), contre 1024 multiplications pour une méthode naïve.

3 Retour sur la dichotomie

Version récursive « diviser pour régner » de la recherche dichotomique déjà connue.

Voir la réponse 
def recherche(t, v, g, d):
    if g > d:
        return None
    m = (g + d) // 2
    if t[m] < v:
        return recherche(t, v, m + 1, d)
    elif t[m] > v:
        return recherche(t, v, g, m - 1)
    else:
        return m

def recherche_dichotomique(t, v):
    return recherche(t, v, 0, len(t) - 1)
Séquence d'appels pour recherche_dichotomique([0,1,1,2,3,5,8,13,21], 12) :
recherche(t,12,0,8) → m=4 → recherche(t,12,5,8) → m=6 → recherche(t,12,7,8) → m=7, t[7]=13>12 → recherche(t,12,7,6) → g>d → None

🎯 Défi bonus

Compter les appels de la dichotomie

Ajouter un compteur global à recherche pour vérifier que le nombre d'appels reste proche de log2(n).

Voir la réponse 
compteur_appels = 0
def recherche_compte(t, v, g, d):
    global compteur_appels
    compteur_appels += 1
    if g > d:
        return None
    m = (g + d) // 2
    if t[m] < v:
        return recherche_compte(t, v, m + 1, d)
    elif t[m] > v:
        return recherche_compte(t, v, g, m - 1)
    else:
        return m

Séance 2 — Le tri fusion

Deux implémentations Python, traçage à la main, complexité O(n log n)

Durée : 2hTri fusionO(n log n)

📝 Traçage à la main

Fusion de B = [4, 12, 23, 35, 56] et C = [3, 32, 42, 57] :

Voir la réponse

3, puis 4, 12, 23, 32, 35, 42, 56, et enfin 57 (reste de C) → T = [3, 4, 12, 23, 32, 35, 42, 56, 57]

A Version par indices (avec sentinelle +∞)

Voir la réponse 
def tri_fusion(tab):
    def fusion(tab, p, q, r):
        n1 = q - p + 1
        n2 = r - q
        L = [0]*n1; R = [0]*n2
        for i in range(n1): L[i] = tab[p+i]
        for j in range(n2): R[j] = tab[q+j+1]
        L.append(float("inf")); R.append(float("inf"))
        i = j = 0
        for k in range(p, r+1):
            if L[i] <= R[j]:
                tab[k] = L[i]; i += 1
            else:
                tab[k] = R[j]; j += 1

    def tri_f(tab, p, r):
        if p < r:
            q = (p + r) // 2
            tri_f(tab, p, q)
            tri_f(tab, q+1, r)
            fusion(tab, p, q, r)

    tri_f(tab, 0, len(tab)-1)
    return tab

B Version par slicing

Voir la réponse 
def tri_fusion_slice(tab):
    n = len(tab)
    if n > 1:
        mil = n // 2
        L = tab[:mil]; R = tab[mil:]
        tri_fusion_slice(L); tri_fusion_slice(R)
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                tab[k] = L[i]; i += 1
            else:
                tab[k] = R[j]; j += 1
            k += 1
        while i < len(L):
            tab[k] = L[i]; i += 1; k += 1
        while j < len(R):
            tab[k] = R[j]; j += 1; k += 1

C Fusionner sans récursivité

Adaptation sans liste chaînée : fusion de deux listes Python déjà triées, avec une simple boucle while.

Voir la réponse 
def fusion_listes(B, C):
    resultat = []
    i = j = 0
    while i < len(B) and j < len(C):
        if B[i] <= C[j]:
            resultat.append(B[i]); i += 1
        else:
            resultat.append(C[j]); j += 1
    resultat.extend(B[i:])
    resultat.extend(C[j:])
    return resultat

🎯 Défi bonus

Compter les comparaisons du tri fusion

Vérifier expérimentalement que le nombre de comparaisons reste proche de n × log2(n).

Séance 3 — Autres applications

Quicksort, rotation d'image (exemple officiel), Karatsuba, retour sur Hanoï

Durée : 2hQuicksortRotation d'imageKaratsuba

1 tri_rapide(liste) — Quicksort

Pivot = premier élément, partition en inférieurs/supérieurs, recombinaison directe.

Voir la réponse 
def tri_rapide(liste):
    if len(liste) <= 1:
        return liste
    pivot = liste[0]
    reste = liste[1:]
    inferieurs = [x for x in reste if x <= pivot]
    superieurs = [x for x in reste if x > pivot]
    return tri_rapide(inferieurs) + [pivot] + tri_rapide(superieurs)
O(n log n) en moyenne, mais O(n²) dans le pire des cas (tableau déjà trié, avec ce choix de pivot).

2 Rotation d'une image d'un quart de tour

L'exemple cité par le programme officiel. Découpage en 4 quadrants, rotation récursive, permutation circulaire des quadrants — le tout à coût mémoire constant (rotation en place, sans copie complète de l'image).

Attention, la version ci-dessous contient un bug volontaire (relecture d'une valeur tout juste écrasée) :

for x1 in range(x, x + t):
    for y1 in range(y, y + t):
        px[x1, y1 + t] = px[x1, y1]
        px[x1 + t, y1 + t] = px[x1, y1 + t]   # relit une valeur déjà écrasée !
        px[x1 + t, y1] = px[x1 + t, y1 + t]
        px[x1, y1] = px[x1 + t, y1]
Voir la réponse (version corrigée) 
for x1 in range(x, x + t):
    for y1 in range(y, y + t):
        temp = px[x1, y1]
        px[x1, y1] = px[x1 + t, y1]
        px[x1 + t, y1] = px[x1 + t, y1 + t]
        px[x1 + t, y1 + t] = px[x1, y1 + t]
        px[x1, y1 + t] = temp
Une seule variable temporaire suffit à sauvegarder la valeur avant qu'elle ne soit écrasée : c'est cette économie de mémoire (pas de copie complète de l'image) que vise le commentaire officiel du programme.

3 Multiplication de Karatsuba

3 multiplications au lieu de 4 pour multiplier deux nombres à 2n chiffres.

Voir la réponse 
def karatsuba(x, y, n):
    if n <= 1:
        return x * y
    n //= 2
    a, b = x // 10**n, x % 10**n
    c, d = y // 10**n, y % 10**n
    ac = karatsuba(a, c, n)
    bd = karatsuba(b, d, n)
    abcd = karatsuba(a - b, c - d, n)
    return (ac * 10**(2*n)) + ((ac + bd - abcd) * 10**n) + bd

4 Retour éclair — Hanoï

Déjà vu au chapitre récursivité, reformulé ici en « diviser pour régner » : DIVISER (n-1 disques vers l'intermédiaire) + RÉGNER (trivial, un disque) + COMBINER (n-1 disques de l'intermédiaire vers la cible).

def deplace(a, b, c, k):
    if k > 0:
        deplace(a, c, b, k - 1)
        print("déplace de", a, "vers", b)
        deplace(c, b, a, k - 1)

def hanoi(n):
    deplace(1, 3, 2, n)
# Nombre total de déplacements : 2^n - 1