Algorithmique et Structures de Donnes

Lalgorithmique

- Lalgorithmique est un terme dorigine arabe.

- Le mot algorithme vient du nom du grand mathmaticien persan Al Khawarizmi, qui introduisit en Occident la numration dcimale.

Lalgorithmique
Quest ce quun algorithme Algorithmes et programmation Formaliser un algorithme

Complexit des algorithmes Langages de programmation (langage C)

Les algorithmes
Un algorithme est un ensemble de rgles logiques et chronologiques quon doit suivre pour aboutir la rsolution dun problme particulier. Ces rgles sont constitues dun nombre fini doprations lmentaires.
o Les oprations lmentaires (+, -, *, /, \) et (AND, OR, NON). Ces oprations seront excutes dans un ordre bien dtermin. Un algorithme peut tre assimil un raisonnement que lon peut traduire avec un langage que toute personne peut comprendre : o LDA : Langage de Description dAlgorithme

Les algorithmes
Le LDA nest pas un langage informatique. Le programme informatique est la traduction du LDA un autre langage comprhensible pour la machine (Pascal, Visual Basic, C, C++, C#, Java)

Lalgorithmique et la programmation
Raisonnement logique et chronologique
Langage traduisant la pense de manire comprhensible pour toute personne : Algorithme

LDA

Programme C, C++,

Langage traduisant le LDA de manire comprhensible pour lordinateur : Programme

Quest ce quun algorithme ?

Une suite dinstructions, qui une fois excute correctement, conduit un rsultat donn

Ouvrir un livre de recettes de cuisine,

Indiquer un chemin un touriste gar. chercher un mot dans le dictionnaire Rsoudre une quation de second degr

Quest ce quun algorithme ?

Pour fonctionner, un algorithme doit donc contenir uniquement des instructions comprhensibles par celui qui devra lexcuter.

En informatique les choses auxquelles ont doit donner des instructions sont les ordinateurs et donc on utilise les langages informatiques (Pascal, Visual basic, C, C++, .etc) pour leur dcrire ces instructions.

Pour quoi apprendre lalgorithmique ?

Par ce que lalgorithmique exprime les instructions rsolvant un problme donn indpendamment des particularits de tel ou tel langage.
Apprendre lalgorithmique, cest apprendre manier la structure logique dun programme informatique.

Exemple 1. rsoudre une quation de 1er degr

Rsoudre lquation ax+b = 0

Ecrire un plan dun algorithme permettant le calcul de la valeur de x.

Exemple 1. rsoudre une quation de 1er degr

Dbut algorithme Entres Sortie Traitement Retenir (saisir, lire) la valeur de a. Retenir (saisir, lire) la valeur de b.

Si a est gal zro il y aura pas de solution.

Sinon la valeur de x est obtenue en divisant -b par a. Afficher la valeur de x Fin algorithme

Mthode 1 : Recherche squentielle

Exemple 1. Recherche dun mot dans un Exemple 3: Plan de lalgorithme dictionnaire Recherche d'un mot dans un dictionnaire

a. b. c. d.

Dbut algorithme. Retenir (saisir, lire) le mot rechercher. Ouvrir le dictionnaire la premire page. Tant que le mot ne se trouve pas sur la page courante et la page courante n'est pas la dernire excuter l'tape e) sinon passer l'tape f). e. Passer la page suivante. f. Si le mot s'y trouve lire la dfinition sinon ce mot ne se trouve pas dans le dictionnaire. g. Fin de l'algorithme.

Exercice :

Exemple 1. Recherche dun mot dans un Exemple 3: Plan de lalgorithme dictionnaire Recherche d'un mot dans un dictionnaire

la mthode de recherche squentielle est-elle optimale ?

Donner un plan dalgorithme dune autre mthode de recherche plus rapide

Exemple 1. Recherche dun mot dans un Exemple 3: Plan de lalgorithme dictionnaire Recherche d'un mot dans un dictionnaire
a. Dbut algorithme. b. Retenir (saisir, lire) le mot rechercher. c. Ouvrir le dictionnaire la page du milieu. d. Tant que le mot ne se trouve pas sur la page courante et la page courante n'est pas la dernire excuter l'tape e) et f) sinon passer l'tape g). e. Si le mot se trouve dans la partie droite ouvre la page du milieu de cette partie f. Sinon ouvre la page du milieu de la partie gauche g. Si le mot s'y trouve lire la dfinition sinon ce mot ne se trouve pas dans le dictionnaire. h. Fin de l'algorithme.

Exemples
Conclusion Plusieurs algorithme peuvent donner le mme rsultats Evaluation des algorithmes en fonction du temps dexcution et de la mmoire utilise

Formaliser un algorithme

Deux types de utiliss pour reprsenter des algorithmes:

Reprsentation graphique = organigramme Pseudo - code

Organigramme Pseudo - code

Lire X; si X>=0 alors Y<-- X sinon

Y<-- -X fin si; Afficher Y;

* Structure dun
Dclaration du nom de lalgorithme

Algorithme
algorithme nom de lalgorithme const liste des constantes

Dclaration des constantes, des variables et des structures

var struct

liste des variables

liste des structures

Le corps de lalgorithme

dbut algorithme action 1 // commentaire 1 action 2 // commentaire 2 . . . action n // commentaire n fin algorithme

* Structure dun
Nom de lalgorithme :

Algorithme

o Il permet tout simplement didentifier un algorithme parmi dautres. Les dclarations : o Cest une liste exhaustive de variables utilises et manipules dans le corps de lalgorithme. Le corps de lalgorithme : o Dans cette partie de lalgorithme, sont places les tches excuter (instructions, oprations, ). Les commentaires : o Pour permettre une lecture plus aise et plus comprhensive de lalgorithme

* Les Dclarations
Les Constantes :
o Elles reprsentent des chiffres, des nombres, des caractres, des chanes de caractres, dont la valeur ne peut pas tre modifie au cours de lexcution de lalgorithme. Les Variables : o Elles peuvent stocker des chiffres des nombres, des caractres, des chanes de caractres, dont la valeur peut tre modifie au cours de lexcution de lalgorithme. Les Structures :

o Elles permettent de rassembler plusieurs variables ou constantes sous un mme identificateur, on parle galement dentits ou dobjets.

* Les Dclarations des variables et des

constantes
Les constantes et les variables sont dfinies dans la partie dclarative par deux caractristiques essentielles, savoir :

L identificateur :
o Il reprsente le nom de la variable, de la constante ou de la structure. Il est compos gnralement de lettres mais peut galement contenir et de chiffres. Il ne doit pas commencer par des chiffres Il ne doit pas contenir despaces, de caractres de ponctuation ou de caractres accentus.

* Les Dclarations des variables et des

constantes
Le type : o Il reprsente la nature de la variable ou de la constante (entier, rel, boolen, chane de caractres) Exemples :

o var age : rel o var adresse, ville : chaine o var nbr_enfants , etage : entier

* Les types de variables

De faon gnrale, pour toute variable cens contenir une ou plusieurs informations devant tres traites par le processeur, lordinateur doit lui rserver de la mmoire volatile (RAM). La taille mmoire ncessaire pour stocker cet objet dpend de la nature de linformation en question.
Exemple dinformations de base : Les nombres entiers : 0, -1, 45, 36, -10 en dcimal 45H, 0FBH, 64H en hexadcimal 10101111, 1011 en binaire Les nombres rels : -3.67, 4.2569, 564.0, 18.36 10e-6 Le caractre : a , A , * , 7 , z , ! , .

La chane de caractres "lectronique", "cd ROM de 80mn" ,

Le boolen : Il ne peut prendre que deux tats possibles : VRAI ou FAUX (True ou False)

* Les types de variables en langage C

Type de donne Signification Caractre Caractre non sign Entier court Taille (en octets) 1 1 2 Plage de valeurs accepte -128 127 0 255 -32 768 32 767
0 65 535

char unsigned char short int unsigned short int

int

Entier court non sign 2 2 (sur processeur 16 bits) 4 (sur processeur 32 bits) 2 (sur processeur 16 bits) 4 (sur processeur 32 bits) 4

Entier

-32 768 32 767 -2 147 483 648 2 147 483 647

0 65 535 0 4 294 967 295 -2 147 483 648 2 147 483 647 0 4 294 967 295 3.4*10-38 3.4*1038 1.7*10-308 1.7*10308 3.4*10-4932 3.4*104932

unsigned int long int

Entier non sign Entier long

unsigned long int Entier long non sign 4 float double long double
Flottant (rel) Flottant double Flottant double long 4 8 10

* Dclarations des variables

Algorithme (LDA) Var x, y : entiers Var a, b : rels Var z1, z2, z3 : caractres Langage C int x, y ; Float a, b ; Char z1, z2, z3 ;

* Les Oprateurs
Arithmtique Comparaison

Oprateur
Addition

Algo
+

C
+

Oprateur Suprieur stricte Infrieur stricte

Algo > <

C > <

Soustraction
Multiplication

Division
Modulo

/
MOD

/
% Pow()

Suprieur ou gal
Infrieur ou gal Egal Diffrent

