L’objectif du TP est de présenter quelques exemples d’utilisation de boucles imbriquées. On parle de boucles imbriquées lorsqu’une boucle (for ou while) se trouve dans le corps d’une autre boucle.
À chaque itération de la boucle extérieure, la boucle intérieure est alors exécutée intégralement. De plus, la boucle intérieure peut dépendre de la variable qui parcourt la boucle extérieure, comme dans l’exemple suivant.
for i in range (1, 4) :
for j in range (i+1, 5) :
print([i, j])
[1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4]
Extrait du programme officiel : Algorithmes opérant sur une structure séquentielle par boucles imbriquées. Recherche d’un facteur dans un texte. Recherche des deux valeurs les plus proches dans un tableau. Tri à bulles. Notion de complexité quadratique. On propose des outils pour valider la correction de l’algorithme.
Q1. Écrire un script qui calcule $\displaystyle\sum_{1\leq i\leq j\leq 100}\dfrac{i}{j}$ c’est-à-dire qui calcule $\displaystyle\sum_{j=1}^{100}\left(\displaystyle\sum_{i=1}^j\dfrac{i}{j}\right)$.
somme = 0
for j in range(1, 101) :
for i in range(1, j+1) :
somme = somme + i/j
Q2. On peut montrer par le calcul que
$\displaystyle\sum_{1\leq i\leq j\leq n}\dfrac{i}{j}=\dfrac{n(n+3)}{4}$ pour tout $n\in\mathbb{N}^*$. Tester si votre programme renvoie
la bonne valeur.
Attention, des erreurs d’arrondi peuvent apparaı̂tre avec la manipulation des flottants.
print(somme)
print(100*103/4)
2575.0000000000005 2575.0
On remarque qu'il y a eu des erreurs d'arrondi.
Q3. Écrire une fonction plus_petite_distance
prenant en argument une liste de nombres L
, qu’on supposera
de longueur au moins 2, et renvoyant la plus petite distance entre deux valeurs de la liste.
La distance entre deux nombres x
et y
est abs(x-y)
.
On pourra s’appuyer sur l’algorithme suivant.
n
et dref
où n
est la longueur de la liste L
et dref
est la distance de référence
initialisée à abs(L[0]-L[1])
.(i, j)
tels que $0\leq i < j < n$ afin de comparer abs(L[i]-L[j])
et dref
.
Si abs(L[i]-L[j])<dref
, alors on actualise dref
en lui affectant abs(L[i]-L[j])
.dref
.Ainsi, plus_petite_distance([-2,1,8,0])
doit renvoyer 1
.
Dans la fonction précédente, la fonction abs
est appelée $\dfrac{n(n-1)}{2}$ fois (où $n$ est la taille de la liste). Le terme
dominant de $\dfrac{n(n-1)}{2}$
est en $n^2$. On dit que la fonction est de coût quadratique.
def plus_petite_distance(L) :
n = len(L)
dref = abs(L[0]-L[1])
for i in range(n) :
for j in range(i+1, n) :
if abs(L[i] - L[j]) < dref :
dref = abs(L[i] - L[j])
return dref
plus_petite_distance([-2,1,8,0])
1
Q4. Pour les plus rapides. En modifiant le code de la fonction plus_petite_distance
, écrire une fonction
valeurs_plus_proches
d’argument toujours L
et renvoyant, sous forme de tableau, les paires dont les
valeurs sont les plus proches.
Ainsi, valeurs_plus_proches([-2,1,6,8,3,-9,-7])
doit renvoyer [[1,3],[6,8],[-9,-7]]
.
Alors que valeurs_plus_proches([-2,1,6,8,3,-9,-7,4])
doit renvoyer [[3,4]]
.
def valeurs_plus_proches(L) :
n = len(L)
dref = abs(L[0]-L[1])
liste = [ [ L[0], L[1] ] ]
for i in range(n) :
for j in range(i+1, n) :
if abs(L[i] - L[j]) < dref :
dref = abs(L[i] - L[j])
liste = [ [ L[i], L[j] ] ]
elif abs(L[i] - L[j]) == dref :
liste.append([ L[i], L[j] ])
return liste
valeurs_plus_proches([-2,1,6,8,3,-9,-7])
[[1, 3], [6, 8], [-9, -7]]
valeurs_plus_proches([-2,1,6,8,3,-9,-7,4])
[[3, 4]]
On souhaite déterminer à quelles positions le facteur f
est présent dans la chaı̂ne de caractères ch
.
On supposera, pour simplifier, que les chaı̂nes de caractères ch
et f
ne sont pas vides, et que la longueur de f
est
inférieure (ou égale) à celle de ch
.
Q5. Écrire une fonction positions_facteurs
prenant en argument les chaı̂nes de caractères ch
et f
, et renvoyant
les positions du facteur f
dans la chaîne ch
.
On pourra introduire n
la longueur de f
et tester si ch[0:n]==f
, puis si, ch[1:n+1]==f
...
Ainsi, positions_facteurs(’blablabla’,’bla’)
doit renvoyer [0,3,6]
.
def positions_facteurs(ch ,f) :
n = len(f)
liste = []
for k in range(0, len(ch)-n+1) :
if ch[k:k+n] == f :
liste.append(k)
return liste
positions_facteurs('blablabla', 'bla')
[0, 3, 6]
Q6. Dans cette question, on s’interdit d’utiliser la comparaison de sous-chaı̂nes de caractères. Ecrire une fonction
positions_facteurs_prim
qui réalise la même chose que positions_facteurs et qui n’utilise que des
comparaisons caractère à caractère, c’est à dire des instructions comme ch[0]==f[0]
.
def positions_facteurs_prim(ch ,f) :
n = len(f)
liste = []
for k in range(0, len(ch)-n+1) :
flag = True
for j in range(n) :
if ch[k+j] != f[j] :
flag = False
if flag :
liste.append(k)
return liste
positions_facteurs_prim('blablabla', 'bla')
[0, 3, 6]
Nous verrons plus tard dans l’année les différents algorithmes de tri d’une liste dans un TP spécifique. Dans cette partie, nous nous intéressons uniquement au tri à bulles.
Le tri à bulles est un algorithme de tri dont le principe est de faire remonter à chaque étape le plus grand élément du tableau à trier, comme les bulles d’air remontent à la surface de l’eau (d’où le nom de l’algorithme).
Commençons par un exemple du fonctionnement de l’algorithme. On souhaite trier la liste de nombres : [2, 5, 4, 3, 1]
.
[2, 5, 4, 3, 1]
, on compare 2
et 5
et on ne fait rien car 2 <= 5
;[2, 5, 4, 3, 1]
, on compare 5
et 4
et on les échange car 5 > 4
;[2, 4, 5, 3, 1]
, on compare 5
et 3
et on les échange;[2, 4, 3, 5, 1]
, on compare 5
et 1
et on les échange;[2, 4, 3, 1, 5]
, fin du premier passage. Le dernier élément est à la bonne place.[2, 4, 3, 1, 5]
, on compare 2
et 4
et on ne fait rien ; on compare 4
et 3
et on les échange ;[2, 3, 4, 1, 5]
, on compare 4
et 1
et on les échange ;[2, 3, 1, 4, 5]
, fin du deuxième passage. L’avant-dernier élément est à la bonne place.[2, 3, 1, 4, 5]
, on compare 2
et 3
et on ne fait rien ; on compare 3
et 1
et on les échange ;
[2, 1, 3, 4, 5]
, fin du troisième passage.[2, 1, 3, 4, 5]
, on compare 2
et 1
et on les échange ;[1, 2, 3, 4, 5]
, fin du quatrième passage. La liste est triée.Q7. Appliquer << à la main >> l’algorithme sur la liste [5, 1, 2, 3, 6, 4]
afin de vous familiariser avec ce tri.
[5, 1, 2, 3, 6, 4]
, on compare 5
et 1
et on ne fait rien car 5 > 1
;[1, 5, 2, 3, 6, 4]
, on compare 5
et 2
et on les échange car 5 > 2
;[1, 2, 5, 3, 6, 4]
, on compare 5
et 3
et on les échange;[1, 2, 3, 5, 6, 4]
, on compare 5
et 6
et on ne fait rien;[1, 2, 3, 5, 6, 4]
, on compare 6
et 4
et on les échange;[1, 2, 3, 5, 4, 6]
, fin du premier passage. Le dernier élément est à la bonne place.[1, 2, 3, 5, 4, 6]
, on compare 1
et 2
et on ne fait rien ; on compare 2
et 3
et on ne fait rien ; on compare 3
et 5
et on ne fait rien ; on compare 5
et 4
et on les échange ;[1, 2, 3, 4, 5, 6]
, fin du deuxième passage. L'avant-dernier élément est à la bonne place.[1, 2, 3, 4, 5, 6]
, on compare 1
et 2
et on ne fait rien ; on compare 2
et 3
et on ne fait rien ; on compare 3
et 4
et on ne fait rien ;
[1, 2, 3, 4, 5, 6]
, fin du troisième passage. L'avant-avant-dernier élément est à la bonne place.[1, 2, 3, 4, 5, 6]
, on compare 1
et 2
et on ne fait rien ; on compare 2
et 3
et on ne fait rien ;
[1, 2, 3, 4, 5, 6]
, fin du quatrième passage. Les quatre derniers éléments sont à la bonne place.[1, 2, 3, 4, 5, 6]
, on compare 1
et 2
et on ne fait rien ;
[1, 2, 3, 4, 5, 6]
, fin du cinquième passage. La liste est triée.Q8. Compléter la fonction premier_passage
ci-dessous. Celle-ci doit prendre en argument une liste L
et renvoyer
une copie de cette liste ayant subi un passage de l’algorithme du tri à bulles.
def premier_passage(L) :
M = L.copy()
for i in range(len(L)-1) :
if M[i] > M[i+1] :
M[i], M[i+1] = M[i+1], M[i] # affectation simultanée
return M
Ainsi, premier_passage([-2,8,1,0])
doit renvoyer [-2,1,0,8]
.
premier_passage([-2,8,1,0])
[-2, 1, 0, 8]
Q9. Écrire une fonction tri_bulles
implémentant l’algorithme de tri à bulles. On pourra partir de la fonction
précédente et la modifier. On testera ensuite cette fonction avec une liste aléatoire de nombres entiers L
.
Pour générer une liste L
de n
nombres entiers aléatoires compris dans l’intervalle d’entiers $[\![a,b]\!]$, on peut écrire
L =[randint(a,b) for i in range(n)]
, sans oublier d’importer la fonction randint
via from random import randint
.
def tri_bulles(L) :
M = L.copy()
n = len(L)
for j in range(n-1) :
for i in range(n-j-1) :
if M[i] > M[i+1] :
M[i], M[i+1] = M[i+1], M[i] # affectation simultanée
return M
from random import randint
L =[randint(-50,50) for i in range(20)] # 20 entiers entre -50 et 50
print(L)
print(tri_bulles(L))
[25, -45, -28, -21, -46, 24, -36, -14, -5, 27, -26, -31, -43, -50, -9, 19, 37, -38, -39, -14] [-50, -46, -45, -43, -39, -38, -36, -31, -28, -26, -21, -14, -14, -9, -5, 19, 24, 25, 27, 37]
Q10. Pour les plus rapides. Déterminer, en fonction de la longueur de la liste en argument, le nombre de comparaisons effectuées par cet algorithme.
Dans la boucle intérieure on fait une seule comparaison. Donc cette boucle en effecteur $n-j-2+1=n-j-1$.
Au total avec les deux boucles: $\displaystyle\sum_{j=0}^{n-2}(n-j-1)=\sum_{j'=1}^{n-1}j'=\frac{n(n-1)}{2}$.
La complexité est quadratique.
Q11. Pour les plus rapides. À partir de l’exemple de la question 7, proposer une optimisation de l’algorithme permettant de gagner du
temps dans les meilleurs cas. Implémenter cette optimisation par une fonction tri_bulles2
.
On arrête l'algorithme si un passage n'a effectué aucun échange: cela signifie que la liste est déjà triée.
def tri_bulles2(L) :
M = L.copy()
n = len(L)
for j in range(n-1) :
flag = False # pour tester si le j-ième passage effectue un échange
for i in range(n-j-1) :
if M[i] > M[i+1] :
M[i], M[i+1] = M[i+1], M[i] # affectation simultanée
flag = True # on a fait un échange
if not(flag) : # si on n'a pas fait d'échange
return M # on arrête tout et on renvoie M
return M
print(tri_bulles2(L))
[-45, -28, -21, -46, 24, -36, -14, -5, 25, -26, -31, -43, -50, -9, 19, 27, -38, -39, -14, 37]
Q12. Pour les plus rapides. Comparer les temps d’exécution des fonctions tri_bulles
et tri_bulles2
sur une liste de $1000$ éléments.
Pour calculer le temps d’exécution d’une fonction, on peut utiliser la fonction time
de la bibliothèque time
.
Le plus facile étant de créer deux variables start = time.time()
et end = time.time()
entre lesquelles on
exécute l’algorithme étudiée, puis d’afficher start - end
.
import time
L =[ randint (1 ,100) for i in range (1000) ]
start = time.time()
tri_bulles(L)
end = time.time()
duree = end - start
print ( " temps d'exécution première méthode : " , duree, " s " )
start = time.time()
tri_bulles2(L)
end = time.time()
duree = end - start
print ( " temps d'exécution deuxième méthode : " , duree, " s " )
temps d'exécution première méthode : 0.04012441635131836 s temps d'exécution deuxième méthode : 3.600120544433594e-05 s
On voit qu'on a amélioré le temps d'exécution d'un facteur 1000.