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
É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 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!