Solution de Coloration de composante connexe - Sujet 43 - EP NSI 2025

Résoudre ce problème
Moyen Officiel
Python (3.14.0)

Énoncé du problème

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)

Solution

Exercice 1 - les couples d’entiers consécutifs

L’idée. On cherche les endroits où une valeur est immédiatement suivie, dans le tableau, de la valeur juste au-dessus d’elle. Il suffit donc de parcourir tab en comparant chaque case avec la case d’après : si la suivante vaut la précédente plus 1, on range le couple dans une liste résultat. On ne trie rien et on ne compare que des cases voisines.

Un petit exemple. Pour [7, 1, 2, 5, 3, 4] on regarde les paires voisines (7, 1), (1, 2), (2, 5), (5, 3), (3, 4). Seules (1, 2) et (3, 4) sont formées de deux entiers qui se suivent, d’où le résultat [(1, 2), (3, 4)].

def couples_consecutifs(tab):
    couples = []
    # La dernière case n'a pas de suivante : la boucle s'arrête donc à len(tab) - 1
    for i in range(len(tab) - 1):
        if tab[i + 1] == tab[i] + 1:
            couples.append((tab[i], tab[i + 1]))
    return couples

couples accumule les résultats dans l’ordre où on les rencontre, et c’est lui qu’on renvoie à la fin. L’indice i désigne la case de gauche du couple testé, i + 1 celle de droite : la boucle va donc jusqu’à len(tab) - 2 inclus, sinon tab[i + 1] sortirait du tableau. Un tableau d’un seul élément n’entre dans aucun tour de boucle et renvoie [], ce qui est correct. Les couples peuvent se chevaucher : dans [5, 1, 2, 3, 8, -5, -4, 7], le 2 sert de fin au couple (1, 2) puis de début au couple (2, 3), et on obtient bien [(1, 2), (2, 3), (-5, -4)].

Exercice 2 - colorer une composante

L’idée. Colorer une composante, c’est partir d’un pixel valant 1, lui donner la valeur val, puis recommencer exactement la même opération sur ses quatre voisins : au-dessus, en dessous, à gauche, à droite. C’est une fonction récursive. Deux détails font qu’elle s’arrête : on ne fait rien si le pixel ne vaut pas 1 (le premier if de la fonction), et on écrit val dans le pixel avant d’appeler les voisins, donc un pixel déjà coloré ne sera jamais retraité. Chaque if placé avant un appel sert seulement à vérifier qu’on ne sort pas de l’image.

Un petit exemple. Avec colore_comp1(M, 2, 1, 3), le pixel M[2][1] vaut 1 : il devient 3, puis on relance la fonction sur M[1][1], M[3][1], M[2][0] et M[2][2], qui valent 1 et deviennent 3 à leur tour, et ainsi de suite jusqu’à ce que tous les voisins soient soit hors de l’image, soit des 0, soit déjà colorés.

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 i+1 < len(M): # propage en bas
        colore_comp1(M, i+1, j, val)
    if j-1 >= 0: # propage à gauche
        colore_comp1(M, i, j-1, val)
    if j+1 < len(M[i]): # propage à droite
        colore_comp1(M, i, j+1, val)

i est le numéro de ligne, j le numéro de colonne. len(M) est le nombre de lignes, donc i+1 < len(M) teste qu’il existe une ligne en dessous ; len(M[i]) est le nombre de colonnes, donc j+1 < len(M[i]) teste qu’il existe une colonne à droite. Les deux autres tests, i-1 >= 0 et j-1 >= 0, empêchent de passer à un indice négatif, qui en Python repartirait de la fin du tableau au lieu de signaler une erreur.

La fonction ne renvoie rien : elle modifie M sur place, et l’appelant relit M après l’appel. Enfin, les quatre voisins testés sont ceux du haut, du bas, de la gauche et de la droite : les diagonales ne sont pas des voisins, conformément à l’énoncé qui parle de pixels côte à côte horizontalement ou verticalement.