Algorithme.

http://www.ininfo.fr

par YOUSSEF NEJJARI

Algorithme. Définition : Un algorithme, c’est une suite d’instructions, qui une fois exécutée correctement, conduit à un résultat donné. Il s'agit de fournir la solution à un problème, en se passant par les étapes suivantes : Problème ------------> analyse --------------------->

Algorithmique

Le langage de description utilisé pour écrire le résultat de l'analyse est appelé algorithme. L'étape suivante consiste à traduire l'algorithme dans un langage de programmation spécifique, il s'agit de la phase de programmation. Exemples : -trier une liste par ordre alphabétique. -trouver un chemin pour aller d'une station de métro a une autre. -calculer la factorielle d'un nombre. -Trouver les solutions réelles approchées d'une équation de la forme : a x2 + b x + c = 0. - ....... Structure d'un algorithme : Nom_du_programme

Généralement :

Variables Début

Nom du programme (Entête)

instruction 1

Variables

instruction 2

Début

.........

Corps

Fin

Fin

Remarque : pour stocker des données pendant le traitement de l'algorithme on utilise les variables. Variable : Une variable est comme une boîte qui a un nom et contient une valeur. On peut changer le contenu de la boîte (la valeur) à volonté. Elle est caractérisée par un nom

et un type. Nom de variable : suite continue des caractères, l'alphabet et des numéros et (-,_). un nom de variable ne peut jamais commencer par un numéro. Type de variable : Le type d'une variable indique au compilateur ce que cette variable est supposée représenter. Une variable peut contenir un entier, une valeur réelle, un caractère, l'adresse d'une autre variable... la liste est longue. Il est donc important que le compilateur sache quel type de variable il doit attendre. Plus encore, étant donné que les différents types de variables peuvent avoir des tailles en mémoire différentes, le compilateur a besoin de savoir absolument quelle quantité de mémoire il doit allouer. La syntaxe pour déclarer une variable en précisant son type est : Nom_de_variable : type; Les types des variables : ►Les types élémentaires : Type Type Numériq ue

Plage

Byte (octet)

0 à 255

Entier simple

-32 768 à 32 767

Entier long

-2 147 483 648 à 2 147 483 647

Réel simple

-3,40E38 à -1,40E-45 pour les valeurs négatives 1,40E-45 à 3,40E38 pour les valeurs positives

Réel double

1,79E308 à -4,94E-324 pour les valeurs négatives 4,94E-324 à 1,79E308 pour les valeurs positives

........... Types Booléen non numériqu es Alphanumérique

................ Deux valeurs (Vrai, Faux), (0,1), (Oui, Non), ...

Char, LongChar, ....

►Les types structurés : - le type TABLEAU ou MATRICE (à une ou plusieurs dimensions). - le type ENREGISTREMENT ou LISTE (ou type composé).

Remarque : Une constante est un objet qui ne peut pas être modifié par l’algorithme. Affectation : Définition : l'affectation est l'opération qui consiste à stocker une valeur dans une variable. cette opération se fait à l'aide du syntaxe suivante : Nom_Variable ← Valeur ; Expressions arithmétiques : La formulation des expressions arithmétiques est elle aussi similaire à la notation mathématique : ·2+3 · 17 * 73 + 2 · 7 mod 2 · 7 div 2 (vaut 3 : division entière) · 7 / 2 (vaut 3.5 : division réelle) · 0.3 * 168.2 + (4. + 0.11)/5. . ........ . Exemple : Programme Somme; variables entier x, y, z; début Ecrire("Somme de 2 valeurs "); Ecrire("Entrez la 1ere valeur "); x := lire(); Ecrire("Entrez la 2eme valeur "); y := lire(); z := x+y; afficher("La somme vaut : "); afficher(z);

fin Programme Surface_cercle; constantes réel pi vaut 3.14159; variables réel rayon, surface; début Ecrire("entrez la valeur du rayon du cercle : "); rayon := lire(); surface := pi * rayon*rayon; Ecrire("La surface vaut : " , surface); fin Les instructions : ► Les instructions élémentaires. - La lecture au clavier du contenu d'une ou plusieurs variables. Syntaxe : LIRE(variable) ; LIRE(x,y); Remarques : la lecture au clavier s'achève dès que l'on presse la touche "entrée" ou ("retour chariot"). La donnée tapée doit être du même type que la variable qui la reçoit. - L'affichage à l'écran (ou l'édition sur imprimante) d'un objet (nombre, chaîne, ...) du contenu d'une ou plusieurs variables, d'une expression, ... Syntaxe : ECRIRE('la somme est ',x+y); ► Les instructions composées. - Un bloc d'instructions est une suite d'instructions (élémentaires ou non) séparées par des points-virgules et encadrées des deux mots DEBUT et FIN. Dans la suite, "instruction" désignera soit une instruction élémentaire soit un bloc. - Les instructions conditionnelles : L'alternative : On effectue un test pour choisir entre deux instructions possibles : SI ALORS instruction_1 SINON instruction_2; Fin Si Le résultat de l’expression logique (ou condition) est un booléen.

