25-NSIJ1G11-2

  Énoncé   Sujet

1. La variable v contient la valeur 6.

2. def plateau_init(n, m, cartes):
       shuffle(cartes)
       plateau = []
       for i in range(n):
           plateau.append([cartes[i + j * n]  for j in range(m)])
       return plateau
   

3. def cartes_voisines(n, m, i, j):
       voisines = []
       for i2 in range(i - 1, i + 2):
           for j2 in range(j - 1, j + 2):
               if (i2, j2) != (i, j) and i2 in range(n) and j2 in range(m):
                   voisines.append((i2, j2))
       return voisines
   

4. • La chaine e1 a pour valeur associée $9 + 8 + 6 + 7 = \boxed{30}$.
   • La chaine e2 est invalide car le mouvement $(1, 2)$ vers $(2, 0)$ est illégal.
   • La chaine e3 est invalide car les coordonnées $(1, 4)$ sont hors plateau.

5. def chaine_evalue(plateau, chaine):
       total = 0
       for i, j in chaine:
           total += plateau[i][j]
       return total
   

   Si chaine peut être invalide, la fonction devient :

   def chaine_evalue(plateau, chaine):
       n, m = len(plateau), len(plateau[0])
       i, j = chaine[0]
       if i not in range(n) or j not in range(m):
           return None
       total = plateau[i][j]
       for k in range(1, len(chaine)):
           i, j = chaine[k]
           if (i, j) not in cartes_voisines(n, m, *chaine[k - 1]):
               return None
           total += plateau[i][j]
       return total
   

6. Dans un parcours en largeur classique, les sommets sont visités par ordre croissant de leur distance (en nombre d'arêtes) depuis le sommet de départ. Cela revient ici à explorer les chaînes par longueur croissante.

   Puisqu'on cherche à minimiser le nombre de cartes utilisées, c'est-à-dire minimiser le nombre de sommets traversés, dès qu'on découvre une chaîne dont la somme correspond à la cible, elle est nécessairement la plus courte possible.

   Un parcours en profondeur n'a pas cette propriété.

7. def explore(plateau, cible):
       n, m = len(plateau), len(plateau[0])
       a_visiter = file_init()
       for i in range(n):
           for j in range(m):
               file_ajoute(a_visiter, [(i, j)])
   
       while not file_est_vide(a_visiter):
           chemin = file_retire(a_visiter)
           if chaine_evalue(plateau, chemin) == cible:
               return chemin
           dernier = chemin[-1]
           i0, j0 = dernier
           for i, j in cartes_voisines(n, m, i0, j0):
               if (i, j) not in chemin:
                   file_ajoute(a_visiter, chemin + [(i, j)])
   
       # Pas de solutions
       return None
   

8. Une solution simple serait de :

   • initialiser une liste vide solutions = [] en début de fonction,
   • remplacer la ligne 11 return chemin par solution.append(chemin) (cela permet de poursuivre l'exploration),
   • remplacer la ligne 20 return None par return solutions.