Numérique et sciences informatiques (NSI) · Terminale

Exercices : la méthode « diviser pour régner »

22 exercices avec correction détaillée, en 3 séries. Aucune inscription : ta progression reste sur ton appareil.

ULUMINE · Numérique et sciences informatiques (NSI) · Terminale

La méthode « diviser pour régner » — S’entraîner

Feuille d’exercices

Prénom : ……………………………Date : ……………………Score : ……… / 8

Les fonctions dicho, fusion et tri_fusion sont celles du cours.

Exercice 1 — Coche la bonne réponse.
Quelles sont, dans l’ordre, les trois étapes de la méthode « diviser pour régner » ?
- Trier, chercher, afficher
- Diviser, régner, combiner
- Combiner, diviser, régner
- Diviser, trier, rechercher
Exercice 2 — Coche la bonne réponse.
Que renvoie fusion([1, 4, 9], [2, 3, 10]) ?
- [1, 4, 9, 2, 3, 10]
- [1, 2, 3, 4, 9, 10]
- [1, 2, 4, 3, 9, 10]
- [10, 9, 4, 3, 2, 1]

Exercice 3

Combien de comparaisons A[i] <= B[j] effectue l’appel fusion([1, 4, 9], [2, 3, 10]) ?

def fusion(A, B):
    """Fusionne deux listes triées en une liste triée."""
    R = []
    i = 0
    j = 0
    while i < len(A) and j < len(B):
        if A[i] <= B[j]:
            R.append(A[i])
            i = i + 1
        else:
            R.append(B[j])
            j = j + 1
    return R + A[i:] + B[j:]

def tri_fusion(L):
    if len(L) <= 1:
        return L
    m = len(L) // 2
    return fusion(tri_fusion(L[:m]), tri_fusion(L[m:]))

Python

Écris tes calculs :

Réponse : ………………

Exercice 4

Combien d’appels à dicho sont effectués pour rechercher 40 dans L = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] avec dicho(L, 40, 0, 9) ?

def dicho(L, x, g, d):
    """Indice de x dans la liste triée L, entre les indices g et d, ou -1."""
    if g > d:
        return -1
    m = (g + d) // 2
    if L[m] == x:
        return m
    if L[m] < x:
        return dicho(L, x, m + 1, d)
    return dicho(L, x, g, m - 1)

Python

Écris tes calculs :

Réponse : ………………

Exercice 5 — Coche « Vrai » ou « Faux ».
Le tri fusion a, dans le pire des cas, un coût de l’ordre de n log₂(n) pour une liste de n éléments.
VraiFaux
Exercice 6
Combien de fois faut-il diviser 1 024 par 2 pour obtenir 1 ?
Écris tes calculs :
Réponse : ………………
Exercice 7 — Complète les trous.
Complète la description du tri fusion.
On la liste en deux moitiés, on trie chacune par un appel , puis on les deux moitiés triées.
Exercice 8
Écris une fonction récursive maximum(L, g, d) qui renvoie le plus grand élément de L entre les indices g et d (inclus), en appliquant la méthode diviser pour régner.

ulumine.com — exercices corrigés gratuits

ULUMINE · Numérique et sciences informatiques (NSI) · Terminale

La méthode « diviser pour régner » — S’entraîner

Corrigé détaillé — pour les parents et les enseignants

Exercice 1
Réponse : Diviser, régner, combiner
On divise le problème, on résout (règne sur) les sous-problèmes récursivement, puis on combine leurs solutions.
Exercice 2
Réponse : [1, 2, 3, 4, 9, 10]
La fusion prend à chaque étape le plus petit des deux premiers éléments restants : 1, 2, 3, 4, 9, puis le 10 restant.
Exercice 3
Réponse : 5
On compare 1/2, 4/2, 4/3, 4/10, 9/10. La liste A est alors épuisée : le 10 est ajouté sans comparaison.
Exercice 4
Réponse : 5
On suit les bornes g et d.
1. (0, 9) : m = 4, 16 < 40 → (5, 9)
2. m = 7, 56 > 40 → (5, 6)
3. m = 5, 23 < 40 → (6, 6)
4. m = 6, 38 < 40 → (7, 6)
5. g > d : on renvoie −1. Total : 5 appels.
Exercice 5
Réponse : Vrai
Il y a environ log₂(n) niveaux de découpage et chaque niveau demande de l’ordre de n opérations de fusion.
Exercice 6
Réponse : 10
1 024 = 2¹⁰ : il faut 10 divisions par 2. C’est log₂(1 024) = 10, l’ordre de grandeur du nombre d’étapes d’une dichotomie sur 1 024 éléments.
Exercice 7
Réponse : divise · récursif · fusionne
Ce sont les trois étapes : diviser, régner (récursivement), combiner (fusionner).
Exercice 8
Exemple de réponse : Cas de base : si g == d, il n’y a qu’un élément, on renvoie L[g]. Sinon on calcule m = (g + d) // 2, le maximum de la partie gauche (g à m) et celui de la partie droite (m + 1 à d), puis on renvoie le plus grand des deux.
Les trois étapes apparaissent clairement : découpage au milieu, deux appels récursifs, comparaison des résultats.
```
def maximum(L, g, d):
    if g == d:
        return L[g]
    m = (g + d) // 2
    return max(maximum(L, g, m), maximum(L, m + 1, d))
```
Python
- Cas de base pour un seul élément.
- Découpage au milieu sans chevauchement ni oubli.
- Combinaison avec max (ou une comparaison).

