Vous travaillez pour une entreprise qui est active dans toute la Belgique. En tant que composant d'un système plus grand, l'entreprise a besoin d'outils qui permettent de trouver l'emplacement des communes belges. Vous avez trouvé une liste des communes et leur coordonnées GPS en ligne et devez utiliser Python pour créer les outils demandés.
A l’issue de ce problème, chacun d’entre vous :
A l’issue de ce problème, le groupe tout entier :
La matière relative à cette mission est décrite dans les sections suivantes du syllabus en ligne :
Les questions à choix multiples de cette mission sont également accessibles en ligne depuis https://inginious.info.ucl.ac.be/course/LSINF1101-PYTHON/Session5_QCM
Donnée est une liste d'événements qui ont lieu sur certains coordonnées. Un exemple d'une telle liste est la suivante:
events = [(0,1),(2,3),(0,1),(4,5),(1,2),(0,1),(1,1),(0,2),(1,1)]
Donnée est une coordonnée (i,j), créez une fonction count(events,i,j) pour calculer le nombre d'événement sur cette coordonnée.
Étant données deux listes ordonnées de nombres entiers, on veut calculer une nouvelle liste ordonnée des nombres entiers qui sont communs entre les deux listes. Par exemple, étant données les listes ordonnées [-2,-1,0,1,2,3,4] et [0,1,2,5,6], on veut calculer la liste [0,1,2], qui contient les nombres entiers [0,1,2] qui sont communs entre les deux listes.
Une idée pour calculer cette liste est de parcourir les deux listes en même temps; pour chaque élément de la première liste, on regarde si on peut trouver l'élément dans la deuxième partie qu'on n'a pas encore regardé. Cette idée a été mise en oeuvre dans la fonction suivante:
def intersect ( l1, l2 ): """ Retourne une liste ordonnée des nombres entiers communs entre l1 et l2. Args: l1: une liste ordonnée de nombres entiers, positif ou négatif l2: une liste ordonnée de nombres entiers, positif ou négatif Retourne: Une liste ordonnée de nombres entiers communs entre l1 et l2. """ l = [] p1 = 0 p2 = 0 while p1 < len(l1): while l1[p1] > l2[p2]: p2 += 1 if l1[p1] == l2[p2]: l.append ( p2 ) p1 += 1 return l
Malheureusement, le code ne fonctionne pas encore correctement.
Dans les exercices suivants, on va étudier une répresentation d'un ensemble de chaînes de caractères et un ordre de ces chaînes. Cette répresentation se compose d'une liste de tuples; dans chaque tuple, le premier élément contient une chaîne de caractères; le deuxième élément contient la position de l'élément suivant dans l'ordre voulu. Par exemple :
l = [ ( "", 2 ), ( "Bertram", 5 ), ( "Anna", 1 ), ( "Xavier", None ), ( "Nicolas", 3 ), ( "Dominic", 4 ) ]
On suppose que le premier tuple correspond toujours à la chaîne de caractères vide; si il n'y pas un élément suivant, on utilise None. Notez que dans la liste, on peut avoir seulement un élément None.
L'ordre des chaînes de caractères indiqué par les nombres entiers dans cette liste est ["Anna","Bertram","Dominic","Nicolas","Xavier"] -- par conséquent, l'ordre alphabétique.
Étudiez maintenant la spécification suivante d'une fonction is_sorted_tuple_list(l).
def is_sorted_tuple_list ( l ): """ Détermine si l se compose d'une liste de tuples ordonnés par ordre alphabétique. Une liste est considérée ordonnée par ordre alphabétique si e[0] < l[e[1]][0], pour tous les éléments de la liste tels que e[1] != None; en plus, l[i][0] doit correspondre à ""; il ne peut y avoir qu'un seul tuple dans la liste pour lequel e[1] == None. Args: l: une liste de tuples, dont chacun se compose d'une chaîne de caractères et un nombre entier ou None. Returns: True si l se compose d'une liste de tuples (chaîne de caractères, nombre entier) ordonnés, False si non. """
Écrivez quelques tests en utilisant assert pour évaluer l'exactitude de cette fonction.
Faites une implémentation de la fonction is_sorted_tuple_list et évaluez-la en utilisant les tests d'exercice 3.
Étudiez la spécification de la fonction suivante.
def get_index ( l, s ): """ Retourne l'indexe de la plus grande chaîne de caractères plus petite que s dans la liste l. Une chaîne de caractères en l est plus petite que s, si cette chaîne est plus petite dans l'ordre alphabétique ou égale. Args: l: une liste de tuples, dont chacun se compose d'une chaîne de caractères et un nombre entier ou None; la première chaîne de caractères en l est "". s: une chaîne de caractères. Retourne: L'indexe de la chaîne de caractères la plus grande en l, mais plus petite que s. """
Écrivez quelques tests pour évaluer l'exactitude de cette fonction.
Créez une implémentation de la fonction get_index et évaluez-la avec vos tests.
Étudiez la spécification de la fonction suivante.
def add ( l, s ): """ Ajoute la chaîne de caractères s à la liste ordonnée de telle sorte que la liste reste ordonnée. Si s se trouve déjà dans la liste, la liste n'est pas modifiée. Une liste est considérée ordonnée par ordre alphabétique si e[0] < l[e[1]][0], pour tous les éléments de la liste tels que e[1] != None; en plus, l[i][0] doit correspondre a ""; il ne peut y avoir qu'un seul tuple dans la liste pour lequel e[1] == None. Si la chaîne s ne se trouve pas déjà dans la liste, la fonction ajoute l'élément à la fin de la liste l, de telle sorte que les nombres entiers continuent à indiquer l'ordre alphabétique des chaines de caractères. Args: l: une liste de tuples, dont chacun se compose d'une chaîne de caractères et un nombre entier ou None; la première chaîne de caractères en l est "". Les nombres entiers indiquent l'ordre alphabétique des chaines de caractères. s: une chaîne de caractères. Retourne: Rien; l est modifiée comme indiqué. """
Écrivez quelques tests pour évaluer l'exactitude de cette fonction.
Écrivez une implémentation de cette fonction et évaluez-la avec vos tests; considérez réutiliser une fonction que vous aviez écrite pour un exercice précédent! Cet exercice est le dernier exercice sur le sujet de listes ordonnées.
On représente les cours suivis par des étudiants en utilisant des listes imbriquées, comme suit:
[('LINFO1101', ['Jean', 'Pierre']), ('LINFO1110', ['Jean']),\ ('LINFO1111', ['Jean']), ('LINFO1112', ['Jacques', 'Pierre']),\ ('LINFO1113', ['Pierre'])]
Donnez un algorithme binary_search(course,list_of_courses) pour trouver tous les étudiants d'un cours dans cette structure de données. Copiez le code du cours et modifiez-le.
On peut appliquer l'algorithme de question 9 pour trouver les étudiants de plusieurs cours. Supposez que chaque fois que vous calculez middle, tu imprimes la valeur calculée pour middle. Dans ce cas, le nombre de valeurs imprimées pour middle correspond à la nombre de fois que la boucle while est exécutée. Combien de fois est-ce que la boucle est exécutée pour l'exemple suivant ?
La liste est:
[('LINFO1101', ['Jean', 'Pierre']), ('LINFO1110', ['Jean']),\ ('LINFO1111', ['Jean']), ('LINFO1112', ['Jacques', 'Pierre']), \ ('LINFO1113', ['Pierre'])]
Les cours donnés sont: LINFO1110, LINFO1112, LINFO1111, LINFO1114.
On suppose donnés deux noms de cours et une structure de données comme donnée en question 9. Écrivez un algorithme pour retourner tous les noms de cours entre les deux noms spécifiés.
Notez qu'il y a beaucoup d'algorithmes qu'on pourrait utiliser pour cette tâche. On pourrait modifier binary_search, ou utiliser binary_search pour le premier nom, le deuxième nom, etc. Réfléchissez sur les différents algorithmes possibles!
Pour cette mission, vous devez écrire des fonctions et tester leur bon fonctionnement. Comme dans les exercices de préperation, vous devez travailler à deux de cette façon: pendant qu'un étudiant écrit une fonction, l'autre développe la fonction de test correspondante. Lorsqu'une fonction est correctement spécifiée, on peut écrire les tests permettant de vérifier son bon fonctionnement sans connaître son code.
Dans cette mission vous allez créer plusieurs fonctions qui fonctionnent sur une liste de communes de la Belgique.
Téléchargez le fichier sorted_belgian_communes.py, qui contient une liste de toutes les communes de la Belgique ainsi que leurs coordonnées (selon une projection Mercator). Ecrivez toutes les fonctions demandées durant cette mission dans ce fichier.
Finalement, appliquez votre fonction à la liste all_communes.
Écrivez une fonction distance(commune1, commune2, all_communes) pour calculer la distance euclidienne entre deux communes dont les noms sont donnés. La distance euclidienne entre deux coordonnées (x1,y1) et (x2,y2) est:
Rappel: le module math contient une implémentation d'une fonction sqrt. Écrivez une fonction auxiliaire pour calculer la distance entre deux coordonnées (x1,y1) et (x2,y2).
De nouveau: ajoutez des spécifications pour toutes les fonctions, ainsi que des tests, dans une fonction test_distance().
Écrivez une fonction tour_distance(communes, all_communes) pour calculer la distance totale d'une tournée à travers tous les communes dans la liste communes. La tournée commence à communes[0], va ensuite vers communes[1], communes[2], ..., communes[-1], pour finalement retourner à communes[0].
De nouveau: ajoutez des spécifications pour la fonction, ainsi que des tests, dans une fonction test_tour_distance().
Écrivez une fonction closest(commune, all_communes) pour calculer la commune la plus proches d'une commune donnée commune. Ajoutez les spécifications pour cette fonction, ainsi que des testes pour vérifier l'exactitude de la fonction, dans une fonction test_closest ().
Pour cette mission, vous devez soumettre votre fichiers sorted_belgian_communes.py et README.txt au serveur de soumissions de programmes du cours. Les fonctions et les testes doivent être dans le même fichier. Le fichier ne doit contenir que des fonctinos. Votre fichier sorted_belgian_communes.py doit au moins contenir les fonctions :
verify_order(communes) coordinate(commune,all_communes) distance(commune1, commune2, all_communes) tour_distance(communes, all_communes) closest(commune all_communes)
Donnée est une liste de coordonnées. Par exemple:
l = [ ( 2.0, 5.0 ), ( 8.0, 12.0 ), ( 10.0, 40.0 ), (8.0, 50.0), (8.0, 50.0) ]
Nous voulons créer un dictionnaire pour identifier rapidement les valeurs y pour une x donnée. Pour l'exemple:
d = { 2.0: [ 5.0 ], 8.0: [ 12.0, 50.0, 50.0 ], 10.0: [ 40.0 ] }
Écrivez une fonction create_dict(l) qui crée cette dictionnaire (pas limité à cet exemple).
Donnée est une liste de coordonnées, comme dans l'exercice précédente. Nous voulons créer un dictionnaire pour identifier rapidement la valeur maximale y pour une x donnée. Pour l'exemple:
d = {2.0: 5.0, 8.0: 50.0, 10.0: 40.0}
Écrivez une fonction create_dict_max(l) qui crée ce dictionnaire (pas limité à cet exemple).
def get_ordered_list ( l ): """ Retourne les chaînes de caractères dans la liste l dans l'ordre indiquée par la liste l L'ordre est déterminée par les nombres entiers dans la liste: pour chaque tuple e dans la liste l, le successeur est l[e[1]], si e[1] != None. Args: l: une liste de tuples, dont chacun se compose d'une chaîne de caractères et un nombre entier ou None; les nombres entiers définissent un ordre total sur les éléments de la liste. Retourne: Les chaines de caractères dans la liste l dans l'ordre indiqué par les nombres entiers. """
Nous avons la structure de données suivante pour stocker la relation entre étudiants et cours qu'ils ont suivis:
student_courses = [ ( "Jean", "LINFO1111" ), ( "Jean", "LINFO1101"), \ ( "Pierre", "LINFO1101" ), ( "Pierre", "LINFO1112" ) ]
Écrivez le code pour ajouter un tuple ("Jacques", "LINFO1112") à student_courses.
Créez une fonction students(course, student_courses) qui, pour un cours donné, renvoie une liste des étudiants qui suivent le cours. Par exemple, si on appelle la fonction avec "LINFO1101" et la liste de la question 3 comme paramètres, le résultat doit être ["Jean", "Pierre"].
On présume qu'il n'y a pas d'ordre dans la liste student_courses.
Écrivez une fonction remove_student(student,student_courses) qui, pour un étudiant donné présent dans une liste donnée, retourne la liste sans les tuples qui concernent cet étudiant.
Par exemple, si on appelle la fonction avec "Jean" et la liste de la question 1 comme paramètres le résultat doit être :
[ ( "Pierre", "LINFO1101" ), ( "Pierre", "LINFO1112" ) ]On présume qu'il n'y a pas d'ordre dans la liste student_courses.
Écrivez une fonction nest_students(student_courses) qui, pour chaque cours, crée une liste imbriquée des étudiants qui suivent le cours. Sur l'exemple précédent, la fonction doit retourner cette structure de données:
[('LINFO1101', ['Jean', 'Pierre']), ('LINFO1111', ['Jean']), ('LINFO1112', ['Pierre'])]
La liste doit être triée par ordre de cours. Utilisez le code de question 4 et de question 5 comme inspiration. Réfléchissez sur la question: comment est-ce qu'on peut ajouter un élément dans une liste imbriquée qui vient d'être créée?
Vous faites partie de l'organisation des 5 et 10 miles de Louvain-la-Neuve. Mais le système est tombé en panne juste avant le départ.
Il y avait deux étudiants pour prendre note des arrivées des coureurs. Heureusement, il n'y avait que deux lignes à compter. Votre job consiste à faire une liste de ces deux listes pour avoir un classement général.
Les listes que vous recevez sont une succession de ['name', time] avec le temps dans un ordre croissant. Créez une fonction merge(first_list, second_list) qui retournera une liste qui a les éléments des deux listes dans l'ordre.
En sciences informatiques, un algorithme de tri est un algorithme qui place les éléments d'une liste dans un certain ordre. Les ordres les plus utilisés sont l'ordre numérique et l'ordre lexicographique. Un tri efficace est important pour optimiser l'utilisation d'autres algorithmes (tels que les algorithmes de recherche ou de fusion) qui ont besoin d'une liste triée en entrée ; c'est aussi souvent utile pour la canonicalisation des données et pour produire des sorties lisibles par les humains. Plus formellement, la sortie doit satisfaire deux conditions :
Une fois de plus, c'est l'heure de la cérémonie de la répartition . Les premières années attendent en rangs devant un vieux chapeau, à la fois anxieux et excités. Le directeur fait un long discours pour les accueillir et laisse la place à un mystérieux intervenant.
Tous les premières années sont ébahis lorsque le Choixpeau Magique brise le silence en chantant l'une de ses célèbres chansons.
Cependant, le choixpeau en fait un peu trop et rencontre quelques problèmes. Il perd sa voix et ne sera pas en état d'assurer la suite de la cérémonie. Heureusement, nous avons toujours accès aux connaissances des fondateurs et nous pourrons répartir les élèves avec votre aide.
Créez une fonction house_designation(student_qualities) qui va retourner une liste avec les noms des quatres maisons, la première étant celle où l'étudiant devrait aller et la dernière, celle qui convient le moins à l'étudiant. Pour décider de cette répartition, l'étudiant devrait être placé dans la maison où il a le plus d'affinités, c'est-à-dire, la maison avec laquelle il partage le plus de qualités. Si deux maisons sont à égalité, on les retourne dans l'ordre dans lequel elles sont placées dans les connaissances des fondateurs.