Algorithmique & Programmation Orientée Objet
Semestre 2 ST
Structuration des programmes en sous-algorithmes
Cours Exercices PDL - Corrections Exercices Java

Exercice n°1: Sous-algorithmes "simples"

a) Ecrire un sous-algorithme de calcul du sinus d'un angle donné en degrés.

La fonction développée possède un paramètre d'entête de type réel passé en entrée pour l'angle (en degré). Elle retourne un réel: le sinus de l'angle.
Une alternative aurait été de développer une fonction sans paramètre retourné, mais avec un paramètre d'entête supplémentaire passé en sortie.

Sinus.lda

{ Calcul du du sinus d'un angle en degres   }

constante reel PI <- 3.14159

reel fonction sinus(-> réel angle)
  reel sn
  sn <- sin(angle*PI/180.0)
  retourner sn
fin fonction

Exemple d'exécution

b) Ecrire un sous-algorithme de test si un caractère est alphabétique (minuscule ou majuscule).

La fonction développée possède un paramètre d'entête passé en entrée de type caractère pour le caractère à tester. Elle retourne un booléen: vrai ou faux en fonction du résultat du test.
Une alternative aurait été de développer une fonction sans paramètre retourné, mais avec un paramètre d'entête supplémentaire passé en sortie.

TestCaractereAlphabetique.lda

{ Test si un caractere est alphabetique ou non    }

booleen fonction estAlphabetique(-> caractere c)
  booleen res
  si ( ( c >= 'a' ) et ( c <= 'z' ) ) ou
     ( ( c >= 'A' ) et ( c <= 'Z' ) ) alors
    res <- vrai
    sinon
    res <- faux
  fsi
  retourner res
fin fonction

Exemple d'exécution

c) Ecrire un sous-algorithme de lecture au clavier d'un nombre entier positif.
Si l'utilisateur frappe une valeur non positive, il devra être sollicité de nouveau jusqu'à ce qu'il tape une valeur admissible.

La fonction développée ne possède pas de paramètre d'entête. Elle retourne un entier: la valeur positive saisie.
Une alternative aurait été de développer une fonction sans paramètre retourné, mais avec un paramètre d'entête passé en sortie.

LectureEntierPositif.lda

