Enchaînements d'instructions
============================

.. include:: common.rst.inc

Géométrie
+++++++++

#. .. _cercle:

   |exo| Calculer le diamètre, le périmètre et la surface d'un cercle
   à partir de son rayon ::

     def cercle(r: float) -> (float, float, float):
         """
         :entrée r: float
         :pré-cond: r ≥ 0
         :sortie d: float
         :sortie p: float
         :sortie s: float
         :post-conf: d contient le diamètre d'un cercle de centre r,
                     p contient le périèmtre d'un cercle de centre r,
                     s contient la surface d'un cercle de centre r
         """

   .. raw:: html

       <script type="text/x-autoeval">
       [
         ((0.0,), (0.0, 0.0, 0.0)),
         ((0.5,), (1.0, 3.141592653589793, 0.7853981633974483)),
         ((1.0,), (2.0, 6.283185307179586, 3.141592653589793)),
         ((1.5,), (3.0, 9.42477796076938, 7.0685834705770345)),
         ((2.0,), (4.0, 12.566370614359172, 12.566370614359172)),
         ((10.0,), (20.0, 62.83185307179586, 314.1592653589793)),
       ]
       </script>


#. .. _coef_droite:

   |exo| Calculer les coefficients d'une droite à partir de deux points ::

     def coef_droite(x1: float, y1: float, x2: float, y2: float) -> (float, float):
         """
         :entrée x1: float
         :entrée y1: float
         :entrée x2: float
         :entrée y2: float
         :pré-cond: les deux points de coordonnées (x1, y1) et (x2, y2)
                    sont distincts et ne sont pas alignés verticalement,
                    autrement dit x1 ≠ x2
         :sortie a: float
         :sortie b: float
         :post-cond: a et b sont les coefficients de la droite passant par
                     les deux points de coordonnées (x1, y1) et (x2, y2),
                     autrement dit y1 = a×x1 + b et y2 = a×x2 + b

         """

   .. raw:: html

       <script type="text/x-autoeval">
       [
         (( 0.0, 0.0, 1.0, 1.0), (1.0, 0.0)),
         (( 0.0, 0.0, 0.5, 0.5), (1.0, 0.0)),
         (( 0.0, 0.0, 9.9, 9.9), (1.0, 0.0)),
         (( 0.0, 0.0, 1.0, 0.5), (0.5, 0.0)),
         (( 0.0, 0.0, 2.0, 1.0), (0.5, 0.0)),
         (( 0.0, 0.0, 0.5, 1.0), (2.0, 0.0)),
         (( 0.0, 0.0, 1.0, 2.0), (2.0, 0.0)),
         (( 0.0, 1.0, 1.0, 2.0), (1.0, 1.0)),
         (( 1.0, 2.0, 3.0, 4.0), (1.0, 1.0)),
         (( 1.0, 0.0, 0.0, 0.0), (0.0, 0.0)),
         (( 1.0, 0.0, 9.9, 0.0), (0.0, 0.0)),
         (( 9.9, 0.0,-9.9, 0.0), (0.0, 0.0)),
       ]
       </script>

Conditions et calcul
++++++++++++++++++++

#. .. _plus_petit:

   |exo| Calculer le plus petit parmi trois nombres ::

    def plus_petit(a: int, b: int, c: int) -> int:
        """
        :entree a: int
        :entree b: int
        :entree c: int
        :pré-cond: (aucune)
        :sortie pp: int
        :post-cond: pp = le plus petit nombre de l'ensemble {a, b, c}
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
        (( 1.0, 2.0, 3.0,), (1.0,)),
        (( 2.0, 1.0, 3.0,), (1.0,)),
        (( 2.0, 3.0, 1.0,), (1.0,)),
        (( 3.0, 2.0, 1.0,), (1.0,)),
        (( 1.0, 1.0, 1.0,), (1.0,)),
        (( 1.0, 1.0, -9.0,), (-9.0,)),
      ]
      </script>


#. .. _racines_2nd_degre:

   |exo| Calculer si elles existent les racines d'une équation du second degré ::

    def racines_2nd_degre(a: float, b: float, c: float) -> (float, float):
        """
        :entrée a: float
        :entrée b: float
        :entrée c: float
        :pré-cond: a ≠ 0
        :sortie r1: float ou None
        :sortie r2: float ou None
        :post-cond: si l'équation ax²+bx + c n'a pas de racine réelle,
                    r1 = r2 = None,
                    sinon, si elle a exactement une racine réelle,
                    r1 a pour valeur cette racine et r2 = None,
                    sinon (l'équation a deux racine réelles),
                    r1 et r2 ont pour valeur ces deux racines,
                    avec r1 > r2
        """

   NB: pour calculer les racines,
   il est nécessaire de calculer une racine carrée.
   On pourra pour cela utiliser la fonction racine_carree_ ci-dessous
   ou la fonction ``sqrt`` fournie par Python
   (inclure la ligne  ``from math import sqrt`` en haut de votre programme).

   .. raw:: html

      <script type="text/x-autoeval">
      [
        (( 1.0, 0.0, 1.0,), (None, None)),
        (( 1.0, 0.0, 2.0,), (None, None)),
        (( 1.0, 1.0, 1.0,), (None, None)),
        (( 1.0, 0.0, 0.0,), (0.0, None)),
        (( 2.0, 0.0, 0.0,), (0.0, None)),
        (( 1.0, -2.0, 1.0,), (1.0, None)),
        (( 2.0, -4.0, 2.0,), (1.0, None)),
        (( 1.0, 0.0, -1.0,), (1.0, -1.0)),
        (( 1.0, 0.0, -2.0,), (1.414, -1.414)),
        (( 2.0, 0.0, -4.0,), (1.414, -1.414)),
        (( 1.0, 2.0, -3.0,), (1.0, -3.0)),
      ]
      </script>


.. _durees_et_dates:

Durées et dates
+++++++++++++++

#. .. _duree_en_secondes:

   |exo| Convertir une durée en secondes ::

    def duree_en_secondes(j: int, h: int, m: int, s: int) -> float:
        """
        :entrée j: int
        :entrée h: int
        :entrée m: int
        :entrée s: float
        :pré-cond: j > 0 , 0 ≤ h < 24 , 0 ≤ m < 60, 0 ≤ s < 60
        :sortie ds: float
        :post-cond: ds est le nombre de secondes correspond à
                    une durée de j jours, h heures, m minutes et s secondes.
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
        (( 0, 0, 0, 0.0),      (0.0,)),
        (( 0, 0, 0, 1.0),      (1.0,)),
        (( 0, 0, 1, 0.0),     (60.0,)),
        (( 0, 0, 3, 0.0),    (180.0,)),
        (( 0, 1, 0, 0.0),   (3600.0,)),
        (( 0, 3, 0, 0.0),  (10800.0,)),
        (( 1, 0, 0, 0.0),  (86400.0,)),
        (( 2, 0, 0, 0.0), (172800.0,)),
        (( 1, 1, 1, 1.0),  (90061.0,)),
        (( 1, 2, 3, 4.5),  (93784.5,)),
      ]
      </script>

