Nombre de façons de monter un escalier — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 1)

Nombre de façons de monter un escalier

Glouton ou dynamique ? · niveau 1 (application)

Énoncé

On monte un escalier de $n$ marches par pas de $1$ ou de $2$ marches. On note $f (n)$ le nombre de façons différentes d'arriver en haut (l'ordre des pas compte : $1 + 2$ et $2 + 1$ sont deux façons différentes de monter $3$ marches).

Calculer $f (1)$ , $f (2)$ , $f (3)$ , $f (4)$ .
Supposons le problème résolu : quel est le dernier pas ? En déduire une équation de récurrence. Quelle suite célèbre reconnaît-on ?
Écrire une fonction qui calcule $f (n)$ en $Θ (n)$ . Donner $f (10)$ et $f (40)$ .

Corrigé

$f (1) = 1$ ; $f (2) = 2$ ( $1 + 1$ , $2$ ) ; $f (3) = 3$ ( $1 + 1 + 1$ , $1 + 2$ , $2 + 1$ ) ; $f (4) = 5$ .
Le dernier pas est de $1$ marche (il reste $n - 1$ marches à monter avant, de $f (n - 1)$ façons) ou de $2$ marches ( $f (n - 2)$ façons). Base : $f (0) = 1$ (ne rien faire), $f (1) = 1$ . Hérédité : $\forall n \geq 2$ , $f (n) = f (n - 1) + f (n - 2)$ . C'est la suite de Fibonacci, décalée d'un rang : $f (n) = F_{n + 1}$ . -


static long f(int n) {
    long[] F = new long[n + 1];
    F[0] = 1;                                   // base
    if (n >= 1) F[1] = 1;
    for (int k = 2; k < n + 1; k++) F[k] = F[k-1] + F[k-2];
    return F[n];
}

On obtient $f (10) = 89$ et $f (40) = 165580141$ .