Algorithme de calcul de longueur d’une File
Pour connaitre la longueur de la file nous sommes conduit à utiliser le Schéma itératif qui nous permet de répéter un certain nombre de fois une séquence d’instruction.
TantQue Condition
Faire
Séquence d'instructions
Fin-Faire
Nous allons écrire cet algorithme en tenant compte des points suivants:
- On choisit la variable dont l’identificateur du nombre d’éléments est Long pour ranger la valeur de la longueur
- On n’oublie pas d’initialiser la variable Long à zéro
- On choisit de parcourir la file avec un schéma itératif pour ce calcul
- On n’oublie pas de positionner le curseur de parcours au début de la file
- On n’oublie pas de faire avancer le curseur de parcours.
Pour établir cet algorithme on intègre, au schéma élémentaire de parcours de file, les instructions de calcul de la longueur de la file. L’instruction Prendre n’est pas nécessaire puisque la valeur pointée par le curseur ne participae pas au calcule de la longueur de la file
Premier(File)
TantQue Non Dernier(File)
Faire
-- Instruction de comptage
Avancer(File)
Fin-Faire
L’algorithme peut s’écrire:
Affecter(0,Long) -- Attribuer la valeur du nombre 0 à Val
Premier(File) -- Place le curseur de parcours sur le premier
-- élément si celui-ci existe
TantQue Non Dernier(File) -- On continue tant que ce n'est pas la
Faire -- fin de la file
Ajouter(1,Long) -- Ajouter 1 à la valeur contenue dans Long
Avancer(File) -- Place la valeur de l'élément courant dans Val
Fin-Faire
Afficher ("la longueur est" Long) -- Affiche le résultat sur un média virtuel
Etude de la cohérence d’un schéma
Pour assurer la cohérence d’un schéma on doit vérifier les points suivants:
- Le schéma de choix : la cohérence de la condition
- Le schéma itératif: la condition de contrôle de l’itération est cohérente si l’itération se termine au bout d’un nombre fini de boucles. On s’assure qu’au moins une instruction ou un schéma primitive, Premier, Avancer de l’itération doit modifier la condition de contrôle Dernier
- Instructions: La cohérence des valeurs d’initialisation des variables
On vérifie aussi les point suivants:
- Il est obligatoire de placer la primitive Premier(File) avant le schéma d’itération TantQue puisque que la primitive Premier permet de définir Dernier(File) à VRAI s’il existe au moins un élément et à FAUX si la file est vide.
- La primitive Premier(File) doit précéder l’ action Avancer pour que cette dernière soient définie.
- L’itération se termine car une file séquentielle est finie ( par définition) et la primitive Avancer positionne la marque de fin au bout d’un nombre fini d’exécution en permettant à la primitive Dernier de retourner une valeur VRAI
Remarques
- Dans le cas d’une file vide l’itération n’est pas exécutée puisque le primitive Dernier délivre vrai après l’exécution de la primitive Premier et la valeur de la variable Long retourne bien la valeur zéro initialisée au début.
- La primitive Ajouter(1,Long) est placée avant La primitive Avancer. En effet une file de longueur i, la i ème itération permet de donner la valeur i à la variable Long , l’exécution de la primitive suivante Avancer va permettre de positionner la fin de file et par la suite de permettre à la primitive Dernier de retourner une résultat VRAI
Schéma d’algorithme: Définition formelle
On définit le schéma d’algorithme comme un moyen d’organiser les instructions d’un algorithme en deux parties dans lesquelles, on décrit la partie Quoi avec le mot-clé Description et la partie Comment avec le mot-clé Action.
La partie Description permet de préciser toutes les variables et primitives établissant une communication avec l’extérieur. Elle permet pour un acteur externe d’identifier ce pour quoi l’algorithme est réalisé, autrement dit le QUOI.
La partie Action encapsule la séquence d’instructions et primitives qui réalise l’algorithme, le COMMENT encapsule la partie non visible.
En terme de programmation on parle d’Interface ou Spécification pour désigner le Quoi et d’Implémentation pour désigner le Comment
La partie Description contient les élément descriptifs suivants:
- Objectif : La liste des objectifs à atteindre
- Données: La liste des données nécessaire au traitement
- Résultat: Le ou les résultats à obtenir
- Remarque: Les limitations ou contraintes
La partie Action contient les schéma élémentaires et les primitives:
- Déclaration de donnée
- Primitives: (Prendre, Dernier, Premier)
- Schéma itératif
- Schéma conditionnel
En tenant compte des remarques ci-dessus, nous allons écrire un schéma d’algorithme pour le comptage du nombre occurrences d’un élément donné dans une file. On appelle occurrence d’un élément l’apparition de cet élément dans un ensemble. Dans cette présentation de schéma d’algorithme on décrit la partie Quoi (Interface) avec le mot-clé Description et la partie Comment ( Implémentation) avec le mot-clé Action
Schéma algorithme CompterElement Description Objectif: -- Comptage des occurrences d'un élément dans une file. Donnée: File -- File séquentielle Elément -- Variable contenant la valeur à compter Résultat: -- Le nombre d'occurrence de l'élément dans la file Remarque: -- La file et élément ne sont pas modifiés par cette action Fin-Description Action CompterElement Premier (File) Affecter (0,compteur) TantQue Non Dernier (File) Faire Prendre (File,Val) Si Egal(Val,Element) Alors Ajouter (1,compteur) Fin-Si Avancer(File) Fin-Faire Afficher ("Le nombre d’occurrences est",compteur) Fin-Action Fin-Schéma