Objectifs individuels

A l’issue de ce problème, chacun d’entre vous :

• sera en mesure d’exploiter les notions suivantes :

  • tuples
  • algorithmes de recherche linéaire et binaire
  • tests

• aura modifié un algorithme de recherche binaire pour l'utilisation dans une situation spécifique
• aura découpé un gros problème en petits problèmes

Objectifs collectifs

A l’issue de ce problème, le groupe tout entier :

• aura montré sa capacité à travailler ensemble pour répondre à une série de questions relatives à ce qui aura été appris dans le cadre de la mission,
• peut lire et écrire des spécifications qui sont lisibles pour les autres membres de l'équipe,
• peut écrire des testes pour vérifier la fonctionnalité de fonctions écrites par d'autres membres de l'équipe.

Questions à choix multiple

Les questions à choix multiples de cette mission sont également accessibles en ligne depuis https://inginious.info.ucl.ac.be/course/LSINF1101-PYTHON/Session5_QCM

Question 1

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.
      """
  

• Écrivez 6 tests en utilisant assert pour évaluer si la fonction is_sorted(l) a été mise en oeuvre correctement.

• É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.

• Écrivez un test sur lequel le code (incorrect) marche correctement; dans ce test la fonction doit être appelée avec deux listes de longueur 3.

• Corrigez l'erreur en modifiant deux lignes de code de la fonction.

Question 2

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)]

• Étant donnée une coordonnée (i,j), créez une fonction count(cordonnees,i,j) pour calculer le nombre de fois que la coordonnée (i,j) apparaît dans la liste.

• É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.

Question 3

Question 4

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.