Editions ENI Livres | Vidéos | e-Formations
Développement à partir d’algorithmes
Présentation de la notion d’algorithme
Un algorithme est la description des opérations nécessaires pour obtenir un résultat à partir de valeurs d’entrée, les "données". Un programme est un algorithme écrit dans un langage spécifique, nous y reviendrons plus tard.
Une recette de cuisine peut être considérée comme un algorithme. À titre d’exemple, la fabrication d’un gâteau est basée sur des ingrédients (lait, beurre, farine, sucre...) et une démarche méthodique (recette de la grand-mère) sera appliquée pour mettre en œuvre ces ingrédients (mélange, temps de cuisson...). Vous l’aurez compris dans notre vie de tous les jours nous utilisons des algorithmes sans réellement nous en rendre compte (recettes, notices, plans de conception, modèles...).
Reconsidérons notre exemple de la recette de cuisine. En son absence, il est possible de réussir son plat par une succession de tentatives (dosages divers, temps de cuisson approximatifs). Évidemment cette démarche (même si certains y trouveront du plaisir) est assez inefficace (perte de temps et gâchis des ingrédients).
La programmation va être le moyen de définir et de spécifier à l’ordinateur l’ensemble des opérations...
Notion de variable
1. Présentation des notions de variable et de type
Un algorithme manipule des objets sur lesquels il peut effectuer des actions. Les objets simples sont :
-
des nombres (3.14159, 1980, 9...),
-
des caractères ("A", "9"...) et des chaînes de caractères ("PAULINA"...),
-
des valeurs booléennes ou logiques (vrai ou faux).
Pour pouvoir manipuler ces objets, des opérations sont disponibles. Ces objets ainsi que les opérations qui leur sont associées doivent être parfaitement définis. Analysons les trois exemples suivants qui sont des situations d’échange entre un client et un vendeur.
Exemple 1 :
-
"Bonjour Monsieur l’épicier, je voudrais 1 kg et 1 kg."
-
"??"
Exemple 2 :
-
"Bonjour Monsieur l’épicier, je voudrais 1 kg de riz et 1 kg de vin."
-
"Voici votre kilo de riz et que voulez-vous par ailleurs ?"
Exemple 3 :
-
"Bonjour Monsieur l’épicier, je voudrais 1 kg de riz et 1 litre de vin."
-
"Voilà je vous ai tout rangé dans un petit sac"
On constate sur ces exemples la nécessité :
-
de citer la nature des objets que l’on veut manipuler (riz, vin...),
-
de ne pas utiliser ces objets n’importe comment (on pèse du riz, on boit du vin...), c’est-à-dire qu’à chaque nature d’objet sont liées des opérations particulières.
On appelle type l’association :
-
d’une nature d’objets (riz, vin, ou encore entiers, réels...),
-
et des opérations associées (peser, laver, cuire le riz, additionner, multiplier des entiers...).
2. Types de base et opérations associées
On distingue quatre types de base : entier, réel, booléen, caractère.
Le type entier :
-
Les valeurs sont des nombres entiers.
-
Notation : la notation décimale est utilisée (Exemples : 365, -15).
-
Opérations : addition, soustraction, multiplication, division entière, modulo (reste de la division entière)...
Le type réel :
-
Les valeurs sont des nombres réels.
-
Notation : le point anglo-saxon remplace la virgule (Ex : 124.89, 0.136, 1986).
-
Opérations : celles utilisées usuellement sur les réels...
Manipulation des variables
1. Nommage des variables
Lors de l’analyse d’un problème, on est souvent amené à le décomposer en sous-problèmes qui doivent être résolus dans un ordre séquentiel bien précis. Chaque sous-problème produit des résultats qui peuvent être utilisés dans les sous-problèmes qui suivent. Il convient donc, pour pouvoir manipuler ces résultats, de les nommer. Ce nommage se fait par l’intermédiaire d’un identificateur. On parle aussi très souvent de variable mémoire.
À chaque variable mémoire, on associe les caractéristiques suivantes :
-
sa dénomination, qui doit être judicieuse (deux résultats différents sont désignés par un identificateur différent),
-
son type (ensemble auquel appartient la valeur qu’il désigne).
Ces caractéristiques sont précisées lors de la déclaration de la variable mémoire.
Syntaxe de la déclaration :
|
|
Type IDENTIFICATEUR |
Type est le type et IDENTIFICATEUR la dénomination de la variable mémoire.
Exemples :
|
|
Réel PI Car SEPARATEUR Bool TEST Ent NBMOIS, NBJOURS |
Une fois une variable mémoire définie, on ne peut plus changer son type.
Toute variable mémoire utilisée dans un algorithme doit avoir été déclarée auparavant.
Dans la suite de ce support de cours, il a été choisi de nommer les variables mémoire en majuscules pour une meilleure lisibilité. Sachez que de nombreux langages de programmation sont sensibles à la "casse" des variables mémoire (une variable MONTANT est différente d’une variable Montant !!!).
Évidemment en programmation ensuite (JavaScript dans notre cas), des conventions de nommages différentes pourront vous être proposées.
En JavaScript pour les variables mémoire (et les fonctions) la convention communément acceptée est le "camelCaps", c’est-à-dire que les noms doivent commencer systématiquement par une minuscule et ensuite des majuscules viendront s’insérer en début de chaque mot constituant le nom de la variable. Par exemple une variable comme CUMUL_ANNUEL...
Fonctions prédéfinies
Une fonction prédéfinie est un "microprogramme" autonome auquel il est possible de demander un traitement (un calcul en général) par passage d’un ou de plusieurs paramètres. Une fois le calcul assuré, la fonction restitue une valeur de retour (la réponse) au demandeur (séquence de code ayant fait appel à la fonction). Cette notion vous est sûrement familière car vous avez par exemple utilisé des fonctions natives sous Microsoft Excel (SOMME, RECHERCHEV...).
Nous verrons plus tard dans cette présentation de l’algorithmique (et aussi surtout sous JavaScript) comment développer ses propres fonctions.
L’objectif n’est pas ici d’énumérer la liste des fonctions courantes en algorithmique (elle peut d’ailleurs varier d’un auteur à un autre) mais plutôt de vous montrer comment elles peuvent s’utiliser. Une présentation au travers d’exemples ou d’exercices va être privilégiée.
1. Exercice n°4 : Affichage de la longueur d’un nom
Sujet
Écrire un algorithme permettant la saisie au clavier d’un nom pour afficher le nombre de caractères.
Complément de cours : Une fonction Longueur(variable_chaîne) prédéfinie sera utilisée pour déterminer le nombre de caractères du mot saisi.
Corrigés
|
Début |
|
|
Co Déclarations Fco Car NOM |
|
|
|
Co Saisie du nom au clavier Fco Ecrire("Nom : ") NOM <- Lire |
|
|
Co Affichage du résultat Fco Ecrire(NOM, " contient " , Longueur(NOM), " caractère(s)") |
|
Fin |
|
ou encore :
|
Début |
|
|
|
Co Déclarations Fco Car NOM Ent NB_CAR |
|
|
Co Saisie du nom au clavier Fco Ecrire("Nom : ") NOM <- Lire |
|
|
Co Affichage du résultat Fco NB_CAR <-... |
Traitements conditionnés
Dans beaucoup de situations, des actions ne sont à effectuer que si certaines conditions sont remplies :
-
Une équation du second degré a 0, 1 ou 2 solutions réelles suivant que le discriminant soit négatif, nul ou positif.
-
Si une quantité d’articles en stock tombe en dessous d’un certain seuil, il faut émettre une commande.
-
S’il fait beau alors on va à la plage, sinon on fait de l’algorithmique ensemble.
-
S’il ne fait pas beau alors on fait de l’algorithmique ensemble.
Chacun de ces choix est conditionné par une expression booléenne qui, lorsqu’elle est vraie, entraîne l’exécution du traitement associé.
La syntaxe algorithmique pour programmer des traitements conditionnés est des plus simples :
|
Si Condition |
|
|
Alors |
|
|
|
T1 |
|
[Sinon |
|
|
|
T2] |
|
Finsi |
|
Juste quelques remarques sur cette structure très intuitive :
-
Condition est une expression à résultat booléen (Vrai ou Faux).
-
T1 et T2 sont des traitements.
-
Finsi signifie la fin du si.
-
Une forme simplifiée, sans l’alternative, existe (sans Sinon T2).
-
Le test sur la condition se fait sur une hypothèse de condition vraie.
-
Le tracé d’un trait vertical (à gauche) entre Si et Finsi sera un moyen mnémotechnique pour ne pas oublier le Finsi.
-
Pensez à indenter les traitements T1 et T2.
L’ordinogramme correspondant à cette structure est le suivant :
Dans l’exemple présenté ci-après, une variable de nom NBLU est affectée d’une valeur saisie au clavier et l’algorithme précise ensuite s’il s’agit d’une valeur paire ou impaire :
|
Début |
||
|
|
Co Déclarations Fco Ent NBLU |
|
|
|
Co Saisie clavier Fco Ecrire("Nombre : ") |
|
|
|
NBLU <- Lire |
|
|
|
Co Détermination de la parité Fco Si NBLU Mod 2 = 0 |
|
|
|
Alors |
|
|
|
|
Ecrire(NBLU, " est pair") |
|
|
Sinon |
|
|
|
|
Ecrire(NBLU, " est impair") |
|
|
Finsi |
|
|
Fin |
|
|
1. Exercice n°6 : Polynôme du second degré
Sujet
Calculer les racines d’un polynôme du second degré Ax2+Bx+C (avec A<>0 dans l’absolu mais ce test ne sera pas effectué...
Structures itératives
1. Principe des itérations
Dans la plupart des problèmes, certaines actions doivent être exécutées plusieurs fois.
Quand le nombre de répétitions est grand, il est fastidieux de réécrire n fois la même séquence de code. Cette réécriture est même impossible dans le cas où le nombre de répétitions (itérations) est inconnu a priori (traiter un ensemble de données jusqu’à ce qu’il n’y en ait plus).
Il faut pouvoir exprimer la répétition d’une action, qui une fois initialisée se continuera jusqu’à ce qu’un certain événement se produise. Cet événement d’arrêt sera spécifié dans l’algorithme par l’intermédiaire d’une condition.
2. Structures itératives de base
Étudions quatre types d’itérations (boucles) dont vous trouverez l’équivalent dans les principaux langages de programmation.
Boucle "Tant que" avec un test en début d’itération :
|
Tantque Condition Faire |
|
|
|
Actions |
|
Refaire |
|
Boucle "Jusqu’à" avec un test en début d’itération :
|
Jqa Condition Faire |
|
|
|
Actions |
|
Refaire |
|
Boucle "Tant que" avec un test en fin d’itération :
|
Faire |
|
|
|
Actions |
|
Tantque Condition Refaire |
|
Boucle "Jusqu’à" avec un test en fin d’itération :
|
Faire |
|
|
|
Actions |
|
Jqa Condition Refaire |
|
Ces quatre boucles ont un certain nombre de points communs :
-
Jqa est une abréviation pour Jusqu’à
-
Tantque est une abréviation pour Tant que
-
Condition est une expression booléenne de résultat Vrai ou Faux
-
Actions représente une séquence d’actions
Avec les deux dernières itérations pour lesquelles le test se fait en fin de boucle, les Actions sont effectuées au moins une fois.
Les boucles "Tant que" et "Jusqu’à" ont un fonctionnement très proche dans la mesure où il suffit d’inverser la condition pour passer d’une syntaxe à l’autre. Par exemple COMPTEUR > 10 dans le cas d’une boucle "Tant que" deviendra COMPTEUR <= 10 dans...
Tableaux à dimension unique
Un tableau regroupe plusieurs valeurs de même type. On peut nommer globalement toutes les valeurs ou avoir une désignation précise d’une des valeurs par une opération d’indiçage.
Par exemple, considérons ALPHABET comme l’ensemble des lettres de l’alphabet. Dans ce cas :
-
ALPHABET désigne un tableau qui pourrait servir à stocker l’ensemble des lettres de l’alphabet.
-
ALPHABET(14) pourrait représenter la lettre "N".
-
l’entier 14 est appelé indice.
Dans un algorithme, tout comme pour les variables (simples) vues jusqu’à présent, les tableaux doivent être déclarés avant de pouvoir être utilisés. La syntaxe de déclaration est :
|
|
Type IDENTIFICATEUR(INF:SUP) |
Notons ceci au niveau de cette déclaration :
-
IDENTIFICATEUR est le nom global du tableau (nom librement choisi par le programmeur, en majuscules si possible).
-
Type indique le type des éléments du tableau et tous les éléments du tableau ont le même type (Ent, Réel, Car et Bool).
-
INF et SUP sont respectivement les bornes inférieure et supérieure de l’intervalle de variation de l’indice du tableau. Un tel tableau possède N éléments où N = SUP - INF + 1.
-
INF et SUP sont des constantes...
Tableaux à dimensions multiples
Lorsque les éléments d’un tableau sont eux-mêmes des tableaux, on parle de tableau à plusieurs dimensions.
Au niveau de la déclaration de ce genre de tableau, pas de surprise, il faut annoncer les limites de l’indice pour chacune des dimensions :
Type IDENTIFICATEUR(INF1:SUP1, ..., INFi:SUPi, ..., INFn:SUPn)
Pour accéder aux différentes cellules d’un tableau à plusieurs dimensions, il faut tout naturellement indiquer une valeur d’indice pour chacune d’entre elles. À titre d’exemple pour un tableau à deux dimensions (tableau de lignes subdivisées en colonnes comme une matrice 2D sous Microsoft Excel), le premier indice conventionnellement désigne le numéro de la ligne et le second indice le numéro de la colonne de la cellule à laquelle il est fait référence. La syntaxe est donc :
IDENTIFICATEUR(INDICE1, ..., INDICEi, ..., INDICEn)
1. Exercice n°15 : Mini-tableur
Sujet
Soit le tableau TB à deux dimensions comportant quatre lignes et cinq colonnes. Réaliser les traitements suivants :
-
saisir au clavier des valeurs dans les trois premières lignes et les quatre premières colonnes (on conserve la dernière ligne et la dernière colonne libres pour des sommations de lignes et de colonnes),
-
additionner...
Procédures, fonctions et passage de paramètres
1. Les objectifs
Ces nouveaux mécanismes permettent au programmeur de traiter un problème sans se soucier, dans un premier temps, du règlement dans le détail des sous-problèmes. Il s’agit d’outils très similaires aux fonctions mathématiques.
En programmation, une procédure ou une fonction représente un algorithme opérant sur des arguments ou paramètres formels (valeurs fictives en quelque sorte). L’exécution de cet algorithme se produit à l’appel de la procédure ou de la fonction. Les données de cet algorithme appelé sont alors les paramètres effectifs (provenant de l’algorithme appelant).
L’intérêt méthodologique de ces mécanismes consiste essentiellement, dans une première étape, à convertir les sous-problèmes en procédures (ou en fonctions) et à traiter le problème général (ou principal) comme si ces sous-problèmes étaient résolus. Dans une seconde étape, ces procédures ou fonctions sont décrites. Un autre intérêt réside dans le fait que si le même sous-problème doit être résolu plusieurs fois avec des paramètres effectifs différents, l’emploi d’une procédure ou d’une fonction permet une meilleure lisibilité de l’algorithme.
2. Les procédures
Débutons l’étude de ce mécanisme par la syntaxe de la déclaration :
|
Procédure NOM_PROCEDURE([Type1 IDFO1, ..., Typei IDFOi]) |
|
|
|
Corps de la procédure |
|
Fin_procédure |
|
Dans cette déclaration :
-
NOM_PROCEDURE est un nom librement choisi par le programmeur.
-
IDFOi est le nom du ième paramètre formel de la procédure.
-
Typei est le type du ième paramètre formel de la procédure.
-
La procédure ne rend pas de valeurs à moins qu’elle n’intervienne sur des variables de portée (accessibilité) globale.
-
Procédure et Fin_procédure sont des mots réservés.
L’appel d’une procédure depuis une autre procédure ou depuis l’algorithme principal se fait en respectant le schéma...