1
Algorithmique
TOUHTOUH Samira
Ecole Nationale des Sciences Appliques dEl Jadida
[Link]@[Link]
Plan
Introduction Informatisation dun problme : Langage algorithmique Les variables Les constantes Fonctions dentre-sortie Les structures Les tableaux Les fonctions
Les fichiers
Plan
Introduction Informatisation dun problme : Langage algorithmique Les variables Les constantes Fonctions dentre-sortie Les structures de contrles Les tableaux Les fonctions
Les fichiers
VII. Les tableaux
Introduction Dans certains conditions, les variables que nous connaissons sont trs mal adaptes aux traitements effectuer. Lorsquil sagit dun grand nombre de valeurs de mme types qui se rpte, le traitement est lourd. Imaginons, que nous avons plusieurs traitements effectuer sur des consommations mensuelles deau. Pour conserver ces valeurs en mmoire, nous pouvons prendre 12 variables numriques que nous appellerons, par exemple, Eau1, Eau2,..,Eau12. Pour calculer la consommation mensuelle moyenne sur lanne nous pouvons crire la longue formule : Moyenne = (eau1 + eau2 + eau3+ eau4 + eau5+ eau6+ eau7 + eau8+ eau9+eau10 + eau11+ eau12)/12
Les tempratures 16 heures de chacun des jours dune semaine seront les 7 valeurs de la variable Temp qui est un tableau de 7 variables de type nombre qui sont dsignes par Temp[1], Temp[2], Temp[7]
Temp 1 2 3 4 5 6 7 8 6 7 11 6 Cette case du tableau reprsente la variable Temp[5] dont la valeur est 6 Le nom Temp dsigne lensemble du tableau
8
9
Exemple : Ecrire un algorithme qui permet de calculer la moyenne des tempratures de la semaine : Algorithme calcul de la moyenne des tempratures de la semaine Variables : Temp : tableau [7] dentiers k : entier Somme : entier Dbut somme 0 Pour k de 1 jusquau 7 faire somme somme + Temp[k] moyenne somme/7 Fin
Le principe d'un tableau est trs simple : on stocke les lments dans des cases, chaque case tant tiquete d'un numro(gnralement appel indice). Pour accder un lment particulier d'un tableau, on donne son indice. Le nombre maximal dlments du tableau, qui est prcis la dfinition, sappelle sa dimension. Le type de ses lments sappelle le type du tableau.
Pour accder aux lments dun tableau, un indice indique le rang de llment.
Dclaration dun tableau
1) T: Tableau [6] de rels 2) T: Tableau [1,6] de rels
// liste de notes ou de tempratures
3) T: Tableau [0,5] de rels
Rels : Type des lments du tableau [6] : Nombre dlments dans le tableau. Chaque lment est repr dans le tableau par un indice varie de 0 taille-1 ou de 1 taille. On accde la case 2 par T[2]. (cest la 3e case ou la 2e case)
Utilisation dun tableau
Tableau une dimension La manipulation des lments du tableau (notes) est dcrite dans lexemple suivant : une seule variable permet de stocker 4 notes entires. Algorithme utilisation dun tableau Variables : notes : tableau[4] dentiers; Dbut notes[0] notes[1] notes[2] notes[3] Fin 12; : on peut fixer la valeur de llment dindice 0 14; 10; 18;
10
Ltat de mmoire
12
14
10
18
11
Manipulation de tous les lments dun tableau
Exemple 1 : Lire les valeurs des lments dun tableau T de N
nombres entiers.
12
Tableau deux dimensions Linformatique nous offre la possibilit de dclarer des tableaux dans lesquels les valeurs ne sont pas repres par une seule, mais par deux coordonnes. Tableau cases [7,7] en Entier
13
Exemple :
Ecrire un algorithme remplissant un tableau de 6 sur 13, avec des zros.
14
Plan
Introduction Informatisation dun problme : Langage algorithmique Les variables Les constantes Fonctions dentre-sortie Les structures de contrles Les tableaux Procdures et fonctions
Les fichiers
15
Procdures
Nous voulons poser plusieurs questions aux quelles nous attendons une rponse sous la forme O ou N. Un compteur nous permettra de compter le nombre de rponse positive.
Peut-on passer au feu rouge clignotant?
Doit-on marquer un arrt au STOP?
Pour prendre en compte la rponse de lutilisateur qui doit rpondre seulement par OUI ou par NON
Ceci ncessite lutilisation de plusieurs instructions en particulier lutilisation de la boucle tant que,
16
Algorithme : rponseOuiNon Variables : rep : caractre Dbut : Compteur 0 Ecrire Peut-on passer au feu rouge clignotant Lire rep Tant que rep # O ET rep # N { Ecrire rpondez O pour oui et N pour non Lire rep } Si Rep N alors compteur compteur + 1 Ecrire Doit-on marquer un arrt au STOP Lire rep Tant que rep # O ET rep # N { Ecrire rpondez O pour oui et N pour non Lire rep } Si Rep O alors compteur compteur + 1 Ecrire points marqus : , compteur Fin
17
Pour ne pas avoir recopier plusieurs fois les mmes lignes dans lalgorithme, nous pouvons crer une procdure qui est une partie dalgorithme, crite part, dsign par un nom, et que lon fait excuter plusieurs fois, en citant son nom.
18
Dfinition dune procdure :
Procdure maProcdure ( )
// dclaration des variables
Variables var1 : entier Dbut instructions 1 instructions 2 Fin procdure
19
Variables Question : chane de caractres Rep : caractre; Compteur: nombre entier Procdure ReponseOuiNon ( ) Dbut Ecrire Question Lire Rep Tant que (rep # O) et (Rep # N) Faire Ecrire rpondez par O ou par N Lire Rep Fin
20
Dbut Compteur 0 Question peut-on passer au feu rouge clignotant? PeponseOuiNon Si Rep N alors compteur compteur + 1 Question doit-on marquer un arrt au STOP? PeponseOuiNon Si Rep O alors compteur compteur + 1 Ecrire points marqus : , compteur Fin
21
Les variables locales et globales
Les variables dclares dans lalgorithme appelant ne sont pas utilisables dans les procdures. Chaque algorithme et sous algorithme a son propre espace de variables, inaccessible par les autres.
Les variables sont dites LOCALES.
Il peut exister des variables GLOBALES, mais leur usage est dconseill.
22
Paramtres
Un paramtre est une variable particulire sert la communication entre algorithme appelant et sous-algorithme. Deux types de communication de valeurs par paramtres apparaissent : La valeur du paramtre effectif est affecte avant lexcution de la procdure au paramtre formel qui est une variable appartenant la procdure : on dit que le paramtre est en entre. Le paramtre formel est une autre dsignation du paramtre effectif, valable pendant la dure de la procdure, il ne lui correspond aucune variable propre la procdure : Le paramtre est en sortie.
23
Paramtres en entre : transmission par valeur
Dans lexemple 1, on peut dclarer une nouvelle variable quest, qui va service dun variable locale la procdure.
24
Procdure ReponseOuiNon (Quest : chane de caractres) Dbut Ecrire Quest Lire Rep Tant que (rep # O) et (Rep # N) Faire Ecrire rpondez par O ou par N Lire Rep Fin Dbut BonnesReponses 0 ReponseOuiNon(peut-on passer au feu rouge?) Si Rep = N Alors BonnesReponses BonnesReponses + 1 ReponseOuiNon(Doit-on marquer un arrt au STOP?) Si Rep = O Alors BonnesReponses BonnesReponses + 1 Fin
25
Le paramtre est crit entre parenthses, on le qualifie de paramtre formel dans la dclaration, de paramtre effectif lors de chaque appel.
Lors du premier appel la procdure, le texte Peut-on passer au
feu rouge clignotant? est automatiquement affect au paramtre Quest, Il sera remplac par doit-on marquer un arrt au STOP? lors du deuxime appel. On na plus soccuper de la variable Question qui peut disparaitre du programme, mais seulement fournir, lors de chaque appel, le paramtre effectif qui correspond au paramtre formel.
26
Paramtre en sortie : transmission par adresse
Exemple : Nous voulons stocker les rponses successives dans le tableau R de [1..20] caractres pour permettre un traitement ultrieur. Dbut lectureOuiNon(peut-on passer au feu rouge clignotant?) R[1] Rep LectureOuiNon(doit-ont marquer un arrt u STOP?) R[2] Rep Nous prfrons crer un second paramtre : la variable effective dans laquelle la procdure doit lire la rponse. Lalgorithme devient :
27
Procdure ReponseOuiNon (Quest : chane de caractres, Rep : caractre) Dbut Ecrire Quest Lire Rep Tant que (Rep # O) et (Rep # N) Faire Ecrire rpondez par OUI ou par NON Lire REP Fin Dbut ReponseOuiNon(peut-on passer au feu rouge?, R[1]) ReponseOuiNon(Doit-on marquer un arrt au STOP?, R[2]) Fin
28
La correspondance entre la variable R[1] et le paramtre Rep ne peut pas fonctionner comme pour le paramtre quest, On ne souhaite pas voir affecter la valeur de R[1] Rep, mais on veut au contraire que la valeur finale de Rep se trouve dans R[1], Le nom Rep, dfini comme paramtre formel de la procdure est un nom provisoire dsignant le paramtre effectif pour la dure de lexcution de la procdure.
R[1] dsigne pendant la premire excution et R[2] pendant la deuxime.
29
Pour distinguer dans lcriture, nous choisirons de faire procder, chaque nom de paramtre formel de lindication du type de transmission, suivant le modle : Procdure Deux Paramtres ( ParamtreEnEntre, ParamtreEnSorte)
Les paramtres en Entre/Sortie, ils sont galement transmis par adresse et nots par la double flche
30
Les fonctions
Certains traitements ne peuvent tre effectus par un algorithme, exemple le cas du calcul du sinus dun angle.
Tout langage de programmation propose un certain nombre de fonctions; certains sont indispensables, car elles permettent deffectuer des traitements qui seraient sans elles impossibles. Dautres servent faciliter la programmation.
31
Structure gnrale des fonctions
Reprenons lexemple du sinus. Les langages informatiques, proposent gnralement une fonction SIN. Si nous voulons stocker le sinus de 35 dans la variable A, nous crirons :
sin(35)
32
Une fonction est donc constitue de trois parties :
- Le nom de la fonction. Le nom dune fonction commence par une minuscule. Le nom dune fonction ne comporte pas despace. Si le nom de la fonction est compos de plusieurs mots, faire commencer chacun deux par une majuscule (par exemple : sommeDeDeuxEntiers,) et ne pas faire figurer de traits dunion.
- Deux parenthses, une ouvrante, une fermante.
- Une liste de valeurs, indispensables la bonne excution de la fonction. Ces valeurs sappellent des arguments, ou des paramtres. Certaines fonctions exigent un seul argument, dautres deux, etc. et dautres aucun.
33
Lutilit des fonctions :
Le programmeur doit penser concevoir et crire des fonctions pour amliorer son programme. Il y gagnera sur plusieurs points : Le code des algorithmes est plus simple, plus clair et plus court. Dans un algorithme, appeler une fonction se fait en une seule ligne et la fonction peut tre appele plusieurs reprises. Une seule modification dans la fonction sera automatiquement rpercute sur tous les algorithmes qui utilisant cette fonction. Lutilisation de fonctions gnriques dans des algorithmes diffrents permet de rutiliser son travail et de gagner du temps.
34
Les fonctions sont comparables aux procdures : Leur appel ne constitue pas lui seul une instruction, mais figure dans une expression. Leur excution produit un rsultat qui prend la place de la fonction lors de lvaluation de lexpression.
Linstruction retourne,
35
Trois tapes sont toujours ncessaires lexcution dune fonction :
1.
Le programme appelant interrompt son excution.
2.
La fonction appele effectue son bloc dinstructions. Ds quune instruction retourne est excute, la fonction sarrte.
Le programme appelant reprend alors son excution.
3.
36
Larrt de la fonction
Une fonction sarrte lorsque son excution atteint la fin du bloc dinstructions, ou lorsque linstruction retourne est excute (avec ou sans valeur).
37
Fonction sans valeur retourne
Ecrire et utiliser une fonction simple qui doit afficher bonjour . Cette fonction ne retourne pas de valeur : ceci est signal en prcisant quelle retourne vide. Fonction afficheBonjour () : vide Dbut crire (bonjour) retourne Fin Une fonction se termine toujours par linstruction retourne. Cette fonction effectuera les instructions entre Debut et Fin.
38
Ecrire un algorithme qui appelle la fonction afficheBonjour (). Algorithme utilise-fonction Dbut afficheBonjour () Fin
39
La suite des instructions excutes au cours du temps :
40
Exemple :
Ecrire un algorithme qui appelle 10 fois la fonction afficheBonjour ().
41
Fonction avec une valeur retourne
Dfinition La valeur de retour
Une fonction peut retourner une valeur au programme appelant. Cette valeur est unique. Le retour de la valeur signifie larrt de la fonction.
Exemple : Ecrire une fonction qui permet de lire une note entre 0 et 20.
42
Fonction lireNote() : entier
Variables : note: entier Debut ecrire(Entrez une note : ) lire(note); // lutilisateur entre la note tant_que ((note<0) OU (note>20)) faire { ecrire (vous avez fait une erreur, essayez encore : ) message derreur affich lire(note); // on recommence la saisie } retourne(note) Fin
//
43
Fonctions rcursives Construire la solution dun problme en utilisant la solution du mme problme dans un contexte diffrent (plus simple). La suite des contextes doit tendre vers une solution directe (cas terminal). Les fonctions rcursives sont adaptes une certaine classe de problmes. Exemple : la factorielle
