Coloration de composante connexe - Sujet 43 - EP NSI 2025

Exercice 1

Écrire une fonction couples_consecutifs qui prend en paramètre un tableau de nombres entiers tab non vide (type list), et qui renvoie la liste Python (éventuellement vide) des couples d’entiers consécutifs successifs qu’il peut y avoir dans tab.

Exemples :

>>> couples_consecutifs([1, 4, 3, 5])
[]
>>> couples_consecutifs([1, 4, 5, 3])
[(4, 5)]
>>> couples_consecutifs([1, 1, 2, 4])
[(1, 2)]
>>> couples_consecutifs([7, 1, 2, 5, 3, 4])
[(1, 2), (3, 4)]
>>> couples_consecutifs([5, 1, 2, 3, 8, -5, -4, 7])
[(1, 2), (2, 3), (-5, -4)]

Exercice 2

Soit une image binaire représentée dans un tableau à 2 dimensions. Les éléments M[i][j], appelés pixels, sont égaux soit à 0 soit à 1.

Une composante d’une image est un sous-ensemble de l’image constitué uniquement de 1 et de 0 qui sont côte à côte, soit horizontalement soit verticalement.

Par exemple, les composantes de

[Figure : à gauche, la matrice M = tableau 4×4 dont les lignes sont (0, 0, 1, 0), (0, 1, 0, 1), (1, 1, 1, 0), (0, 1, 1, 0) ; à droite, le mot « sont » suivi de la même matrice M dans laquelle les composantes sont délimitées par des contours épais regroupant les cases voisines de même nature.]

sont

On souhaite, à partir d’un pixel égal à 1 dans une image M, donner la valeur val à tous les pixels de la composante à laquelle appartient ce pixel.

La fonction colore_comp1 prend pour paramètre une image M (représentée par une liste de listes), deux entiers i et j et une valeur entière val. Elle met à la valeur val tous les pixels de la composante du pixel M[i][j] s’il vaut 1 et ne fait rien sinon.

Par exemple, colore_comp1(M, 2, 1, 3) donne

[Figure : la matrice M = tableau 4×4 dont les lignes sont (0, 0, 1, 0), (0, 3, 0, 1), (3, 3, 3, 0), (0, 3, 3, 0), la case de la ligne 2 et de la colonne 1 contenant le 3 en gras.]

Compléter le code récursif de la fonction colore_comp1 donné ci-dessous :

def colore_comp1(M, i, j, val):
    if M[i][j] != 1:
        return

    M[i][j] = val

    if i-1 >= 0: # propage en haut
        colore_comp1(M, i-1, j, val)
    if ... < len(M): # propage en bas 
        colore_comp1(M, ..., j, val) 
    if ...: # propage à gauche 
        colore_comp1(M, ..., ..., val) 
    if ...: # propage à droite 
        ...

Exemple :

>>> M = [[0, 0, 1, 0], [0, 1, 0, 1], [1, 1, 1, 0], [0, 1, 1, 0]]
>>> colore_comp1(M, 2, 1, 3)
>>> M
[[0, 0, 1, 0], [0, 3, 0, 1], [3, 3, 3, 0], [0, 3, 3, 0]]

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

tab est une liste Python non vide d’entiers : 1 <= len(tab) <= 10^4
-10^9 <= tab[i] <= 10^9
tab n’est pas nécessairement trié et ses valeurs peuvent se répéter
la liste renvoyée peut être vide, et ses éléments sont des tuples de deux entiers

Exercice 2

Contraintes :

M est une liste de listes d’entiers rectangulaire : toutes les lignes ont la même longueur
1 <= len(M) <= 30 et 1 <= len(M[0]) <= 30
chaque pixel M[i][j] vaut 0 ou 1 avant l’appel
0 <= i < len(M) et 0 <= j < len(M[0])
val est un entier avec 2 <= val <= 10^3 (donc différent de 0 et de 1)
toute composante de pixels valant 1 compte au plus 200 pixels, ce qui garde la récursion sous la limite de CPython
colore_comp1 modifie M sur place et ne renvoie rien (None)

Énoncé du problème

Exercice 1

Exercice 2