TP - Diviser pour régner & Programmation dynamique

Terminale NSI

Ce TP est sur Capytale

---

Partie 1 — Diviser pour régner

Exercice 1 — Recherche dichotomique

Implémenter la recherche dichotomique dans un tableau trié. La fonction renvoie l’indice de la valeur cherchée, ou -1 si elle est absente.

def recherche_dicho(tableau, valeur):
    """
    Recherche valeur dans tableau (trié) par dichotomie.
    Renvoie l'indice de valeur dans tableau, ou -1 si absente.
    """
    gauche = 0
    droite = len(tableau) - 1

    while gauche <= droite:
        # Calculer l'indice du milieu
        milieu = ...

        # Si on a trouvé la valeur, renvoyer son indice
        if tableau[milieu] == valeur:
            ...

        # Si la valeur cherchée est plus grande, chercher dans la moitié droite
        elif tableau[milieu] < valeur:
            ...

        # Sinon, chercher dans la moitié gauche
        else:
            ...

    # Si on sort de la boucle, la valeur est absente
    return -1


# Tests
t = [2, 5, 8, 12, 16, 23, 38, 42, 55, 72, 91]
assert recherche_dicho(t, 42) == 7
assert recherche_dicho(t, 2)  == 0
assert recherche_dicho(t, 91) == 10
assert recherche_dicho(t, 30) == -1
assert recherche_dicho(t, 100) == -1
print("Tous les tests sont passés !")

Exercice 2 — Compter les occurrences par diviser pour régner

Implémenter le comptage d’occurrences d’un élément dans une liste, en utilisant la stratégie « diviser pour régner » : couper la liste en deux, compter dans chaque moitié, additionner.

def compter_occurrences(liste, x):
    """
    Compte le nombre d'occurrences de x dans liste,
    par la méthode diviser pour régner.
    """
    # Cas de base : liste vide → 0 occurrence
    ...

    # Cas de base : un seul élément → 1 si c'est x, 0 sinon
    ...

    # Diviser : trouver le milieu et couper la liste
    milieu = ...
    gauche = ...
    droite = ...

    # Régner : compter récursivement dans chaque moitié
    ...

    # Combiner : additionner les deux résultats
    ...


# Tests
assert compter_occurrences([3, 7, 3, 1, 3, 8, 3, 2], 3) == 4
assert compter_occurrences([3, 7, 3, 1, 3, 8, 3, 2], 5) == 0
assert compter_occurrences([], 3) == 0
assert compter_occurrences([1], 1) == 1
print("Tous les tests sont passés !")

Exercice 3 — Vérifier si une liste est triée

Implémenter une fonction qui vérifie si une liste est triée par ordre croissant, en utilisant « diviser pour régner » :

• Une liste d’un seul élément est toujours triée.
• Une liste plus longue est triée si : la moitié gauche est triée, la moitié droite est triée, et le dernier élément de la moitié gauche est inférieur ou égal au premier élément de la moitié droite.

def est_triee(liste):
    """
    Renvoie True si liste est triée par ordre croissant, False sinon.
    Utilise la méthode diviser pour régner.
    """
    # Cas de base : liste vide ou d'un seul élément → toujours triée
    ...

    # Diviser : couper la liste en deux
    milieu = ...
    gauche = ...
    droite = ...

    # Régner : vérifier récursivement chaque moitié
    ...

    # Combiner : les deux moitiés sont triées ET la jonction est correcte
    # (le dernier élément de gauche <= premier élément de droite)
    ...


# Tests
assert est_triee([1, 3, 5, 7, 9]) == True
assert est_triee([1, 3, 2, 7, 9]) == False
assert est_triee([]) == True
assert est_triee([5]) == True
assert est_triee([1, 1, 2, 3]) == True   # égalité autorisée
print("Tous les tests sont passés !")

Exercice 4 — Somme des éléments d’une liste

Implémenter le calcul de la somme d’une liste par diviser pour régner, puis mesurer expérimentalement sa complexité.

def somme_diviser(liste):
    """
    Calcule la somme des éléments de liste par diviser pour régner.
    """
    # Cas de base : liste vide
    ...

    # Cas de base : un seul élément
    ...

    # Diviser, régner, combiner
    milieu = len(liste) // 2
    ...


