TP 2 : Boucles imbriquées

Dans ce TP, on considère des algorithmes utilisant des boucles imbriquées (les unes dans les autres). Par exemple, dans le code suivant, print(i, j) est exécuté pour tous les i entre $0$ et $3$ et tous les j entre $0$ et $2$ :

In [4]:

for i in range(4):
    for j in range(3):
        print(i, j) # affiche i et j

for i in range(4): for j in range(3): print(i, j) # affiche i et j

0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
3 0
3 1
3 2

Exercice

Deviner puis vérifier ce qui va être affiché par le code suivant :

for i in range(4):
    for j in range(i, 3):
        print(i, j)

Solution

In [1]:

for i in range(4):
    for j in range(i, 3):
        print(i, j)

for i in range(4): for j in range(i, 3): print(i, j)

0 0
0 1
0 2
1 1
1 2
2 2

Facteur d'une chaîne de caractères¶

Les chaînes de caractères (string en anglais) servent à stocker du texte, sous forme d'une suite de caractères (symboles). Contrairement aux listes, il n'est pas possible de modifier une chaîne de caractères (on dit que c'est un type immutable). Par exemple, il n'y a pas de append sur les chaînes de caractères.

In [2]:

s = "l'informatique c'est fun"  # définition d'une chaîne de caractères
print(len(s))  # taille de s
print(s[2])  # caractère d'indice 2 (c'est à dire en 3ème position)

s = "l'informatique c'est fun" # définition d'une chaîne de caractères print(len(s)) # taille de s print(s[2]) # caractère d'indice 2 (c'est à dire en 3ème position)

24
i

In [3]:

s[0] = "L"  # ERREUR : on ne peut pas modifier un str
s.append("!")  # ERREUR : on ne peut pas modifier un str

s[0] = "L" # ERREUR : on ne peut pas modifier un str s.append("!") # ERREUR : on ne peut pas modifier un str

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-3-f7ab6b692a46> in <module>
----> 1 s[0] = "L"  # ERREUR : on ne peut pas modifier un str
      2 s.append("!")  # ERREUR : on ne peut pas modifier un str

TypeError: 'str' object does not support item assignment

Exercice

Écrire une fonction permettant de savoir si une chaîne de caractères contient la lettre a.

Solution

In [2]:

def contient_a(s):
    for i in range(len(s)):
        if s[i] == "a":
            return True
    return False

def contient_a(s): for i in range(len(s)): if s[i] == "a": return True return False

Soit s et m deux chaînes de caractères. On dit que m est un facteur de s si m apparaît dans s (consécutivement).
Par exemple, "thm" est un facteur de "Algorithme" mais "rime" n'est pas un facteur de "Algorithme".

Exercice

1. Écrire une fonction facteur_i telle que facteur_i(s, m, i) détermine si m apparaît dans s à partir de l'indice i. Dit autrement, il faut s[i] et m[0] soient égaux, que s[i + 1] et m[1] soient égaux...
   Par exemple, facteur_i("Algorithme", "go", 2) doit renvoyer True mais facteur_i("Algorithme", "go", 0) doit renvoyer False.
2. En déduire une fonction facteur telle que facteur(s, m) détermine si m est un facteur de s.

Solution

In [5]:

# 1.
def facteur_i(s, m, i):
    for j in range(len(m)):
        if s[i + j] != m[j]:
            return False
    return True

assert(facteur_i("Algorithme", "go", 2) and not facteur_i("Algorithme", "go", 0))

# 2.
def facteur(s, m):
    for i in range(len(s) - len(m) + 1):
        if facteur_i(s, m, i):
            return True
    return False

assert(facteur("Algorithme", "go") and not facteur("Algorithme", "lit"))

# 1. def facteur_i(s, m, i): for j in range(len(m)): if s[i + j] != m[j]: return False return True assert(facteur_i("Algorithme", "go", 2) and not facteur_i("Algorithme", "go", 0)) # 2. def facteur(s, m): for i in range(len(s) - len(m) + 1): if facteur_i(s, m, i): return True return False assert(facteur("Algorithme", "go") and not facteur("Algorithme", "lit"))

Recherche des deux valeurs les plus proches¶

On veut connaître, dans une liste, les deux valeurs les plus proches.
Par exemple, les deux valeurs les plus proches dans [4, -1, 8, 2, 13] sont 4 et 2.

Exercice

Écrire une fonction plus_proches renvoyant un couple des deux valeurs les plus proches dans une liste de nombres.
On pourra compléter le code suivant (en supposant la liste de taille au moins 2) :

def plus_proches(L):
    m = abs(L[1] - L[0]) # m contient la distance minimum entre 2 valeurs de L
    res = (L[0], L[1]) # les deux valeurs les plus proches
    for i in range(len(L)):
        for j in range(..., len(L)): # on veut i différent de j
            # si la distance de L[i] à L[j] est plus petite que m, mettre à jour m et res
    return res

Solution

In [8]:

def plus_proches(L):
    m = abs(L[1] - L[0]) # m contient la distance minimum entre 2 valeurs de L
    res = (L[0], L[1]) # les deux valeurs les plus proches
    for i in range(len(L)):
        for j in range(i + 1, len(L)):
            d = abs(L[i] - L[j])
            if d < m:
                m = d
                res = (L[i], L[j])
    return res

plus_proches([4, -1, 8, 2, 13])

def plus_proches(L): m = abs(L[1] - L[0]) # m contient la distance minimum entre 2 valeurs de L res = (L[0], L[1]) # les deux valeurs les plus proches for i in range(len(L)): for j in range(i + 1, len(L)): d = abs(L[i] - L[j]) if d < m: m = d res = (L[i], L[j]) return res plus_proches([4, -1, 8, 2, 13])

Out[8]:

(4, 2)

Tri à bulle¶

Le tri à bulle permet de trier une liste L de taille n par ordre croissant de la façon suivante :

Pour i variant de 0 à n - 1
    Pour j variant de i + 1 à n - 1
        Si L[i] > L[j]
            Inverser L[i] et L[j]

Exercice

Traduire ce pseudo-code en une fonction Python.

Solution

In [11]:

def tri_bulle(L):
    for i in range(len(L)):
        for j in range(i + 1, len(L)):
            if L[i] > L[j]:
                L[i], L[j] = L[j], L[i]
          
L = [4, 1, 8, 2, 3]
tri_bulle(L)
L

def tri_bulle(L): for i in range(len(L)): for j in range(i + 1, len(L)): if L[i] > L[j]: L[i], L[j] = L[j], L[i] L = [4, 1, 8, 2, 3] tri_bulle(L) L

Out[11]:

[1, 2, 3, 4, 8]