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

  1. Proposez une fonction rand qui prend en argument un entier N et qui retourne une liste de taille N contenant des entiers de l’intervalle \([0, 100]\) (on pourra utiliser la fonction randint du module random.

  2. 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.

  3. Testez votre algorithme.

  4. 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.

  5. Testez votre nouvelle version de l’algorithme.

Hide 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.

Hide 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…

Hide 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.

Hide 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…

Hide 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