# Tests
assert somme_diviser([1, 2, 3, 4, 5]) == 15
assert somme_diviser([]) == 0
assert somme_diviser([42]) == 42
print("Tous les tests sont passés !")

# Mesure du nombre d'appels récursifs
compteur_appels = [0]

def somme_avec_compteur(liste):
    """Même algorithme que somme_diviser, mais en comptant les appels récursifs."""
    compteur_appels[0] += 1
    # Reprendre ici la même logique que somme_diviser
    # en remplaçant les appels récursifs à somme_diviser
    # par des appels à somme_avec_compteur
    ...

print(f"\n{'n':>6} | {'appels':>8}")
print("-" * 18)
for n in [8, 16, 32, 64, 128]:
    compteur_appels[0] = 0
    somme_avec_compteur(list(range(n)))
    print(f"{n:>6} | {compteur_appels[0]:>8}")

# Question : que remarquez-vous sur le nombre d'appels en fonction de n ?

---

Partie 2 — Programmation dynamique

Exercice 5 — L’escalier

Un enfant monte un escalier de n marches. A chaque pas, il peut monter 1 ou 2 marches. On cherche le nombre de facons differentes d’atteindre la marche n.

Consignes : 1. Completer les fonctions de chaque etape en remplacant .... 2. Verifier votre code avec les tests/fichiers d’affichage proposes. 3. Expliquer en une phrase pourquoi les versions memoisee et iterative sont plus efficaces.

Etape 1 : Version recursive naive (pour comprendre le probleme).

def escalier_naif(n):
    """
    Renvoie le nombre de facons de monter n marches (1 ou 2 a la fois).
    Version recursive naive.
    """
    # Cas de base : 0 marche -> 1 facon (ne rien faire)
    if n == ...:
        return ...

    # Cas de base : 1 marche -> 1 seule facon
    if n == ...:
        return ...

    # Relation de recurrence : f(n) = f(n-1) + f(n-2)
    return ...


# Verification sur les petites valeurs
for n in range(8):
    print(f"escalier({n}) = {escalier_naif(n)}")

Etape 2 : Version avec memoisation (approche descendante).

La version naive recalcule plusieurs fois les memes valeurs. Ici, on memorise les resultats deja calcules dans un dictionnaire memo.

Consignes : 1. Completer le test d’appartenance a memo. 2. Completer le calcul de la valeur manquante. 3. Stocker la valeur calculee dans memo avant de la renvoyer.

def escalier_memo(n, memo=None):
    """
    Renvoie le nombre de facons de monter n marches.
    Version avec memoisation (approche descendante).
    """
    if memo is None:
        memo = {}

    # Cas de base
    if n == 0 or n == 1:
        return 1

    # Si le resultat est deja dans le dictionnaire, le renvoyer directement
    if n in memo:
        return ...

    # Sinon, le calculer puis le stocker
    memo[n] = ...
    return ...


# Verification : memes resultats que la version naive
for n in range(8):
    assert escalier_memo(n) == escalier_naif(n)
print("Memoisation OK")

# On peut maintenant calculer pour de grandes valeurs
print(f"escalier(50) = {escalier_memo(50)}")

Etape 3 : Version iterative (approche ascendante / tabulation).

On construit un tableau f ou f[i] contient le nombre de facons de monter i marches. On remplit ce tableau du bas vers le haut, en commencant par les cas de base.

Consignes : 1. Completer l’initialisation du tableau. 2. Completer les cas de base f[0] et f[1]. 3. Completer la boucle de remplissage avec la relation de recurrence.

def escalier_tab(n):
    """
    Renvoie le nombre de facons de monter n marches.
    Version iterative (approche ascendante).
    """
    if n == 0 or n == 1:
        return 1

    # Creer un tableau f de taille n+1, initialise a 0
    f = ...

    # Remplir les cas de base
    f[0] = ...
    f[1] = ...

    # Remplir le reste du tableau, de l'indice 2 jusqu'a n
    # Pour chaque marche i, f[i] se calcule a partir de f[i-1] et f[i-2]
    for i in range(2, n + 1):
        ...

    return f[n]


