Tableaux
========

.. include:: common.rst.inc

Comparaisons et tests de tableaux
+++++++++++++++++++++++++++++++++

#. .. _tableaux_egaux:

   |exo| Déterminer si deux tableaux sont identiques ::

    def tableaux_egaux(a: [int], b: [int]) -> bool:
        """
        :entrée a: tableau d'int
        :entrée b: tableau d'int
        :sortie te: bool
        :post-cond: te est True si et seulement si len(a) == len(b) et
                    ∀ i ∈ [0;len(a)[, a[i] == b[i]

        >>> tableaux_egaux([1, 2, 4, 3], [1, 2, 4, 3])
        True
        >>> tableaux_egaux([1, 2, 4, 3], [9, 2, 4, 3])
        False
        >>> tableaux_egaux([1, 2, 4, 3], [1, 2, 4])
        False
        >>> tableaux_egaux([1, 2, 4], [1, 2, 4, 3])
        False
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
            (([1, 2, 4, 3], [1, 2, 4, 3]), (True,)),
            (([1, 2, 4, 3], [9, 2, 4, 3]), (False,)),
            (([1, 2, 4, 3], [1, 2, 3, 4]), (False,)),
            (([1, 2, 4, 3], [1, 2, 4]),    (False,)),
            (([1, 2, 4],    [1, 2, 4, 3]), (False,)),
            (([],           []),           (True,)),
            (([1, 2, 4, 3], []),           (False,)),
            (([],           [1, 2, 4, 3]), (False,)),
      ]
      </script>


#. .. _tableau_prefixe:

   |exo| Déterminer si le tableau b est un préfixe du tableau a ::

    def tableau_prefixe(a: [int], b: [int]) -> bool:
        """
        :entrée a: tableau d'int
        :entrée b: tableau d'int
        :sortie te: bool
        :post-cond: te est True si et seulement si len(a) >= len(b) et
                    ∀ i ∈ [0;len(b)[, a[i] == b[i]

        >>> tableaux_prefixe([1, 2, 4, 3], [1, 2, 4, 3])
        True
        >>> tableaux_prefixe([1, 2, 4, 3], [9, 2, 4, 3])
        False
        >>> tableaux_prefixe([1, 2, 4, 3], [1, 2, 4])
        True
        >>> tableaux_prefixe([1, 2, 4], [1, 2, 4, 3])
        False
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
            (([1, 2, 4, 3], [1, 2, 4, 3]), (True,)),
            (([1, 2, 4, 3], [9, 2, 4, 3]), (False,)),
            (([1, 2, 4, 3], [1, 2, 3, 4]), (False,)),
            (([1, 2, 4, 3], [1, 2, 4]),    (True,)),
            (([1, 2, 4],    [1, 2, 4, 3]), (False,)),
            (([],           []),           (True,)),
            (([1, 2, 4, 3], []),           (True,)),
            (([],           [1, 2, 4, 3]), (False,)),
      ]
      </script>


#. .. _tableau_palindrome:

   |exo| Retourner True si et seulement si le tableau a est un Palindrome ::

    def tableau_palindrome(a: [int]) -> bool:
        """
        :entrée a: tableau d'int
        :sortie p: bool
        :post-cond: p est True si et seulement si
                    ∀ i ∈ [0;len(a)[,  a[i] == a[len(a)-1-i]

        >>> tableau_palindrome([1, 2, 4, 3])
        False
        >>> tableau_palindrome([1, 2, 4, 2, 1])
        True
        >>> tableau_palindrome([1, 2, 2, 1])
        True
        >>> tableau_palindrome([4])
        True
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
        (([1, 2, 4, 3],),    (False,)),
        (([1, 2, 4, 2, 1],), (True,)),
        (([1, 2, 4, 2, 1],), (True,)),
        (([1, 2, 2, 1],),    (True,)),
        (([4],),             (True,)),
        (([], ),             (True,)),
        (([1, 2, 2, 3],),    (False,)),
      ]
      </script>



Recherche de valeurs
++++++++++++++++++++

#. .. _indice_min:

   |exo| Trouver l'indice du plus petit élément d'un tableau ::

    def indice_min(a: [float]) -> int:
        """
        :entrée a: tableau de float
        :pré-cond: len(a) > 0
        :sortie imin: int
        :post-cond: ∀ i ∈ [0;len(a)[, a[imin] ≤ a[i]

        >>> indice_min([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0])
        2
        >>> indice_min([2.0, 1.0, -3.0, 7.0, -3.0, 5.0, 1.0])
        2
        >>> # mais 4 est aussi une réponse correcte
        """

   NB : si le tableau contient plusieurs minima ex-æquo,
   cette spécification n'impose pas lequel doit être retourné.


#. .. _indice_min_gauche:

   |exo| Trouver l'indice le plus à gauche du plus petit élément d'un tableau ::

    def indice_min_gauche(a: [float]) -> int:
        """
        :entrée a: tableau de float
        :pré-cond: len(a) > 0
        :sortie imin: int
        :post-cond: ∀ i ∈ [0;imin[,       a[imin] < a[i],
                    ∀ i ∈ ]imin;len(a)[,  a[imin] ≤ a[i],

        >>> indice_min_gauche([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0])
        2
        >>> indice_min_gauche([2.0, 1.0, -3.0, 7.0, -3.0, 5.0, 1.0])
        2
        """

   NB : La différence avec indice_min_ ci-dessus est que,
   si le tableau contient plusieurs minima ex-aequo,
   cette spécification impose de retourner l'indice du plus à gauche.


#. .. _indice_min_droite:

   |exo| Trouver l'indice le plus à droite du plus petit élément d'un tableau ::

    def indice_min_droite(a: [float]) -> int:
        """
        :entrée a: tableau de float
        :pré-cond: len(a) > 0
        :sortie imin: int
        :post-cond: ∀ i ∈ [0;imin[,       a[imin] ≤ a[i],
                    ∀ i ∈ ]imin;len(a)[,  a[imin] < a[i],

        >>> indice_min_droite([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0])
        2
        >>> indice_min_droite([2.0, 1.0, -3.0, 7.0, -3.0, 5.0, 1.0])
        4
        """


#. .. _indice_max:

   |exo| Trouver l'indice du plus grand élément d'un tableau ::

    def indice_max(a: [float]) -> int:
        """
        :entrée a: tableau de float
        :sortie imax: int
        :pré-cond: len(a) > 0
        :post-cond: ∀ i ∈ [0;len(a)[, a[imax] ≤ a[i]

        >>> indice_max([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0])
        3
        >>> indice_max([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0])
        3
        >>> # mais 5 est aussi une réponse correct
        """

   NB : si le tableau contient plusieurs maxima ex-aequo,
   cette spécification n'impose pas lequel doit être retourné.


#. .. _indice_gauche:

   |exo| Trouver l'indice le plus à gauche de la valeur v dans un tableau ::

    def indice_gauche(a: [float], v: float) -> int:
        """
        :entrée a: tableau de float
        :entrée v: float
        :sortie ival: int
        :post-cond: si v ∈ a,  a[ival] = v  et  ∀ i ∈ [0;ival[, a[i] ≠ v
                    sinon      ival = -1

        >>> indice_gauche([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0], 2.0)
        0
        >>> indice_gauche([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0], 7.0)
        3
        >>> indice_gauche([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 7.0)
        3
        >>> indice_gauche([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0], 9.0)
        -1
        """


#. .. _indice_droite:

   |exo| Trouver l'indice le plus à droite de la valeur v dans un tableau ::

    def indice_droite(a: [float], v: float) -> int:
        """
        :entrée a: tableau de float
        :entrée v: float
        :sortie ival: int
        :post-cond: si v ∈ a,  a[ival] = v  et  ∀ i ∈ ]ival, len(a)[, a[i] ≠ v
                    sinon      ival = -1

        >>> indice_droite([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0], 2.0)
        0
        >>> indice_droite([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0], 7.0)
        3
        >>> indice_droite([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 7.0)
        5
        >>> indice_droite([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 9.0)
        -1
        """

#. .. _indice_n:

   |exo| Trouver l'indice de la n-ème occurrence de v dans un tableau ::

    def indice_n(a: [float], v: float, n: int) -> int:
        """
        :entrée a: tableau de float
        :entrée v: float
        :entrée n: int
        :sortie ival: int
        :pré-cond: n > 0
        :post-cond: si v apparaît au moins n fois dans a,
                    alors a[ival] = v,
                       et a[0:ival] contient v exactement n-1 fois,
                    sinon ival = -1

        >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 2.0, 1)
        0
        >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 2.0, 2)
        -1
        >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 7.0, 1)
        3
        >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 7.0, 2)
        5
        >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 7.0, 3)
        -1
        >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 9.0, 1)
        -1
        >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 9.0, 2)
        -1
        """

#. .. _nb_occurences:

   |exo| Compter le nombre d'occurrences de v dans un tableau::

    def nb_occurences(a: [float], v: float) -> int:
        """
        :entrée a: tableau de float
        :entrée v: float
        :sortie n: int
        :post-conf: n = |{ i | i ∈ [0;len(a)[  et  a[i] = n }|

        >>> nb_occurences([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 2.0)
        1
        >>> nb_occurences([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 7.0)
        2
        >>> nb_occurences([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 9.0)
        0
        """


Calculs sur les valeurs
+++++++++++++++++++++++

#. .. _somme:

   |exo| Calculer la somme des éléments d'un tableau ::

    def somme(a: [float]) -> float:
        """
        :entrée a: tableau de float
        :pré-cond: len(a) > 0
        :sortie s: float
        :post-cond: s = Σ a[i]  pour  i ∈ [0;len(a)[

        >>> somme([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0])
        18.0
        """


#. .. _moyenne:

   |exo| Calculer la moyenne des éléments d'un tableau ::

    def moyenne(a: [float]) -> float:
        """
        :entrée a: tableau de float
        :pré-cond: len(a) > 0
        :sortie m: float
        :post-cond: s est la moyenne des éléments de a

        >>> moyenne([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0])
        2.5714285714285716
        """


#. .. _moyenne_ponderee:

   |exo| ⭑ Calculer la moyenne pondérée des éléments d'un tableau ::

    def moyenne_ponderee(a: [float], poids: [float]) -> float:
        """
        :entrée a: tableau de float
        :entrée poids: tableau de float
        :pré-cond: len(a) > 0,  len(poids) == len(a),  somme(poids) != 0
        :sortie mp: float
        :post-cond: s est la moyenne pondérée des éléments de a telle que
                    ∀ i ∈ [0;len(a)[,  a[i] est pondérée par poids[i]

        >>> moyenne_ponderee([10.0, 12.0, 7.0], [1.0, 2.0, 1.0])
        10.25
        """


Génération et modification de tableaux
++++++++++++++++++++++++++++++++++++++

#. .. _premiers:

   |exo| ⭑ Retourner un tableau contenant les `n` premiers nombres premier ::

    def premiers(n: int) -> [int]:
        """
        :entrée n: int
        :pré-cond: n > 0
        :sortie a: tableau d'int
        :post-cond: len(a) == n
                    ∀ i ∈ [0;n[,  a[i] est le (i+1)-ème nombre premier

        >>> premiers(3)
        array([2, 3, 5])
        >>> premiers(10)
        array([2, 3, 5, 7, 11, 13, 17, 19, 23, 29])
        """


   On rappelle qu'un nombre premier admet exactement deux diviseurs :
   1 et lui même.

   Par exemple, premiers(10) retournera le tableau
   ``[2,3,5,7,11,13,17,19,23,29]``\ [#tip_premiers]_.


#. .. _fibonacci:

   |exo| ⭑ Retourner un tableau contenant les `n` premiers termes de la suite de
   Fibonacci ::

    def fibonacci(n: int) -> [int]:
        """
        :entrée n: int
        :pré-cond: n > 0
        :sortie a: tableau d'int
        :post-cond: len(a) == n
                    ∀ i ∈ [0;n[,  a[i] = Fi

        >>> fibonacci(4)
        array([1, 1, 2, 3])
        >>> fibonacci(10)
        array([1, 1, 2, 3, 5, 8, 13, 21, 34, 55])
        """

   On rappelle que la suite de Fibonnaci\ [#tip_fibonacci]_ est définie par :

   .. math::

      & F_0 = 1 \\
      & F_1 = 1 \\
      & \forall n > 1, ~~ F_n = F_{n-1} + F_{n-2}


#. .. _eratosthene:

   |exo| ⭑ Retourner un tableau de `n` booléen indiquant,
   pour chaque nombre entre 0 et n-1, s'il est premier ou non ::

    def eratosthene(n: int) -> [bool]:
        """
        :entrée n: int
        :pré-cond: n > 0
        :sortie a: tableau de bool
        :post-cond: len(a) == n
                    ∀ i ∈ [0;n[,  a[i] est True si et seulement si i est premier

        >>> eratosthene(4)
        array([False, False, True, True])
        >>> eratosthene(10)
        array([False, False, True, True, False, True, False, True, False, False])
        """

   La méthode proposée (le crible d'Ératosthène) consiste à :

   * initialiser tous les éléments du tableau à True (à part 0 et 1),
   * pour chaque élément à partir de 2, s'il vaut True,
     mettre tous ses multiples à False.

   À la fin de ce processus, les nombres premiers et uniquement eux seront à True.


#. .. _tableau_inverse:

   |exo| Retournerr le tableau inverse de a ::

    def tableau_inverse(a: [float]) -> [float]:
        """
        :entrée a: tableau de float
        :sortie b: tableau de float
        :post-cond: ∀ i ∈ [0;len(a)[,  b[i] == a[len(a)-1-i]

        >>> tableau_inverse([])
        array([])
        >>> tableau_inverse([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0])
        array([1.0, 7.0, 3.0, 7.0, -3.0, 1.0, 2.0])
        """

#. .. _moyennes_par_groupe:

   |exo| ⭑ Calculer les moyennes par groupe pour un tableau contenant
   toutes les notes d'une promotion d'étudiants ::

    def moyennes_par_groupe(notes: [float], nbEtu: [int]) -> [float]:
        """
        :entrée notes: tableau de float
        :entrée nbEtu: tableau d'int
        :pré-cond:
           - la somme des éléments de nbEtu est égale à len(notes)
           - notes[0 : nbEtu[0]] contient les notes du premier groupe ;
             notes[nbEtu[0] : nbEtu[0] + nbEtu[1]] contient les notes du
             deuxième groupe, et ainsi de suite...
        :sortie moy: tableau de float
        :post-cond:
           - len(moy) = len(nbEtu)
           - ∀ i ∈ [0;len(moy)[,  moy[i] contient la moyenne des étudiants
             du (i+1)ème groupe

        >>> moyennes_par_groupes([11.0, 9.0, 10.0, 15.0, 16.0, 2.0, 3.0, 4.0],
                                 [3, 2, 3])
        array([10.0, 15.5, 3.0])
        """

#. .. _moyennes_par_groupe2:

   |exo| ⭑⭑ Calculer les moyennes par groupe pour un tableau contenant
   toutes les notes d'une promotion d'étudiants ::

    def moyennes_par_groupe2(notes: [float], groupe: [int], nbGroupe, int) -> [float]:
        """
        :entrée notes: tableau de float
        :entrée groupe: tableau d'int
        :entrée nbGroupes: int
        :pré-cond:
           - len(notes) = len(groupe)
           - ∀ i ∈ [0;len(notes)[,
               notes[i] est la note du (i+1)ème étudiant, et
               groupe[i] est le numéro de groupe (entre 0 et nbGroupes-1)
               de cet étudiant
        :sortie moy: tableau de float
        :post-cond:
           - len(moy) = nbGroupes
           - ∀ i ∈ [0;len(moy)[,  moy[i] contient la moyenne des étudiants
             du groupe n° i

        >>> moyennes_par_groupes2([11.0, 15.0, 9.0, 3.0, 10.0, 16.0, 2.0, 4.0],
                                  [   0,    1,   0,   2,    0,    1,   2,   2])
        array([10.0, 15.5, 3.0])
        """

#. .. _mots_ab:

   |exo| ⭑⭑ Générer toutes les chaînes de caractères de longueur `n`
   composées des caractères ``'a'`` et ``'b'``\ ::

     def mots_ab(n: int) -> [str]:
         """
         :entrée n: int
         :pré-cond: n ≥ 0
         :sortie mots: tableau de str
         :post-cond: mots contient toutes les chaînes de caractères de
                     longueur n composées des caractères 'a' et 'b'.

         >>> # l'ordre peut être différent
         >>> mots_ab(0)
         array([""])
         >>> mots_ab(1)
         array(["a", "b"])
         >>> mots_ab(2)
         array(["aa", "ab", "ba", "bb"])
         >>> mots_ab(3)
         array(["aaa", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"])
         >>> mots_ab(4)
         array(["aaaa", "aaab", "aaba", "aabb", "abaa", "abab", "abba", "abbb",
                "baaa", "baab", "baba", "babb", "bbaa", "bbab", "bbba", "bbbb",
              ])
         """

   NB: pour n = 0, la réponse est constituée de l'unique chaîne ``""``
   (qui a bien pour longueur 0, et qui ne contient aucun autre caractère
   que ``'a'`` ou ``'b'``).

   Bien que ce ne soit pas une obligation,
   cet algorithme est plus simple à écrire sous forme récursive qu'itérative.


#. .. _mots:

   |exo| ⭑⭑ Générer toutes les chaînes de caractères de longueur `n`
   composées d'un ensemble de caractères donnés ::

     def mots(chars: str, n: int) -> [str]:
         """
         :entrée chars: str
         :entrée n: int
         :sortie mots: tableau de str
         :pré-cond: n ≥ 0, len(chars) > 0,
                    tous les caractères de chars sont différents
         :post-cond: mots contient toutes les chaînes de caractères de
                     longueur n composées des caractères de chars.

         >>> mots("abc", 0)
         array([""])
         >>> mots("abc", 1)
         array(["a", "b", "c"])
         >>> mots("abc", 2)
         array(["aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc"])
         >>> mots("XyZ", 2)
         array(["XX", "Xy", "XZ", "yX", "yy", "yZ", "ZX", "Zy", "ZZ"])
         """

   On pourra s'inspirer de la solution de mots_ab_,
   dont cet algorithme est une généralisation.


Modification de tableau
+++++++++++++++++++++++

#. .. _inverse_tableau:

   |exo| Modifier le tableau a de sorte à inverser l'ordre de ses éléments ::

    def inverse_tableau(a: [float]):
        """
        :e/s a: tableau de float
        :post-cond: ∀ i ∈ [0;len(a)[,  aₑ[i] == aₛ[len(a)-1-i]

        >>> a = array([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0])
        >>> inverse_tableau(a)
        >>> a
        array([1.0, 7.0, 3.0, 7.0, -3.0, 1.0, 2.0])
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
        (([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0],),
         ([1.0, 7.0, 3.0, 7.0, -3.0, 1.0, 2.0],)),
        (([1.0, 7.0, 3.0, 7.0, -3.0, 1.0, 2.0],),
         ([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0],)),
        (([1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 5.0],),
         ([5.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0],)),
        (([1.0, 1.0, 1.0, 1.0],),
         ([1.0, 1.0, 1.0, 1.0],)),
        (([1.0],),
         ([1.0],)),
        (([],),
         ([],)),
      ]
      </script>

#. .. _insere_val:

   |exo| Insèrer une valeur dans un tableau,
   en décalant les autres valeurs vers la droite ::

    def insere_val(a: [float], v: float, i: int):
        """
        :e/s a: tableau de float
        :entrée v: float
        :entrée i: int
        :pré-cond: 0 ≤ i < len(a)
        :post-cond: ∀ j ∈ [0;len(a)[,
                    aₛ[j] == aₑ[j]   si j < i
                    aₛ[j] == v      si j = i
                    aₛ[j] == aₑ[j-1] si j > i
        >>> a = array([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0])
        >>> insere_val(a, 9.0, 2)
        >>> a
        array([1.0, 7.0, 9.0, 3.0, 7.0, -3.0, 1.0])
        """

   NB: le tableau ne change pas de taille, donc
   cette procédure perd la valeur initialement la plus à droite du tableau.


Tableaux triés
++++++++++++++

#. .. _indice_val:

   |exo| ⭑ Trouver l'indice de la valeur v dans un tableau trié ::

    def indice_gauche(a: [float], v: float) -> int:
        """
        :entrée a: tableau de float
        :entrée v: float
        :pré-cond: a est trié:  ∀ i ∈ [1;len(a)[,  a[i] ≥ a[i-1]
        :sortie ival: int
        :post-cond: si v ∈ a,  a[ival] = v
                    sinon      ival = -1
        """

   Si `v` a plusieurs occurences dans le tableau,
   on ne spécifie pas l'indice de laquelle doit être retourné.
   En revanche, il faut tirer partie du fait que le tableau est trié
   pour trouver *rapidement* le résultat\ [#tip_indice_val]_.


#. .. _insere_val_trie:

   |exo| ⭑ Insèrer une valeur à sa place dans un tableau trié,
   en décalant les autres valeurs vers la droite ::

    def insere_val(a: [float], v: float) -> int:
        """
        :e/s a: tableau de float
        :entrée v: float
        :pré-cond: a est trié:  ∀ i ∈ [1;len(a)[,  a[i] ≥ a[i-1]
        :sortie ival: int
        :post-cond: a est toujours trié ;
                    ∀ i ∈ [0;len(a)[,
                    aₛ[i] == aₑ[i]   si i < ival
                    aₛ[i] == v       si i = ival
                    aₛ[i] == aₑ[i-1] si i > ival
        """

   NB: le tableau ne change pas de taille, donc
   cette procédure perd la valeur initialement la plus à droite du tableau.

#. .. _suppression_doublons:

   |exo| Supprimer tous les doublons d'un tableau trié ::

     def suppression_doublons(a: [float]) -> int:
         """
         :e/s a: tableau de float
         :sortie newlen: int
         :pré-cond: a est trié:  ∀ i ∈ [1;len(a)[,  a[i] ≥ a[i-1]
         :post-cond:
            - 0 ≤ newlen ≤ len(a)
            - ∀ i ∈ [0;len(a)[, ∃ j ∈ [0;newlen[,  aₛ[j] = aₑ[i]
            - ∀ i ∈ [1;newlen[, aₛ[i-1] < aₛ[i]
         """

   NB: le tableau ne change pas de taille,
   mais `newlen` est la nouvelle longueur "utile" du tableau,
   c'est à dire l'indice à partir duquel les valeurs dans `aₛ`
   ne sont plus pertinentes.

#. .. _interclassement:

   |exo| Copier les valeurs de deux tableaux triés dans un troisième tableau
   de sorte à ce que ce dernier soit trié lui aussi ::

     def interclassement(a1: [float], a2: [float]) -> [float]:
         """
         :entrée a1: tableau de float
         :entrée a2: tableau de float
         :pré-cond: a1 est trié:  ∀ i ∈ [1;len(a1)[,  a1[i] ≥ a1[i-1]
                    a2 est trié:  ∀ i ∈ [1;len(a2)[,  a2[i] ≥ a2[i-1]
         :sortie a3: tableau de float
         :post-cond:
            - len(a3) = len(a1) + len(a2)
            - a3 est trié:  ∀ i ∈ [1;len(a3)[,  a3[i] ≥ a3[i-1]
            - a3 contient toutes les valeurs de a1 et a2
         """

.. only:: html

  .. rubric:: Indices

.. [#tip_premiers] Bien que cela soit possible,
   il n'est pas conseillé de réutiliser la fonction `premier <premier>`:ref:,
   car il existe une solution plus efficace qui ne l'utilise pas.
.. [#tip_fibonacci] Bien que cela soit possible,
   il n'est pas conseillé de réutiliser la fonction `fibo <fibo>`:ref:,
   car il existe une solution plus efficace qui ne l'utilise pas.
.. [#tip_indice_val] Pour cela on effectuera une recherche dichotomique :
   à chaque étape, on regarde au milieu de la plage d'indice considérée,
   et selon que la valeur trouvée est plus grande ou plus petite que `v`,
   on n'en considère plus que la moitié gauche ou la moitié droite.