Solution de Doublons et grille de démineur - Sujet 28 - EP NSI 2025
Énoncé du problème
Exercice 1
EXERCICE 1 (10 points)
Écrire une fonction a_doublon qui prend en paramètre un tableau trié de nombres dans l’ordre croissant et renvoie True si ce tableau contient au moins deux nombres identiques, False sinon.
Exemple :
>>> a_doublon([])
False
>>> a_doublon([1])
False
>>> a_doublon([1, 2, 4, 6, 6])
True
>>> a_doublon([2, 5, 7, 7, 7, 9])
True
>>> a_doublon([0, 2, 3])
False
Exercice 2
EXERCICE 2 (10 points)
On souhaite générer des grilles du jeu de démineur à partir de la position des bombes à placer. On se limite à la génération de grilles carrées de taille $n \times n$ où $n$ est le nombre de bombes du jeu.
Dans le jeu du démineur, chaque case de la grille contient soit une bombe, soit une valeur qui correspond aux nombres de bombes situées dans le voisinage direct de la case (au-dessus, en dessous, à droite, à gauche ou en diagonale : chaque case a donc 8 voisins si elle n’est pas située au bord de la grille).
Un exemple de grille $5 \times 5$ de démineur dans laquelle la bombe est représentée par une étoile est représenté ci-dessous.
[Figure : grille 5 × 5 du démineur, les bombes étant représentées par une étoile]
| 1 | 1 | 1 | 0 | 0 |
| 1 | * | 1 | 1 | 1 |
| 2 | 2 | 3 | 2 | * |
| 1 | * | 2 | * | 3 |
| 1 | 1 | 2 | 2 | * |
On utilise une liste de listes pour représenter la grille et on choisit de coder une bombe par la valeur -1.
L’exemple ci-dessus sera donc codé par la liste :
[[1, 1, 1, 0, 0],
[1, -1, 1, 1, 1],
[2, 2, 3, 2, -1],
[1, -1, 2, -1, 3],
[1, 1, 2, 2, -1]]
Compléter le code situé à la page suivante afin de générer des grilles de démineur, on pourra vérifier que l’appel
genere_grille([(1, 1), (2, 4), (3, 1), (3, 3), (4, 4)])
renvoie bien la liste donnée en exemple.
def voisinage(n, ligne, colonne):
""" Renvoie la liste des coordonnées des voisins de la case
(ligne, colonne) dans un grille de taille n x n,
en tenant compte des cases sur les bords. """
voisins = []
for dl in range(-1, 2):
for dc in range(-1, 2):
l = ligne + dl
c = colonne + dc
if (l, c) != (ligne, colonne) \
and 0 <= l < n and 0 <= c < n:
voisins.append((l,c))
return voisins
def incremente_voisins(grille, ligne, colonne):
""" Incrémente de 1 toutes les cases voisines d'une bombe."""
voisins = ...
for l, c in voisins:
if grille[l][c] != ...: # si ce n'est pas une bombe
... # on ajoute 1 à sa valeur
def genere_grille(bombes):
""" Renvoie une grille de démineur de taille nxn où n est
le nombre de bombes, en plaçant les bombes à l'aide de
la liste bombes de coordonnées (tuples) passée en
paramètre. """
n = len(bombes)
# Initialisation d'une grille nxn remplie de 0
grille = [[0 for colonne in range(n)] for ligne in range(n)]
# Place les bombes et calcule les valeurs des autres cases
for ligne, colonne in bombes:
grille[ligne][colonne] = ... # place la bombe
... # incrémente ses voisins
return grille
Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.
Exercice 1
Contraintes :
tabest une liste d’entiers, éventuellement vide :0 <= len(tab) <= 2*10^5-10^9 <= tab[i] <= 10^9tabest trié dans l’ordre croissant (au sens large : deux éléments consécutifs peuvent être égaux)- la fonction renvoie un booléen
TrueouFalse - une solution en
O(n^2)(comparaison de toutes les paires) dépassera la limite de temps
Exercice 2
Contraintes :
bombesest une liste non vide de tuples(ligne, colonne)d’entiers :1 <= len(bombes) <= 200- on note
n = len(bombes); la grille renvoyée est de taillen x n 0 <= ligne < net0 <= colonne < npour chaque tuple debombes- les coordonnées de
bombessont deux à deux distinctes - la valeur renvoyée est une liste de
nlistes denentiers, une bombe étant codée par-1et toute autre case par son nombre de bombes voisines (entre0et8)
Solution
Exercice 1 - détecter un doublon dans un tableau trié
L’idée. L’énoncé précise que le tableau est trié dans l’ordre croissant. C’est toute l’astuce : dans un tableau trié, deux valeurs égales sont forcément rangées l’une à côté de l’autre. On n’a donc pas besoin de comparer chaque nombre avec tous les autres, il suffit de comparer chaque nombre avec son voisin de droite. Si on trouve deux voisins égaux, il y a un doublon ; si on arrive au bout sans rien trouver, il n’y en a pas.
Un petit exemple. Pour [2, 5, 7, 7, 7, 9], on compare 2 et 5 (différents), 5 et 7 (différents), puis 7 et 7 : égaux, on renvoie True tout de suite, sans regarder la fin du tableau.
def a_doublon(tab):
# Le tableau est trié : deux valeurs égales sont forcément côte à côte
for i in range(len(tab) - 1):
if tab[i] == tab[i + 1]:
return True
return False
i est l’indice de la case que l’on regarde, et on la compare toujours à la case suivante i + 1. La boucle s’arrête à len(tab) - 1 et pas à len(tab) : sur la dernière case il n’y a plus de voisin de droite, et tab[i + 1] provoquerait une erreur d’indice. Ce choix règle aussi tout seul les deux cas particuliers de l’énoncé : pour [] comme pour [1], range(len(tab) - 1) est vide, la boucle ne tourne jamais et on tombe directement sur return False. Enfin, le return True est dans la boucle : dès qu’un doublon est trouvé on sort, alors que le return False est après la boucle, car pour affirmer qu’il n’y a pas de doublon il faut avoir tout parcouru.
On ne parcourt le tableau qu’une seule fois : c’est ce qui permet de traiter les grands tableaux de l’énoncé. Comparer toutes les paires avec deux boucles imbriquées donnerait le bon résultat, mais serait beaucoup trop lent.
Exercice 2 - générer une grille de démineur
L’idée. Plutôt que de calculer, pour chaque case, combien de bombes l’entourent, on fait l’inverse, ce qui est bien plus simple : on part d’une grille remplie de 0, puis pour chaque bombe on écrit -1 dans sa case et on ajoute 1 à chacune de ses cases voisines. À la fin, chaque case libre a reçu exactement 1 par bombe voisine : elle contient donc le bon compte.
La fonction voisinage est déjà écrite et fait le travail délicat : elle renvoie la liste des coordonnées des voisins d’une case en ignorant ce qui sortirait de la grille. Il ne reste que trois trous à combler.
Un petit exemple. Avec genere_grille([(0, 0), (0, 1)]), la grille fait 2 x 2. La bombe (0, 0) met -1 en haut à gauche et ajoute 1 en (0,1), (1,0) et (1,1). La bombe (0, 1) écrase ensuite sa propre case par -1 et ajoute encore 1 en (1,0) et (1,1). On obtient [[-1, -1], [2, 2]].
def incremente_voisins(grille, ligne, colonne):
""" Incrémente de 1 toutes les cases voisines d'une bombe."""
voisins = voisinage(len(grille), ligne, colonne)
for l, c in voisins:
if grille[l][c] != -1: # si ce n'est pas une bombe
grille[l][c] = grille[l][c] + 1 # on ajoute 1 à sa valeur
def genere_grille(bombes):
n = len(bombes)
grille = [[0 for colonne in range(n)] for ligne in range(n)]
for ligne, colonne in bombes:
grille[ligne][colonne] = -1 # place la bombe
incremente_voisins(grille, ligne, colonne) # incrémente ses voisins
return grille
Dans incremente_voisins, la taille de la grille n’est pas donnée en paramètre : on la retrouve avec len(grille), puisque la grille est carrée et a donc autant de lignes que de colonnes. Le test grille[l][c] != -1 sert à ne pas abîmer une bombe voisine : une case qui contient déjà -1 doit rester -1, et non devenir 0. La fonction ne renvoie rien, elle modifie la liste de listes reçue en paramètre, ce qui suffit car genere_grille et elle travaillent sur la même grille.
Dans genere_grille, l’ordre des deux lignes du corps de la boucle est important : on écrit -1 dans la case de la bombe avant d’incrémenter ses voisins. Deux bombes côte à côte ne se gênent donc jamais. Et si une case avait déjà accumulé des 1 avant de recevoir sa propre bombe, le -1 écrase simplement ce compte, ce qui est le comportement voulu : une case qui contient une bombe n’affiche pas de nombre.
On peut vérifier que genere_grille([(1, 1), (2, 4), (3, 1), (3, 3), (4, 4)]) renvoie bien la grille 5 x 5 donnée dans l’énoncé.