# Verification
for n in range(8):
    assert escalier_tab(n) == escalier_naif(n)
print("Tabulation OK")
print(f"escalier(100) = {escalier_tab(100)}")

Exercice 6 — Le livreur de colis

Un livreur parcourt une rue avec n maisons. Chaque maison i a colis[i] colis a livrer. Il ne peut pas livrer deux maisons consecutives. On cherche le nombre maximal de colis qu’il peut livrer.

Consignes : 1. Executer l’etape 1 pour observer une strategie gloutonne. 2. Completer l’etape 2 (programmation dynamique) pour calculer le maximum. 3. Completer l’etape 3 pour retrouver les maisons effectivement choisies. 4. Comparer les resultats glouton / dynamique sur l’exemple donne.

Etape 1 : Comprendre le probleme sur un exemple.

# Exemple de la fiche papier
colis = [2, 7, 9, 3, 1, 5]

# Algorithme glouton (donné, à observer)
def glouton_livreur(colis):
    """Stratégie gloutonne : toujours choisir la maison disponible avec le plus de colis."""
    n = len(colis)
    disponible = [True] * n
    total = 0
    maisons_choisies = []

    while True:
        # Trouver la maison disponible avec le plus de colis
        meilleur_idx = -1
        meilleur_val = -1
        for i in range(n):
            if disponible[i] and colis[i] > meilleur_val:
                meilleur_val = colis[i]
                meilleur_idx = i

        if meilleur_idx == -1:
            break

        # Choisir cette maison et bloquer ses voisines
        maisons_choisies.append(meilleur_idx + 1)  # numérotation à partir de 1
        total += colis[meilleur_idx]
        disponible[meilleur_idx] = False
        if meilleur_idx > 0:
            disponible[meilleur_idx - 1] = False
        if meilleur_idx < n - 1:
            disponible[meilleur_idx + 1] = False

    return total, maisons_choisies


total_glouton, maisons = glouton_livreur(colis)
print(f"Glouton : {total_glouton} colis, maisons {maisons}")
print("(Vérifier si c'est le maximum...)")

Etape 2 : Solution par programmation dynamique (approche ascendante).

Consignes : 1. Completer les cas de base pour n = 0 et n = 1. 2. Completer l’initialisation de m[0] et m[1]. 3. Completer la relation de recurrence dans la boucle : m[i] = max(colis[i] + m[i-2], m[i-1]).

def livreur_max(colis):
    """
    Renvoie le nombre maximal de colis pouvant etre livres
    sans choisir deux maisons consecutives.
    """
    n = len(colis)

    if n == ...:
        return ...
    if n == ...:
        return ...

    # Creer un tableau m ou m[i] = maximum de colis livrables
    # en ne considerant que les maisons 0 a i.
    m = [0] * n

    # Cas de base
    m[0] = ...
    m[1] = ...

    # Pour chaque maison i a partir de la 3e :
    # Soit on livre la maison i -> on ajoute colis[i] au meilleur resultat
    #   jusqu'a la maison i-2 (car i-1 est interdite)
    # Soit on ne livre pas la maison i -> on garde le meilleur resultat jusqu'a i-1
    # On prend le maximum des deux options.
    for i in range(2, n):
        ...

    return m[n - 1]


# Tests
assert livreur_max([2, 7, 9, 3, 1, 5]) == 16
assert livreur_max([1, 2, 3, 1]) == 4
assert livreur_max([2, 1, 1, 2]) == 4
assert livreur_max([5]) == 5
print("Tous les tests sont passes !")

print(f"\nExemple cours : maximum = {livreur_max(colis)} colis")
print(f"Algorithme glouton avait trouve : {total_glouton} colis")

Etape 3 : Retrouver quelles maisons ont ete selectionnees.

Consignes : 1. Reprendre la meme recurrence que dans livreur_max pour remplir m. 2. Completer la reconstruction de droite a gauche. 3. Verifier que la somme des maisons selectionnees est egale au maximum annonce.