>=
<= == !=

Division entire
Puissance

\
^

Logique
Oprateur Fonction ET Fonction OU Fonction OU Exclusif Algo ET OU OUX C && || ^^

Remarque: En C la division entire sobtient en convertissant la variable rel en entier

Fonction NON

NON

* Priorit des oprateurs usuels

Priorit croissante de bas vers le haut Oprateur algorithme Langage C

Oprateur de multiplication
Oprateur de division Oprateur d'addition Oprateur de soustraction Oprateur d'infriorit stricte Oprateur de supriorit stricte Oprateur d'infriorit ou d'galit Oprateur de supriorit ou d'galit Oprateur d'galit Oprateur d'ingalit Oprateur et logique ET Oprateur ou logique OU

*
/ + < > <= >= = <> ET OU

*
/ + < > <= >= == != && ||

Oprateur d'affectation

Loprateur Affectation
L'opration par laquelle on attribue une valeur une variable s'appelle affectation. Dans un algorithme (pseudo-code), l'instruction d'affectation se note avec le signe "" le signe " " se traduit dans les langage informatique par le signe " = " Le signe = est utilis dans certains langages la fois comme tant oprateur de comparaison mais aussi comme oprateur daffectation
Var X Y : entier X5 YX Var X Y : chaine X AB Y CD

Ordre des instructions

Lordre dans lequel les instructions sont crites va jouer un rle essentiel dans le rsultat final.

Variable A en Entier Dbut A 34 A 12 Fin

Variable A en Entier Dbut A 12 A 34 Fin

Valeur finale A=12

Valeur finale A=34

Structure fondamentale dun algorithme

Pseudo Code (LDA)
Algorithme principal Dbut main() { Langage C

var x, y en rels var p en rels Ecrire "Entrez la valeur de x: " Lire x (rserver une adresse en mmoires pour stocker
une valeur de type rel)

Ecrire "Entrez la valeur de y: " Lire y Px*y Ecrire "Le produit de x et y est: ", p Fin }

float x, y; float p; printf(" Entrez la valeur de x:"); scanf("%f", &x); printf(" Entrez la valeur de y:"); scanf("%f", &y); p=x*y; printf("Le produit de x et y est: %f", p); system("PAUSE");

Exercices
Exercice 1
Quelles seront les valeurs des variables A et B aprs excution des instructions suivantes ?

Var A, B : Entier Dbut A 1 B A + 5 A 10 Fin

A=10, B=6

Exercices
Exercice 2
Quelles seront les valeurs des variables A, B et C aprs excution des instructions suivantes ?

Variables A, B, C en Entier Dbut A 5 B 3 C A + B A 2 C B A + B Fin

A=2, B=3, C=4

Exercices
Exercice 3 Quelles seront les valeurs des variables A et B aprs excution des instructions suivantes ?

Variables A, B en Entier Dbut A 5 B A + 4 A A + 1 B A 7 B A B - 7 Fin

A=6, B=0

Exercices
Exercice 4 Quelles seront les valeurs des variables A, B et C aprs excution des instructions suivantes ?

Variables A, B, C en Entier Dbut A 3 B 10 C A + B B A + B A C Fin

A=13, B=13, C=13

Exercices
Exercice 5

Quelles seront les valeurs des variables A et B aprs excution des instructions suivantes ?

Variables A, B en Entier Dbut A 5 B 2 A B B A Fin

A=2, B=2

Exercices
Exercice 6
Ecrire un algorithme permettant dchanger les valeurs de deux variables A et B, et ce quel que soit leur contenu pralable.

Var A, B, K : entiers Lire (A) Lire (B) KA AB BK Ecrire(A, B)

Exercices
Exercice 7
Une variante du prcdent : on dispose de trois variables A, B et C. Ecrivez un algorithme transfrant B la valeur de A, C la valeur de B et A la valeur de C (toujours quels que soient les contenus pralables de ces variables). Var A, B, C, K : entiers Lire (A) Lire (B) Lire (C) KB BA AC CK Ecrire(A, B)

A B C

Structures de contrles
La structure linaire se caractrise par une suite dactions excuter dans lordre o elles sont nonces
Traitement 1 Traitement 2 Traitement 3 Traitement 4

Les structure de contrle

Permettent de contrler lexcution dune suite dinstructions o Structures de contrle alternatives o Structures de contrle rptitives

* Les structures Alternatives

Une structure alternative offre la possibilit de donner des issues diffrentes la poursuite dun algorithme. Ces issues sexcluent mutuellement. On peut rencontrer plusieurs formes de structures alternatives :

* Les structures Alternatives

Forme alternative rduite :
Contrle dun seul bloc dinstruction Dans cette structure, lexcution du traitement T2 ne dpend que la ralisation de la condition qui le prcde :
Traitement 1 si la condition nest pas vrifie les traitements se font dans cet ordre : (T1 T3).

si la condition est Si Vrai vrifie les traitements Condition se font dans cet ordre : Si Faux (T1 T2 T3). Traitement 2

Traitement 3

* Les structures Alternatives

Forme alternative complte : Contrle de plusieurs bloc dinstruction Dans cette structure, lexcution de lun des deux traitements distincts possibles T2 et T3 ne dpend que la ralisation de la condition qui les prcde :
Traitement 1 Si Vrai si la condition est vrifie les traitements se font dans cet ordre : (T1 T2 T4). Condition Traitement 2 Traitement 3 Si Faux si la condition nest pas vrifie les traitements se font dans cet ordre : (T1 T3 T4).

Traitement 4

* Les structures Alternatives

Forme rduite

La structure SI ... ALORS.FIN SI

