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 rechercher les coordonnées 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
Dans cet exercice, nous étudions les listes de nombres entiers ordonnées de façon strictement croissante. Un exemple d'une telle liste est [-1,0,3,5]; la liste [-1,0,0,2] ne l'est pas (puisque 0 et 0 sont égales).
Étant donnée une liste de nombres entiers, comme [-2,0,3,4] ou [3,-2,0], écrivez une fonction def is_sorted(l) avec la spécification suivante:
def is_sorted ( l ): """ Retourne si la liste l est ordonnée de façon strictement croissante. Args: l: une liste de nombres entiers, positif ou négatif Retourne: Un booléen qui indique si la liste l est ordonnée de façon strictement croissante. """
Étant données deux listes ordonnées de façon strictement croissante, 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 [-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 première implémentation de cette idée est donnée ci-dessous.
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 = [] for e1 in range(len(l1)): for e2 in range(len(l2)): if e2 == e1: l.append ( e1 ) return l
Malheureusement, le code ne fonctionne pas encore correctement. Écrivez un test qui montre que le code n'est pas correct.
Donnée est une liste de coordonnées, comme par exemple:
coordonnees = [(0,1),(2,3),(0,1),(4,5),(1,2),(0,1),(1,1),(0,2),(1,1)]
Étudiez le code suivant:
coordonnees = [(0,1),(2,3),(0,1),(4,5)] def f ( v ): return v*v def increment ( l ): for i in range(len(l)): l[i][0] = f(l[i][0]) increment ( coordonnees ) assert coordonnees == [(0,1),(4,3),(0,1),(16,5)]
Malheureusement le code donne une erreur et ne passe pas le test. Corrigez une ligne de la fonction increment(l) de telle sorte que le code passe le test.
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 donné dans cette structure de données. Copiez le code du cours et modifiez-le.
On peut appliquer l'algorithme de question 3 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.
Pour cette mission, vous devez écrire des fonctions et tester leur bon fonctionnement. Comme dans les exercices de préparation, 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 toutes 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().
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 fonctions (en plus de la variable all_communes). 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)
Les questions ci-dessous sont des questions supplémentaires de Question 1 de la phase de préperation; ce sont des questions à faire sur papier.
Déterminez combien de fois la ligne de code if e2 == e1: est executée pour le cas de test suivant:
assert intersect ( list(range(100)), list(range(100)) ) == list(range(100))
On va essayer de résoudre le problème plus efficacement. Une idée 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 partie de la deuxième liste qu'on n'a pas encore parcouru. 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.
Écrivez quelques testes qui permettent de découvrir que le code n'est pas correct.
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 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.