Aller au contenu

Ep 21

le document

l'algorithme

Issue de : aucun⚓

EXERCICE 1⚓

Écrire une fonction recherche_motif qui prend en paramùtre une chaüne de caractùres motif non vide et une chaüne de caractùres texte et qui renvoie la liste des positions de motif dans texte. Si motif n’apparaüt pas, la fonction renvoie une liste vide.

Exemple :

🐍 Script Python
>>> recherche_motif("ab", "")
[]
>>> recherche_motif("ab", "cdcdcdcd")
[]
>>> recherche_motif("ab", "abracadabra")
[0, 7]
>>> recherche_motif("ab", "abracadabraab")
[0, 7, 11]

RĂ©ponse

Complétez le code ci-dessous

###
# Mettez votre code icibksl-nlbksl-nl

Solution

###
def recherchepy-undmotif(motif, text):bksl-nl """MĂ©thode naĂŻve"""bksl-nl lgpy-undtext = len(text)bksl-nl lgpy-undmotif = len(motif)bksl-nl position = []bksl-nl for i in range(lgpy-undtext-lgpy-undmotif+1):bksl-nl if text[i:i+lgpy-undmotif] == motif:bksl-nl position.append(i)bksl-nl return positionbksl-nl bksl-nltry:bksl-nl assert recherchepy-undmotif("ab", "") == []bksl-nl assert recherchepy-undmotif("ab", "cdcdcdcd") == []bksl-nl assert recherchepy-undmotif("ab", "abracadabra") == [0, 7]bksl-nl assert recherchepy-undmotif("ab", "abracadabraab") == [0, 7, 11]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-nlbksl-nl

EXERCICE 2⚓

Dans cet exercice, on considĂšre un graphe non orientĂ© reprĂ©sentĂ© sous forme de listes d’adjacence.

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

Ainsi, le graphe suivant:

image

sera reprĂ©sentĂ© par la liste d’adjacence suivante: adj = [[1, 2], [0, 3], [0], [1], [5], [4]]

On souhaite déterminer les sommets accessibles depuis un sommet donné dans le graphe.

Pour cela, on va procéder à un parcours en profondeur du graphe.

Compléter la fonction suivante.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def parcours(adj, x, acc):
    '''Réalise un parcours en profondeur récursif
    du graphe donné par les listes d'adjacence adj 
    depuis le sommet x en accumulant les sommets
    rencontrés dans acc'''
    if x ...: 
        acc.append(x)
        for y in ...: 
            parcours(adj, ...) 

def accessibles(adj, x):
    '''Renvoie la liste des sommets accessibles dans le
    graphe donné par les listes d'adjacence adj depuis
    le sommet x.'''
    acc = []
    parcours(adj, ...) 
    return acc

Exemple :

🐍 Script Python
>>> accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 0)
[0, 1, 2, 3]
>>> accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 4)
[4, 5]
RĂ©ponse

Complétez le code ci-dessous

###
def parcours(adj, x, acc):bksl-nl '''Réalise un parcours en profondeur récursifbksl-nl du graphe donné par les listes d'adjacence adj bksl-nl depuis le sommet x en accumulant les sommetsbksl-nl rencontrés dans acc'''bksl-nl if x ...: bksl-nl acc.append(x)bksl-nl for y in ...: bksl-nl parcours(adj, ...) bksl-nlbksl-nldef accessibles(adj, x):bksl-nl '''Renvoie la liste des sommets accessibles dans lebksl-nl graphe donné par les listes d'adjacence adj depuisbksl-nl le sommet x.'''bksl-nl acc = []bksl-nl parcours(adj, ...) bksl-nl return accbksl-nlbksl-nl

Solution

###
def parcours(adj, x, acc):bksl-nl '''RĂ©alise un parcours en profondeur rĂ©cursifbksl-nl du graphe donnĂ© par les listes d'adjacence adj bksl-nl depuis le sommet x en accumulant les sommetsbksl-nl rencontrĂ©s dans acc'''bksl-nl if x not in acc: bksl-nl acc.append(x)bksl-nl for y in adj[x]: bksl-nl parcours(adj, y, acc) bksl-nlbksl-nldef accessibles(adj, x):bksl-nl '''Renvoie la liste des sommets accessibles dans lebksl-nl graphe donnĂ© par les listes d'adjacence adj depuisbksl-nl le sommet x.'''bksl-nl acc = []bksl-nl parcours(adj, x, acc) bksl-nl return accbksl-nlbksl-nltry:bksl-nl assert accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 0) == [0, 1, 2, 3]bksl-nl assert accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 4) == [4, 5]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-nlbksl-nl