#. .. _secondes_en_duree:

   |exo| Convertir un nombre de secondes en durée ::

    def secondes_en_duree(sec: int) -> (int, int, int, int):
        """
        :entrée sec: int
        :pré-cond: sec ≥ 0
        :sortie j: int
        :sortie h: int
        :sortie m: int
        :sortie s: int
        :post-cond: sec est le nombre de secondes correspond à
                    une durée de j jours, h heures, m minutes et s secondes
                    avec j > 0 , 0 ≤ h < 24 , 0 ≤ m < 60, 0 ≤ s < 60 .
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
        (      (0,), ( 0, 0, 0, 0)),
        (      (1,), ( 0, 0, 0, 1)),
        (     (60,), ( 0, 0, 1, 0)),
        (    (180,), ( 0, 0, 3, 0)),
        (   (3600,), ( 0, 1, 0, 0)),
        (  (10800,), ( 0, 3, 0, 0)),
        (  (86400,), ( 1, 0, 0, 0)),
        ( (172800,), ( 2, 0, 0, 0)),
        (  (90061,), ( 1, 1, 1, 1)),
        (  (93784,), ( 1, 2, 3, 4)),
      ]
      </script>

#. .. _ordre_heures:

   |exo| ⭑ Déterminer l'ordre entre deux heures de la journée ::

    def ordre_heures(h1: int, m1: int, s1: int, h2: int, m2: int, s2: int) -> int:
       """
        :entrée h1: int
        :entrée m1: int
        :entrée s1: int
        :entrée h2: int
        :entrée m2: int
        :entrée s2: int
        :pré-cond: 0 ≤ h1 < 24 , 0 ≤ m1 < 60 , 0 ≤ s1 < 60 ,
                   0 ≤ h2 < 24 , 0 ≤ m2 < 60 , 0 ≤ s2 < 60
        :sortie o: int
        :post-cond: o est un entier positif si h1:m1:s1 est après h2:m2:s2 ,
                    un entier négatif si h1:m1:s2 est avant h2:m2:s2 ,
                    0 si les deux heures sont identiques .
       """

   NB : notez que les post-conditions sont peu spécifiques :
   seul le *signe* de `o` est spécifié;
   sa valeur est laissée
   à la discrétion de l'implémentation\ [#tip_ordre_heures]_.

   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((12, 34, 56,  12, 34, 56), (0,)),
        ((12, 34, 56,  12, 34, 57), ((lambda x: x<0),)),
        ((12, 34, 56,  12, 34, 55), ((lambda x: x>0),)),
        ((12, 34, 56,  12, 35, 56), ((lambda x: x<0),)),
        ((12, 34, 56,  12, 33, 56), ((lambda x: x>0),)),
        ((12, 34, 56,  13, 34, 56), ((lambda x: x<0),)),
        ((12, 34, 56,  11, 34, 56), ((lambda x: x>0),)),
        ((12, 34, 56,  13, 33, 55), ((lambda x: x<0),)),
        ((12, 34, 56,  11, 35, 57), ((lambda x: x>0),)),
      ]
      </script>

#. .. _difference_heures:

   |exo| ⭑ Calculer la différence entre deux heures de la journée ::

    def difference_heures(h1: int, m1: int, s1: int, h2: int, m2: int, s2: int) -> int:
        """
        :entrée h1: int
        :entrée m1: int
        :entrée s1: int
        :entrée h2: int
        :entrée m2: int
        :entrée s2: int
        :pré-cond: 0 ≤ h1 < 24 , 0 ≤ m1 < 60 , 0 ≤ s1 < 60 ,
                   0 ≤ h2 < 24 , 0 ≤ m2 < 60 , 0 ≤ s2 < 60 ,
                   ordre_heures(h1, m1, s1, h2, m2, s2) ≥ 0
        :sortie d: int
        :post-cond: d est le nombre de secondes entre h2:m2:s2 et h1:m1:s1 .
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((12, 34, 56,  12, 34, 56), (0,)),
        ((12, 34, 56,  12, 34, 55), (1,)),
        ((12, 34, 56,  12, 33, 56), (60,)),
        ((12, 34, 56,  11, 34, 56), (3600,)),
        ((12, 34, 56,  11, 35, 57), (3539,)),
        ((12, 34, 56,  11, 33, 55), (3661,)),
      ]
      </script>

   Variante : relâcher la contrainte
   sur l'ordre des heures de la journée passées en entrée,
   en retournant une valeur négative
   si la première est antérieure à la deuxième.

