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

Énoncé du problème