Corrigé X-ENS 2025 Informatique B MP-PC-PSI — Partie IV (Q10 à Q15) : Programmation dynamique avec cases bonus

Sujet officiel du concours X-ENS, session 2025, épreuve Informatique B MP-PC-PSI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Grille T de taille $N \times N$ , sauts par défaut sauts (ensemble $Γ$ ), dictionnaire bonus ; tous les sauts vérifient (*) : $δ i > 0$ ou ( $δ i = 0$ et $δ j > 0$ ). On remplit poids_opt[i][j][c], poids d'un chemin optimal de $(i, j)$ à $(N - 1, N - 1)$ lorsque l'ensemble des cases bonus déjà activées a pour code $c$ , et saut_opt[i][j][c], un saut optimal à jouer depuis $(i, j)$ .

Les $n$ cases bonus sont numérotées de $0$ à $n - 1$ ; $Δ_{k}$ est l'ensemble des sauts activés par la case numéro $k$ . Un masque $[b_{0}, \dots, b_{n - 1}]$ de booléens indique les cases activées ; son code $⟨ b_{0} \dots b_{n - 1} ⟩$ est l'entier qui s'écrit $b^_{n - 1} \dots b^_{0}$ en base 2 ( $True^= 1$ , $False^= 0$ ). Ainsi [False, False] a pour code 0 et [True, False] a pour code 1. Depuis une case non bonus, on utilise $Γ$ et les $Δ_{k}$ activés, le code étant inchangé. Depuis la case bonus numéro $k$ , on ajoute $Δ_{k}$ et les successeurs sont pris avec $b_{k}$ mis à True. Les masques doivent être traités par inclusion décroissante. L'algorithme suggéré part du masque plein et engendre, à l'aide d'une file, chaque ligne suivante en basculant un True en False, jusqu'au masque vide.

Fonctions supposées données : ranger_bonus(bonus) renvoie (bonus_au_rang, rang_du_bonus), où bonus_au_rang[k] est la liste des sauts de la case numéro $k$ et rang_du_bonus[(i,j)] le numéro de la case $(i, j)$ ; ajouter_bonus(bonus, rang_du_bonus, i, j, bonus_actifs, code_bonus_actifs) renvoie le code après activation de $(i, j)$ , inchangé si ce n'est pas une case bonus.

Q10. Écrire code_bonus(masque_bonus).
Q11. Écrire la définition de poids_opt[i][j][ $⟨ b_{0} \dots b_{n - 1} ⟩$ ], à l'aide de $Γ$ et des $Δ_{k}$ .
Q12. Écrire combinaisons_bonus(nb_bonus), qui renvoie la liste des masques par inclusion décroissante, selon l'algorithme décrit.
Q13. Écrire la fonction trouver_sauts_possibles, d'arguments sauts, bonus_au_rang et masque_bonus, qui renvoie la liste des sauts possibles.
Q14. Compléter les sept trous du code suivant, puis donner sa complexité.


def trouve_dynamique(T, sauts, bonus):
  N = len(T)
  nb_bonus = len(bonus)
  nb_code_bonus = ...                             # A COMPLETER (1)
  poids_opt = [[[INFINI for bonus_code in range(nb_code_bonus)]
                        for j in range(N)] for i in range(N)]
  saut_opt = [[[(0,0,0) for bonus_code in range(nb_code_bonus)]
                        for j in range(N)] for i in range(N)]
  (bonus_au_rang, rang_du_bonus) = ranger_bonus(bonus)
  for bonus_actifs in combinaisons_bonus(nb_bonus):
    code_bonus_actifs = code_bonus(bonus_actifs)
    poids_opt[N-1][N-1][code_bonus_actifs] = ...  # A COMPLETER (2)
    sauts_possibles = ...                         # A COMPLETER (3)
    for i in range(...):                          # A COMPLETER (4)
      for j in range(...):                        # A COMPLETER (5)
        code_bonus_dest = ajouter_bonus(bonus, rang_du_bonus, i, j,
                                        bonus_actifs, code_bonus_actifs)
        if (i,j) in bonus:
          sauts_possibles_final = sauts_possibles + bonus[(i,j)]
        else:
          sauts_possibles_final = sauts_possibles
        for (delta_i, delta_j) in sauts_possibles_final:
          i_dest = i+delta_i
          j_dest = j+delta_j
          if (i_dest in range(N) and j_dest in range(N)):
            poids_opt_dest = poids_opt[i_dest][j_dest][code_bonus_dest]
            if (poids_opt[i][j][code_bonus_actifs] > poids_opt_dest):
              poids_opt[i][j][code_bonus_actifs] = ... # A COMPLETER (6)
              saut_opt[i][j][code_bonus_actifs] = ...  # A COMPLETER (7)
        poids_opt[i][j][code_bonus_actifs] += T[i][j]
  return (poids_opt, saut_opt)