#. .. _decale_heure:

   |exo| ⭑ Calculer une heure de la journée relativement à une autre ::

    def decale_heure(h: int, m: int, s: int, d: int) -> (int, int, int):
        """
        :entrée h: int
        :entrée m: int
        :entrée s: int
        :entrée d: int
        :pré-cond: 0 ≤ h < 24 , 0 ≤ m < 60 , 0 ≤ s < 60 , 0 ≤ d < 24*3600
        :sortie h2: int
        :sortie m2: int
        :sortie s2: int
        :post-cond: h2:m2:s2 est l'heure de la journée située d secondes
                    après h:m:s .
        """

   NB : L'heure retournée en sortie peut-être « inférieure »
   à celle passée en entrée si la durée `d` fait changer de jour.

   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((12, 34, 56,     0), (12, 34, 56)),
        ((12, 34, 56,     1), (12, 34, 57)),
        ((12, 34, 56,     4), (12, 35,  0)),
        ((12, 34, 56,    10), (12, 35,  6)),
        ((12, 34, 56,    60), (12, 35, 56)),
        ((12, 34, 56,    61), (12, 35, 57)),
        ((12, 34, 56,    64), (12, 36,  0)),
        ((12, 34, 56,   120), (12, 36, 56)),
        ((12, 34, 56,  1504), (13,  0,  0)),
        ((12, 34, 56,  3600), (13, 34, 56)),
        ((12, 34, 56,  3601), (13, 34, 57)),
        ((12, 34, 56,  3660), (13, 35, 56)),
        ((12, 34, 56,  3661), (13, 35, 57)),
        ((12, 34, 56, 43200), ( 0, 34, 56)),
        ((12, 34, 56, 46800), ( 1, 34, 56)),
        ((12, 34, 56, 48304), ( 2,  0,  0)),
      ]
      </script>

   Variante : autoriser `d` à prendre une valeur négative
   pour calculer une heure située `-d` secondes *avant* ``h:m:s``.

#. .. _annee_bissextile:

   |exo| Déterminer si une année est bissextile ::

    def annee_bissextile(a: int) -> bool:
        """
        :entrée a: int
        :pré-cond: a > 0
        :sortie b: bool
        :post-cond: b est True ssi l'année a est bissextile.
        """

   NB : on rappelle que les années bissextiles sont

    * les années multiples de 4,
    * sauf les années multiples de 100 qui ne le sont pas,
    * sauf les années multiples de 400 qui le sont tout de même.

   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((2016,), (True,)),
        ((2017,), (False,)),
        ((2018,), (False,)),
        ((2019,), (False,)),
        ((2020,), (True,)),
        ((2021,), (False,)),
        ((2024,), (True,)),
        ((2100,), (False,)),
        ((2200,), (False,)),
        ((2300,), (False,)),
        ((2400,), (True,)),
      ]
      </script>


#. .. _jours_par_annee:

   |exo| Déterminer le nombre de jours d'une année donnée ::

    def jours_par_annee(a: int) -> int:
        """
        :entrée a: int
        :pré-cond: a > 0
        :sortie j: int
        :post-cond: j est le nombre de jour de l'année a.
        """

   NB : attention aux années bissextiles –voir l'exercice annee_bissextile_.

   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((2016,), (366,)),
        ((2017,), (365,)),
        ((2018,), (365,)),
        ((2019,), (365,)),
        ((2020,), (366,)),
        ((2021,), (365,)),
        ((2024,), (366,)),
        ((2100,), (365,)),
        ((2200,), (365,)),
        ((2300,), (365,)),
        ((2400,), (366,)),
      ]
      </script>


