Exercice 1 - Partie B · 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 B – Génération aléatoire d'itinéraires

On souhaite créer des chemins de façon aléatoire. Pour cela, on utilise la méthode choice de la bibliothèque random dont on fournit ci-dessous la documentation.

Documentation

random.choice(sequence: list)

Renvoie un élément choisi dans une liste non vide. Si la population est vide, lève IndexError.

On rappelle que l'opérateur * permet de répéter une chaîne de caractères. Par exemple, on a:

>>> "Hello world ! " * 3

'Hello world ! Hello world ! Hello world ! '

L'algorithme proposé est le suivant:

on initialise:

une variable itineraire comme une chaîne de caractères vide,

les variables i et j à 0;

tant que l'on n'est pas sur la dernière ligne ou la dernière colonne du tableau:

on tire au sort entre un déplacement à droite ou en bas,

le déplacement est concaténé à la chaîne de caractères itineraire,

si le déplacement est vers la droite, alors j est incrémenté de 1,

si le déplacement est vers le bas, alors i est incrémenté de 1;

il reste à terminer le chemin en complétant par des déplacements afin d'atteindre la cellule en bas à droite.

6. Écrire les lignes manquantes dans le code ci-dessous. Le nombre de lignes effacées dans le code n'est pas indicatif.

from random import choice

def itineraire_aleatoire(m, n):

itineraire = ''

i, j = 0, 0

while i != m and j != n:

if i == m:

itineraire = itineraire + 'D'*(n-j)

if j == n:

itineraire = itineraire + 'B'*(m-i)

return itineraire