3.6. Exercices#
N’oubliez pas de documenter les fonctions. C’est indispensable pour bien écrire du code.
3.6.1. Le tri bulle#
Le tri bulle est un algorithme de tri (par défaut, nous considérons que le tri est fait dans l’ordre croissant). L’algorithme parcourt le tableau et compare les éléments consécutifs. Lorsque deux éléments consécutifs ne sont pas dans l’ordre, ils sont échangés.
Après un premier parcours complet du tableau, le plus grand élément est forcément en fin de tableau, à sa position définitive. En effet, aussitôt que le plus grand élément est rencontré durant le parcours, il est mal trié par rapport à tous les éléments suivants, donc échangé à chaque fois jusqu’à la fin du parcours.
Après le premier parcours, le plus grand élément étant à sa position définitive, il n’a plus à être traité. Le reste du tableau est en revanche encore en désordre. Il faut donc le parcourir à nouveau, en s’arrêtant à l’avant-dernier élément. Après ce deuxième parcours, les deux plus grands éléments sont à leur position définitive. Il faut donc répéter les parcours du tableau, jusqu’à ce que les deux plus petits éléments soient placés à leur position définitive.
Questions
Proposez une fonction
rand
qui prend en argument un entierN
et qui retourne une liste de tailleN
contenant des entiers de l’intervalle \([0, 100]\) (on pourra utiliser la fonctionrandint
du modulerandom
.Proposez une fonction
tri_bulle
qui prend en argument une liste et qui retourne la liste triée selon l’algorithme du tri par sélection.Testez votre algorithme.
Modifiez votre fonction pour qu’elle accepte un argument optionnel qui sera une fonction d’ordre. Par défaut, vous prendrez la fonction
lambda x, y: True if x < y else False
.Testez votre nouvelle version de l’algorithme.
Show code cell source
from random import randint
def rand(N):
"""
retourne une liste de taille N
contenant des entiers alétoires entre 0 et 100
"""
l = []
for _ in range(N):
l.append(randint(0, 100))
return l
def tri_bulle(T, f=lambda x, y: True if x < y else False):
"""tri bulle"""
for j in range(len(T)): # tri du j-eme élément en partant de la fin
tbl_trie = True
for i in range(len(T)-j-1):
if not f(T[i], T[i+1]):
T[i], T[i+1] = T[i+1], T[i]
tbl_trie = False
if tbl_trie:
break
return T
T = rand(20)
print(T)
print(tri_bulle(T))
print(tri_bulle(T, lambda x, y: True if x > y else False))
[58, 31, 21, 1, 47, 42, 49, 35, 34, 45, 87, 36, 39, 1, 29, 11, 18, 72, 58, 53]
[1, 1, 11, 18, 21, 29, 31, 34, 35, 36, 39, 42, 45, 47, 49, 53, 58, 58, 72, 87]
[87, 72, 58, 58, 53, 49, 47, 45, 42, 39, 36, 35, 34, 31, 29, 21, 18, 11, 1, 1]
3.6.2. Manipulation de fonctions#
Dans cet exercice, nous construisons des fonctions qui prennent en arguments des fonctions et qui retournent des fonctions.
Questions
Créez une fonction
add
qui prend en argument deux fonctions \(f\) et \(g\) et qui retourne la fonction \(f+g\).Créez une fonction
mul
qui prend en argument deux fonctions \(f\) et \(g\) et qui retourne la fonction \(f*g\).Utilisez les deux fonctions précédentes pour fabriquer la fonction polynomiale \(X^2+1\) et testez cette nouvelle fonction.
Show code cell source
def add(f, g):
"""additionne deux fonctions"""
def fpg(x):
return f(x) + g(x)
return fpg
def mul(f, g):
"""multiplie deux fonctions"""
def fmg(x):
return f(x) * g(x)
return fmg
X = lambda x: x
Un = lambda x: 1
P = add(mul(X, X), Un)
print(P(2))
5
3.6.3. Construction d’une fonction qui affiche tous ses arguments…#
Pour bien prendre en main la façon dont on accède aux arguments d’une fonction, nous allons fabriquer une fonction qui prend un nombre arbitraire d’arguments éventuellement rangés dans des listes ou des tuples et qui les affiche.
Question
Proposez une fonction
affiche_0
qui prend un nombre arbitraire d’arguments et les affiche brutalement (sans se préoccuper du type des objets passés en argument).Documentez et testez votre fonction…
Show code cell source
def affiche_0(*args):
"""affiche tous les arguments"""
for argk in args:
print(argk, end=' ')
affiche_0("toto", 1, [2, 3], [1, [2, 3]])
toto 1 [2, 3] [1, [2, 3]]
Question
Modifiez la fonction précédente en une fonction
affiche_1
qui “entre” dans les listes, c’est-à-dire qu’elle affiche les éléments des listes plutôt que la liste complète.Documentez et testez votre fonction…
Indication
Pour tester si un élément est une liste, vous pourrez utiliser la commande isinstance
.
Show code cell source
def affiche_1(*args):
"""affiche tous les arguments"""
for argk in args:
if isinstance(argk, list):
for argki in argk:
print(argki, end=' ')
else:
print(argk, end=' ')
affiche_1("toto", 1, [2, 3], [1, [2, 3]])
toto 1 2 3 1 [2, 3]
Question
Modifiez la fonction précédente en une fonction
affiche_2
qui “entre” dans les listes jusqu’au plus bas niveau, c’est-à-dire qu’elle affiche les éléments des listes plutôt que la liste complète et cela même pour les listes de listes…Documentez et testez votre fonction…
Indication
Pensez récursif…
Show code cell source
def affiche_2(*args):
"""affiche tous les arguments"""
for argk in args:
if isinstance(argk, list):
for argki in argk:
affiche_2(argki)
else:
print(argk, end=' ')
affiche_2("toto", 1, [2, 3], [1, [2, 3]])
toto 1 2 3 1 2 3