#. .. _jours_par_mois:

   |exo| Déterminer le nombre de jours d'un mois ::

    def jours_par_mois(m: int) -> int:
        """
        :entrée m: int
        :pré-cond: 1 ≤ m ≤ 12
        :sortie j: int
        :post-cond: j est le nombre de jour du m-ième mois
                    d'une année non bissextile.
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
        (( 1,), (31,)),
        (( 2,), (28,)),
        (( 3,), (31,)),
        (( 4,), (30,)),
        (( 5,), (31,)),
        (( 6,), (30,)),
        (( 7,), (31,)),
        (( 8,), (31,)),
        (( 9,), (30,)),
        ((10,), (31,)),
        ((11,), (30,)),
        ((12,), (31,)),
      ]
      </script>


#. .. _jours_par_annee_mois:

   |exo| Déterminer le nombre de jours d'un mois d'une année donnée ::

    def jours_par_annee_mois(a: int, m: int) -> int:
        """
        :entrée a: int
        :entrée m: int
        :pré-cond: a > 0 , 1 ≤ m ≤ 12
        :sortie j: int
        :post-cond: j est le nombre de jour du m-ième mois de l'année a.
        """

   NB : attention aux années bissextiles –voir l'exercice annee_bissextile_.

   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((2016,  1,), (31,)),
        ((2016,  2,), (29,)),
        ((2016,  3,), (31,)),
        ((2016,  4,), (30,)),
        ((2016,  5,), (31,)),
        ((2016,  6,), (30,)),
        ((2016,  7,), (31,)),
        ((2016,  8,), (31,)),
        ((2016,  9,), (30,)),
        ((2016, 10,), (31,)),
        ((2016, 11,), (30,)),
        ((2016, 12,), (31,)),
        ((2017,  2,), (28,)),
        ((2018,  2,), (28,)),
        ((2019,  2,), (28,)),
        ((2020,  2,), (29,)),
        ((2100,  2,), (28,)),
        ((2400,  2,), (29,)),
      ]
      </script>


#. .. _ordre_dates:

   |exo| Déterminer l'ordre entre deux dates ::

    def ordre_dates(a1: int, m1: int, j1: int, a2: int, m2: int, j2: int) -> int:
       """
        :entrée a1: int
        :entrée m1: int
        :entrée j1: int
        :entrée a2: int
        :entrée m2: int
        :entrée j2: int
        :pré-cond: a1 > 0 , 1 ≤ m1 ≤ 12 , 1 ≤ j1 < jours_annee_mois(a1, m1) ,
                   a2 > 0 , 1 ≤ m2 ≤ 12 , 1 ≤ j2 < jours_annee_mois(a2, m2)
        :sortie o: int
        :post-cond: o est un entier positif si j1/m1/a1 est après j2/m2/a2 ,
                    un entier negatif si j1/m1/a1 est avant j2/m2/a2 ,
                    0 si les deux dates sont identiques .
       """

   NB : notez que les post-conditions sont peu spécifiques :
   seul le *signe* de `o` est spécifié.

   Question subsidiaire :
   pouvez-vous appliquer la même astuce que pour ordre_heures_? Expliquez ?

#. .. _decale_date:

   |exo| ⭑⭑ Calculer une date relativement à une autre ::

    def decale_date (a: int, m: int, j: int, d: int) -> (int, int, int):
        """
        :entrée a: int
        :entrée m: int
        :entrée j: int
        :entrée d: int
        :pré-cond: a > 0 , 1 ≤ m ≤ 12 , 1 ≤ j ≤ jours_par_annee_mois(a, m) ,
                   d >= 0
        :sortie a2: int
        :sortie m2: int
        :sortie j2: int
        :post-cond: j2/m2/a2 est la date située d jours après j/m/a
        """

   Variante : accepter une valeur négative pour `d`
   (pour trouver une date située *avant* la date passée en entrée).

#. .. _difference_dates:

   |exo| ⭑⭑ Calculer la différence entre deux dates ::

    def difference_dates(a1: int, m1: int, j1: int, a2: int, m2: int, j2: int) -> int:
        """
        :entrée a1: int
        :entrée m1: int
        :entrée j1: int
        :entrée a2: int
        :entrée m2: int
        :entrée j2: int
        :pré-cond: a1 > 0 , 1 ≤ m1 ≤ 12 , 1 ≤ j1 < jours_annee_mois(a1, m1) ,
                   a2 > 0 , 1 ≤ m2 ≤ 12 , 1 ≤ j2 < jours_annee_mois(a2, m2) ,
                   ordre_dates(a1, m1, j1, a2, m2, j2) ≥ 0
        :sortie d: int
        :post-cond: d est le nombre de jours entre j2/m2/a2 et j1/m1/a1 .
        """

   Variante : relâcher la contrainte sur l'ordre des dates passées en entrée,
   en retournant une valeur négative si la première est antérieure à la deuxième.

#. .. _jour_de_la_semaine:

   |exo| Calculer le jour de la semaine d'une date donnée ::

    def jour_de_la_semaine(a: int, m: int, j: int) -> int:
        """
        :entrée a: int
        :entrée m: int
        :entrée j: int
        :pré-cond: a ≥ 1900 , 1 ≤ m ≤ 12 , 1 ≤ j < jours_annee_mois(a, m)
        :sortie js: int
        :post-cond: js représente le rang dans la semaine de la date j/m/a ,
                    où 0 représente le lundi et 6 représente le dimanche.
        """

   NB : on pourra utiliser la solution de l'exercice difference_dates_,
   en se souvenant que le 1\ `er`:sup: janvier 1900 était un lundi.


Chiffres romains
++++++++++++++++

#. .. _romain_chiffre:

   |exo| Convertir un petit nombre en chiffres romains ::

    def romain_chiffre(n: int) -> str:
        """
        :entrée n: int
        :pré-cond: 0 < n < 10
        :sortie r: str
        :post-cond: r est le représentation en chiffres romains de n
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
        (( 1,), ("I",)),
        (( 2,), ("II",)),
        (( 3,), ("III",)),
        (( 4,), ("IV",)),
        (( 5,), ("V",)),
        (( 6,), ("VI",)),
        (( 7,), ("VII",)),
        (( 8,), ("VIII",)),
        (( 9,), ("IX",)),
      ]
      </script>


