1. Spécifier les types abstraits point et vecteur.
type point {constructeurs} { l'origine (0, 0) } origine : point { construit un point à partir de ses coordonnées x,y} consPoint : réel x réel -> point {opérations} { translation d'un point par un vecteur} translate : point x vecteur -> point { distance entre deux points } distance : point x point -> réel { test d'égalité } égale : point x point -> booléen fin type vecteur {constructeurs} { le vecteur nul } vecteurNul : vecteur { construit le vecteur PQ à partir des points P et Q} pointVec : point x point -> vecteur { construit un vecteur à partir de ses coordonnées } consVec : réel x réel -> vecteur {opérations} { norme d'un vecteur, sqrt (x^2 + y^2) } norme : vecteur -> réel { multiplication d'un vecteur par un scalaire, k.V } mulVec : réel x vecteur -> vecteur { produit scalaire de deux vecteurs, x1y1 + x2y2} scalaire : vecteur x vecteur -> réel { vecteur (-y, x), orthogonal au vecteur (x, y) } ortho : vecteur -> vecteur { test de colinéarite, V1 = k.V2 } colinéaire : vecteur x vecteur -> booléen fin
type droite {constucteur} consDroite : point x vecteur -> droite {opérations} pointSurDroite : point x droite -> booléen parallèle : droite x droite -> booléen droiteOrtho : droite x point -> droite fin {réalisation :} type droite = produit origine : point direction : vecteur fin fonction consDroite (p: point, v: vecteur) -> droite { construit une droite à partir d'un point p et d'un vecteur v, qui doit être non nul. } lexique d : droite début d.origine <- p d.direction <- v retourner d fin fonction pointSurDroite (p: point, d: droite) -> booléen { teste si le point p est sur la droite d} début retourner colinéaire (d.direction, pointVec(d.origine, p)) fin fonction parallèle (d1, d2 : droite) -> booléen { teste si deux droites sont parallèles } début retourner colinéaire (d1.direction, d2.direction) fin fonction droiteOrtho (d : droite, p : point) -> droite { calcule la droite orthogonale a d passant par p } début retourner consDroite (p, ortho (d.direction)) fin
3. Fonction qui calcule où se trouve un point M par rapport à une droite D.
type côté = (aGauche, aDroite, dessus) fonction quelCôté (p : point, d : droite) -> côté { calcule la position relative de p par rapport à d } lexique pm : vecteur s : réel début pm <- pointVec (d.origine, p) s <- scalaire (ortho (d.direction), pm) selon le cas s > 0 : retourner aGauche s = 0 : retourner dessus s < 0 : retourner aDroite fin fin
4.a Spécifier le type abstrait polygone.
{ type permettant de représenter un segment de droite } type segment = produit p1, p2 : point fin type polygone {constructeur} { construction d'un polygone avec 3 points } triangle : point x point x point -> polygone {opérations} { ajout d'un point à un polygone } action ajouterPoint : DR polygone x point { retourne le i-ème point du polygone } ièmePoint : polygone x entier -> point { retourne le i-ème segment du polygone } ièmeSegment : polygone x entier -> segment fin
4.b Réaliser le type polygone.
const maxp = 100 { un polygone est constitué d'un tableau de points et d'un nombre de points } type polygone = produit pts : tableau [0 .. maxp] de point nbp : entier fin fonction triangle (p1, p2, p3 : point) -> polygone { crée un polygone à partir de 3 points } lexique poly : polygone début poly.pts [0] <- p1 poly.pts [1] <- p2 poly.pts [2] <- p3 poly.nbp <- 3 retourner poly fin action ajouterPoint (DR poly : polygone, p : point) { ajoute un point à la fin du polygone si c'est possible } début si poly.nbp <= maxp poly.pts [poly.nbp] <- p poly.nbp <- poly.nbp + 1 sinon erreur ("trop de points dans le polygone !") fin fonction ièmePoint (poly : polygone, i : entier) -> point { retourne le i-ème point du polygone s'il existe } début si i >= 0 et i < poly.nbp retourner poly.pts[i] sinon erreur ("point inexistant") fin fonction ièmeSegment (poly:polygone, i:entier) -> segment { retourne le i-ème segment du polygone s'il existe } lexique s : segment début si i >= 0 et i < poly.nbp s.p1 <- poly.pts[i] si i = poly.nbp-1 s.p2 <- poly.pts[i+1] { segment PiPi+1} sinon s.p2 <- poly.pts[0] { segment PnP0 } sinon erreur ("segment inexistant") retourner s fin
5. Spécifier et réaliser une fonction qui calcule si un polygone est convexe.
fonction segDroite (s : segment) -> droite { retourne la droite support du segment s } début retourner consDroite (s.p1, pointVec (s.p1, s.p2)) fin fonction convexe (poly : polygone) -> booléen { calcule si un polygone est convexe. On suppose que trois points successifs du polygone ne sont jamais alignés } lexique seg : droite c, c1 : côté i, j : entier début pour i parcourant [0..poly.nbp -1] début { trouver la droite support du ième segment } s <- segDroite (ièmeSegment (poly, i)) { regarder de quel côté est le point suivant } j <- (i + 1) mod poly.nbp c <- quelCôté (ièmePoint (poly, j), seg) { regarder tous les points et vérifier qu'ils sont du même côté que c } pour j parcourant [0..poly.nbp -1] début c1 <- quelCôté (ièmePoint(poly, j), seg) si c1 != c retourner faux fin fin retourner vrai fin
1. Spécifier et réaliser la fonction permettant d'additionner deux GrandNombre.
fonction somme (n1, n2 : GrandNombre) -> GrandNombre { calcule la somme de deux grands nombres } lexique résultat : GrandNombre retenue : chiffre s, r, rmax : entier début résultat <- zéro retenue <- 0 { r est le rang pour lequel on calcule la somme } r <- 0 { rmax est le nombre maximal de chiffres de n1 et n2} rmax <- max (nbChiffres(n1), nbChiffres(n2)) pour r parcourant [0 .. rmax] début { calculer la somme partielle } s <- ième(r, n1) + ième(r, n2) + retenue { calculer la retenue et le chiffre de rang r } retenue <- s div 10 s <- s mod 10 affecter (résultat , r, s) fin { ne pas oublier la dernière retenue } affecter (résultat , r, retenue) retourner résultat fin
2. Spécifier et réaliser ensuite une fonction qui multiplie deux GrandNombre.
fonction multc (n:GrandNombre, c:chiffre) -> GrandNombre { calcule le produit d'un grand nombre par un chiffre } lexique résultat : GrandNombre retenue : chiffre p, r : entier début résultat <- zéro retenue <- 0 pour r parcourant [0 .. nbChiffres(n)] début p <- c * ième (r, n) + retenue retenue <- p div 10 p <- p mod 10 affecter (résultat, r, p) fin affecter (résultat, r, retenue) retourner résultat fin
fonction produit (n1, n2 : GrandNombre) -> GrandNombre { calcule le produit de deux grands nombres } lexique résultat : GrandNombre partiel : GrandNombre r : entier début résultat <- 0 pour r parcourant [0 .. nbChiffres(n2)] début partiel <- multc (n1, ième (r, n2)) partiel <- mul10n (partiel, r) résultat <- somme (résultat, partiel) fin retourner résultat fin
3. Réaliser les constructeurs et opérations du type abstrait GrandEntier.
const maxc = 100 type GrandNombre = tableau [0 .. maxc] de chiffre fonction zéro -> GrandNombre { retourne le nombre 0 } lexique résultat : GrandNombre i : entier début pour i parcourant [0 .. maxc] résultat [i] <- 0 retourner résultat fin action affecter (DR n:GrandNombre, i:entier, c:chiffre) { effecte le ième chiffre d'un grand nombre. i doit être inférieur à maxc, nombre maximal de chiffres} début n[i] <- c fin fonction nbChiffres (n : GrandNombre) -> entier { retourne le nombre de chiffres d'un grand nombre } lexique i : entier début i <- maxc tantque i > 0 et n[i] = 0 faire i <- i - 1 retourner i fin fonction mul10n (n:GrandNombre, p:entier) -> GrandNombre { multiplie un grand nombre par 10^p, p > 0 } lexique résultat : GrandNombre i : entier début { décaler les chiffres de p rang vers la gauche } pour i parcourant [0 .. maxc - p] résultat [p + i] <- n [i] { mettre des 0 dans les p premier rangs } pour i parcourant [0 .. p] résultat [i] <- 0 retourner résultat fin