Aller au contenu

Ep 48

le document

l'algorithme

Issue de : aucun⚓

EXERCICE 1⚓

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:

image

est reprĂ©sentĂ© par la liste d’adjacence suivante:

🐍 Script Python
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:

🐍 Script Python
adj = [[1, 2], [2], [0], [0]]
>>> voisins_entrants([[1, 2], [2], [0], [0]], 0)
[2, 3]
>>> voisins_entrants([[1, 2], [2], [0], [0]], 1)
[0]
RĂ©ponse

Complétez le code ci-dessous

###
#Mettre votre code icibksl-nlbksl-nl

Solution

###
def voisinspy-undentrants(adj, x):bksl-nl voisin = []bksl-nl noeuds = len(adj)bksl-nl for i in range(noeuds):bksl-nl if x in adj[i]:bksl-nl voisin.append(i)bksl-nl return voisinbksl-nlbksl-nltry:bksl-nl adj = [[1, 2], [2], [0], [0]]bksl-nl assert voisinspy-undentrants([[1, 2], [2], [0], [0]], 0) == [2, 3]bksl-nl assert voisinspy-undentrants([[1, 2], [2], [0], [0]], 1) == [0]bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le rĂ©sultat de votre fonction n\'est pas conforme đŸ€”')bksl-nl

EXERCICE 2⚓

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.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
Exemple :

🐍 Script Python
>>> nombre_suivant('1211')
'111221'
>>> nombre_suivant('311')
'1321
RĂ©ponse

Complétez le code ci-dessous

###
def nombrepy-undsuivant(s):bksl-nl '''Renvoie le nombre suivant de celui representé par sbksl-nl en appliquant le procédé de lecture.'''bksl-nl resultat = ''bksl-nl chiffre = s[0]bksl-nl compte = 1bksl-nl for i in range(...): bksl-nl if s[i] == chiffre:bksl-nl compte = ... bksl-nl else:bksl-nl resultat += ... + ... bksl-nl chiffre = ... bksl-nl ...bksl-nl lecturepy-und... = ... + ... bksl-nl resultat += lecturepy-undchiffrebksl-nl return resultatbksl-nlbksl-nl

Solution

###
def nombrepy-undsuivant(s):bksl-nl '''Renvoie le nombre suivant de celui representĂ© par sbksl-nl en appliquant le procĂ©dĂ© de lecture.'''bksl-nl resultat = ''bksl-nl chiffre = s[0]bksl-nl compte = 1bksl-nl for i in range(1, len(s)): bksl-nl if s[i] == chiffre:bksl-nl compte = compte + 1 bksl-nl else:bksl-nl resultat += str(compte) + str(chiffre)bksl-nl chiffre = s[i] bksl-nl compte = 1bksl-nl lecturepy-undchiffre = str(compte) + chiffrebksl-nl resultat += lecturepy-undchiffrebksl-nl return resultatbksl-nlbksl-nltry:bksl-nl assert nombrepy-undsuivant('1211') == '111221'bksl-nl assert nombrepy-undsuivant('311') == '1321'bksl-nl print('Tout semble correct 👍')bksl-nl bksl-nlexcept AssertionError as asser:bksl-nl print('Le rĂ©sultat de votre fonction n\'est pas conforme')bksl-nlbksl-nl