#. .. _romain_chiffre_generique:

   |exo| ⭑ Convertir de manière générique
   un petit chiffre en chiffres romains ::

    def romain_chiffre_generique(n: int, un: str, cinq: str, dix: str) -> str:
        """
        :entrée n: int
        :entrée un: str
        :entrée cinq: str
        :entrée dix: str
        :pré-cond: 0 < n < 10
        :sortie r: str
        :post-cond: r est le représentation en chiffres romains de n,
                    en utilisant les valeurs d'entrée un, cinq et dix
                    pour au lieu des symboles I, V et X respectivement.
        """

   Par rapport à la précédente, cette fonction présente plusieurs avantages :

    * elle permet d'écrire les chiffres romains en minuscules,
    * elle offre un outil utile pour écrire des chiffres romains plus grands
      (comme dans l'exercice ci-dessous).

   .. raw:: html

      <script type="text/x-autoeval">
      [
        (( 1, "I", "V", "X"), ("I",)),
        (( 2, "I", "V", "X"), ("II",)),
        (( 3, "I", "V", "X"), ("III",)),
        (( 4, "I", "V", "X"), ("IV",)),
        (( 5, "I", "V", "X"), ("V",)),
        (( 6, "I", "V", "X"), ("VI",)),
        (( 7, "I", "V", "X"), ("VII",)),
        (( 8, "I", "V", "X"), ("VIII",)),
        (( 9, "I", "V", "X"), ("IX",)),
        (( 1, "a", "b", "c"), ("a",)),
        (( 2, "a", "b", "c"), ("aa",)),
        (( 3, "a", "b", "c"), ("aaa",)),
        (( 4, "a", "b", "c"), ("ab",)),
        (( 5, "a", "b", "c"), ("b",)),
        (( 6, "a", "b", "c"), ("ba",)),
        (( 7, "a", "b", "c"), ("baa",)),
        (( 8, "a", "b", "c"), ("baaa",)),
        (( 9, "a", "b", "c"), ("ac",)),
        (( 1, "X", "L", "C"), ("X",)),
      ]
      </script>


#. .. _romain:

   |exo| ⭑⭑ Convertir un nombre en chiffres romains ::

    def romain(n: int) -> str:
        """
        :entrée n: int
        :pré-cond: 0 < n < 4000
        :sortie r: str
        :post-cond: r est le représentation en chiffres romains de n
        """

   On rappelle les symboles utilisés pour les chiffres romains :

   === === ==== ==== ===== ===== ======
    I   V   X    L     C     D     M
    1   5   10   50   100   500   1000
   === === ==== ==== ===== ===== ======

   Il pourra être utile d'utiliser la fonction
   romain_chiffre_generique_\ [#tip_romain]_.

   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((   1,), ("I",)),
        ((   2,), ("II",)),
        ((   3,), ("III",)),
        ((   4,), ("IV",)),
        ((   5,), ("V",)),
        ((   6,), ("VI",)),
        ((   7,), ("VII",)),
        ((   8,), ("VIII",)),
        ((   9,), ("IX",)),
        ((  10,), ("X",)),
        ((  11,), ("XI",)),
        ((  12,), ("XII",)),
        ((  13,), ("XIII",)),
        ((  14,), ("XIV",)),
        ((  15,), ("XV",)),
        ((  19,), ("XIX",)),
        ((  20,), ("XX",)),
        ((  30,), ("XXX",)),
        ((  40,), ("XL",)),
        ((  42,), ("XLII",)),
        ((  50,), ("L",)),
        ((  60,), ("LX",)),
        ((  70,), ("LXX",)),
        ((  90,), ("XC",)),
        (( 100,), ("C",)),
        (( 101,), ("CI",)),
        (( 111,), ("CXI",)),
        (( 200,), ("CC",)),
        (( 400,), ("CD",)),
        (( 500,), ("D",)),
        (( 900,), ("CM",)),
        ((1000,), ("M",)),
        ((2016,), ("MMXVI",)),
        ((3999,), ("MMMCMXCIX",)),
      ]
      </script>



Nombres en base 10
++++++++++++++++++

#. .. _compte_chiffres:

   |exo| Compter le nombre de chiffres ::

    def compte_chiffres(n: int) -> int:
        """
        :entrée n: int
        :pré-cond: n ≥ 0
        :sortie c: int
        :post-cond: c est le nombre de chiffres dans l'écriture en base 10 de n
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((   1,), (1,)),
        ((   2,), (1,)),
        ((   9,), (1,)),
        ((  10,), (2,)),
        ((  11,), (2,)),
        ((  20,), (2,)),
        ((  99,), (2,)),
        (( 100,), (3,)),
        (( 199,), (3,)),
        ((1000,), (4,)),
        ((9999,), (4,)),
        ((   0,), (1,)),
      ]
      </script>


#. .. _somme_chiffres:

   |exo| Calculer la somme des chiffres ::

    def somme_chiffres(n: int) -> int:
        """
        :entrée n: int
        :pré-cond: n > 0
        :sortie s: int
        :post-cond: s est la somme des chiffres dans l'écriture en base 10 de n
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((   1,), ( 1,)),
        ((   2,), ( 2,)),
        ((   9,), ( 9,)),
        ((  10,), ( 1,)),
        ((  11,), ( 2,)),
        ((  20,), ( 2,)),
        ((  99,), (18,)),
        (( 100,), ( 1,)),
        (( 199,), (19,)),
        ((1000,), ( 1,)),
        ((9999,), (36,)),
        ((   0,), ( 0,)),
      ]
      </script>


