Exercice 3 · Bac Numérique et Sciences Informatiques Asie 2023 (jour 2)

Cet exercice porte sur les algorithmes.

On considère le jeu suivant:

Le joueur commence sur la première case du plateau. À chaque tour, il peut soit aller sur la case juste à droite, soit la sauter. À chaque fois qu'il passe sur une case, il gagne le nombre de points affichés sur celle-ci. L'objectif est d'atteindre la case arrivée en maximisant le nombre de points. Par exemple, pour le jeu précédent, le maximum possible est 4 en prenant le chemin grisé:

Dans cet exercice, un plateau est modélisé par une liste de longueur et de valeurs variables.

Par exemple, la liste du plateau précédent est: [4, -3, -1, 3, -2, -3].

1. a.

Donner sans le justifier le plus haut score possible, si le plateau est défini par la liste [-2, 4, -1, -2, 1, 4].

1. b.

Si le plateau ne contient que des valeurs positives, quelle est la meilleure stratégie ?

2. a.

Écrire une fonction parcours1(e) qui prend en paramètre une liste e représentant le plateau et renvoie le score réalisé si le joueur choisit comme stratégie de passer par toutes les cases.

Pour la question suivante, on suppose que le nombre de cases est impair.

2. b.

Écrire une fonction parcours2(e) qui prend en paramètre une liste e représentant le plateau et renvoie le score réalisé si le joueur choisit comme stratégie de ne faire que des sauts.

3.

On modélise les choix du joueur par une chaîne de caractères qui contient les caractères "D" (le joueur se déplace sur la case juste à droite) ou "XS" (le joueur saute une case toujours sur la droite).

Écrire une fonction score(plateau, deplacements) qui reçoit en paramètre un plateau sous forme de liste et un choix de déplacements donné sous forme d'une chaîne de caractères et retourne le score réalisé par ce choix. Dès que l'arrivée est atteinte, le score est renvoyé. On considère que la chaîne de caractères permet d'atteindre la case arrivée.

Par exemple: score([4, -3, -1, 3, -2, -3], "DDXSDDD") renvoie -1 résultat du calcul 4-3+3-2-3 = -1.

On suppose que la fonction genere(n) reçoit en paramètre un entier naturel $n$ non nul et renvoie une chaîne de caractères de longueur $n$ ne contenant que les caractères "D" et "XS" de manière aléatoire et permettant d'atteindre la case arrivée. Par exemple genere(8) peut renvoyer "DXSXSDXS".

4.

On souhaite écrire une fonction meilleur(plateau) qui génère 1000 déplacements dont la longueur est le nombre de cases du plateau pour s'assurer d'arriver au bout et qui renvoie le meilleur score sur ces 1000 déplacements. Recopier puis compléter la fonction ci-dessous:

def meilleur(plateau):

score_max = parcours1(plateau)

for i in range(..........):

d = genere(..........)

s = score(plateau, d)

if..........:

score_max = s

return score_max

5.

Écrire la fonction genere(n) de la question 3. On pourra à cet effet utiliser la fonction randint du module random qui reçoit deux entiers $a$ et $b$ et renvoie un entier de l'intervalle $[a, b]$ avec $a$ et $b$ inclus.