Histoire de boulons
Une boîte à outils contient \(n\) écrous de diamètres tous différents et \(n\) vis correspondantes, mais tout est mélangé !
Une association écrou+vis de même diamètre forment un boulon
L’objectif est d’
chaque écrou avec la vis qui lui correspond.Le seul type d’opération autorisé consiste à essayer un écrou avec une vis, ce qui peut amener trois réponses possibles :
- soit l’écrou est strictement plus large que la vis,
- soit il est strictement moins large,
- soit ils ont exactement le même diamètre.
On se propose d’implémenter des algorithmes en Python à partir de deux listes comportant les mêmes valeurs, mais dans un ordre différent :
import random # Génération de deux listes n = 10 E0 = list(range(n)) random.shuffle(E0) # écrous V0 = list(range(n)) random.shuffle(V0) # vis
Pour apparier les vis et les écrous, il suffit de prendre une vis arbitrairement, de la tester avec tous les écrous.
On encapsulera cet algorithme dans une fonction
boulon_1(V, E, B)
qui attend 3 arguments de type liste, de mêmes tailles : la première contenant les vis, la deuxième contenant les écrous et la dernière destinée à recevoir les boulons (des tuples (indice_vis, indice_écrou)). Cette fonction de renvoie donc rien !Exemple : si on définit les listes d’écrous, de vis et de boulons ainsi …
V = [7, 9, 3, 4, 1, 0, 2, 5, 6, 8] E = [6, 2, 5, 0, 3, 8, 9, 4, 7, 1] B = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # on prérempli B avec n'importe quoi ...
Après l’appel à la fonction boulon_1(V, E, B)
, B
vaut :
[(0, 8), (1, 6), (2, 4), (3, 7), (4, 9), (5, 3), (6, 1), (7, 2), (8, 0), (9, 5)]
Afin d’évaluer plus précisément le coût temporel de cette opération, on se propose d’utiliser le module Python timeit
.
from timeit import timeit duree_en_secondes = timeit("expression Python à évaluer", setup="expression Python à exécuter avant", globals=globals(), # Chargement de toutes les variables globales number=10) # Nombre d'essais
Et pour afficher les résultats, on réalisera plusieurs essais de l’algorithme, avec des tailles de liste différentes, et on affichera la durée d’exécution en fonction de la quantité de boulon à constituer, à l’aide du module matplotlib
:
import matplotlib.pyplot as pl pl.plot(liste_des_abscisses, liste_des_ordonnees, label = "un_nom_pour la légende") pl.legend () # Ajout d'une légende pl.show() # Affichage du graphique
boulon_1()
(faire une fonction boulon_2()
) de sorte qu’une fois que l’écrou compatible avec la vis a été trouvé, on cesse de chercher parmi les écrous.
Supposons qu’au lieu de vouloir apparier toutes les vis avec leur écrou, on souhaite juste trouver le plus petit écrou et la vis correspondante.
vis_mini(V, E)
.