#. .. _compte_chiffre:

   |exo| Compter le nombre d'occurrences d'un chiffre ::

    def compte_chiffre(n: int, c: int) -> int:
        """
        :entrée n: int
        :entrée c: int
        :pré-cond: n > 0,  0 ≤ c ≤ 9
        :sortie nc: int
        :post-cond: nc est le nombre de fois où le chiffre c apparaît
                    dans l'écriture en base 10 de n
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((    1, 1), ( 1,)),
        ((    1, 2), ( 0,)),
        ((   10, 0), ( 1,)),
        ((   10, 1), ( 1,)),
        ((   10, 2), ( 0,)),
        ((12121, 0), ( 0,)),
        ((12121, 1), ( 3,)),
        ((12121, 2), ( 2,)),
      ]
      </script>


#. .. _compte_chiffres_pairs:

   |exo| Compter le nombre de chiffres pairs ::

    def compte_chiffres_pairs(n: int) -> int:
        """
        :entrée n: int
        :pré-cond: n ≥ 0
        :sortie c: int
        :post-cond: c est le nombre de chiffres pairs apparaissant
                    dans l'écriture en base 10 de n
        """


   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((    1), ( 0,)),
        ((    2), ( 1,)),
        ((12345), ( 2,)),
        ((67890), ( 3,)),
        ((22222), ( 5,)),
        ((99999), ( 0,)),
        ((    0), ( 1,)),
      ]
      </script>


#. .. _chiffre_au_rang:

   |exo| Déterminer le chiffre à un rang donné ::

    def chiffre_au_rang(n: int, i: int) -> int:
        """
        :entrée n: int
        :entrée i: int
        :pré-cond: n > 10ⁱ
        :sortie c: int
        :post-cond: c est le chiffre au rang r dans l'écriture de n en base 10
                    (cf. ci-dessous pour la définition du rang).
        """

   Dans cet exercice (et les suivants),
   on appelle **rang** d'un chiffre `c`
   dans l'écriture en base 10 d'un nombre `n`
   la puissance de 10 que représente `c`.
   Ainsi,

   * le chiffre des unités a le rang 0 (`1 = 10^0`),
   * le chiffre des dizaines a le rang 1 (`10 = 10^1`),
   * le chiffre des centaines a le rang 2 (`100 = 10^2`),
   * et ainsi de suite...


   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((    1, 0), ( 1,)),
        ((12345, 0), ( 5,)),
        ((12345, 1), ( 4,)),
        ((12345, 2), ( 3,)),
        ((12345, 3), ( 2,)),
        ((12345, 4), ( 1,)),
        ((67890, 0), ( 0,)),
        ((67890, 1), ( 9,)),
        ((67890, 2), ( 8,)),
        ((67890, 3), ( 7,)),
        ((67890, 4), ( 6,)),
      ]
      </script>


#. .. _rang_max:

   |exo| Déterminer le rang maximum (le plus à gauche) d'un chiffre donné ::

    def rang_max(n: int, c: int) -> int:
        """
        :entrée n: int
        :entrée c: int
        :pré-cond: n > 0, 0 ≤ c ≤ 9
        :sortie r: int
        :post-cond: r est le rang maximal du chiffre c
                    dans l'écriture de n en base 10,
                    ou -1 si c n'y est pas présent.
        """

   Reportez-vous à l'exercice chiffre_au_rang_ pour la définition du *rang*.

   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((    1, 0), (-1,)),
        ((    1, 1), ( 0,)),
        ((12345, 0), (-1,)),
        ((12345, 1), ( 4,)),
        ((12345, 2), ( 3,)),
        ((12345, 3), ( 2,)),
        ((12345, 4), ( 1,)),
        ((12345, 5), ( 0,)),
        ((12345, 6), (-1,)),
        ((12121, 1), ( 4,)),
        ((12121, 2), ( 3,)),
        ((12121, 3), (-1,)),
      ]
      </script>


#. .. _rang_min:

   |exo| ⭑ Déterminer le rang minimum (le plus à droite) d'un chiffre donné ::

    def rang_min(n: int, c: int) -> int:
        """
        :entrée n: int
        :entrée c: int
        :pré-cond: n > 0, 0 ≤ c ≤ 9
        :sortie r: int
        :post-cond: r est le rang minimal du chiffre c
                    dans l'écriture de n en base 10,
                    ou -1 si c n'y est pas présent.
        """

   Reportez-vous à l'exercice chiffre_au_rang_ pour la définition du *rang*.


   .. raw:: html

      <script type="text/x-autoeval">
      [
        ((    1, 0), (-1,)),
        ((    1, 1), ( 0,)),
        ((12345, 0), (-1,)),
        ((12345, 1), ( 4,)),
        ((12345, 2), ( 3,)),
        ((12345, 3), ( 2,)),
        ((12345, 4), ( 1,)),
        ((12345, 5), ( 0,)),
        ((12345, 6), (-1,)),
        ((12121, 1), ( 0,)),
        ((12121, 2), ( 1,)),
        ((12121, 3), (-1,)),
      ]
      </script>


Fonctions mathématiques
+++++++++++++++++++++++

#. .. _valeur_absolue:

   |exo| Calculer la valeur absolue de `x` ::

    def valeur_absolue(x: float) -> float:
        """
        :entrée x: float
        :sortie a: float
        :post-cond: a = |x|
        """

   .. raw:: html

      <script type="text/x-autoeval">
      [
        (( 1.0,), (1.0,)),
        ((-1.0,), (1.0,)),
        (( 0.0,), (0.0,)),
        (( 2.0,), (2.0,)),
        ((-2.0,), (2.0,)),
        (( 2.5,), (2.5,)),
        ((-2.5,), (2.5,)),
      ]
      </script>


#. .. _puissance_n:

   |exo| Calculer une puissance entière de `x` ::

    def puissance_n(x: float, n: int) -> float:
        """
        :entrée x: float
        :entrée n: int
        :pré-cond: n ≥ 0
        :sortie p: float
        :post-cond: p = xⁿ
        """

   Écrivez cet algorithme sans utiliser l'opérateur ``**`` de Python.

   .. raw:: html

      <script type="text/x-autoeval">
      [
        (( 1.0, 0), ( 1.0,)),
        (( 1.0, 1), ( 1.0,)),
        (( 1.0, 2), ( 1.0,)),
        ((-1.0, 0), ( 1.0,)),
        ((-1.0, 1), (-1.0,)),
        ((-1.0, 2), ( 1.0,)),
        (( 0.0, 1), ( 0.0,)),
        (( 0.0, 2), ( 0.0,)),
        (( 2.0, 0), ( 1.0,)),
        (( 2.0, 1), ( 2.0,)),
        (( 2.0, 2), ( 4.0,)),
        (( 2.0, 3), ( 8.0,)),
        (( 2.0, 4), (16.0,)),
        (( 2.0, 5), (32.0,)),
        ((-2.0, 0), ( 1.0,)),
        ((-2.0, 1), (-2.0,)),
        ((-2.0, 2), ( 4.0,)),
        ((-2.0, 3), (-8.0,)),
        (( 2.5, 0), ( 1.0,)),
        (( 2.5, 1), ( 2.5,)),
        (( 2.5, 2), ( 6.25,)),
      ]
      </script>

   Variante : relâcher la contrainte sur `n`
   en autorisant des valeurs négatives.


#. .. _premier:

   |exo| Détermine si `n` est premier ou non ::

    def premier(n: int) -> bool:
        """
        :entrée n: int
        :pré-cond: n > 1
        :sortie p: bool
        :post-cond: p est True si et seulement si n est premier
        """

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

   ⭑⭑ Question subsidiaire : quelle est la complexité de votre algorithme ?
   Pouvez-vous écrire un algorithme avec une complexité meilleure que O(n) ?


   .. raw:: html

      <script type="text/x-autoeval">
      [
        (( 1,), ( False,)),
        (( 2,), ( True,)),
        (( 3,), ( True,)),
        (( 4,), ( False,)),
        (( 5,), ( True,)),
        (( 6,), ( False,)),
        (( 7,), ( True,)),
        (( 8,), ( False,)),
        (( 9,), ( False,)),
        ((10,), ( False,)),
        ((11,), ( True,)),
        ((12,), ( False,)),
        ((13,), ( True,)),
        ((14,), ( False,)),
        ((15,), ( False,)),
        ((16,), ( False,)),
        ((17,), ( True,)),
        ((18,), ( False,)),
        ((19,), ( True,)),
        ((997,), ( True,)),
        ((9971,), ( False,)),
        ((9973,), ( True,)),
        ((999981,), ( False,)),
        ((999983,), ( True,)),
      ]
      </script>

#. .. _racine_carree:

   |exo| ⭑⭑ Approximer la racine carrée de `x` ::

    def racine_carree(x: float, ε: float) -> float:
        """
        :entrée x: float
        :entrée ε: float
        :pré-cond: x ≥ 0
        :sortie r: float
        :post-cond: |√x - r| ≤ ε
        """

   Écrivez cet algorithme sans utiliser l'opérateur ``**`` de Python
   (ni bien sûr la fonction ``sqrt`` du module ``math``).

   Une méthode possible est la **recherche dichotomique**,
   qui consiste à encadrer la valeur cherchée par un intervalle,
   puis couper répétitivement cet intervalle en deux par le milieu
   jusqu'à ce que sa largeur soit inférieure à ε.
   Pour cela, on fait les remarques suivantes :

    * si 0 ≤ x ≤ 1, alors x ≤ √x ≤ 1
    * si x ≥ 1,     alors 1 ≤ √x ≤ x
    * quels que soient x et y positifs,  x ≤ y ↔ √x ≤ √y


#. .. _racine_nieme:

   |exo| ⭑⭑ Approximer la racine n\ `ème`:sup: de `x` ::

    def racine_nieme(x: float, n: int, ε: float) -> float:
        """
        :entrée x: float
        :entrée n: int
        :entrée ε: float
        :pré-cond: x ≥ 0 , n > 0
        :sortie r: float
        :post-cond: |ⁿ√x - r| ≤ ε
        """

   Pour écrire cet algorithme, vous pouvez utiliser l'opérateur ``**`` de Python
   à condition de n'utiliser que des entiers comme opérande de droite.
   Vous pouvez aussi vous passer complètement de cet opérateur
   et utiliser à la place la fonction puissance_n_.

   On pourra appliquer la même méthode dichotomique que pour racine_carree_.


#. .. _log_base:

   |exo| ⭑⭑ Approximer le logarithme à base `b` de `x` ::

    def log_base(x: float, n: float, ε: float):
        """
        :entrée x: float
        :entrée n: float
        :entrée ε: float
        :sortie l: float
        :pré-cond: x ≥ 1
        :post-cond: |logₙ(x) - l| ≤ ε
        """

   On rappelle que le logarithme à base `n` de `x` est la valeur `l` telle que
   `b^l = x`.
   On pourra appliquer la même méthode dichotomique que pour racine_carree_,
   en utilisant l'opérateur ``**`` de Python.


#. .. _factorielle:

   |exo| Calculer la factorielle de `x` ::

    def factorielle(n: int) -> int:
        """
        :entrée n: int
        :sortie f: int
        :pré-cond: n > 0
        :post-cond: f = n! = 1×2×3×...×(n-2)×(n-1)×n
        """

#. .. _arrangements:

   |exo| ⭑ Calculer le nombre d'arrangements `A^k_n`
   de `k` éléments pris dans `n` ::

    def arrangements(k: int, n: int) -> int:
        """
        :entrée k: int
        :entrée n: int
        :sortie akn: int
        :pré-cond: n > 0
        :post-cond: akn = n!/(n-k)!
        """

   Ceci correspond au nombre de séquences que l'on peut obtenir
   en tirant au hasard `k` numéros parmi `n` et en tenant compte de l'ordre.

   On peut bien sûr utiliser la fonction factorielle_ ci-dessus,
   mais il existe une solution plus judicieuse,
   qui effectue moins de calculs
   et évite notamment à l'ordinateur de calculer de très grands entiers
   pour les diviser ensuite.

#. .. _sin:

   |exo| ⭑⭑ Approximer le sinus de `x` ::

    def sin(x: float, ε: float) -> float:
        """
        :entrée x: float
        :entrée ε: float
        :sortie s: float
        :pré-cond: x > 0
        :post-cond: |sin(x) - s| ≤ ε
        """

   On pourra utiliser le développement limité du sinus :

     `\sin(x) = x-\frac{x^3}{3!}+\frac{x^5}{5!}-\cdots+(-1)^n\frac{x^{2n+1}}{(2n+1)!}+o(x^{2n+2})`

#. .. _fibo:

   |exo| ⭑⭑ Calculez le terme de rang `n` de la suite de Fibonacci ::

    def fibo(x: int) -> int:
        """
        :entrée n: int
        :sortie f: int
        :pré-cond: n > 0
        :post-cond: f est le terme de rang n de la suite de Fibonacci
        """

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

   .. math::

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




.. only:: html

  .. rubric:: Indices

.. [#tip_ordre_heures] Cette sous-spécification vous permet
   une utilisation astucieuse de l'algorithme duree_en_secondes_.

.. [#tip_romain] Plus spécifiquement, on pourra extraire
   les unités, les dizaines, les centaines et les milliers,
   et pour chacun d'eux appeler romain_chiffre_generique_
   avec les valeurs appropriées pour `un`, `cinq` et `dix`.

.. [#tip_fibo] Une version récursive naïve de cette algorithme
   (invoquant deux fois la fonction ``fibo``) est un piège à éviter
   car elle répétera les mêmes calculs un nombre exponentiel de fois.
   Une meilleuure solution consiste à écrire une boucle
   dans laquelle on mémorise les *deux* derniers termes calculés.