Q15. Écrire solution_dynamique(saut_opt, N), qui renvoie le chemin optimal (liste de cases), ou [] s'il n'existe aucun chemin du départ à l'arrivée.

Corrigé

Q10. Le code vaut $\sum_{k = 0}^{n - 1} b^_{k} 2^{k}$ . On l'évalue par la méthode de Horner, en lisant le masque de la fin vers le début (bit de poids fort d'abord).


def code_bonus(masque_bonus):
    code = 0
    for k in range(len(masque_bonus) - 1, -1, -1):   # de b_(n-1) à b_0
        code = 2 * code              # décalage d'un rang en base 2
        if masque_bonus[k]:
            code = code + 1          # le bit b_k vaut 1
    return code

Invariant : après le traitement de l'indice $t$ , $code = \sum_{k = t}^{n - 1} b^_{k} 2^{k - t}$ ; pour $t = 0$ , c'est le code cherché. Coût $O (n)$ . Vérifié : [False, False] $\mapsto 0$ , [True, False] $\mapsto 1$ , [False, True] $\mapsto 2$ , [True, True, True] $\mapsto 7$ , [] $\mapsto 0$ . Ce que le correcteur attend : le jury relève deux erreurs, compter les True au lieu de calculer l'entier, et calculer en base 10.

Q11. Notons $P (i, j, b)$ pour poids_opt[i][j][ $⟨ b_{0} \dots b_{n - 1} ⟩$ ] et posons, pour la case $(i, j)$ et le masque $b$ ,

$A_{i, j} (b) = Γ \cup k : b_{k} = True ⋃ Δ_{k} \cup {Δ_{r} \emptyset si (i, j) est la case bonus num e ˊ ro r, sinon,$

et $b^{'}$ le masque $b$ où $b_{r}$ est mis à True si $(i, j)$ est la case bonus numéro $r$ , $b^{'} = b$ sinon. Alors :

$P (N - 1, N - 1, b) = T [N - 1] [N - 1],$

et, pour $(i, j) \neq = (N - 1, N - 1)$ ,

$P (i, j, b) = T [i] [j] + min {P (i + δ i, j + δ j, b^{'}) (δ i, δ j) \in A_{i, j} (b), 0 ⩽ i + δ i < N et 0 ⩽ j + δ j < N},$

avec la convention $min \emptyset = + \infty$ (INFINI) quand aucun successeur n'est dans la grille.

Justification (sous-structure optimale). Un chemin correct de $(i, j)$ à l'arrivée, avec les bonus de $b$ activés, est soit réduit à l'arrivée, soit formé d'un premier saut de $A_{i, j} (b)$ qui reste dans la grille, puis d'un chemin correct depuis la case atteinte avec les bonus de $b^{'}$ . Son poids est $T [i] [j]$ plus celui de ce reste. Ce reste doit être optimal : sinon, en le remplaçant par un meilleur, on améliorerait le tout (argument de couper-coller). Réciproquement, toute telle concaténation est un chemin correct. Le cas de l'arrivée est à part : le chemin s'y arrête, et d'ailleurs, par (), aucun saut n'en part en restant dans la grille. Ce que le correcteur attend :* le jury signale qu'il manquait souvent le test de validité de la case successeur.

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →