Enchaînements d’instructions¶

Géométrie¶

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

➥ 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

    """

Conditions et calcul¶

➥ 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}
    """

➥ 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).

Durées et dates¶

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

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

➥ ⭑ 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émentation1.

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

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.

➥ ⭑ 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.

Variante : autoriser \(d\) à prendre une valeur négative pour calculer une heure située \(-d\) secondes avant h:m:s.
➥ 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.
➥ 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.

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

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

➥ 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 ?

➥ ⭑⭑ 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).

➥ ⭑⭑ 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.

➥ 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 janvier 1900 était un lundi.

Chiffres romains¶

➥ 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
    """
```
➥ ⭑ 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).
➥ ⭑⭑ 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 2.

Nombres en base 10¶

➥ 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
    """
```
➥ 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
    """
```

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

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

➥ 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…
➥ 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.
➥ ⭑ 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.

Fonctions mathématiques¶

➥ Calculer la valeur absolue de \(x\) :
```
def valeur_absolue(x: float) -> float:
    """
    :entrée x: float
    :sortie a: float
    :post-cond: a = |x|
    """
```
➥ 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.

Variante : relâcher la contrainte sur \(n\) en autorisant des valeurs négatives.
➥ 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) ?
➥ ⭑⭑ 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
➥ ⭑⭑ Approximer la racine n^ème 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.

➥ ⭑⭑ 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.

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

➥ ⭑ 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.

➥ ⭑⭑ 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})\)

➥ ⭑⭑ 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 Fibonnaci3 est définie par :

\[\begin{split}& F_0 = 1 \\ & F_1 = 1 \\ & \forall n > 1, ~~ F_n = F_{n-1} + F_{n-2}\end{split}\]

Indices

1: Cette sous-spécification vous permet une utilisation astucieuse de l’algorithme duree_en_secondes.
2: 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\).
3: 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.

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