Pseudo - Code SI <condition> ALORS [<bloc d'actions-1>] FIN SI Langage C IF ( <condition> ) {

[<bloc d'actions-1>]
} [<bloc d'actions-2>]

[<bloc d'actions-2>]

Le bloc dactions 1 est excut seulement au cas o la condition prend la valeur Vrai. Dans le cas contraire le programme passe directement le bloc 2 . Avec cette structure on ne peut contrler quun seul bloc daction

* Les structures Alternatives

Forme complte

La structure SI ... ALORSSINON.FIN SI

Pseudo - Code Langage C IF ( <condition> ) { [<bloc d'actions 1>] } ELSE { [<bloc d'actions 2>] }

SI <condition> ALORS
[<bloc d'actions 1>] SINON [<bloc d'actions 2>] FIN SI [<bloc d'actions 3>]

Au cas o la condition est vraie seul le bloc d'instruction-1 est excut. Dans le cas contraire seul le bloc d'instructions-2 est excut. Avec cette structure on peut contrler plusieurs bloc daction

* Les structures Alternatives

Action 0 SI <condition> ALORS

Action 0
SI <condition> ALORS Action 1 Action 2 SINON Action 3 FIN SI Action 4 . .

Action 1
Action 2 FIN SI Action 3 . . . . .

* Les structures Alternatives

* Les structures Alternatives

Si Cond 1 Vrai T1 Vrai T2 TAT2TB TAT1TB

TA

Faux Si Cond 2

Faux

Si Cond n Faux
Aucune Cond

Vrai Tn

TATnTB

T n+1

TATn+1TB

TB

* Les structures Alternatives

Si <condition1> Alors Traitement 1; Sinon Si <condition2> Alors Traitement 2; Sinon Si <condition3> Alors Traitement 3; Sinon Si <condition4> Alors Traitement 4; Sinon Traitement 5; Fin Si Fin Si Fin Si Fin Si

Si <condition1> Alors Traitement 1; Sinon Si <condition2> Alors Traitement 2; Sinon Si <condition3> Alors Traitement 3; Sinon Si <condition4> Alors Traitement 4; Sinon Traitement 5; Fin Si

* Les structures Alternatives

Forme alternative : (Cas des conditions non disjointes)

contrle deux traitements (T et T) dans ce cas on va combiner les conditions Ci avec les oprateurs logiques (AND, OR, XOR). Exemple : Si C1 AND C2 . AND Cn Alors Traitement (T) Sinon Traitement (T) Fin Si
C1 0 0 0 0 1 1 1 C2 0 0 1 1 0 0 1 C3 0 1 0 1 0 1 0 T T T T T T T T

* Les structures Alternatives

Forme alternative multiple : (Cas des conditions non disjointes)

Contrle de plusieurs traitements dans ce cas on va imbriquer les structures alternatives. Exemple :
C1 0 C2 0 C3 0 T T1

0
0 0 1

0
1 1 0

1
0 1 0

T1
T1 T1 T2

1
1 1

0
1 1

1
0 1

T2
T3 T3

* Les structures Alternatives

Si C1 TA
Vrai
Si Cond 2 Si C2

Vrai Vrai

Faux

Si C3
Faux
Faux

Si Cn
Aucune Cond

Vrai

Faux

Tn
T n+1

Tn T3

T2 TB T1

* Les structures Alternatives

Si <condition1> Alors Si <condition2> Alors Si <condition3> Alors . . Si <condition(n)> Alors Traitement n Sinon Traitement n Fin si . . Sinon Traitement 3 Fin Si Sinon Traitement 2 Sinon Traitement 1 Fin Si

Tn : Si C1 AND C2 AND AND Cn

Exemple 1
Var X, Y : rels X5 Y7 YY2 Si X > Y Alors XY+X Sinon XYX YY+X Fin Si Afficher X, Y Fin Var X, Y, Z : rels X3 Y5 Z9 Si X > Y OR Y > Z Alors X Y 2*X Sinon XYX YY+X Fin Si Afficher X, Y, Z Fin X=2 Y=7 Z=9

X=0 Y=5

Exemple 2
Elaborer un algorithme pour calculer le montant hors taxe et le montant TTC pour un produit donn. Le prix unitaire, la quantit et le taux TVA sont fournis en entre. Une rduction de 10% est applique si le montant hors taxe est suprieur 1000 Dh,

Exemple 2
Var PU, Q, TVA : rels Var MHT, MTTC : rels Ecrire ( donner le prix unitaire ) Lire(PU) Ecrire ( donner la quantit) Lire(Q) MHT PU*Q Si MHT>1000 Alors MHT MHT*(1-0.1) Fin si MTTC MHT*(1+TVA) Ecrire( le prix hors taxe est: , MHT) Ecrire( le prix toutes taxes compris est: , MTTC)

Exemple 3
Elaborer un algorithme pour calculer le montant hors taxe et le montant TTC pour un produit donn. Le prix unitaire, la quantit et le taux TVA sont fournis en entre. Une rduction de 10% est applique si le montant hors taxe est infrieur 1000 Dh, une rduction de 20% si le montant est compris entre 1000 et 2000 et une rduction de 30% si le montant est suprieur 2000.

Var PU, Q, TVA : rels Var MHT, MTTC : rels Ecrire ( donner le prix unitaire ) Lire(PU) Ecrire ( donner la quantit) Lire(Q) MHT PU*Q Si (MHT < 1000) Alors MHT MHT*(1-10%) Sinon Si (MHT < 2000) Alors MHT MHT*(1-20%) Sinon MHT MHT*(1-30%) FinSi FinSi PTTC MHT*(1+TVA) Ecrire( le prix hors taxe est: , PHT) Ecrire( le prix toutes taxes compris est: , PTTC)

Exemple 3

Exemple 4
Ecrire lalgorithme permettant la rsolution de lquation ax+b=c (quelque soit la valeur de a)

Var a, b, c : entiers Var x : rel Lire (a, b, c) Si (a=0) alors Ecrire (impossible ) Sinon X (c-b)/a Ecrire(x) Fin si Fin

Exemple 5
Ecrire lalgorithme permettant la rsolution de lquation ax2+bx+c=0 (quelque soit les valeurs de a, b#0 et c#0)
Var a, b, c : entiers Var x1, x2, D : rels Lire (a, b, c) D b^2 4*a*c Si (a=0) alors Ecrire(la solution est: , -c/b) Sinon si (D>0) alors Ecrire(les solutions sont: , (-b+sqrt(D))/(2*a), (-b-sqrt(D))/(2*a)) Sinon si(D=0) alors Ecrire(la solution est: , -b/(2*a)) sinon Ecrire ( pas de solution dans IR ) FinSi Fin

Exemple 5
Var a, b, c : entiers Var x1, x2, D : rels Lire (a, b, c) Si (a=0) alors Ecrire(la solution est: , -c/b) Sinon D b^2 4*a*c si (D>0) alors Ecrire(les solutions sont: , (-b+sqrt(D))/(2*a), (-b-sqrt(D))/(2*a)) Sinon si(D=0) alors Ecrire(la solution est: , -b/(2*a)) sinon Ecrire ( pas de solution dans IR ) FinSi FinSi FinSi Fin

Exemple 5
Var a, b, c : entiers Var D : rels Lire (a, b, c) Si (a<>0) alors D b^2 4*a*c Si (D>0) alors Ecrire(les solutions sont: , (-b+sqrt(D))/(2*a), (-b-sqrt(D))/(2*a)) Sinonsi(D=0) alors Ecrire(la solution est: , -b/(2*a)) sinon Ecrire ( pas de solution dans R ) FinSi Sinon Ecrire(la solution est: , -b/c) Fin Si

Si (a=0) AND (b=0) AND (c=0)

Si (a=0) AND (b=0) AND (c#0) Si (a=0) AND (b#0) Si (a#0)

alors la solution est IR

alors impossible alors x1 -c/b alors calcul de Delta

Var a, b, c : entiers Var x1, x2, D : rels Lire (a, b, c) Si (a=0) alors Si (b=0) alors Si (c=0) alors Ecrire(la solution est IR ) Sinon Ecrire(impossible) Finsi Sinon x1 -c/b Ecrire(la solution est :, x1) Finsi Sinon D b^2 4*a*c si (D>0) alors Ecrire(les solutions sont: , (-b+sqrt(D))/(2*a), (-b-sqrt(D))/(2*a)) Sinon si(D=0) alors Ecrire(la solution est: , -b/(2*a)) sinon Ecrire ( pas de solution dans IR ) FinSi FinSi FinSi Fin

Structures de contrle itratives

Les structures itratives permettent de rpter lexcution dun ensemble dinstructions une ou plusieurs fois.
Ces structures sont regroupes sous deux grandes familles selon si : le nombre de rptitions est connu ou pas. Nombre connu de rptitions Nombre inconnu de rptitions

Structures de contrle itratives

Cas ou le nombre de rptition est connu :
Pour.allant.suivant
Dans cette structure, la sortie de la boucle ditration seffectue lorsque le nombre souhait de rptition est atteint. On utilise donc une variable ditrations caractrise par :

sa valeur initiale, sa valeur finale, son pas de variation.

Structures de contrle itratives

Cas ou le nombre de rptition est connu :
Pour.allant.suivant
Faire la somme de N valeurs
Var V, S entiers S0 Lire (V) SS+V Lire (V) SS+V Lire (V) SS+V Lire (V) SS+V . . . Afficher (S) Var V, S, N,i entiers S0 Lire (N) Pour i 1 N Lire (V) SS+V Suivant i Afficher (S)

Structures de contrle itratives

Pour.allant.suivant

Si la valeur finale de lindice est infrieure sa valeur initiale le pas de variation est ngatif, la structure est dite dcroissant dans le cas contraire, le pas est positif et la structure est dite croissant
i0 < i f

Pour i i0 if . . Suivant i

Pour i if i0 . . Suivant i

Structures de contrle itratives

Pour.allant.suivant
Pseudo - code
Pour i Vi Vf [pas p] [<bloc dactions >] Suivant i

Language C
for(i = Vi ; i <= Vf ; i = i + 1) { [<bloc dactions >] }

Le bloc d'instructions est excut un nombre de fois connu lavance contrl par un compteur allant de la valeur Vi (valeur initiale) la valeur Vf(valeur finale). Attention : le traitement ne doit pas modifier la variable de boucle (compteur)

Structures de contrle itratives

Exemples
Pseudo - code Var i, S, var : entiers S0 Pour i allant de 0 3 Afficher ("var =" ) Lire (var) S S + var Suivant i Afficher("La somme est :", S) Afficher(i)

Pour.allant.suivant
Language C int i, S, var; S = 0; for (i=0; i<=3; i++) { printf("var ="); scanf("%d",&var); S = S + var; } printf("la somme est :%d", S);

Cet algorithme fait la somme dun certain nbre de valeurs saisies)

Structures de contrle itratives

Exemples
var S : entier var i : entier
i=0 S 0; Pour i allant de 0 3 lire (var) S=S+var suivant i Ecrire (la valeur de S est , S) Fin i=1 i=2

Pour.allant.suivant
SIMULATION

var=2 var=-3 Var=4

S=0+2 S=2-3 S=-1+4

2 -1 3

i=3
i=4

Var=-8

S=3-8

-5

Arrt des itrations

EN MEMOIRE i=4 S = -5

Structures de contrle itratives

Exemples
var A,B,C : entiers A 6 B 4 C -2 Pour i 1 5 si A > B alors A=A+C B=C sinon B=BC C=B FinSi Suivant i Ecrire (A=, A) Ecrire (B=, B) Ecrire (C=, C)

Pour.allant.suivant

A=6; B=4; C=-2 itration Test logique (A>B) A=6 B=4 C=-2

i=1
i=2

Vrai
Vrai

6-2= 4
4-2 = 2

-2
-2

-2
-2

i=3
i=4 i=5

Vrai
Vrai Faux

2-2 = 0
0-2 = -2 -2

-2
-2 -2+2 = 0

-2
-2 0

En mmoire
i=6 A=-2 B=0 C=0

Structures de contrle itratives

Exemples

Pour.allant.suivant

Ecrire un algo qui permet de calculer la somme suivante: S = 1 1/2 + 1/3 1/4 + 1/5 + + (-1)n+1/n
Var Nmax, S : rels Var n : entier Ecrire (donner le nbe des termes) Lire (Nmax) S0 Pour n 1 Nmax S = S + (-1) ^ (n + 1) / n Suivant n Ecrire(S =, S) Fin

Structures de contrle itratives

Pour.allant.suivant Cas des boucles imbriques
Pseudo - code Pour i allant de Vi Vf [pas p] Pour j allant de Wi Wf [pas p] [<bloc dactions >] Suivant j Suivant i Visual Basic for(i = Vi ; i <= Vf ; i = i + 1) { for(j = Vi ; j <= Vf ; j = j + 1) { [<bloc dactions >] } }

Structures de contrle itratives

Exemples
var S : rel var j : entier
i=1 S 0; Pour i allant de 1 3 Pour j allant de 1 2 S=S+i+j suivant j Suivant i Ecrire (la somme est , S) Fin i=2

Pour.allant.suivant

j=1 S=0+1+1=2 S=5+2+1=8

j=2 S=2+1+2=5 S=8+2+2=12

j=3

i=3
i=4

S=12+3+1=16

S=16+3+2=21

Arrt des itrations

EN MEMOIRE i=4 S = 21 j=3

Structures de contrle itratives

Cas ou le nombre de rptition est inconnu :
Tant que . faire

Dans cette structure, la sortie de la boucle ditration seffectue lorsquune condition nest plus vrifie.
Tant que la condition est vrifie on rpte lexcution du bloc dinstruction contrl Le nombre des itrations est donn aprs la sortie de la boucle

Structures de contrle itratives

Tant que . faire
Pseudo - code
i Vi Tant que <condition> faire [<bloc dactions >] i i+1 Fin tant que

Langage C
i i0 While <condition> { [<bloc dactions >] i i+1 }

Dans ce cas la vrification de la condition se fait avant lexcution du bloc dinstruction

Le bloc dinstruction peut ne jamais tre excut

Structures de contrle itratives

Exemples Tant que . faire
Cet algorithme fait la somme des valeurs saisies, arrt lorsque var = -1) Pseudo - code Var S, var i0 S0 Afficher ("var =" ) Lire (var) Tant que (var < > -1) faire S S + var Afficher ("var =" ) Lire (var) ii+1 Fin tant que Afficher("La somme est :", S) Afficher("Le nombre de valeur est :", i) Language C int S, var; i = 0; S = 0; printf("var ="); scanf("%d",&var); while (var!=-1) { S = S + var; printf("var ="); scanf("%d",&var); i = i + 1; } printf("la somme est :%d",S); printf("le nbre de valeur est :%d",S);

Structures de contrle itratives

Tant que . faire
var S : entier var i : entier i 1; S 0; lire (var) tant que (var <> -1) faire S S+var lire (var) ii+1 fin tant que Afficher (la valeur de S est , S) Afficher (le nbre de valeur est , i-1)
SIMULATION

var=2 var=-3 Var=4

i=1 i=2 i=3

S=0+2 S=2-3 S=-1+4

2 -1 3

Var=-8
Var=-1

i=4
i=5

S=3-8

-5

Arrt des itrations

EN MEMOIRE i=5 S = -5

Comparaison boucles pour et tant que Implicitement, linstruction pour: initialise un compteur incrmente le compteur chaque pas vrifie que le compteur ne dpasse pas la borne suprieure

Explicitement, linstruction tant que il faut

initialiser un compteur {amorage} incrmenter le compteur chaque pas {relance} vrifier que le compteur ne dpasse pas la borne suprieure {test de boucle}

Structures de contrle itratives

Cas ou le nombre de rptition est inconnu :
Rpter ..Tant que

Dans cette structure, la sortie de la boucle ditration seffectue lorsquune condition nest plus vrifie.
Tant que la condition est vrifie on rpte lexcution du bloc dinstruction contrl Le nombre des itrations est donn aprs la sortie de la boucle

Structures de contrle itratives

Rpter .tant que
Pseudo - code i Vi Rpter [<bloc dactions >] i i+1 Tant que <condition> Visual Basic i=i0 do { [<bloc dactions >] i=i+1 } while ([condition]);

Dans ce cas la vrification de la condition se fait aprs lexcution du bloc dinstruction

Le bloc dinstruction sexcute au moins une fois

Structures de contrle itratives

Exemples
Pseudo - code
Var S, var i0 S0 Rpter Afficher ("var =" ) Lire (var) S S + var ii+1 Tant que (S <1000) Afficher("La somme est :", S) Afficher("Le nombre de valeur est :", i)

Rpter .tant que

Language C
int S, i, var; i = 0; S = 0; do { printf("var ="); scanf("%d",&var); S = S + var; i = i + 1; } while (var!=-1); printf("la somme est :%d",S); printf("le nbre de valeur est :%d",i);

Cet algorithme fait la somme des valeurs saisies, arrt la lecture de -1)

Comparaison boucles rpter et tant que

boucle tant que condition vrifie avant chaque excution du traitement le traitement peut donc ne pas tre excut la condition porte surtout sur la saisie de nouvelles variables (relance) boucle rpter tant que condition vrifie aprs chaque excution du traitement le traitement est excut au moins une fois la condition porte surtout sur le rsultat du traitement Remarque: la boucle rpter est typique pour les saisies avec vrification.

Choisir pour... tant que rpter

Boucle Tant que

Traitement excut au moins une fois Nombre ditration connu ?

Boucle Rpter

Boucle Pour

Lalgorithme du Max et du Min

Trouver la max dun certain nombre connu de valeur Var x, Max, Nmax : entiers Nmax=0 Ecrire( saisir la 1re valeur) Lire (x) Max X Pour i=1 4 Ecrire( saisir la valeur , i) Lire (x) si X>Max alors Max x Nmax=0 FinSi si Max = X alors Nmax=Nmax+1 Fin si Suivant i Ecrire( la valeur Max est : , Max) Ecrire( le nbre des Max est : , Nmax) Var x, Min, Nmin : entiers Nmin=0 Ecrire ( saisir la valeur , 1) Lire (x) Min X i2 Tant que (x >=0) faire si x<Min alors Min x Nmin=0 FinSi si Min = X alors Nmin=Nmin+1 Fin si Ecrire( saisir la valeur , i) Lire (x) i i+1 Fin tan que Ecrire( la valeur Min est ; , Min) Ecrire( le nbre des Min est : , Nmin)

Trouver la max et le min dun certain nombre inconnu de valeur. La saisie sarrte lorsquon saisie une valeur gale zro

Lalgorithme du Max et du Min

Var x, Max, Min : rels Ecrire ( donner la 1re la valeur ) lire (X) Max X i=2 Tantque (X<>0) si (X >= Max) alors Max X FinSi FinSi Ecrire ( donner la valeur , i) lire (X) i i+1 Ecrire( la plus grande valeur est: , Max)

Les tableaux
Ensemble de donnes du mme type Exemple de problme : Saisir une suite de nombres, puis afficher cette suite aprs avoir divis tous les nombres par la valeur maximale de la suite. Ncessit de conserver les nombres en mmoire
Variable contenant une valeur var 132 Variable contenant plusieurs valeurs var 132 52 -45 78 345 -543 54 23

Les tableaux
Nom de la variable 0 1 3 2 4 3 -56 4 -8 valeurs indice 12

Tab

les "cases" sont numrotes partir de zro, autrement dit que le plus petit indice est zro. Lors de la dclaration d'un tableau, on prcise la plus grande valeur de l'indice diffrente, donc, du nombre de cases du tableau, si on veut 12 emplacements, le plus grand indice sera 11).

Les tableaux
Syntaxe:
tableau Tab (19) : entiers Pour i = 0 19 Ecrire ( donner la valeur , i) Lire (Tab(i)) Suivant i Syntaxe:

Var Tab : entiers Pour i = 0 19 Ecrire ( donner la valeur , i) Lire (Tab) Suivant i

Mmoriser les 20 valeurs

Mmoriser une seule valeur

Les Tableaux
Exemple de problme : Saisir une suite de nombres, puis afficher cette suite aprs avoir divis tous les nombres par la valeur maximale de la suite. Tab T(4) entier
Var Max entier Ecrire( donner la 1re valeur ) Lire (T(0)) Max T(0) Pour i = 1 4 Ecrire( donner les valeur , i) Lire (T(i)) Si (T(i) > Max) alors Max T(i) Fin si Suivant i Ecrire ( les nouvelles valeurs sont: ) Pour i = 0 4 Ecrire T(i)/Max)

Les tableaux Dynamiques

Il arrive frquemment que lon ne connaisse pas lavance le nombre dlments que devra comporter un tableau.

- On dclare un tableau avec une dimension maximale - Inconvnient : on peut tre sr du nombre dlment - Consommation de la mmoire - On dclare un tableau dynamique - dclarer le tableau sans prciser au dpart sa dimension - au cours du programme, on va fixer la dim via une instruction de redimensionnement : Redim.

Les Tableaux Dynamiques

Tableau Notes() en Numrique Variable nb en Numrique Dbut Ecrire "Combien y a-t-il de notes saisir ?" Lire nb Redim Notes(nb-1) .. .. .. Fin

Exercice: Donner un algorithme qui stocke n notes dans un tableau de valeur et calcule et affiche la moyenne. Lutilisateur peut saisir un nombre n de note. Note() : rels Var S, Moy : rel Var i, n : entier Dbut Ercire( donner le nombre de note ) Lire(n) Redim(Note(n-1)) S 0 Pour i 0 n-1 Ecrire( donner la note , i+1) lire(Note(i)) SS+Note(i) Suivant i Moy S/n Ecrire( la moyenne est : , Moy)

Les fonctions & les procdures

On peut dans une application procder aux mmes traitements, ou des traitements similaires, plusieurs endroits de son droulement. Ces traitements vont tre crite dans des algorithmes part Fonctions procdures
Dans lalgorithme principale on peut appeler plusieurs fois une fonction ou une procdure

Une fonction ou une procdure peut elle-mme appeler une ou plusieurs fonctions et procdures.

Les fonctions & les procdures

Structuration

Diviser pour mieux rgner

Les fonctions et les procdures permettent de dcomposer un programme complexe en une srie de sous-programmes plus simples, lesquels peuvent leur tour tre dcomposs eux-mmes en fragments plus petits, et ainsi de suite.

Intrts Les fonctions & les procdures

Regrouper un ensemble dinstruction dans le mme algorithme afin de pouvoir y faire appel autant de fois que ncessaire. Lisibilit et identification des erreurs, rutilisation Il est inutile de connatre comment est dfinie une fonction ou une procdure pour y faire appel. Par contre il est ncessaire de connatre sa dclaration (son manuel dutilisation): Quel est son rle? Quels sont les arguments fournir? Quelles est la valeur retourne?

Les fonctions & les procdures

Les procdures et fonctions peuvent ncessiter ventuellement un ou plusieurs paramtres dentre ou de sortie. Un paramtre dentre est la rfrence une variable manipule par la procdure ou la fonction. Dans ce cas la valeur dune variable du programme principal est copie dans ce paramtre. Un paramtre de sortie est une variable dont la valeur est affecter par les instructions du sous-programme

Les fonctions
Les fonctions sont des sous-programmes admettant des paramtres et retournant un seul rsultat (comme les fonctions mathmatiques y=f(x,y,. . .)) les paramtres sont en nombre fixe (n>0) une fonction possde un seul type, qui est le type de la valeur retourne la valeur de retour est spcifie par l'instruction retourner (renvoyer) Gnralement le nom dune fonction doit tre explicite: Maximum() Minimum()

Les fonctions
Syntaxe: Exemple Fonction (a : entier, b : chaine: ) : rel Dbut Var .., res en rel .. .. Renvoi res Fin

Les fonctions
Exemple : fonction qui renvoi le maximum de deux variables a et b (paramtres dentrs).

Max(a: rel, b: rel) : rel Dbut Var res : rel Res a Si (a<b) alors Res b Fin si Renvoi (res) Fin

Var x, y : rel Ecrire(x=) Lire(x) Ecrire(y=) Lire(y) T Max(x, y) Ecrire( le maximum est: , T)

Les Procdures
Les procdures sont des sous-programmes qui ne retournent aucun rsultat Par contre elles admettent des paramtres dentrs, de sorties ou dentrs/sorties: Gnralement le nom d'une procdure est explicite (verbe)

Syntaxe: Exemple

Procdure (Entier: E a, chaine: S b, rel : E/S c) Dbut Var .. en rel .. .. Fin

Les Procdures
Max(a: rel, b: rel) : rel Dbut Var res1 : rel Res1 a Si (b<a) alors Res1 b Fin si Renvoi (res1) Fin Min(a: rel, b: rel) : rel Dbut Var res2 : rel Re2s a Si (b<a) alors Res2 b Fin si Renvoi (res2) Fin

Procdure MaxMin(E a,b : entier , S M, m : entier) Dbut M Max(a, b) m Min(a, b) Afficher (M, m) Fin

Fonction & procdure

x
Paramtres

y z t

Fonction
Maximum

Max

Valeur renvoye

Paramtres

x y z t

Procdure
Tri

Les fonctions
0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. Entier: terme (entier: rang, entier: raison, entier: terme0) Dbut var val : entier val terme0 + raison*rang Renvoi val Fin Dbut Var n, U0, U, r : entier Ecrire( premier terme ?) Lire(U0) Ecrire( raison ?) Lire(r) Ecrire( les termes U0, U1, U10 sont: ) Pour n=1 10 U terme(n, r, U0) Ecrire(U) Ecrire( ) Suivant n Fin

Paramtres dune fonction

Dans sa dclarations ils sont appels paramtres formels
Au sein dun appel, ils sont appels paramtres effectifs chaque paramtre formel correspond un paramtre effectif, de mme type Le nom dun paramtres effectif peut tre diffrents de celui du paramtre formel associ. Dans l criture des paramtres effectifs On doit respecter le mme ordre des paramtres formels

Les fonctions Exemple de dclaration dune fonction

Moyenne(rel: A, rel: B): rel Dbut Var Moy : rel Moy (A+B)/2 dlivre (Moy) Fin
Exemple dappelle dune fonction

Algorithme principale dbut Var x, y: rel lire(x) Lire(y) Ecrire("Moy =" , Moyenne(x,y)) Fin

Mme exemple en C
Exemple de dclaration dune fonction

float Moyenne(float X, float Y) { float Moy; Moy = (X+Y)/2; return (Moy) ; }

Exemple dappelle dune fonction

main() { float x, y ; scanf("%f", &x); scanf("%f", &y); printf("Moy = %.2f",Moyenne (x, y)) ; system("pause"); return 0; }

Exercice Ecrire une fonction Maximum(T, n) qui permet de trouver le maximum dun tableau dun certain nombre de valeurs.
Maximum(T(): rel, n :entier) Var Max : rel Var i : entier Max T(0) Pour i 1 n-1 si(T(i)>Max) alors Max T(i) Fin si Suivant i Renvoyer(Max) Tableau V() : rels Var M : rel Var N, k : entiers Dbut Ecrire(N=) Lire (N) Redim(V(N-1)) Pour k 0 N-1 Ecrire( donner la valeur , k) lire(V(k)) Suivant k M maximum(V, N) Ecrire( le max est : , M)

Exercice

Ecrire une procdure permute(a, b) qui permute les valeurs de ceux variables entiers. Ecrire une autre procdure Tri (x, y, z) qui tri dans lordre croissant en appelant la procdure permute(a, b). Ecrire un algorithme dessai.

Exercice
Permuter (a : entier, b: entier) Dbut Var k : entier Ka ab bk Fin Trier (x: entier, y : entier, z : entier) Dbut Si (x<y) alors Permuter(x, y) Fin si Si (y<z) alors Permuter(y, z) Fin si Si (x<y) alors Permuter(x, y) Fin si Fin

Var w1, w2, w3 : entiers Ecrire( donner les 3 valeurs ) Lire (w1, w2, w3) Trier(w1, w2, w3) Ecrire(les valeurs tries sont: , w1, w2, w3)

Exercice
Crer une fonction max2(a, b) qui renvoi le maximum de deux variables: Crer une fonction VMAX(T) qui permet trouver le maximum des lments dun vecteur de 4 valeurs et ceci en appelant la fonction max2(). Crer un algorithme dessai.

Max2(a: rel, b: rel) : rel Ddut Var k : rel K a Si (b>a) alors Kb Finsi Renvoyer (k)

VMAX(T(3)): rel Dbut Var M :rel MMax2(Max2(Max2(T(0), T(1)),T(2)),T(3)) Renvoyer (M) Tableau V(3) :rel Var k : entier Pour k 0 3 Ecrire( donner la valeur, k) Lire V(k) Suivant k Ecrire( la maximum est: , VMAX(V))

Processus danalyse
La dcomposition en sous traitement Le processus danalyse permet de dcomposer un traitement complexe en sous traitement plus simples mais diffrent du prcdent. leur tour, ces sous problmes seront leur tour dcomposs jusqu un niveau dopration lmentaires faciles raliser.

Processus danalyse
La dcomposition rcursive Dans certain cas, le sous traitement est une illustration du problme initial, mais pour un cas plus simple . Par consquent, la solution du problme sexprime par rapport elle-mme! On appelle se phnomne rcursivit.

Dans un raisonnement par rcurrences : pour rsoudre un problme complexe on appelle le mme traitement initial mais avec un cas plus simple.

Traitement complexe Sous Traitement 1 Sous traitement 2 Traitement lmentaire

Raisonnement par rcurrence

Exemple de Rcursivit la factoriel de n est : 1*2*3..*n Mais n! = 1*2*..*(n-1)*n n! = n*(n-1)! Pour calculer la valeur de n!, il suffit donc de savoir calculer (n-1)! Et ensuite de multiplier cette valeur par n. Le sous problme du calcul (n-1)! Est le mme problme initial, mais pour un cas plus simple car (n-1 < n)

*
Raisonnement par rcurrence Soit une proprit P sur telle que P(0) est vraie et l'implication P(n) P(n+1). Alors P(n) est vraie pour tout n de . Suite rcurrente Soit un ensemble E, on note (an) une suite dlments de E telle que: a0 est connue an = f(an-1), pour n>0 et f: E E.
La suite (an) avec n est une suite rcurrente. Elle est entirement dtermine pour tout n de .

Fonction rcursive
Dans les algorithmes Pendant le traitement dune fonction nous pouvons appeler dautres fonctions dj dclares (dcomposition en sous problmes) Nous pouvons aussi, Pendant le traitement dune fonction, appeler la mme fonction initiale mais avec des arguments plus simples (dcomposition rcursive) Une fonction rcursive est une fonction qui sappelle elle-mme dans son traitement. Si la fonction appele nest autre que la fonction qui appelle, on dclenche une boucle infinie.

Fonction rcursive
F(a : Entier, b : chaine): Rel Dbut Var res en rel .. Dlivre res Fin RF(z: entier) Rel Dbut Var x, res : rel .. Res = RF(x) Dlivre res Fin

NF(z : entier) : Rel Dbut Var x, y, res2 : rel .. res2 = F(x, y) Dlivre res Fin

RF(x)

RF() est fonction une rcursive

Fonction Factorielle
On peut crire la factorielle de N par une suite:

Avec Un = n!. Sous cette forme Un dpend de n et Un-1. Ecrire l'algorithme de la fonction factorielle en employant la rcursivit.

Fonction itrative Factorielle

Fact(n: entier): entier Var res, i : entier Si (n=0) alors res 1 Sinon Res 1 Pour i 2 n Res Res*i Suivant i Fin si Revoyer (Res) Fin Font Algo: principal Var N : entier Ecrire(N=) Lire(N) Ecrire (N, !=, Fact(N)) Fin algo

Fonction rcursive Factorielle

Fact(n: entier) : entier Dbut Var res : entier Si(n=1) alors res 1 sinon Res n*Fact(n-1) finSi Renvoyer (res) Fin fonct Algo : principal var N : entier Dbut Ecrire( donner la valeur de N ) Lire(N) Ecrire(N, !=, FACT(N)) Fin Fin Algo Simulation: Pour N = 5 Fact(5)=5*Fact(4) =5*4*Fact(3) =5*4*3*Fact(2) =5*4*3*2*Fact(1) =5*4*3*2*1

Fact(0)=1 Fact(n)=n*fact(n-1)

Fonction Racine carre

La valeur de la racine carre d'un nombre A peut tre approxime en employant la suite rcurrente d'ordre 1 suivante:
La rcursivit ne porte pas sur la variable principale du problme A (variable dont on cherche la racine : A) mais la rcursivit porte sur une autre variable X

*
Version itrative du calcul de la racine carre
0. Rel racine(A : rel) 1. Dbut 2. variable X : rel 3. X 1 4. TantQue Abs(X^2 - A) >= 0.001 Faire 5. X ( X + A / X ) / 2 6. Fin tantque 7. renvoyer X 8. Fin 1. Var Z rel 2. Ecrire(Z=) 3. lire(Z) 4. Ecrire(la racine carr de, z, est, racine(Z)) 5. Fin

*
Version rcursive du calcul de la racine carre

0. Rel racine(A : rel, X : rel) 1. Dbut 2. variable res en rel 3. Si ABS(X*X A) <= 0,001 Alors 4. Res x 5. Sinon 6. Res racine(A, ( X + A / X ) / 2) 7. FinSi 8. Dlivre res 9. Fin

Simulation A=2, X=1 Res=racine(2, 1.5) 2,25 2 = 0,25 > 0,001 Res=racine(2, 1,416) Res=racine(2, 1,414) |(1,414)2 2| = 0,0006 < 0,001

1. Var Z rel 2. Ecrire(Z=) 3. lire(Z) 4. Ecrire(la racine carr de, z, est, racine(Z, 1)) 5. Fin

Exercice: trouver le Maximum de V(n-1) avec une fonction rcursive Soit la fonction Max(a, b). Ecrire une fonction rcursive qui renvoi le maximum des valeurs dun tableau V de dimension n. cette fonction aura pour argument les lments du vecteur V et la dimension n RecMax(V, n) Cette fonction rcursive doit renvoyer la valeur suivante:

Pour n=5 on doit renvoyer

Donc trouver le max des lments dun vecteur V de dimension N revient trouver le Max des lments dun vecteur V de dimension N-1 et V(N-1)

Correction
Max(a: entier, b: entier) Dbut Si a > b alors renvoyer (a) Sinon renvoyer (b) Fin si Fin Fonct RecMax(V() : entier, n : entier) Var G : entier Si (n=2) alors G Max(V(0), V(1)) sinon G Max(RecMax(V, n-1), V(n-1)) Finsi Renvoyer (G) Fin Fonct

Algo principale Tableau T() : entier Var N, i : entiers Ecrire( donner la dimension du tableau ) Lire (N) Redim(T(N-1)) Pour i 0 N-1 Ecrire(T()=, i) lire(T(i)) Suivant i Ecrire( le maximum est : , RecMax(T, N)) Fin algo

Algo : principal Var Z : rel, N: entier Dbut Ecrire(Z=) Lire (Z) Ecrire(N=) Lire (N) Ecrire(ZN=, puiss(Z, N) Fin algo

Puiss(X: rel, n : entier): rel Var P : rel Si (n=0) alors p 1 Sinon si (n mod 2 = 0) alors p puiss(x*x, n/2) sinon p x*puiss(x*x, (n-1)/2) finsi Finsi Fin fonct

Recherche du Max Mthode de diviser pour rgner

5 5 5 6 9 9 12 6 6 6 9 9 9 9 8 8 8 -4 -4 -4 12 12 12 12 12 12 -13 -13 -13 1 7 1 1 1 2 2 2 7 7 7 7

Algorithmes de tri
Les tableaux permettent de stocker plusieurs lments de mme type au sein d'une seule entit,
Trier un tableau c'est donc ranger les lments d'un tableau en ordre croissant ou dcroissant Il existe plusieurs mthodes de tri qui se diffrencient par leur complexit d'excution et leur complexit de comprhension pour le programmeur.

Nous exposons deux mthodes :

le tri par minimum (maximum) successif (tri de

selection)

Le tri bulles

Algorithmes de tri
Tous les algorithmes de tri utilisent une procdure qui permet d'changer (de permuter) la valeur de deux variables. Permuter (E/S a, b : Entier) var T : Entier Dbut T a ab bT Fin

Tri par slection Tri par Min ou Max successif

on parcourt le tableau de gauche droite, on cherche le plus petit lment puis on le positionne dans lindice i du tableau. On recommence la mme opration pour le sous-tableau de droite qui commence par lindice i+1.
plus gnralement : Pour trier le sous-tableau t[i..nbElements] il suffit de positionner au rang i le plus petit lment de ce sous-tableau et de trier le sous-tableau t[i+1..nbElements]

Tri par minimum successif

Par exemple, pour trier [221, 215, 130, 163, 147, 120], on va avoir les boucles suivantes :
r=0 r=1 r=2 r=3 r=4 r=5

i=0; 221
i=1; 120 i=2; 120 i=3; 120

215
215

130
130

163
163

147
147

120
221

130
130

215
147

163
163

147
215

221
221

i=4; 120
i=5; 120

130
130

147
147

163
163

215
215

221
221

Tri par minimum successif

Il nous faut donc une fonction qui soit capable de dterminer lindice du petit lment d'un tableau partir d'un certain rang
Index_min(V(): entier, n:entier, rang: entier) :entier Dbut Var i, pmin, Min : entiers Min V(rang) Tri(T() : entiers, N: entier) Pmin rang Dbut Pour i rang+1, n-1 Var i_min, i, k : entiers si V(i)<Min alors Pour i = 0, N-2 Min V(i) i_min Index_min(T, N, i) pmin i si(i <> i_min) alors fin si k V(i) Suivant i V(i) V(i_min) Renvoyer(pmin) V(i_min) k Fin font Fin si Suivant i Fin procdure
Algo test Tableau Tab() : entiers Var i, D : entiers Dbut Ecrire( donner le nbre de valeurs) Lire(D) Redim (tab(D-1)) Pour i 0, D-1 Ecrire( Tab() , i) lire(Tab(i)) Suivant i Tri(tab, D) Pour i 0, D-1 Ecrire(Tab(i)) Suivant i

Le tri bulles
Principe de la mthode :
Slectionner le minimum du tableau en parcourant le tableau du dbut la fin et en changeant tout couple d'lments conscutifs non ordonns.

Le tri bulles
Par exemple, pour trier [130, 156, 213, 230, 300], on va avoir les boucles suivantes :
i=0; 130 156 213 130 213 213 213 230 156 230 230 230 213 130 230 230 300 230 156 300 300 230 230 130 300 130 300 300 156 130 130 130 300 300 300 130
k=0; 156 k=1; 156 k=2; 156 k=3; 156

i=1;

156

213

k=0; 213 k=1; 213 k=2; 213

Le tri bulles
Tri(V():entier, n:entier) Dbut Var k, i, j : entiers Pour i 0 n-2 Pour j 0 n-2 - i si (V(j)>V(j+1) alors k V(j) V(j) V(j+1) V(j+1) k Finsi Suivant j Suivant i Fin procdure
Algo test Tableau Tab() : entiers Var i, D : entiers Dbut Ecrire( donner le nbre de valeurs) Lire(D) Redim (tab(D-1)) Pour i 0, D-1 Ecrire( Tab() , i) lire(Tab(i)) Suivant i Tri(tab, D) Pour i 0, D-1 Ecrire(Tab(i)) Suivant i

Les algorithmes de Recherche

Recherche dans un ensemble non tri On procd par une recherche linaire: on parcoure le tableau et lorsque quon trouve le nombre recherch (t(i)=X) on renvoi lindice correspondant. Si on parcours tous le tableau sans trouver la valeur recherche on dclare que le nombre nexiste pas.

Les algorithmes de Recherche

Recherche dans un ensemble non tri

Fonction Recherche (T(), X, Nb) Var i, R : entier i0 Tant que (i<=Nb-1 ET T(i) <> X) Alors i i+1 Fin tant que Si (i = Nb) alors Ecrire ( le nombre est introuvable ) Sinon Ecrire ( le nombre de trouve dans lindice ) Renvoyer (i) Fin

Les algorithmes de Recherche

Recherche dans un ensemble tri suivant un ordre croissant
On procd par une recherche linaire: on parcourt le tableau et tant que llment du tableau est infrieur au nombre recherch (t(i) < X) on continu la recherche. Si on parcours tous le tableau sans trouver la valeur recherche on dclare que le nombre nexiste pas.

Les algorithmes de Recherche

Recherche dans un ensemble tri suivant un ordre croissant Fonction Recherche (T(), X, Nb) Var i, R : entier i0 Tant que (i<=Nb-1 ET T(i) < X) Alors i i+1 Fin tant que Si (i = Nb) alors Ecrire ( le nombre est introuvable ) Sinon Ecrire ( le nombre de trouve dans lindice ) Renvoyer (i) Fin

Les algorithmes de Recherche

Algorithme de Dichotomie Le jeu du nombre cach

Une personne choisi un nombre compris entre 1 et 100, on doit deviner ce nombre. Nous allons faire des propositions et la personne rpond "trop grand", "trop petit" ou "gagn". Le jeu sarrte lorsquon va trouv le nombre.

N: nombre choisi entre 0 et 100 P: proposition

Var X, N, P Ecrire ( donner un nombre entre 0 et 100) Lire (N) Lire (P) Tant que (P <> N) faire si (P > N) alors Ecrire ( trop grand ) sinon Ecrire ( trop petit ) Fin Si Lire (P) Fin tant que Ecrire ( gagn )

Initiation la dichotomie
Quelles techniques de jeu peut-on employer pour gagner le plus rapidement possible ?
La technique-1 est la suivante: Si on propose un nombre G plus grand que celui recherch, on va proposer un autre nombre dans lintervalle [0..G-1] Si on propose aprs un nombre P plus petit que celui recherch, on va proposer un autre nombre dans lintervalle [P+1..G-1] et ainsi de suite

Chaque fois quon propose un nombre on limite plus lintervalle de recherche

Var X, N, P, Min, Max : entier; Ecrire( choisir un nombre entre 0 et 100 "); Lire(N) Lire(P) Min=0; Max=100; Tant que (P <> N) Si (P > N) Alors Max = P-1; Ecrire("donner un nbre entre", Min, Max) Sinon Min = P+1; printf("donner un nbre entre", Min, Max) FinSi Lire (P); Fin tant que Ecrire("gagn");

Simulation
Le nombre cach est 72

Min
0 35 57 57 61 61 Gagn

Max
100 100 100 79 79 74

Proposition
34 56 80 60 75 72

Initiation la dichotomie
La technique-2 Mthode de dichotomie:
Cette mthode est identique la prcdente seulement les valeurs proposes seront proche du milieu des intervalles [Min..Max] Chaque fois quon propose un nombre on limite plus lintervalle de recherche en crasant les valeurs de Min et Max.

Var X, N, P, Min, Max : entier Ecrire("donner un nombre entre 0 et 100 "); Lire(N); Min 0; Max 100; P (Max+Min)/2; Ecrire(P); Tant que (P <> N) faire Si (P > N) Alors Max = P-1 Sinon Min = P+1 Fin Si P=(Max+Min)/2; Ecrire(P); Fin tant que Ecrire("gagn", P);

Simulation
Le nombre cach est 72

Min 0 51 51 63 69 72 72 gagn

Max 100 100 74 74 74 74 72

Proposition milieu 50 75 62 68 71 73 72

Utilisation de la dichotomie rsolution de f(x)=0

f est une fonction dfinie sur lintervalle [a, b] et strictement monotone sur [a; b]. On cherche rsoudre numriquement lquation f(x) = 0.

Utilisation de la dichotomie rsolution de f(x)=0

Var X, N, P, Min, Max : rel Lire(Min) Min Lire(Max) Si (f(Max)*f(Min)>0) Alors Ecrire("pas de solution") Sinon P=(Max+Min)/2; Ecrire(P) tant que (abs(f(P)) > 0.001) faire si (f(Min) * f(P)<=0) Alors Max P sinon Min P Fin Si P=(Max+Min)/2; Fin tant que Ecrire( la solution est:", P); Fin Si Fin

P2 P3

P1

Min

f(Min)

f(P2) P2 f(P3) f(P1) Min P3 P1 Max

f(Max)

Complexit
Comment valuer les performances d'un algorithme ?
diffrents algorithmes ont des couts diffrents en termes de temps d'excution (nombre d'oprations effectues par l'algorithme), taille mmoire (taille ncessaire pour stocker les diffrentes structures de donnes pour l'excution).

Ces deux concepts sont appels la complexit en temps et en espace de l'algorithme.

Complexit
La complexit algorithmique permet de mesurer les performances d'un algorithme et de le comparer avec d'autres algorithmes ralisant les mme fonctionnalits. La complexit algorithmique est un concept fondamental pour tout programmeur, elle permet de dterminer si un algorithme a et meilleur quun algorithme b et sil est optimal ou bien il ne doit pas tre utilis

*
Le temps d'excution d'un programme dpend : 1. du nombre de donnes, 2. de la taille du code, 3. du type d'ordinateur utilis (processeur, mmoire), 4. de la complexit en temps de l'algorithme. Soit n la taille des donnes du problme et T(n) le temps d'excution de l'algorithme. On distingue : o Le temps du plus mauvais cas Tmax(n) qui correspond au temps maximum pris par l'algorithme pour un problme de taille n o Comportement de T(n) pour un n est grand.

*
Rgles gnrales : 1. le temps d'excution TE d'une affectation, dune incrmentation, dune opration lmentaire ou d'un test est considr comme constant c. 2. Le temps d'une squence d'instructions est la somme des TE des instructions qui la composent. 3. le temps d'un branchement conditionnel est gal au TE du test plus le max des deux TE correspondant aux deux alternatives (dans le cas d'un temps max). 4. Le temps d'une boucle est gal au cot du test de sortie de boucle plus le corps de la boucle.

Exemple-1: Calcul d'une somme

{dbut}
R <-- 0 i <-- 1 TantQue i <= n Faire R <-- R+T[i] i <-- i+1 FinTantQue t1 : affectation t2 : test t3 : somme t4 : incrmentation

{fin}

R=0 i=1 i<=n?? (oui) R=R+T(1) i=2 i<=n?? (oui) R=R+T(2) i=3 i<=n?? (oui) R=R+T(3) i=n i<=n?? (oui) R=R+T(n) i=n+1 i<=n?? (non)

Lalgorithme est donc asymptotiquement linaire en n.

Notion de complexit: comportement asymptotique du TE: elle correspond au terme dominant de lexpression du nombre doprations T(n) en fonction de la taille des donnes en entre. On adopte la notation de Landau: O(.).
Cette algorithme une complexit O(n).

Exemple-2: Calcul d'une somme

R <-- 0 i <-- 1 TantQue i <= N Faire R <-- R+T[i] Si R>1000 Alors R<-- 2*R FinSi i <-- i+1 FinTantQue t1 : affectation t2 : test t3 : somme t4 : incrmentation t5: multiplication

Cette algorithme une complexit O(n).

Exemple-3 : calcul du factorielle (fonction rcursive)

Fonction factorielle(n ; naturel) : naturel Dbut Si n 0 alors Retourner 1 Sinon Retourner n*factorielle(n-1) Finsi Fin

t1: test t2: multiplication

Dans le cas dun traitement rcursive les deux branchements vont tre excuts
T(n) = t1 + t2 + T(n-1)
T(n) = (n+1)*t1 + n*t2 = (t1+t2)*n + t1

Complexit linaire O(n)

Exemple-4 (deux boucles imbriques). B<--0 i <--1 Pour i <-- 1 n Faire B<--B+2 Pour j <-- 1 n Faire T[i,j] <-- (1+T[i,j] )*B Suivant j Suivant i
t1: t2: t3: t4: t5: affectation somme test multiplication incrmentation

Cette algorithme une complexit O(n2).

Exemple-5 algorithme de Recherche du Max

Var : X, i, Max : entiers Ecrire( donner la valeur , 0) Lire X Max X i1 Tant que (X <> -1) faire si(X > Max) alors Max X FinSi Ecrire( donner la valeur , i) lire X ii+1 Fin tant que Ecrire(Max=, Max)

c1:affectation c2: incrmentation c3: test

La complexit est en O(n)

Exemple-6 Somme de deux matrice

Tableau M1()(), M2()(), S()() Var i, j: entier Ecrire(donner la dimension des deux matrices) Lire (n, m) Redim(M1(n-1)(m-1)) Pour i 0 n-1 Redim(M2(n-1)(m-1)) pour j0 m-1 Redim(S(n-1)(m-1)) S(i)(j)M1(i)(j)+M1(i)(j) Pour i = 0 n-1 Ecrire( S()()= , i, j, S(i)(j)) pour j=0 m-1 suivant j Ecrire( M1()() , i, j) Suivant i lire M1(i)(j) suivant j Suivant i Pour i = 0 n-1 pour j=0 m-1 Ecrire( M1()() , i, j) lire M1(i)(j) suivant j Suivant i La complexit est en O(n2)

Exemple-7 Fonction Echange

1. 2. 3. 4. 5. 6. 7.

Fonction changer (E/S a, b : Entier) Dclaration T : Entier Dbut T a ab bT fin

T(n) = c1+c1+c1 = 3c1 Complexit constante en O(1)

(c1 : affectation)

*
Algorithmes de recherche linaire
Fonction Recherche (T(), X, Nb) Var i, R : entier i0 Tant que (i<=Nb-1 ET T(i) <> X) Alors i i+1 Fin tant que Si (i = Nb) alors Ecrire ( le nombre est introuvable ) Sinon Ecrire ( le nombre de trouve dans lindice ) Renvoyer (i) Fin

Pire des cas, lment cherch absent du tableau On va effectuer n tests: T(n)=n*C complexit linaire : O(n)
Le temps dexcution est proportionnel aux nombres de donnes. Naf il existe un algorithme plus efficace

*
Fonction Recherchedico(T() : entier, Nb : entier, X : entier): entier Var m : entier Min 0; Max Nb-1; m (Max+Min)/2; Tant que (T(m) <> X) faire Si (T(m) > X) Alors Max = m-1 Sinon Si (T(m) < X) Alors Min = m+1 Fin Si P=(Max+Min)/2; Fin tant que Renvoyer (m);

Les algorithmes usuels peuvent tre classs en un certain nombre de grandes classes de complexit.
Les algorithmes sous-linaires, dont la complexit est en gnral en O(logn). sont considrs comme les plus rapides. C'est le cas de la recherche d'un lment dans un ensemble ordonn fini de cardinal n. Les algorithmes linaires en complexit O(n) ou en O(nlogn) sont considrs comme rapides, comme l'valuation de la valeur d'une expression compose de n symboles ou les algorithmes optimaux de tri. Plus lents sont les algorithmes de complexit situe entre O(n2) et O(n3), c'est le cas de la multiplication des matrices et du parcours dans les graphes. Au del, les algorithmes polynomiaux en O(nk) pour k > 3 sont considrs comme lents, sans parler des algorithmes exponentiels (dont la complexit est suprieure tout polynme en n) que l'on s'accorde dire impraticables ds que la taille des donnes est suprieure quelques dizaines d'units.

Ordre de grandeur du temps ncessaire l'excution d'un algorithme d'un type de complexit

Conclusion
Qualits d'un algorithme :
1. Maintenable (facile comprendre, coder, dboguer), 2. Rapide Conseils : 1. Privilgier le point 2 sur le point 1 uniquement si on gagne en complexit. 2. ce que fait l'algorithme doit se lire lors d'une lecture rapide : Une ide par ligne. 3. Faire galement attention la prcision, la stabilit et la scurit. La rapidit d'un algorithme est un lment essentiel pour dfinir les qualits de celui-ci.

Mthodologie
Comment trouver un algorithme? Prenez un exemple tentez de voir intuitivement dessus comment rsoudre le problme. Tentez alors de gnraliser ces oprations pour obtenir les principes gnraux de votre algorithme. traduisez ces principes en pseudo-code. Si besoin, dcomposez le problme en sous problmes que vous traitez indpendamment,

Langage de programmation C
#include <stdio.h> main() { printf("Premier programme\n "); }
#include <stdio.h> #include <stdlib.h> #include <math.h>

Langage de programmation C
La directive # include Pour compiler correctement un fichier, le compilateur a besoin o d'informations concernant les dclarations de: o structures de donnes o variables externes o l'aspect (prototype) des fonctions prdfinies. Toutes ces informations sont contenues dans des fichiers avec l'extension .h .Ces fichiers doivent tre inclus dans le fichier que l'on veut compiler.
Par exemple, pour utiliser la fonction printf, il faut inclure le fichier stdio.h (standard input output) .

*
La fonction main

Est un "en-tte", elle prcise que ce qui sera dcrit la suite est le programme principal. Un programme en C apparat comme une fonction qui porte le nom main(), le programme doit tre dlimit par des accolades { pour le dbut, et } pour la fin. On dit que les instructions situes entre ces accolades forment un "bloc".

Langage de programmation C
La fonction printf() Dans linstruction : printf(Premier programme \n); On appelle la fonction prdfinie printf(). Cette fonction reoit un argument qui est : "Premier programme \n" Les guillemets servent dlimiter une "chane de caractres". La notation \n est conventionnelle: elle reprsente un caractre de fin de ligne qui, lorsqu'il est envoy l'cran, provoque le passage la ligne suivante.

Langage de programmation C
de manire gnrale, le langage C prvoit une notation de ce type (\ suivi d'un caractre) pour un certain nombre de caractres dits "de contrle".
\n nouvelle ligne
\t tabulation horizontale \v tabulation verticale \b retour d'un caractre en arrire \r retour chariot \f saut de page \a beep

Langage de programmation C
Les types des variables Le type char On peut stocker dans ces variables des chaines caractres. dsigne un entier sign cod sur 1 octet

Les types short, int Le type short reprsente un entier sign cod sur 2 octets Le type int reprsente un entier sign cod sur 4 octets

Langage de programmation C
Les types des variables Le type rel Les nombres virgule flottante (nombres rels) servent coder de manire approche les nombres rels. On dispose de trois types de nombres virgule flottante, les types float, double et long double.

Langage de programmation C
Les Oprateurs Les oprateurs arithmtiques : - : changement de signe * : Multiplication / : Division % : Modulo (reste de la division de deux entiers) + : Addition - : Soustraction

Langage de programmation C
Les Oprateurs Les oprateurs relationnels : Ces oprateurs binaires (vrai ou faux) permettent dtablir des conditions logiques en comparant leurs deux oprandes. == test si gal != test si diffrent < test si infrieur <= test si infrieur ou gal > test si suprieur >= test si suprieur ou gal

Langage de programmation C
Les Oprateurs

Les oprateurs logiques:

Ces oprateurs permettent les oprations boolennes classiques sur des conditions logiques.

! Ngation logique dune condition

&& ET logique de conditions || OU logique de conditions

Langage de programmation C
Les Oprateurs

Oprateur dincrmentation
Incrmentation prfixe/postfixe. a++ est quivalent a=a+1;

b=a++; est quivalent b=a; puis a=a+1;

b=++a; est quivalent a=a+1; puis b=a;

Langage de programmation C
La fonction printf()

Le premier argument de printf est une chane de caractres qui spcifie la fois des caractres afficher tels quels, des "codes de format" reprs par %. Un "code de conversion" (tel que c, d ou f) y "prcise le type de l'information afficher.
Printf("%d" , X) Printf( la valeur de de X et Y est %d %d" , X, Y) %d int, %f float, %c char

Langage de programmation C
La fonction scanf()

D'une manire gnrale, l'appel de scanf se prsente ainsi : scanf ( format, liste_d_adresses)
format : constante chane (entre " "), liste_d_adresses : liste de "lvalue", spares par des virgules, d'un type en accord avec le code de format correspondant.

Scanf("%d " , &X)

Langage de programmation C
Les Structures de contrle If (condition) {Bloc 1} Else {Bloc 2} If (condition) {Bloc 1} Else IF {Bloc 2} Else IF {Bloc 3} Else {Bloc 4}

Langage de programmation C
Les Structures de contrle
main() { int n ; do { printf ("donnez un nb < 0 : ") ; scanf ("%d", &n) ; } while (n<=0) printf ("vous avez fourni %d\n", n) ;

Langage de programmation C
Les Structures de contrle
main() { int Som, X ; Som = 0; while(Som <= 100) { printf("donnez un nb : "); scanf("%d", &X) ; Som = Som + X; } printf ("la somme est termine") ; system("PAUSE"); return 0; } main() { int Som, X ; Som = 0; For (i=1; i<=N; i++) { printf("donnez un nb : "); scanf("%d", &X) ; Som = Som + X; } printf ("la somme est termine") ; system("PAUSE"); return 0; }