{ Lecture au clavier d'une valeur entiere    }
{ positive et retour                         }

entier fonction lectureEntierPositif()
  entier valeur
  valeur <- Clavier.sasirEntier()
  tant que valeur < 0 faire
    afficherln("Erreur!!! Veuillez ressaisir)
    valeur <- saisir()
  fait
  retourner valeur
fin fonction

Exemple d'exécution

d) Ecrire un sous-algorithme de lecture au clavier d'un nombre réel compris dans un intervalle [min, max].
Si l'utilisateur frappe une valeur en dehors de l'intervalle, il devra être sollicité de nouveau jusqu'à ce qu'il tape une valeur admissible.

La fonction développée possède deux paramètres d'entête réels passés en entrée: les valeurs min et max. Elle retourne un réel: la valeur saisie dans l'intervalle [min,max].
Une alternative aurait été de développer une fonction sans paramètre retourné, mais avec un paramètre d'entête supplémentaire passé en sortie.

LectureReelDansIntervalle.lda

{ Lecture au clavier d'une valeur reelle     }
{ comprise dans un intervalle et retour      }

reel fonction lectureReelDansIntervalle(-> reel min,-> reel max)
  reel valeur
  valeur <- saisir()
  tant que valeur < min ou valeur > max faire
    afficherln("Erreur!!! Veuillez ressaisir)
    valeur <- saisir()
  fait
  retourner valeur
fin fonction

Exemple d'exécution

e) Ecrire un sous-algorithme d'affichage en hexadécimal d'un nombre entier.
On considérera que le nombre à afficher est compris dans l'intervalle [0,255].

La fonction développée possède un paramètre d'entête de type entier passé en entrée: la valeur à afficher en hexadécimal. Elle retourne aucune valeur car son but est uniquement de réaliser un affichage.
Une fonction affichageChiffreHexadecimal a été développée pour afficher un chiffre hexadécimal ('0' à '9' puis 'A' à 'F') suivant sa valeur décimale (0 à 15). Le nombre entier passé en paramètre étant compris entre 0 et 255, deux chiffres hexadécimaux sont à afficher. La fonction affichageChiffreHexadecimal est appelée 2 fois: une fois pour chacun des 2 chiffres.

AffichageHexadecimal.lda

{ Affichage hexadecimal d'un entier compris entre 0 et 255 }

action affichageHexadecimal(-> entier v)
  entier chiffreHaut
  entier chiffreBas
  chiffreHaut <- v/16
  chiffreBas <- v modulo 16
  affichageChiffreHexadecimal(chiffreHaut)
  affichageChiffreHexadecimal(chiffreBas)
fin action

{ Affichage hexadecimal d'un chiffre                       }
action affichageChiffreHexadecimal(-> entier chiffre)
  dans le cas de chiffre
    10 :
      afficher('A')
    11 :
      afficher('B')
    12 :
      afficher('C')
    13 :
      afficher('D')
    14 :
      afficher('E')
    15 :
      afficher('F')
    autre cas :
      afficher(chiffre)
  fcas
fin action

Exemple d'exécution

f) Ecrire un sous-algorithme de calcul de la valeur de sin(a) au voisinage de 0.0 par développement limité.
La formule de calcul est sin(a) = a - a3/3! + a5/5! - a7/7! + a9/9! - ... +/- an/n!       (a en radians)

La fonction développée possède un paramètre d'entête de type réel passé en entrée: la valeur de l'angle (en radians) pour laquelle on calcule le sinus. Elle retourne une valeur de type réel: la valeur de sinus calculée.
Une alternative aurait été de développer une fonction sans paramètre retourné, mais avec un paramètre d'entête supplémentaire passé en sortie.

Pour optimiser l'exécution, toutes les puissances et toutes les factorielles ne sont pas calculées intégralement. Chaque terme de la suite est calculé à partir du terme précédent. Le terme 1 est égal à a (a/1). Ensuite chaque terme i est égal au terme i-1 multiplié par a*a et divisé par i*2-2 et par i*2-1. Le développement limité est obtenu par somme d'un certain nombre de termes.
On notera que, dans l'implantation, plutôt que de numéroter les termes 1, 2, 3, 4, 5, ..., on a préféré les numéroter 1, 3, 5, 7, 9, ...

DeveloppementLimiteSinus.lda

{ Calcul de la valeur de sin(a) au voisinage de 0.0 }
{ Utilisation du developpement limite               }
{ Les valeurs a et n sont donnees                   }

reel fonction sinus(-> reel a,-> entier n)
  reel sn
  reel terme
  entier i
  terme <- a
  sn <- a
  pour i de 3 à n pas 2 faire
    terme <- -terme*a*a/(i*(i-1))
    sn <- sn + terme
  fait
  retourner sn
fin fonction

Exemple d'exécution

Exercice n°2: Sous-algorithmes avec données agrégées

a) Ecrire un sous-algorithme de calcul du sinus et du cosinus d'un angle donné en degrés.

Première alternative: Développer une fonction avec un paramètre d'entête de type réel passé en entrée pour l'angle (en degré) et deux paramètres d'entête passés en sortie pour les deux valeurs calculées.
Deuxième alternative: Développer une fonction avec un paramètre d'entête de type réel passé en entrée pour l'angle (en degré) et un paramètre d'entête passé en sortie agrégeant deux réels (un pour le sinus, un pour le cosinus) (Solution non développée ci-dessous).
Troisième alternative: Développer une fonction avec un paramètre d'entête de type réel passé en entrée pour l'angle (en degré) et une valeur retournée agrégeant deux réels (un pour le sinus, un pour le cosinus).

CosinusEtSinus.lda
(Solution sans type agrégé)

{ Calcul du cosinus et du sinus d'un angle    }
{ donne en degres                             }

action calculCosinusEtSinus(-> reel angle,reel cosinus ->,reel sinus ->)
  reel a
  a <- angle*3.1415926535897932/180.0
  cosinus <- cos(a)
  sinus <- sin(a)
fin action

Exemple d'exécution

CosinusEtSinusAvecStructure.lda
(Solution avec type agrégé)

{ Type agrege de stockage du cosinus          }
{ et du sinus d'un angle                      }

structure cosinusEtSinus
  reel cosinus <- 1.0
  reel sinus   <- 0.0
fin structure

{ Calcul du cosinus et du sinus d'un angle    }
{ donne en degres                             }

cosinusEtSinus fonction calculCosinusEtSinus(-> reel angle)
  reel a
  cosinusEtSinus res
  a <- angle*3.1415926535897932/180.0
  res.cosinus <- cos(a)
  res.sinus <- sin(a)
  retourner res
fin fonction

Exemple d'exécution

b) Ecrire un sous-algorithme de test de l'inclusion d'un point de coordonnées (x,y) à l'intérieur d'un cercle de rayon r et de centre (cx,cy).

Première alternative: Développer une fonction avec cinq paramètres d'entête de type réel passés en entrée pour l'abscisse et l'ordonnée du point testé, le rayon, l'abscisse et l'ordonnée du centre du cercle. Elle retourne une valeur de type booléen: vrai ou faux pour inclusion ou non inclusion.
Seconde alternativer: Structurer les données et développer une fonction avec deux paramètres d'entête agrégés de type position2D pour le point testé, et cercle2D pour le cercle. Elle retourne une valeur de type booléen: vrai ou faux pour inclusion ou non inclusion.

TestInclusion.lda
(solution sans type agrégé)

{ Test de l'inclusion d'un point dans un cercle }
{ Les coordonnees du point sont donnees         }
{ ainsi que le rayon et les coordonnees         }
{ du centre du cercle                           }

booleen fonction testInclusion(-> reel x,-> reel y,-> reel rayon,-> reel cx,-> reel cy)
  booleen inclus
  reel distance
  distance <- sqrt((x-cx)*(x-cx)+(y-cy)*(y-cy))
  si distance < rayon alors
    inclus <- vrai
    sinon
    inclus <- faux
  fsi
  retourner inclus
fin fonction

Exemple d'exécution

TestInclusionAvecStructure.lda
(solution avec types agrégés)

{ Type agrege de stockage d'une position du plan }

structure position2D
  reel x <- 0.0
  reel y <- 0.0
fin structure

{ Type agrege de stockage d'un cercle du plan    }

structure cercle2D
  position2D centre
  reel rayon <- 1.0
fin structure

{ Test de l'inclusion d'une position du plan     }
{ dans un cercle du plan                         }

booleen fonction testInclusion(-> position2D p,-> cercle2D c)
  reel dx
  reel dy
  reel distance
  booleen inclus
  dx <- p.x-c.centre.x
  dy <- p.y-c.centre.y
  distance <- sqrt(dx*dx+dy*dy)
  inclus <- (distance <= c.rayon)
  retourner inclus
fin fonction

Exemple d'exécution

c) Ecrire un sous-algorithme de calcul de la surface d'un rectangle du plan à cotés parallèles aux axes.

Le rectangle est représenté par la position de 2 sommets opposés du rectangle.
Première alternative: Développer une fonction avec quatre paramètres d'entête de type réel passés en entrée pour l'abscisse et l'ordonnée du premier sommet et l'abscisse et l'ordonnée du second sommet. Elle retourne une valeur de type réel: la surface.
Seconde alternativer: Structurer les données et développer une fonction avec un paramètre d'entête agrégé de type rectangle2D passé en entrée. Elle retourne une valeur de type réel: la surface.

SurfaceRectangle.lda
(solution sans type agrégé)

{ Calcul de la surface d'un rectangle   }
{ Les coordonnees de deux coins opposes }
{ sont donnees                          }

entier fonction surfaceRectangle(-> reel px1,-> reel py1,-> reel px2,-> reel py2)
  reel surface
  surface <- abs(px2-px1)*abs(py2-py1)
  retourner surface
fin fonction

Exemple d'exécution

SurfaceRectangleAvecStructure.lda
(solution avec types agrégés)

{ Type agrege de stockage d'une position du plan     }

structure position2D
  reel x <- 0.0
  reel y <- 0.0
fin structure

{ Type agrege de stockage d'un rectangle du plan     }

structure rectangle2D
  position2D p1
  position2D p2
fin structure

{ Calcul de la surface d'un rectangle 2D             }

entier fonction surfaceRectangle(-> rectangle2D r)
  reel surface
  surface <- abs(r.p2.x-r.p1.x)*abs(r.p2.y-r.p1.y)
  retourner surface
fin fonction

Exemple d'exécution

Exercice n°1fbis: Sous-algorithme à plusieurs niveaux

Reprendre l'exercice 1f en programmant le calcul du développement limité avec utilisation de fonctions pour les calculs de puissance et de factoriel.

DeveloppementLimiteSinusAvecFonctions.lda

{ Calcul de la puissance entiere d'un reel          }
{ Les valeurs a reelle et n entiere sont donnees    }
  
reel fonction puissance(-> reel a,-> entier n)
  reel res
  entier i
  res <- a
  pour i de 1 à n-1 faire
    res <- res*a
  fait
  retourner res
fin fonction

{ Calcul de n!                                      }
{ La valeur n entiere est donnee                    }
  
entier fonction factoriel(-> entier n)
  entier fct
  entier i
  fct <- 1
  pour i de 2 à n faire
    fct <- fct*i
  fait
  retourner fct
fin fonction

{ Calcul de la valeur de sin(a) au voisinage de 0.0 }
{ Utilisation du developpement limite               }
{ Les valeurs a et n sont donnees                   }

reel fonction sinus(-> reel a,-> entier n)
  reel sn
  reel signe
  entier i
  signe <- -1.0
  sn <- a
  pour i de 3 à n pas 2 faire
    sn <- sn + puissance(a,i)/factoriel(i)
    signe <- -signe
  fait
  retourner sn
fin fonction

Exemple d'exécution

Exercice n°3: Sous-algorithmes à plusieurs niveaux et données agrégées

a) Ecrire un sous-algorithme de test si une année est bissextile.

La fonction développée possède un paramètre d'entête de type entier passé en entrée pour l'année testée. Elle retourne un booléen: vrai ou faux en fonction de la bissextilité de l'année.

TestBissextile.lda

{ Test si une annee est bissextile    }

{ version 1                           }

booleen fonction estBissextile(-> entier annee)
  booleen res
  si annee modulo 400 == 0 alors
    res <- vrai
    sinon
    si annee modulo 100 == 0 alors
      res <- faux
      sinon
      si annee modulo 4 == 0 alors
        res <- vrai
        sinon
        res <- faux
      fsi
    fsi
  fsi
  retourner res
fin fonction

{ version 2                           }

booleen fonction estBissextile(-> entier annee)
  booleen res
  si ( annee modulo 400 == 0 ) ou 
     ( ( annee modulo 100 <> 0 ) et ( annee modulo 4 == 0 ) ) alors
        res <- vrai
        sinon
        res <- faux
  fsi
  retourner res
fin fonction

Exemple d'exécution

b) Ecrire un sous-algorithme de calcul du nombre de jours d'un mois codé sous la forme d'un nombre.

La fonction développée possède deux paramètres d'entête de type entier passés en entrée pour le mois et l'année testés. Elle retourne un entier: le nombre de jours du mois.

NombreJoursMois.lda

{ Calcul du nombre de jours d'un mois     }
{ Si le numero de mois est invalide,      }
{ la fonction retourne -1                 }

entier fonction nombreJoursMois(-> entier mois,-> entier annee)
  entier res
  dans le cas de mois
    2 :
      si estBissextile(annee) alors
        res <- 29
        sinon
        res <- 28
      fsi
    4 :
    6 :
    9 :
    11 :
      res <- 30
    1 :
    3 :
    5 :
    7 :
    8 :
    10 :
    12 :
      res <- 31
    autre cas :
      res <- -1
  fcas
  retourner res
fin fonction

Exemple d'exécution

c) Ecrire un sous-algorithme de calcul de la date du jour suivant immédiatement une date codée sous la forme jour-mois-année en nombres.

Solution 1: La fonction développée possède un paramètre d'entête passé en entrée de type date. Elle retourne une date: la date correspondant au jour suivant la date passée en entête.

Solution 2: L'action développée possède deux paramètres d'entête. Le premier est passé en entrée et est de type date. Le second est passé en sortie et est de type date. Le second paramètre est destiné à recueillir la date calculée

JourSuivant.lda

structure date
  entier jour <- 1
  entier mois <- 1
  entier annee <- 1901
fin structure

{ Calcul de la date suivant une date codee }
{ sous la forme jour mois annee en entier  }

{ Version 1                                }

date fonction jourSuivant(-> date d)
  date dt
  dt.annee <- d.annee
  dt.mois <- d.mois
  dt.jour <- d.jour+1
  si dt.jour > nombreJoursMois(d.mois,d.annee) alors
    dt.jour <- 1
    dt.mois <- dt.mois+1
    si dt.mois > 12 alors
      dt.mois <- 1
      dt.annee <- dt.annee+1
    fsi
  fsi
  retourner dt
fin fonction

{ Version 2                                }

action jourSuivant(-> date d,date dt ->)
  dt.annee <- d.annee
  dt.mois <- d.mois
  dt.jour <- d.jour+1
  si dt.jour > nombreJoursMois(d.mois,d.annee) alors
    dt.jour <- 1
    dt.mois <- dt.mois+1
    si dt.mois > 12 alors
      dt.mois <- 1
      dt.annee <- dt.annee+1
    fsi
  fsi
fin action

Exemple d'exécution

d) Ecrire un sous-algorithme de modification d'une date codée sous la forme jour-mois-année en nombres pour l'incrémenter de un jour.

jourDApres.lda

structure date
  entier jour <- 1
  entier mois <- 1
  entier annee <- 1901
fin structure

{ Modification d'une date codee sous forme }
{ jour mois annee en entier pour passer    }
{ au jour d'apres                          }

action jourDApres(-> date d ->)
  d.jour <- d.jour+1
  si d.jour > nombreJoursMois(d.mois,d.annee) alors
    d.jour <- 1
    d.mois <- d.mois+1
    si d.mois > 12 alors
      d.mois <- 1
      d.annee <- d.annee+1
    fsi
  fsi
fin action

Exemple d'exécution