Les fonctions dicho, fusion et tri_fusion sont celles du cours.

Exercices corrigés : 0 / 8

Exercice 1 sur 8
QCM
Quelles sont, dans l’ordre, les trois étapes de la méthode « diviser pour régner » ?
Choisis une réponse
Trier, chercher, afficherDiviser, régner, combinerCombiner, diviser, régnerDiviser, trier, rechercher
Aide d’ULU pour cet exercice
Exercice 2 sur 8
QCM
Que renvoie fusion([1, 4, 9], [2, 3, 10]) ?
Choisis une réponse
[1, 4, 9, 2, 3, 10][1, 2, 3, 4, 9, 10][1, 2, 4, 3, 9, 10][10, 9, 4, 3, 2, 1]
Aide d’ULU pour cet exercice

Exercice 3 sur 8

Calcul

Combien de comparaisons A[i] <= B[j] effectue l’appel fusion([1, 4, 9], [2, 3, 10]) ?

def fusion(A, B):
    """Fusionne deux listes triées en une liste triée."""
    R = []
    i = 0
    j = 0
    while i < len(A) and j < len(B):
        if A[i] <= B[j]:
            R.append(A[i])
            i = i + 1
        else:
            R.append(B[j])
            j = j + 1
    return R + A[i:] + B[j:]

def tri_fusion(L):
    if len(L) <= 1:
        return L
    m = len(L) // 2
    return fusion(tri_fusion(L[:m]), tri_fusion(L[m:]))

Python

Aide d’ULU pour cet exercice

Exercice 4 sur 8
Calcul
Combien d’appels à dicho sont effectués pour rechercher 40 dans L = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] avec dicho(L, 40, 0, 9) ?
```
def dicho(L, x, g, d):
    """Indice de x dans la liste triée L, entre les indices g et d, ou -1."""
    if g > d:
        return -1
    m = (g + d) // 2
    if L[m] == x:
        return m
    if L[m] < x:
        return dicho(L, x, m + 1, d)
    return dicho(L, x, g, m - 1)
```
Python
Ta réponse
Aide d’ULU pour cet exercice
Exercice 5 sur 8
Vrai ou faux
Le tri fusion a, dans le pire des cas, un coût de l’ordre de n log₂(n) pour une liste de n éléments.
Vrai ou faux ?
VraiFaux
Aide d’ULU pour cet exercice
Exercice 6 sur 8
Calcul
Combien de fois faut-il diviser 1 024 par 2 pour obtenir 1 ?
Ta réponse
Aide d’ULU pour cet exercice
Exercice 7 sur 8
Texte à trous
Complète la description du tri fusion.
On la liste en deux moitiés, on trie chacune par un appel , puis on les deux moitiés triées.
Aide d’ULU pour cet exercice
Exercice 8 sur 8
Question ouverte
Écris une fonction récursive maximum(L, g, d) qui renvoie le plus grand élément de L entre les indices g et d (inclus), en appliquant la méthode diviser pour régner.
Ta réponse
Aide d’ULU pour cet exercice

À découvrir aussi

Terminale · Numérique et sciences informatiques (NSI)

La récursivité

Fonctions récursives en Python : cas de base, appels récursifs, pile d’appels, terminaison et comparaison avec l’itératif. Cours et exercices de NSI Terminale.

Terminale · Numérique et sciences informatiques (NSI)

La programmation orientée objet

Classes, objets, attributs et méthodes en Python : constructeur __init__, self, interface et références. Cours et exercices de programmation objet en NSI Terminale.

Terminale · Numérique et sciences informatiques (NSI)

Listes, piles, files et dictionnaires

Interface et implémentation des structures linéaires : listes chaînées, piles (LIFO), files (FIFO) et dictionnaires en Python. Cours et exercices de NSI Terminale.