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
#. .. _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
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
#. .. _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
.. _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
#. .. _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
#. .. _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
#. .. _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
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
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
#. .. _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
#. .. _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
#. .. _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
#. .. _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
#. .. _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
#. .. _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
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
#. .. _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
#. .. _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
#. .. _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
#. .. _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
#. .. _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
#. .. _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
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
#. .. _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
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
#. .. _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.