def livreur_avec_selection(colis):
    """
    Renvoie (maximum, liste des indices des maisons selectionnees).
    """
    n = len(colis)
    if n == 0:
        return 0, []
    if n == 1:
        return colis[0], [0]

    m = [0] * n
    m[0] = colis[0]
    m[1] = max(colis[0], colis[1])

    for i in range(2, n):
        ...  # meme formule que dans livreur_max

    # Reconstruction : on relit le tableau m de droite a gauche
    # pour retrouver quelles maisons ont ete choisies.
    selection = []
    i = n - 1
    while i >= 2:
        # Si m[i] vient du choix de livrer la maison i
        if m[i] == colis[i] + m[i - 2]:
            selection.append(i)
            i -= 2   # on saute la maison precedente (interdite)
        else:
            i -= 1   # la maison i n'a pas ete choisie

    # Traiter les cas restants (maison 0 ou 1)
    if i == 1 and m[1] == colis[1]:
        ...
    elif i >= 0 and (not selection or selection[-1] != 0):
        if ...:
            ...

    selection.sort()
    return m[n - 1], selection


maximum, indices = livreur_avec_selection(colis)
maisons_noms = [f"maison {i+1} ({colis[i]} colis)" for i in indices]
print(f"Maximum : {maximum} colis")
print(f"Selection : {', '.join(maisons_noms)}")
print(f"Verification : {sum(colis[i] for i in indices)} = {maximum}")

Exercice 7 — Pavage d’un couloir

On veut paver un couloir de longueur n avec des dalles de longueur 1 ou 2. On cherche le nombre de facons differentes de paver ce couloir.

Consignes : 1. Completer la version recursive naive. 2. Completer la version iterative par tabulation. 3. Verifier que les deux versions donnent les memes resultats sur n = 0..7.

def pavages_naif(n):
    """
    Renvoie le nombre de facons de paver un couloir de longueur n.
    Version recursive naive.
    """
    # Un couloir de longueur 0 : 1 facon (ne rien poser)
    # Un couloir de longueur 1 : 1 seule facon (une dalle de 1)
    if n == ... or n == ...:
        return ...

    # Sinon : recurrence identique au probleme de l'escalier
    return ...


# Afficher les resultats pour n = 0 a 7
for n in range(8):
    print(f"pavages({n}) = {pavages_naif(n)}")

def pavages_tab(n):
    """
    Renvoie le nombre de facons de paver un couloir de longueur n.
    Version iterative par tabulation.
    """
    if n == 0 or n == 1:
        return 1

    # Construire le tableau f ou f[i] = nombre de facons pour un couloir de longueur i
    f = ...

    # Cas de base
    f[0] = ...
    f[1] = ...

    # Remplir f[2], f[3], ..., f[n]
    # Pour chaque longueur i, le nombre de pavages s'obtient en additionnant
    # le nombre de pavages pour i-1 et pour i-2.
    for i in range(2, n + 1):
        ...

    return f[n]


# Verification
for n in range(8):
    assert pavages_tab(n) == pavages_naif(n)
print("Tabulation OK")
print(f"pavages(10) = {pavages_tab(10)}")
print(f"pavages(30) = {pavages_tab(30)}")

Exercice 8 — Chemins dans une grille

On dispose d’une grille de n lignes et m colonnes. On part du coin superieur gauche (0,0) et on veut atteindre le coin inferieur droit (n-1, m-1). On ne peut se deplacer qu’a droite ou vers le bas.

Consignes : 1. Completer l’initialisation de la grille de DP. 2. Completer les cas de base (premiere ligne et premiere colonne). 3. Completer la formule de recurrence pour les autres cases. 4. Reutiliser la meme formule dans l’affichage final de la grille.

Observation : Pour arriver en (i, j), on vient forcement de (i-1, j) ou de (i, j-1). Donc le nombre de chemins menant a (i, j) est la somme des chemins menant a (i-1, j) et a (i, j-1).

def chemins_grille(n, m):
    """
    Renvoie le nombre de chemins du coin (0,0) au coin (n-1, m-1)
    en ne se deplacant qu'a droite ou vers le bas.
    """
    # Creer une grille (tableau 2D) de taille n x m, remplie de 0
    grille = ...

    # Cas de base : toute la premiere ligne
    # (on ne peut y arriver que par des deplacements vers la droite -> 1 seul chemin)
    for j in range(m):
        ...

    # Cas de base : toute la premiere colonne
    # (on ne peut y arriver que par des deplacements vers le bas -> 1 seul chemin)
    for i in range(n):
        ...

    # Remplir le reste de la grille ligne par ligne
    # grille[i][j] = chemins venant du dessus + chemins venant de la gauche
    for i in range(1, n):
        for j in range(1, m):
            ...

    return grille[n - 1][m - 1]


