chap5pdf

Cours de Programmation par Ecclsiaste DEUDJUI (+237) 96 46 96 37 [email protected]

1

CHAPITRE 5 :

QUELQUES ALGORITHMES LABORS : LA RECHERCHE ET LE TRI

Dans ce chapitre il ne sera pas question dapprendre une nouvelle leon, mais plutt dutiliser les concepts dj tudis pour shabituer dvelopper des algorithmes optimiss. Nous verrons donc successivement comment vrifier manuellement lexcution dun programme (trace), nous utiliserons les matrices pour construire un triangle de Pascal, et enfin nous verrons les cas particuliers des algorithmes de recherche et de tri.

I- LA TRACE Cest une manire dtaille de suivre le droulement dun programme au fur et

mesure de son excution. Elle se fait au moyen dun tableau :

Variables

Instructions Var 1 Var i

Instruction 1 Instruction i

Par exemple, soit un algorithme o il faut faire la somme des 3 premiers entiers.

Algorithme somme_3

Var i, S : entier

DEBUT

S 0

POUR i 1 A 3 FAIRE


2

S S + i

FINPOUR

Ecrire(La somme des 3 premiers nombres est , S) FIN

La vrification dun tel algorithme sera donc :

Variables

Instructions i S

S 0 NULL 0 i 1 1 0

S S + i 1 1 i 2 2 1

S S + i 2 3 i 3 3 3

S S + i 3 6

II- CONSTRUCTION DU TRIANGLE DE PASCAL Le triangle de Pascal est un triangle invent par le mathmaticien Franais Blaise

Pascal. Initialement il avait pour but daider au calcul des probabilits.

RAPPEL : un triangle de Pascal est en ralit une matrice carre o :

- La 1re colonne de chaque ligne a la valeur 1.

- Chaque case appartenant la diagonale a la valeur 1.

- Les cases situes droite de la diagonale nont pas de valeur (NULL). - partir de la 3me ligne, les cases situes entre la 1re colonne et la diagonale

sont la somme de la case du dessus et celle gauche de cette dernire.

Exemple : voyons ce que a donne si nous avons une matrice carre dordre 7 :


3

1

1 1

1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1

EXEMPLE : crire un algorithme qui effectue un triangle de Pascal dordre 10.

Algorithme triangle_pascal

Const n=10

Type matrice=tableau[1..n, 1..n] de entier Var i, j : 1..n ; M : matrice DEBUT

POUR i 1 A n FAIRE

M[i, 1] 1 ; M[i, i] 1 FINPOUR

POUR i 3 A n FAIRE

POUR j 2 A (i-1) FAIRE M[i, j] m[i-1, j] + m[i-1, j-1] FINPOUR

FINPOUR

III- LES PROBLMES DE RECHERCHE La recherche est une opration trs importante lorsquil sagit de manipuler de grandes

quantits de donnes en informatique. Elle permet de retrouver une information spcifique dans un tableau, un fichier, un enregistrement, une liste chane, une base de donnes


4

En programmation algorithmique, il existe plusieurs principes de recherche. Nous allons en tudier 2 qui sont : la recherche squentielle et la recherche dichotomique.

III-1) La recherche squentielle : A- La recherche squentielle sans sentinelle

Cest une recherche effectue entre les diffrentes valeurs dun tableau. On parcourt progressivement chacune des cellules (cases), et ds que la valeur recherche est trouve le programme renvoie VRAI. Sinon il renvoie FAUX.

EXEMPLE : crire un algorithme qui recherche une valeur val dans un tableau dj rempli. Algorithme recherche_sequentielle

Const N=25

Type vecteur=tableau[1..N] de entier Var i : 1..N

Val : entier ; V : vecteur ; trouve : boolen

DEBUT

Ecrire(Entrez la valeur recherche) Lire(val) i 1

TANT QUE (v[i] val) ET (i


5

SINON

Ecrire(La valeur , val, nest pas dans le tableau) FINSI

FIN

B- La recherche squentielle avec sentinelle

Le principe reste le mme que prcdemment, sauf que cette fois on utilisera une sentinelle en fin de tableau pour savoir si la valeur recherche est bel et bien prsente.

EXEMPLE : crire un algorithme qui recherche une valeur val dans un tableau dj rempli. Algorithme recherche_avec_sentinelle

Const N=25

Type vecteur=tableau[1..N+1] de entier Var i : 1..N+1

Val : entier ; V : vecteur

DEBUT

Ecrire(Entrez la valeur recherche) Lire(val) V[N+1] val i 1

TANT QUE (v[i] val) FAIRE i i + 1

FINTANTQUE

Si i


6

SINON


FIN

III-2) La recherche dichotomique : Contrairement la recherche squentielle, la recherche dichotomique ne peut tre

