Types abstraits¶

Géométrie¶

Dans cette section, on considère le type abstrait Vecteur pour représenter les vecteurs du plan :

class Vecteur:
    "type abstrait"

def base_v() -> (Vecteur, Vecteur):
    """
    :post-cond: retourne les deux vecteurs unitaires du plan
    """

def add_v(v1: Vecteur, v2: Vecteur) -> Vecteur:
    """
    :post-cond: retoune v1 + v2
    """

def mult_v(r: float, v: Vecteur) -> Vecteur:
    """
    :post-cond: retoune r⋅v
    """

def produit_scalaire(v1: Vecteur, v2: Vecteur) -> float:
    """
    :post-cond: retoune v1⋅v2 (le produit scalaire de v1 et v2)
    """

➥ Créer un vecteur à partir de ses coordonnées :
```
def cree_vecteur(x: float, y: float) -> Vecteur:
    """
    :post-conf: retourne le vecteur de coordonnées cartésiennes (x, y)
    """
```
N’importe quel vecteur peut être créé à l’aide des fonctions spécifiées plus haut : si \(\overrightarrow{v_x}\) et \(\overrightarrow{v_y}\) sont les vecteurs unitaires, alors le vecteur \(\overrightarrow{v}\) de coordonnées \((x, y)\) est égal à \(x⋅\overrightarrow{v_x} + y⋅\overrightarrow{v_y}\).
➥ Calculer les coordonnées cartésiennes d’un vecteur :
```
def coordonnees(v: Vecteur) -> (float, float):
    """
    :post-cond: retourne x et y les coordonnées cartésiennes de v
    """
```
On rappelle que les coordonnées \(x\) et \(y\) d’un vecteur \(\overrightarrow{v}\) sont en fait le produit scalaire de \(\overrightarrow{v}\) avec les vecteurs unitaires \(\overrightarrow{v_x}\) et \(\overrightarrow{v_y}\), respectivement.
➥ Calculer la norme (la longueur) d’un vecteur :
```
def norme(v: Vecteur) -> float:
    """
    :post-cond: retourne la norme du vecteur v
    """
```
On peut utiliser pour cela les coordonnées du vecteurs, ou le fait que la norme est égale à la racine carrée du produit scalaire du vecteur avec lui même.

➥ Calculer si deux vecteurs sont orthogonaux :

def orthogonaux(v1: Vecteur, v2: Vecteur) -> bool:
    """
    :post-cond: retourne True ssi v1 et v2 sont orthogonaux
    """

➥ Calculer si deux vecteurs sont colinéaires :

def colineaires(v1: Vecteur, v2: Vecteur) -> bool:
    """
    :post-cond: retourne True ssi v1 et v2 sont colinéaires
    """

➥ Implémenter le type abstrait Vecteur (c’est à dire les quatre fonctions définies au début de cette section) à l’aide d’un tableau de deux nombres flottants, représentant les coordonnées cartésiennes du vecteur.
➥ ⭑⭑ Implémenter le type abstrait Vecteur à l’aide d’un tableau de deux nombres flottants, représentant les coordonnées polaires du vecteur, c’est à dire sa norme et l’angle (orienté) qu’il forme avec l’axe des \(x\).

Date¶

Dans cette section, on considère le type abstrait Date pour représenter les dates du calendrier :

class Date:
    "type abstrait"

def cree_date(annee: int, mois: int, jour: int) -> Date:
    """
    :pré-cond:
       - annee > 0
       - 1 ≤ mois ≤ 12
       - 1 ≤ jour ≤ jours_par_annee_mois(annee, mois)
    :post-cond: retourne la Date correspondant aux entrées fournies
    """

def amj(d: Date) -> (int, int, int):
    """
    :post-cond: retounr (a, m, j) où
                a est l'année de la date d
                m est le numéro du mois (entre 1 et 12) de la date d
                j est le numéro du jour (entre 1 et 31) de la date d
    """

def diff_dates(d1: Date, d2: Date) -> int:
    """
    :post-cond: retourne diff tel que
                |diff| est le nombre de jours qui séparent d1 et d2;
                diff est positif si d1 est après d2, négatif sinon.
    """

def add_jours(d: Date, j: int) -> Date:
    """
    :post-cond: si j ≥ 0, retourne la date située j jours après d,
                sinon, retourne la date située -j jours avant d.
    """