# Tests
assert chemins_grille(1, 1) == 1
assert chemins_grille(2, 2) == 2
assert chemins_grille(3, 3) == 6
assert chemins_grille(3, 7) == 28
print("Tous les tests sont passes !")

# Afficher la grille pour un exemple
# (necessite d'avoir complete chemins_grille correctement)
print("\nNombre de chemins pour chaque case d'une grille 4x4 :")
n, m = 4, 4
grille = [[0] * m for _ in range(n)]
for j in range(m):
    grille[0][j] = 1
for i in range(n):
    grille[i][0] = 1
for i in range(1, n):
    for j in range(1, m):
        ...  # meme formule que ci-dessus
for ligne in grille:
    print(ligne)

Exercice 9 — Sous-sequence croissante la plus longue

On cherche la longueur de la plus longue sous-sequence strictement croissante d’une liste. (Les elements de la sous-sequence ne sont pas forcement consecutifs dans la liste.)

Exemple : dans [3, 1, 4, 1, 5, 9, 2, 6], une sous-sequence croissante de longueur maximale est [1, 4, 5, 9] ou [1, 4, 5, 6] -> longueur 4.

Consignes : 1. Completer l’initialisation du tableau longueur. 2. Completer la mise a jour dans la double boucle. 3. Completer la ligne qui renvoie la reponse finale.

Idee : longueur[i] est la longueur de la plus longue sous-sequence croissante qui se termine a l’indice i.

def sous_sequence_croissante(liste):
    """
    Renvoie la longueur de la plus longue sous-sequence strictement croissante.
    """
    if not liste:
        return 0

    n = len(liste)

    # Chaque element forme a lui seul une sous-sequence de longueur 1
    longueur = ...

    # Pour chaque position i (de 1 a n-1) :
    for i in range(1, n):
        # On examine toutes les positions j avant i
        for j in range(i):
            # Si liste[j] < liste[i], on peut etendre la sous-sequence
            # se terminant en j par l'element en i.
            if liste[j] < liste[i]:
                ...

    # La reponse est le maximum du tableau longueur
    return ...


# Tests
assert sous_sequence_croissante([3, 1, 4, 1, 5, 9, 2, 6]) == 4
assert sous_sequence_croissante([1, 2, 3, 4, 5]) == 5     # deja triee
assert sous_sequence_croissante([5, 4, 3, 2, 1]) == 1     # triee a l'envers
assert sous_sequence_croissante([10, 9, 2, 5, 3, 7, 101, 18]) == 4
assert sous_sequence_croissante([]) == 0
print("Tous les tests sont passes !")

Exercice 10 — Bilan : comparer les approches sur le probleme de l’escalier

Consignes : 1. Executer le tableau comparatif pour n = 10, 20, 30, 35. 2. Rediger une courte conclusion : quelle approche passe le mieux a l’echelle et pourquoi ?

iimport time

print("Comparaison des temps d'execution pour le probleme de l'escalier")
print(f"{'n':>5} | {'naif (ms)':>12} | {'memo (ms)':>12} | {'tab (ms)':>12}")
print("-" * 50)

for n in [10, 20, 30, 35]:
    # Version naive
    t0 = time.perf_counter()
    escalier_naif(n)
    t_naif = (time.perf_counter() - t0) * 1000

    # Version memo
    t0 = time.perf_counter()
    escalier_memo(n)
    t_memo = (time.perf_counter() - t0) * 1000

    # Version tab
    t0 = time.perf_counter()
    escalier_tab(n)
    t_tab = (time.perf_counter() - t0) * 1000

    print(f"{n:>5} | {t_naif:>12.4f} | {t_memo:>12.4f} | {t_tab:>12.4f}")

print("\nQue concluez-vous sur les temps d'execution ?")