View
21
Download
0
Category
Preview:
Citation preview
Cours dAlgorithme
Introduction lAlgorithme Cours et exercices
2
Chapitre 01 : Les lments de base dun algorithme
A. Introduction 1. Notion dalgorithme :
Dans la vie courante, un algorithme peut prendre la forme :
Dune recette de cuisine.
Dun itinraire routier.
Dun mode demploi, etc.
Une recette de cuisine, par exemple, est un algorithme : partir des ingrdients, elle explique comment parvenir au plat. De mme, un itinraire routier explique comment, partir dune position initiale, rejoindre une position finale en un certain nombre dtapes.
2. Dfinition dun algorithme
Le mot Algorithme provient de la forme latine (Algorismus) du nom du nom du mathmaticien arabe AL KHWARIZMI ce dernier formula la premier dfinition : un algorithme est une squence doprations visant la rsolution dun problme en un temps fini
Nous pouvons adopter la dfinition suivante : un algorithme est la description de la mthode de rsolution dun problme quelconque en utilisant des instructions lmentaires. Ces instructions deviennent comprhensibles par lordinateur lors de la traduction de lalgorithme en un programme.
3. Algorithmique et programmation
Tout problme programmer doit tre rsolu, dabord sous forme dalgorithme, puis converti en programme dans le langage de votre choix. En effet, un algorithme est indpendant du langage de programmation utilis.
Un programme est un enchanement dinstruction, crit dans un langage de programmation, excutes par un ordinateur, permettant de traiter un problme et de renvoyer des rsultats. Il reprsente la traduction dun algorithme laide dun langage d programmation.
Le cycle de dveloppement dun programme informatique peut se rsumer ainsi :
Problme (analyse) Algorithme (programmation)Programme(excution)rsultats
B. Structure gnrale dun algorithme
Un algorithme est compos de trois parties principales
Lentte : cette partie sert donner un nom lalgorithme. Elle est prcde par le mot cl
Algorithme ;
La partie dclarative : dans cette partie, on dclare les diffrents objets que lalgorithme
utilise (constantes, variables, etc.) ;
Le corps de lalgorithme : cette partie contient les instructions de lalgorithme. Elle est
dlimite par les mots Dbut et Fin.
Introduction lAlgorithme Cours et exercices
3
Entte Algorithme Nom_Algorithme
Partie dclarative
Constante
Identifiant = valeur
Variable
Identifiant : Type
Corps de lalgorithme
Dbut
Instruction 1
Instruction 2
..
Instruction N
Fin
C. Les variables et les constantes 1. Notion de variable
Les donnes ainsi que les rsultats des calculs intermdiaires ou finaux, sont rangs dans des
cases de mmoires qui correspondent des variables.
Ainsi, une variable est range dans un emplacement mmoire nomm, de taille fixe (ou
non)prenant au cours de droulement de lalgorithme, un nombre indfini de valeurs diffrentes.
2. Dclaration des variables
La partie de dclaration consiste numrer toutes les variables dont on aura besoin au cours de
lalgorithme.
Chaque dclaration doit comporter le nom de la variable (identificateur) et sont type.
Syntaxe :
Var
Identificateur1 : Type
Identificateur2 : type
.
Introduction lAlgorithme Cours et exercices
4
Identificateur
Un identificateur est le nom donn une variable, une fonction, etc. Ce nom doit
obligatoirement commencer par une lettre suivi dune suite de lettre et chiffres et il ne doit pas
contenir despace ni des caractres spciaux.
Type de donnes
Le type dune variable est lensemble des valeurs quelle peut prendre. Par exemple une variable
logique (boolen) peut prendre les valeurs Vrai ou Faux.
Type entier : sert manipuler les nombres entiers positifs et ngatifs. Par exemple 5, 9, -3, etc.
Type rel : sert manipuler les nombres virgule. Par exemple : 3.14, 5, -3.12, etc.
Type caractre : permet de manipuler des caractres alphabtiques et numriques. Par exemple a, A, ?, 1, 2, etc.
Type chaine : sert manipuler des chanes de caractres permettant de reprsenter des mots ou des phrases. Par exemple bonjours, Monsieur, etc.
Type Boolen (logique) : utilise les expressions logiques. Il ny a que deux valeurs boolennes : Vrai et Faux.
Exemple :
Var
Surface : rel
A : entier
C : caractre
A, b, c, d : entier
Nom : chane
Absent : boolen
3. Les constantes
Comme une variable, une constante correspond un emplacement mmoire rserv auquel on accde
par le nom qui lui a t attribu, mais dont la valeur stock ne sera jamais modifie au cours du
programme.
Syntaxe :
Const.
Nom_de_la_constante=valeur
Exemple :
Introduction lAlgorithme Cours et exercices
5
Constante
Pi=3.14
D. Les instructions de base
Une instruction est une action lmentaire commandant la machine un calcul, ou une communication avec lun de ses priphriques dentres ou de sorties. Les instructions de base sont :
1. Linstruction de laffectation
Laffectation permet daffecter une valeur une variable. Elle est symbolis en algorithme par
Syntaxe :
Variable expression
Lexpression peut tre soit : Identificateur, constante, expression arithmtique ou logiques.
Smantique :
Une affectation peut tre dfinie en deux tapes :
Evaluation de lexpression qui se trouve dans la partie droite de laffectation ;
Placement de cette valeur dans la variable.
Exemple :
Algorithme Calcul
Variable
A, B, C, D: Entier
Dbut
A 10
B30
CA+B
DC*A
Fin
2. Linstruction dentre
Linstruction dentre ou de lecture donne la main lutilisateur pour saisir une donne au clavier. La
valeur saisie sera affecte une variable.
Syntaxe :
Lire (identificateur)
Exemple :
Lire(A)
Introduction lAlgorithme Cours et exercices
6
Linstruction lire(A) permet lutilisateur de saisir une valeur au clavier. Cette valeur sera affecte
la variable A.
Remarque :
Lorsque le programme rencontre cette instruction, lexcution sinterrompt et attend que
lutilisateur tape une valeur. Cette valeur et range en mmoire dans la variable dsigne.
3. Linstruction de sortie
Avant de lire une variable, il est conseill dcrire des libelles lcran afin de prvenir lutilisateur
de ce quil doit frapper (sinon, lutilisateur passe son temps se demander ce que lordinateur
attend de lui).
Linstruction de sortie (dcriture) permet dafficher des informations lcran.
Syntaxe :
Ecrire (expression)
Lexpression peut tre une valeur, un rsultat, un message, le contenu dune variable, etc.
Exemple 1 :
Ecrire(A)
Cette instruction permet dafficher lcran la valeur de la variable A.
Exemple 2 :
A2
Ecrire (La valeur de A est : , A)
La dernire instruction affiche lcran : La valeur de A est 2
Exercice : calcul PTTC
Ecrire un algorithme qui permet de saisir le prix HT (PHT) dun article et de calculer son prix total TTC
(PTTC). TVA = 20%.
Exercice : calcule de la surfirence dun cercle
Ecrire un algorithme qui permet de saisir le rayon R dun cercle puis de calculer et afficher son
suconfirance.
Introduction lAlgorithme Cours et exercices
7
Chapitre 2 : La structure alternative
A. Les structures alternatives 1. Introduction
Contrairement au traitement squentiel, la structure alternative ou conditionnelle permet dexcuter
ou non une srie dinstruction selon la valeur dune condition.
2. La structure si Alors. Sinon Fin Si
Syntaxe :
Si Condition Alors Instruction(s) 1
Sinon Instruction(s) 2
Fin si
Une condition est une expression logique ou une variable logique value Vrai ou Faux.
La condition est value, si elle est vraie, la srie dinstruction1 est excute et lensemble
dinstructions2 est ignor, la machine sautera directement la premire instruction situe aprs le
fin si.
De mme, au cas o la condition tait fausse (avait comme valeur Faux), la machine saute
directement la premire ligne aprs le Sinon et excute lensemble dinstructions2.
Exemple :
Ecrire un algorithme qui affiche si un nombre entier saisi au clavier est paire ou impaire
Solution :
Algorithme Parite
Var
N, R : entier
Dbut
Ecrire (Entrer la valeur de N : )
Lire(N)
R N mod 2
Si R=1 alors
Ecrire (N,est impaire ) ;
Sinon
Ecrire (N,est paire ) ;
Fin Si
Fin
Introduction lAlgorithme Cours et exercices
8
Remarque : prsentation de lalgorithme ou du programme
Certaines parties de lalgorithme ou du code sont en retrait par rapport dautres, cest ce quon
appelle lindentation. Celle-ci est trs importante pour la lisibilit de lalgorithme ou du programme.
Elle montre rapidement le dbut et la fin de chaque instruction alternative ou rptitive ainsi le
dbut et la fin de lalgorithme ou du programme.
Note : conditions composes
Certains problmes, exigent de formuler des conditions qui ne peuvent pas tre exprimes sous la
forme simple. Par exemple x est inclus dans lintervalle] 10, 20[ est compos de deux conditions
simple qui sont : x est suprieur 10 et x est infrieur 20 relies par loprateur ET
Exemple
Ecrire un algorithme qui teste si une note saisie au clavier est compris entre 0 et 20
Solution
Algorithme Teste_Note
Var
Note : rel
Message : chane
Dbut
Ecrire (Entrer la Note : )
Lire(Note)
Si Note >=0 et Note
Introduction lAlgorithme Cours et exercices
9
Une grande surface accord ces clients, une rduction de 2% pour les montants dachat suprieurs
1500,00 DH.
Ecrire un algorithme permettant de saisir le prix total HT (PTHT) et de calculer le montant TTC (PTTC)
en prenant compte la remise et la TVA=20%.
Solution :
Algorithme calcul_PTTC
Constant
TVA=0.2
Var
PTHT, PTTC : rel
Dbut
Ecrire (entrer le prix total hors taxe )
Lire (PTHT)
Si PTHT > 1500 alors
PTHT PTHT * 0.98
Fin si
PTTC PTHT *(1 + TVA)
Ecrire (Le prix TTC est : , PTTC)
Fin
C. Structure choix multiple
Cette structure conditionnelle permet de choisir le traitement effectuer en fonction de la valeur ou
de lintervalle de valeurs dune variable ou dune expression.
Syntaxe :
Selon Slecteur faire
Valeur 1 : action(s) 1
Valeur 2 : action(s) 2
..
Valeur N : action(s) N
Sinon
Action(s)
Fin Selon
Introduction lAlgorithme Cours et exercices
10
Lorsque lordinateur rencontre cette instruction, il vrifie la valeur de la variable de slection
(slecteur) et il la compare aux diffrentes valeurs.
Les valeurs sont values dans lordre, les unes aprs les autres, et ds quune de celle-ci est vrifie
laction associe est excute. On peut utiliser une instruction sinon (facultative), dont laction sera
excute si aucune des valeurs value na t remplie.
Exemple :
Ecrire un algorithme permettant safficher le mois en tout lette selon son numro saisi au clavier.
Solution :
Algorithme Mois
Var
N : entier
Dbut
Ecrire (donner le numro du mois )
Lire (N)
Selon N faire
1 : Ecrire (Janvier)
2 : Ecrire (Janvier)
3 : Ecrire (Janvier)
4 : Ecrire (Janvier)
5 : Ecrire (Janvier)
6 : Ecrire (Janvier)
7 : Ecrire (Janvier)
8 : Ecrire (Janvier)
9: Ecrire (Janvier)
10 : Ecrire (Janvier)
11 : Ecrire (Janvier)
12 : Ecrire (Janvier)
Sinon
Ecrire (Le numro saisi est incorrect)
Fin selon
Fin
Introduction lAlgorithme Cours et exercices
11
Chapitre 3 : La structure rptitive
A. Introduction
Prenons le cas dune saisie au clavier, par exemple, on pose une question laquelle lutilisateur doit
rpondre par O (oui) ou N (non).
Lutilisateur risque de taper autre chose (une autre lettre), le programme peut soit planter par une
erreur dexcution soit se drouler normalement jusquau bout, mais en produisant des rsultats
fantaisistes.
Pour remdier ce problme, on peut mettre en place un contrle de saisie pour vrifier que les
donnes entres au clavier correspondent bien celles attendues par lalgorithme.
On pourrait essayer avec un SI.
Algorithme Controle_de_saisie
Var
Rep : caractre
Dbut
Ecrire (voulez vous une copie de ce cours ? (O/N))
Lire (Rep)
Si Rep O ET r=Rep N alors
Ecrire (erreur de saisie. Recommencez )
Lire (Rep)
Fin Si
Fin
Lalgorithme ci-dessus rsout le problme si on se trompe dune seule fois, et on fait entrer une
valeur correcte la deuxime demande, sinon en cas de deuxime erreur, il faudrait rajouter un SI.
Et ainsi de suite, on peut rajouter des centaines de SI.
La solution ce problme consiste utiliser une structure rptitive.
Une structure rptitive, encore appele boucle, est utilise quand une instruction ou une liste
dinstruction, doit tre rpte plusieurs fois. La rptition est soumise une condition.
B. La boucle Tant Que.. Faire
La boucle Tant que permet de rpter un traitement tant que la condition est vraie.
Syntaxe :
Tant que Condition Faire
Instruction(s)
Fin Tant Que
Introduction lAlgorithme Cours et exercices
12
Lexcution de la boucle dpend de la valeur de la valeur de la condition. Si elle est vraie, le
programme excute les instructions qui suivent, jusqu ce quil rencontre la ligne Fin Tant Que. Il
retourne ensuite sur la ligne du Tant Que, procde au mme examen, et ainsi de suite.
La boucle ne sarrte que lorsque la condition prend la valeur fausse, et dans ce cas le programme
poursuit son excution aprs Fin Tant Que.
Exemple :
Algorithme Contrle_de_saisie
Var
Rep : caractre
Dbut
Ecrire (Voulez vous un copie de ce cours ? (O/N))
Lire (Rep)
Tant Que Rep O et Rep N faire
Ecrire (erreur de saisie)
Ecrire (Voulez vous un copie de ce cours ? (O/N))
Lire (Rep)
Fin Tant Que
Fin
Remarque :
tant donn que la condition est value avant la mise en ouvre des instructions, ce qui est
une scurit, il est possible que celles-ci ne soient jamais excutes.
Si une structure Tant Que dans la quelle la condition ne devient jamais fausse. Le programme
tourne dans une boucle infinie et nen sort plus.
Exemple : Boucle infinie
Dans lexemple ci-dessous nous avons une boucle infinie, lordinateurs ne sarrtera jamais dafficher
le message Bonjour car la variable I qui est teste dans la condition nest jamais incrmente :
I1
Tant Que I
Introduction lAlgorithme Cours et exercices
13
Ecrire (Entrer la valeur de N :)
Lire (N)
S 0
i 1
Tant Que i
Introduction lAlgorithme Cours et exercices
14
Pour modifier la valeur de lincrmentation, il suffit de rajouter le mot Pas et la valeur de ce
pas la boucle pour :
Pour compteur valeur initiale jusqu valeur finale pas valeur de Pas Faire
Instruction(s)
Suivant
Exercice :
Ecrire un algorithme qui permet de saisir un nombre entier et qui calcule la somme des entier pairs
jusqu ce nombre. Par exemple 0 + 2+4+6+8+10=30
Solution :
Algorithme Somme
Var
S, i, N : entier
Dbut
Ecrire (Entrer la valeur de N)
Lire (N)
S 0
Pour i 0 jusqu N pas 2 faire
S S + i
Suivant
Ecrire (la somme des nombre pairs est : , S)
Fin
D. La boucle Rpter. Jusqu
Cette boucle sert rpter une ou plusieurs instruction(s) jusqu ce quune condition soit vraie.
Remarque :
Cette boucle ne sutilise en gnral que pour des menus, elle est dangereuse car il ny a pas de
vrification de la condition avant dy entrer !
Syntaxe :
Rpter
Instruction (s)
Jusqu Condition
La liste dinstruction est excute, puis la condition est value, si elle est fausse, le corps de la
boucle est excut nouveau puis la condition est rvalue et si elle a la valeur vrai, le programme
sort de la boucle et excute linstruction qui suit Jusqu.
Exemple :
En utilisant la boucle rpterjusqu, crire un algorithme qui calcule la somme de N premiers
nombres entiers. On suppose que N est strictement positif
Introduction lAlgorithme Cours et exercices
15
Par exemple si N=6, le programme doit calculer : 1 + 2 + 3 + 4 + 5 + 6 =21
Solution :
Algorithme Somme
Var
S, i, N : entier
Dbut
Ecrire (entrer une valeur strictement positif : )
Lire (N)
S 0
I 1
Rpter
S S + i
i i +1
Jusqu i > N
Ecrire (la somme des , N, premiers entiers est : , S)
Fin
Remarque :
Les boucle Rpter et Tant Que sont utilises lorsquon ne sait pas au dpart combien
de fois il faudra excuter ces boucles.
A la diffrence de la boucle Tant Que, la boucle Rpter est excuter au moins une fois.
La condition darrt de la boucle Rpter est la ngation de la condition de poursuit de la
boucle Tant Que
On utilise la boucle Pour quand on connat le nombre ditrations lavance.
Introduction lAlgorithme Cours et exercices
16
Chapitre 4 : Les tableaux
A. Introduction
Introduction lAlgorithme Cours et exercices
17
Chapitre 5 : Exercices
1. Structure squentielles
Exercice 1.1 : donner les identificateurs des variables valables parmi la liste suivante :
Exercice 1.2 : Quelles seront les valeurs des variables aprs l'excution des instructions suivantes
Var
A, B: Entier
Dbut
A 1
B A+3
A3
Exercice 1.3 : Mme question pour l'Algorithme suivant
Var
A, B, C : Entier
Dbut
A5
B3
CA+B
A2
CB-A
Fin
Exercice 1.4 : Mme question pour l'algorithme suivant:
Var
A, B, C : entier
Dbut
A5
BA+4
AA+1
BA-4
Fin
Exercice 1.5 : Mme question pour l'algorithme suivant:
Var
A, B, C : entier
Dbut
A3
B10
CA+B
BA+B
AC
Fin
Introduction lAlgorithme Cours et exercices
18
Exercice 1.6 : Mme question pour l'algorithme suivant:
Var
A, B: entier
Dbut
A5
B2
AB
BA
Fin
Exercice 1.7 : Cet algorithme est destin prdire l'avenir, et il doit tre infaillible !
Il lira au clavier lheure et les minutes, et il affichera lheure quil sera une minute plus tard. Par exemple, si l'utilisateur tape 21 puis 32, l'algorithme doit rpondre :
"Dans une minute, il sera 21 heure(s) 33".
NB : on suppose que l'utilisateur entre une heure valide. Pas besoin donc de la vrifier.
Exercice 1.8 : Quel rsultat produit le programme suivant ?
Variables val, double numriques Dbut Val 231 Double Val * 2 Ecrire Val Ecrire Double Fin
Exercice 1.9 : Ecrire un programme qui permute et affiche les valeurs de trois variables A, B, C de type entier qui sont entres au clavier : A ==> B, B ==> C, C ==> A
Exercice 1.10 : Ecrire un Algorithme qui demande l'utilisateur le prix HT d'un article, le nombre
d'articles et le taux de TVA et qui Affiche le prix TTC.
Exercice 1.13 : Structure alternative
Exercice 1.1 : Un magasin de reprographie facture 0,10 E les dix premires photocopies, 0,09 E les
vingt suivantes et 0,08 E au-del. Ecrivez un algorithme qui demande lutilisateur le nombre de
photocopies effectues et qui affiche la facture correspondante.
Exercice 1.2 : Ecrire un Algorithme qui demande l'utilisateur l'ge d'un enfant ensuit il l'informe
de sa catgorie :
"Poussin" moins de 7ans
"Pupille" de 8 9ans
"Minime" de 10 11 ans
"Cadet" plus de 12ans
Introduction lAlgorithme Cours et exercices
19
Exercice 1.3 : Ecrire un Algorithme qui demande l'utilisateur un nombre et qui l'informe ensuit si ce nombre est positif ou ngatif.
Exercice 1.4 : Ecrire un Algorithme qui demande l'utilisateur trois noms et qui l'informe ensuit s'ils sont rangs dans l'ordre alphabtique
Exercice 1.5 :
Exercice 1.6 :
Exercice 1.7 :
Exercice 1.8 :
Exercice 1.9 :
Exercice 1.10 :
2. Structure itrative
Exercice 1.1 :
Exercice 1.2 :
Exercice 1.3 :
Exercice 1.4 :
Exercice 1.5 :
Exercice 1.6 :
Exercice 1.7 :
Exercice 1.8 :
Exercice 1.9 :
Exercice 1.10 :
3. Les tableaux
Exercice 1.1 :
Exercice 1.2 :
Exercice 1.3 :
Exercice 1.4 :
Exercice 1.5 :
Introduction lAlgorithme Cours et exercices
20
Exercice 1.6 :
Exercice 1.7 :
Exercice 1.8 :
Exercice 1.9 :
Exercice 1.10 :
Recommended