Quand l’expression logique est vraie alors la suite d’actions située après le mot ALORS (instruction_1) est exécutée. Si le résultat est faux , on exécute la suite d’actions située après le mot SINON (instruction_2). Exemple : SI x>20 ALORS Ecrire("Positif") SINON Ecrire("négatif") Fin Si; La conditionnelle simple : même structure mais la deuxième instruction est vide : SI ALORS instruction_1; Dans cette cas si la condition est vérifiée l'instruction 1 qui sera exécutée si non le pointeur passe à la suite du programme. La conditionnelle multiple : Pour faire plusieurs testes on utilise la syntaxe suivante : SELON NomVar Cas_1 : Instruction_1; Cas_2 : Instruction_2; ... Cas_n : Instruction_n; FIN; Dans cette cas les instruction s'exécutent selon la valeur de NomVar. Les boucles (Structures itératives). Un ensemble d’actions qui se répète toujours dans un ordre précis, un nombre déterminé de fois constitue un traitement itératif. La boucle POUR : Si on connaît exactement le nombre de répétitions à effectuer. On utilise un compteur de boucles : POUR var1 VARIANT DE valeur1 A valeur2 EFFECTUER Instruction; FinPour; Instruction peut être simple ou composée. La boucle TANT_QUE : Si le nombre de répétition dépend d'un condition on utilise la boucle TANT_QUE. TANT_QUE

EFFECTUER instruction; FinTantQue; Instruction peut être simple ou composée. La structure Répéter…jusqu’à.. Répéter Instructions Jusqu’à <expression logique> Dans ce cas la suite des instructions est exécutée au moins une fois, car le test de l’expression logique est effectuée après exécution de l’ensemble d’actions. Les tableaux. Pour calculer la moyenne de 15 notes on doit déclarer 15 variables (m = var1 + var2 + var3 +....+ var15)/15) se qu'est non pratique. Et pour éviter ce problème on utilise les tableaux. Donc un tableau est un variable qui rassemble plusieurs variables en 1 seul, au sein de laquelle chaque valeur sera désignée par un numéro. (N[1],N[2],...N[15]) se qu'est plus pratique. Définition : Un tableau est un ensemble de valeurs portant le même nom de variables et repérés par un indice. Déclaration : la déclaration d'un tableau se fait à l'aide du syntaxe suivant : Tableau Nom_Tableau(Nombre_d_indices) en Type. Exemple :Tableau Note(15) en Entier. Utilisation : L’énorme avantage des tableaux, c’est qu’on va pouvoir les traiter en faisant des boucles. Par exemple, pour effectuer notre calcul de moyenne, cela donnera par exemple : Tableau Note(15) en entier Variables Moy, Som en entier Début Som ← 0; Pour i ← 0 à 15 faire Ecrire ("Entrez la note n°", i) ; Lire Note(i); FinPour; Pour i ← 0 à 15 faire Som ← Som + Note(i) ; FinPour; Moy ← Som / 15 ; Ecrire("la moyenne est :",Moy) ; Fin

Les fonctions. Si l'utilisation d'une suite des instructions se répète plusieurs fois dans un programme (Par exemple la moyenne de N notes), on utilise les fonctions. Définition : Une fonction est une suite des instruction permettant de réaliser une taches. Une fonction est caractérisée par un nom est par des paramètres. et elle peut retourner un valeur ou non. Déclaration : la déclaration d'une fonction se fait à l'aide du syntaxe suivant : Fonction Nom_Fonction (Variables1 en type1, Variable2 en type2, ...) en type_fonction instructions 1 ; instructions 2 ; ... instructions n ; Fin Fonctin; Exemples : Fonction Moyenne (x, y, z , t en entier) en reel variable moy en reel; ecrire("donner lavaleur de x"); lire(x); ecrire("donner lavaleur de y"); lire(y); ecrire("donner lavaleur de z"); lire(z); ecrire("donner lavaleur de t"); lire(t); moy = (x+y+z+t)/4; renvoyer moy; Fin Fonction;

Fonction ChoixDuMot() Tableau Liste() en Caractère Variables Nbmots, Choisi en Numérique Ouvrir "Dico.txt" sur 1 en Lecture Nbmots ← -1 Tantque Non EOF(1) Nbmots ← Nbmots + 1 Redim Liste(Nbmots) LireFichier 1, Liste(Nbmots) FinTantQue Fermer 1 Choisi ← Ent(Alea() * Nbmots) Renvoyer Liste(Choisi) FinFonction Les procédures. Une fonction renvoi une seule valeur mais les procédures renvoient rien ou plusieurs. Alors une fonction se caractérisait par les mots-clés Fonction ... Fin Fonction et une procédure est identifiée par les mots-clés Procédure ... Fin Procédure. Toute fonction devait, pour cette raison, comporter l'instruction "Renvoyer". Pour la même raison, l'instruction "Renvoyer" n'est jamais utilisée dans une procédure. La fonction est une valeur calculée, qui renvoie son résultat vers la procédure principale. La procédure, elle, est un traitement ; elle ne "vaut" rien. Remarque : Les fonctions, ne sont finalement qu'un cas particulier des procédures. Exemple : Procédure AffichageMot(m en Caractère par Valeur, t() en Booléen par Valeur) Variable Aff en Caractere Variable i en Numerique Aff ← "" Pour i ← 0 à len(m) - 1 Si Non t(i) Alors Aff ← Aff & "-" Sinon Aff ← Aff & Mid(mot, i + 1, 1) FinSi i suivant Ecrire Aff FinProcédure Voila un lien vers un cours plus détallé. Et un autre pour télécharger un cours complet de l'algorithme au format pdf.