Exercice 1 - Partie C · Bac Numérique et Sciences Informatiques Centres étrangers (Afrique) 2024 (jour 2)

EXERCICE 1 (6 points)

Cet exercice porte sur la programmation en Python en général, la programmation orientée objet et la récursivité.

On se déplace dans une grille rectangulaire. On s’intéresse aux chemins dont le départ est sur la case en haut à gauche et l’arrivée en bas à droite. Les seuls déplacements autorisés sont composés de déplacements élémentaires d’une case vers le bas ou d’une case vers la droite.

Un itinéraire est noté sous la forme d’une suite de lettres:

D pour un déplacement vers la droite d’une case;

B pour un déplacement vers le bas d’une case.

Le nombre de caractères D est la longueur de l’itinéraire. Le nombre de caractères B est sa largeur.

Ainsi l’itinéraire 'DDBDBBDDDDB' a pour longueur 7 et pour largeur 4. Sa représentation graphique est:

S * *

* *

*

* * * * *

E S représente la case de départ (start). Ses coordonnées sont $(0\text{; }0)$;

* représente les cases visitées;

E représente la case d’arrivée (end).

Partie C – Calcul du nombre de chemins possibles

Soit $m$ et $n$ deux entiers naturels non nuls. On se place dans le contexte d'un itinéraire de longueur $m$ et de largeur $n$ de dimension $m \times n$.

On note $N(m, n)$ le nombre de chemins distincts respectant les contraintes de l'exercice.

7.

Pour un itinéraire de dimension $1 \times n$ justifier, éventuellement à l'aide d'un exemple, qu'il y a un seul chemin, c'est-à-dire que, quel que soit $n$ entier naturel, on a $N(1, n) = 1$.

De même, $N(m, 1) = 1$.

8.

Justifier que $N(m, n) = N(m - 1, n) + N(m, n - 1)$.

9.

En utilisant les questions précédentes, écrire une fonction récursive nombre_chemins(m, n) qui renvoie le nombre de chemins possibles dans une grille rectangulaire de dimension $m \times n$.