3MMALG11 Soutien S02

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette page est maintenue uniquement par les enseignants. Afin de ne pas perturber le déroulement des cours, elle n'a pas vocation à être modifiée par les élèves. Mais si vous avez des modifications à proposer, merci d'en discuter ou d'envoyer un e-mail aux auteurs de la page (cf. historique)

Cet exercice a été traité en TP encadré sous le nom d'exercice P8.

Le but de cet exercice est de construire une machine séquentielle de plus en plus compliquée, en partant d'une simplification de l'énoncé et en rajoutant progressivement des fonctionnalités.

On rappelle brièvement le principe du programme à écrire. L'utilisateur va entrer une suite d'entiers positifs, terminée par un entier négatif et le programme doit calculer le nombre d'extremums locaux de cette suite. On défini un extrémum local comme un élément de la suite qui est :

  • soit le premier entier de la suite ;
  • soit le dernier entier de la suite ;
  • soit strictement inférieur à l'élément précédent et à l'élément suivant ;
  • soit strictement supérieur à l'élément précédent et à l'élément suivant.

La suite peut contenir des « bégaiements », c'est à dire le même entier entré plusieurs fois consécutivement : dans ce cas, on ignore les bégaiements en faisant comme si l'entier en question n'avait été entré qu'une seule fois.

On doit détecter les extremums au fur et à mesure que l'utilisateur saisi les entiers : il serait inefficace de commencer par saisir toutes les valeurs puis de refaire une passe sur la suite pour détecter les extremums. Cela implique que puisqu'on ne peut évidemment pas raisonner sur le « futur » (c'est à dire les éléments qui n'ont pas encore été saisis), on travaillera avec un temps de retard et on comparera l'élément précédent avec le précédent du précédent et le courant (et non pas le courant avec le précédent et le suivant).

Détection d'un extremum

On va commencer par écrire une procédure qui détecte si une valeur est un extremum et le cas échéant incrément le compteur d'extrémums (et affiche une trace au passage pour faciliter la mise au point). Cette procédure sera spécifiée par :

procedure Extremum(X_M1, X, X_P1: Integer; N: in out Natural);
-- X_M1, X et X_P1 sont trois entiers consécutifs de la suite
-- N est le compteur d'extrémums

On peut l'intégrer dans le squelette de programme principal suivant :

with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada.Text_IO, Ada.Integer_Text_IO;

procedure S02_E1 is

   procedure Extremum(X_M1, X, X_P1: Integer; N: in out Natural) is
   ...

   Nombre: Natural;

begin
   Put_Line("Entrer une suite de naturels terminee par -1 :");
   ...
   Put("Nombre d'extremum locaux : "); Put(Nombre, Width => 0); New_Line;
end S02_E1;

Version simplifiée de l'algorithme

Une technique efficace pour aborder un problème est de commencer par réfléchir sur une version simplifiée de ce problème. Dans le cas de cet exercice, on peut identifier plusieurs difficultés :

  • la suite vite et la suite constante ne sont pas « régulières », dans le sens qu'on ne peut pas considérer qu'il y a au moins 2 extremums (le premier et le dernier entier de la suite) et ainsi ne pas avoir à traiter le cas des valeurs aux bornes ;
  • les bégaiements compliquent le calcul car on doit les ignorer
  • vu qu'on va devoir tester l'élément courant, le précédent et le précédent du précédent, les suites de tailles 1 et 2 sont des cas particuliers

Pour commencer, on va donc considérer qu'on travaille sur une suite ayant au moins 3 éléments, sans bégaiements et non-constante.

Compléter le programme principal pour gérer une telle suite : on pourra introduire 3 variables Prec_Prec, Prec et Cour pour stocker les 3 éléments significatifs, et initialiser Prec_Prec et Prec en dehors de la boucle (puisqu'on part du principe qu'on a au moins 3 éléments). On recommande d'utiliser une boucle du type suivant pour la structure du programme principal :

loop
    Get(Cour);
    exit when Cour < 0;
    ...
end loop;

Gestion de la suite vide

Ajouter la gestion de la suite vide : cela peut se faire très simplement juste après la lecture initiale de Prec_Prec en dehors de la boucle.

Gestion de la suite constante

Là encore, on peut ajouter la gestion des suites constantes simplement après la gestion de la suite vide, en dehors de la boucle principale.

Gestion des bégaiements

Ajouter enfin la ligne de code très simple permettant d'ignorer les bégaiements.