effectue que sur un tableau pralablement ordonn (par ordre croisant ou dcroissant). Ainsi, soient et les indices infrieur et suprieur du vecteur croissant sur lequel on veut effectuer notre recherche dichotomique. On va procder comme suit :

1. Diviser le vecteur en 2 parties gales. Cela se fait en calculant lindice du milieu : Milieu = (Bi + Bs) div 2

2. Si llment quon veut trouver est gal la valeur qui se situe au milieu du vecteur, alors la recherche sarrte. Dans le cas contraire il y a 2 cas de figure :

a. Soit llment recherch est infrieur la valeur du milieu. Auquel cas la recherche se poursuit dans le demi-vecteur born par et .

b. Soit llment recherch est suprieur la valeur du milieu. Auquel cas la recherche se poursuit dans le demi-vecteur born par et .

3. Ritrer le processus jusqu ce quun lment du milieu soit gal llment recherch, ou alors jusqu ce que soit suprieur

EXEMPLE : crire un algorithme qui recherche une valeur val dans un tableau de valeurs ordonnes par ordre croissant.

Algorithme recherche_dichotomique

Const inf=1

Sup=100

Type vecteur=tableau[inf..sup] de entier


7

Var milieu, val, bi, bs : entier

V : vecteur

trouve : boolen

DEBUT

Bi inf

Bs sup

Ecrire(Entrez la valeur recherche) Lire(val) milieu (bi + bs) div 2 TANT QUE (v[milieu] val) ET (bi val ALORS Bs milieu 1

SINON

Bi milieu + 1

FINSI

milieu (bi + bs) div 2 FINTANTQUE

Trouve v[milieu] = val Si trouve ALORS

Ecrire(La valeur , val, se trouve dans le tableau) SINON



8

FIN

NB : cet algorithme peut tre optimis en supprimant la variable boolenne trouve. Il suffira alors de remplacer SI trouve ALORS par SI v[milieu]=val ALORS.

IV- LES PROBLMES DE TRI Nous venons de voir, avec la recherche dichotomique, quil y a des oprations qui ne

sont valables que sur des variables ranges selon un certain ordre (croissant, dcroissant, alphabtique). En effet, il est possible de dvelopper des algorithmes trs performants ds lors quon a une liste trie. Ainsi, dans cette partie nous tudierons quelques mthodes usuelles dordonnancement des valeurs dans un vecteur.

III-1) Notion de tri : Soit V un vecteur, Bi et Bs ses bornes infrieur et suprieur. Le vecteur V est tri si et

seulement si lune des conditions suivantes est respecte :

V ne contient aucun lment.

V contient un seul lment.

V contient plusieurs lments et, quel que soit i compris entre Bi et Bs, on a toujours v[i] = v[i+1] (si V dcroissant).

III-2) Le tri par slection : Le tri par slection consiste parcourir tout le vecteur la recherche du plus petit

lment. Ds quon lobtient, on le positionne la 1re case. Ensuite on rpte lopration avec le vecteur non encore tri, jusqu ce quil nen reste quun singleton.

EXEMPLE : crire un algorithme qui ordonne de faon croissante un tableau dj rempli. Algorithme tri_selection

Const n=100

Type vecteur=tableau[1..n] de rel


9

Var i, j : entier Aux : rel

V : vecteur

DEBUT

POUR i 1 A (n-1) FAIRE POUR j (i+1) A n FAIRE SI v[j]


10

Aux : rel

V : vecteur

DEBUT

POUR i 2 A n FAIRE

J i

TANT QUE (j > 1) ET (v[j]


11

o Les autres cases nont pas de valeur.

Le rsultat final doit donner ceci :

0

1 0

1 1 0

1 2 2 0

1 3 5 5 0

1 4 9 14 14 0

1 5 14 28 42 42 0

1 6 20 48 90 132 132 0

1 7 27 75 165 297 429 429 0

1 8 35 110 275 572 1001 1430 1430 0

4. Soit une matrice contenant plusieurs valeurs entires. Concevoir un algorithme qui renvoie le nombre total de nombres impairs contenus dans cette matrice, ainsi que leur somme.

5. Soit une matrice M de 10 lignes et 7 colonnes contenant des rels. Concevoir un algorithme permettant de ranger les valeurs de M dans une autre matrice T de mme structure. Le classement se fera par ordre croissant.

Documents

chap5pdf