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’apparier 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.

Écrire un algorithme simple qui apparie chaque écrou avec sa vis.
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
Faire afficher la courbe durée d’exécution en fonction de la quantité de boulons à constituer (on choisit de faire varier la quantité de boulons jusqu’à 1000, en 20 étapes).

 

Calculer l’ordre de complexité de cette fonction, et vérifier la cohérence avec la courbe obtenue.

 

 

Améliorer la fonction 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.

Montrer que ce problème peut être résolu en \(2n-1\) essais, dans le pire des cas. Implémenter cet algorithme dans une fonction vis_mini(V, E).

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *