Nombre de chemins — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 1)

Nombre de chemins

Glouton ou dynamique ? · niveau 2

Énoncé

On note $N (j)$ le nombre de chemins de la case $0$ à la case $j$ (sauts de $2$ ou $3$ ).

Justifier que $N (j) = N (j - 2) + N (j - 3)$ pour $j \geq 3$ et donner $N (0)$ , $N (1)$ , $N (2)$ .
Écrire une fonction long nbChemins(int n) qui retourne en $Θ (n)$ le nombre de chemins de la case $0$ à la case $n - 1$ . Quelle est sa valeur pour un ruban de $100$ cases ?

Corrigé

Tout chemin vers $j \geq 3$ se termine par un saut depuis $j - 2$ ou depuis $j - 3$ , et ces deux familles sont disjointes ; chaque chemin vers $j - 2$ (resp. $j - 3$ ) se prolonge d'une seule façon. D'où $N (j) = N (j - 2) + N (j - 3)$ . Base : $N (0) = 1$ (le chemin réduit à la case $0$ ), $N (1) = 0$ , $N (2) = 1$ . -


static long nbChemins(int n) {
    long[] N = new long[Math.max(n, 3)];
    N[0] = 1; N[1] = 0; N[2] = 1;                 // base
    for (int j = 3; j < n; j++) N[j] = N[j-2] + N[j-3];
    return N[n-1];
}

Une boucle de $n - 3$ tours en temps constant : $Θ (n)$ . Pour un ruban de $100$ cases, $N (99) = 506505428836$ : un demi-million de millions de chemins, qu'aucune énumération ne parcourra. Le type long est nécessaire : la valeur dépasse Integer.MAX_VALUE.