➥ Implémenter le type abstrait Date en utilisant un tableau de trois entiers, représentant respectivement l’année, le mois et le jour.

Vous pourrez réutiliser les fonctions suivantes (proposées au chapitre Durées et dates) :
- jours_par_annee
- jours_par_annee_mois
➥ Implémenter le type abstrait Date en utilisant un entier, représentant le nombre de jours entre cette date et le 1er janvier 1900.

Vous pourrez réutiliser les fonctions suivantes (proposées au chapitre Durées et dates) :
- jours_par_annee
- jours_par_annee_mois
➥ Comparez les deux implémentations proposées ci-dessus pour le type abstrait Date. Lequel vous semble le plus judicieux ?

Pile¶

Dans cette section, on considère un type abstrait Pile possédant les méthodes suivantes :

class Pile:
    "type abstrait"

def cree_pile(n: int) -> Pile:
    """
    :post-cond: retourne p vérifiant pile_vide(p) == True
                p peut contenir au moins n éléments
    """

def pile_vide(p: Pile) -> bool:
    """
    :post-cond: retourne True si et seulement si la Pile est vide
    """

def pile_pleine(p: Pile) -> bool:
    """
    :entrée p: Pile
    :sortie v: bool
    :post-cond: retourne True si et seulement si la Pile est pleine
    """

def sommet(p: Pile) -> int:
    """
    :pré-cond: pile_vide(p) == False
    :post-cond: retourne la valeur au sommet de la pile
    """

def empile(p: Pile, v: int):
    """
    :e/s p: Pile
    :pré-cond: pile_pleine(p) == False
    :post-cond: v est ajouté au sommet de p
    """

def depile(p: Pile):
    """
    :e/s p: Pile
    :pré-cond: pile_vide(p) == False
    :post-cond: la valeur au sommet de p est retirée
    """

➥ Implémenter le type abstrait Pile en utilisant un tableau d’entiers a, tel que
- a[0] contient le nombre d’éléments \(n\) contenus dans la pile,
- ∀ i ∈ [1;n], a[i] est le i-ème élément de la pile (a[n] est le sommet),
- ∀ i ∈ [n;len(a)[, a[i] n’est pas utilisé (sa valeur est indéterminée).
➥ Déterminer si une chaîne de caractères est bien parenthésée, avec deux types de parenthèses :
```
def bien_parenthesee_2(txt: str) -> bool:
    """
    :post-cond: retourne True si et seulement si txt est bien parenthésée
    """
```
Cette chaîne de caractères contient des parenthèses rondes (( et )) et carrées ([ et ]). À chaque parenthèse ouvrante doit correspondre une parenthèse fermante du même type, et réciproquement. Par ailleurs, si une parenthèse ouvrante est ouverte à l’intérieur d’un autre couple de parenthèses, sa parenthèse fermante doit elle aussi de trouver à l’intérieur du même couple.

Le tableau ci-dessous donne des exemples de chaînes bien et mal parenthésées.

Bien parenthésées

Mal parenthésées

abc

(

(abc)

abc)

ab[cd]ef

ab)c

a[b]c(d)e

a(b]c

a((b)c)d

a(b(c)d

a(b[c()e]f)g

a(b[c)d]e

Cet algorithme est une généralisation de bien_parenthesee, mais l’existence de deux types de parenthèses différentes oblige à appliquer une méthode différente. On va parcourir la chaîne de gauche à droite, et mémoriser dans une pile l’ordre et le type des parenthèses ouvertes non encore fermées (par exemple, 1 pour parenthèse ronde, et 2 pour parenthèse carrée). Plus précisément, à chaque parenthèse ouvrante, on empilera son type. À chaque parenthèse fermante, on vérifiera dans la pile qu’elle a bien le type attendu, et si c’est le cas, on peut le dépiler.

NB: cette méthode peut en fait s’appliquer avec un nombre arbitrairement grand de types de parenthèses. On l’utilise notamment avec des documents structurés de type HTML, ou les balises sont autant de types de « parenthèses ».

Indices

Bien parenthésées	Mal parenthésées
`abc`	`(`
`(abc)`	`abc)`
`ab[cd]ef`	`ab)c`
`a[b]c(d)e`	`a(b]c`
`a((b)c)d`	`a(b(c)d`
`a(b[c()e]f)g`	`a(b[c)d]e`