L'escalier et la grille

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 18 — La programmation dynamique

Énoncé

(a) Trouver le nombre de façons différentes de monter un escalier de $n$ marches en effectuant des pas de 1 ou 2 marches à chaque fois. Donner la récurrence, l'algorithme itératif et la valeur pour $n = 10$ . (b) Déterminer le nombre de chemins possibles pour aller du coin supérieur gauche $(0, 0)$ au coin inférieur droit $(p - 1, q - 1)$ d'une grille de taille $p \times q$ en se déplaçant uniquement vers le bas ou vers la droite. Vérifier sur une grille $3 \times 3$ que l'on retrouve la valeur de $6$ .

Corrigé

(a) Pour atteindre la marche $n$ , le dernier pas effectué était soit d'une marche (provenant de la marche $n - 1$ ), soit de deux marches (provenant de la marche $n - 2$ ). Le nombre de chemins $E (n)$ vérifie donc la récurrence de Fibonacci : $E (n) = E (n - 1) + E (n - 2)$ avec $E (0) = 1$ et $E (1) = 1$ . Par calcul itératif, on obtient $E (10) = 89$ . (b) Pour atteindre la case $(i, j)$ , on ne peut provenir que de la case du dessus $(i - 1, j)$ ou de la case de gauche $(i, j - 1)$ . La récurrence est $C (i, j) = C (i - 1, j) + C (i, j - 1)$ avec pour cas de base $C (0, j) = C (i, 0) = 1$ (les bords de la grille ne possèdent qu'un unique chemin d'accès rectiligne).

def nb_chemins(p: int, q: int) -> int:
    C = [[1] * q for _ in range(p)]
    for i in range(1, p):
        for j in range(1, q):
            C[i][j] = C[i - 1][j] + C[i][j - 1]
    return C[p - 1][q - 1]

assert nb_chemins(3, 3) == 6

Note : Mathématiquement, $C (i, j) = (i i + j)$ . Ce calcul correspond au triangle de Pascal.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.