Solution de Voisins entrants dans un graphe orienté - Sujet 01 - EP NSI 2025

EXERCICE 1 (10 points)

On considère dans cet exercice un graphe orienté représenté sous forme de listes d’adjacence.

On suppose que les sommets sont numérotés de 0 à n-1.

Par exemple, le graphe suivant:

flowchart TD
    n3((3)) --> n0((0))
    n0 --> n1((1))
    n0 --> n2((2))
    n2 --> n0
    n1 --> n2

[Figure : graphe orienté à 4 sommets numérotés 0, 1, 2 et 3, représentés par des ellipses. Une flèche va de 3 vers 0, une flèche va de 0 vers 1, une flèche va de 0 vers 2, une flèche va de 2 vers 0, et une flèche va de 1 vers 2.]

est représenté par la liste d’adjacence suivante:

adj = [[1, 2], [2], [0], [0]]

Écrire une fonction voisins_entrants(adj, x) qui prend en paramètre le graphe donné sous forme de liste d’adjacence et qui renvoie une liste contenant les voisins entrants du sommet x, c’est-à-dire les sommets y tels qu’il existe une arête de y vers x.

Exemples:

>>> voisins_entrants([[1, 2], [2], [0], [0]], 0)
[2, 3]
>>> voisins_entrants([[1, 2], [2], [0], [0]], 1)
[0]

EXERCICE 2 (10 points)

On considère dans cet exercice la suite de nombre suivante : 1, 11, 21, 1211, 111221, …

Cette suite est construite ainsi : pour passer d’une valeur à la suivante, on la lit et on l’écrit sous la forme d’un nombre. Ainsi, pour 1211 :

• on lit un 1, un 2, deux 1 ;
• on écrit donc en nombre 1 1, 1 2, 2 1 ;
• puis on concatène 111221.

Compléter la fonction nombre_suivant qui prend en entrée un nombre sous forme de chaine de caractère et qui renvoie le nombre suivant par ce procédé, encore sous forme de chaîne de caractère.

def nombre_suivant(s):
    '''Renvoie le nombre suivant de celui representé par s
    en appliquant le procédé de lecture.'''
    resultat = ''
    chiffre = s[0]
    compte = 1
    for i in range(...):
        if s[i] == chiffre:
            compte = ...
        else:
            resultat += ... + ...
            chiffre = ...
            ...
    lecture_... = ... + ...
    resultat += lecture_chiffre
    return resultat

Exemples

>>> nombre_suivant('1211')
'111221'
>>> nombre_suivant('311')
'1321'

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

Exercice 1

Contraintes :

• adj est une liste de n listes d’entiers, avec 1 <= n <= 10^3
• les sommets sont numérotés de 0 à n-1 : pour tout sommet y, adj[y] est la liste des sommets vers lesquels part une arête issue de y
• 0 <= adj[y][i] <= n-1 pour tout y et tout i
• les valeurs d’une même liste adj[y] sont deux à deux distinctes (pas d’arête en double)
• le nombre total d’arêtes est au plus 10^4
• x est un entier avec 0 <= x <= n-1
• la liste renvoyée contient les sommets y rangés par ordre croissant, comme dans les exemples du sujet

Exercice 2

Contraintes :

• s est une chaîne de caractères non vide composée uniquement de chiffres décimaux 0 à 9
• 1 <= len(s) <= 10^3
• toute suite de chiffres identiques consécutifs de s est de longueur au plus 9, de sorte que chaque groupe se lit avec un seul chiffre de comptage
• la valeur renvoyée est une chaîne de caractères

Exercice 1 - Les voisins entrants

L’idée. La liste d’adjacence donne, pour chaque sommet y, la liste adj[y] des sommets vers lesquels y pointe : ce sont les voisins sortants. La question demande l’inverse, et cette information n’est écrite nulle part telle quelle. Il faut donc la reconstruire : on passe en revue tous les sommets y du graphe, et on garde ceux dont la liste adj[y] contient x.

Un petit exemple. Avec adj = [[1, 2], [2], [0], [0]] et x = 0 : adj[0] = [1, 2] ne contient pas 0, adj[1] = [2] non plus, adj[2] = [0] contient 0 donc on garde 2, et adj[3] = [0] aussi donc on garde 3. On obtient [2, 3].

def voisins_entrants(adj, x):
    entrants = []
    # On parcourt les sommets dans l'ordre 0, 1, 2, ... : la liste
    # obtenue est donc déjà rangée par ordre croissant
    for y in range(len(adj)):
        if x in adj[y]:
            entrants.append(y)
    return entrants

entrants est la liste que l’on construit petit à petit ; on la renvoie à la fin. Le test x in adj[y] pose simplement la question « existe-t-il une arête de y vers x ? ». Comme la boucle visite les sommets dans l’ordre croissant, les valeurs sont ajoutées dans le bon ordre : il n’y a aucun tri à faire ensuite.

Exercice 2 - La suite « lecture »

L’idée. Lire un nombre, c’est le découper en groupes de chiffres identiques qui se suivent, puis écrire, pour chaque groupe, sa longueur suivie du chiffre. La difficulté est qu’on ne connaît la longueur d’un groupe qu’une fois ce groupe terminé. On avance donc caractère par caractère en retenant deux choses : chiffre, le chiffre du groupe en cours, et compte, le nombre de fois qu’on vient de le voir. Tant que le caractère lu est le même, on augmente compte ; dès qu’il change, le groupe est fini : on l’écrit dans resultat, puis on repart sur un nouveau groupe de longueur 1.

Un petit exemple. '311' se découpe en 3, puis 11 : on lit un 3, deux 1, on écrit donc 13 puis 21, ce qui donne '1321'.

def nombre_suivant(s):
    '''Renvoie le nombre suivant de celui representé par s
    en appliquant le procédé de lecture.'''
    resultat = ''
    chiffre = s[0]
    compte = 1
    for i in range(1, len(s)):
        if s[i] == chiffre:
            compte = compte + 1
        else:
            # Le groupe en cours s'arrête ici : on l'écrit avant de repartir à zéro
            resultat += str(compte) + chiffre
            chiffre = s[i]
            compte = 1
    # Aucun changement ne suit le dernier groupe : la boucle ne l'a pas écrit
    lecture_chiffre = str(compte) + chiffre
    resultat += lecture_chiffre
    return resultat

Le premier caractère est déjà pris en compte avant la boucle (chiffre = s[0], compte = 1), c’est pourquoi la boucle démarre à 1 et non à 0 : sinon on compterait ce chiffre deux fois. str(compte) transforme le nombre en caractère, pour pouvoir le coller devant chiffre.

Le point sur lequel on se trompe le plus souvent est la ligne lecture_chiffre, après la boucle. Un groupe n’est écrit que lorsqu’on rencontre un chiffre différent ; or le dernier groupe de la chaîne n’est suivi de rien. Sans cette ligne finale, '1211' donnerait '1112' au lieu de '111221' : les deux derniers 1 seraient comptés mais jamais écrits.