M12

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.


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

.


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 :


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)


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.


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


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


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


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)








9: Ecrire (Janvier)




Sinon

Ecrire (Le numro saisi est incorrect)

Fin selon

Fin


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


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


13

Ecrire (Entrer la valeur de N :)

Lire (N)

S 0

i 1

Tant Que i


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


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.


16

Chapitre 4 : Les tableaux

A. Introduction


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


Var

A, B, C : entier

Dbut

A3

B10

CA+B

BA+B

AC

Fin


18


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


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 :


20

Exercice 1.6 :

Exercice 1.7 :

Exercice 1.8 :

Exercice 1.9 :

Exercice 1.10 :

Documents

M12