ALGORITHME TABLEAUX

1 17/02/2013 1 ALGORITHME TABLEAUX Mr KHATORY 2 Ensemble de donn es du m me type Exemple de probl me : Saisir une suite de nombres, puis afficher cette suite apr s avoir divis tous les nombres par la valeur maximale de la suite. -21 57 8902 841 -641 8100 0 132 Remarque : appeler cette variable TabVal plut t que Val TABLEAUX 132 val Val : Variable contenant une valeur variable : Variable contenant une collection de valeurs du m me type N cessit de conserver les nombres en m moire 17/02/2013 2 3 Structure de donn es permettant d'effectuer un m me traitement sur des donn es de m me nature tableau une dimension Ensemble de valeurs enti res, r elles, bool ennes,.. Ensemble de noms (type cha ne) Ensemble de caract res (type caract re) Ensemble d'adresses (type Adresse : nom,adresse, num t l phone) Ensemble d'ouvrages .. tableau deux dimensions TABLEAUX Exemples d'applications: 4 On veut pouvoir : cr er des TABLEAUX ranger des valeurs dans un tableau r cup rer, consulter des valeurs rang es dans un tableau rechercher si une valeur est dans un tableau mettre jour des valeurs dans un tableau modifier la fa on dont les valeurs sont rang es dans un tableau (par exemple : les trier de diff rentes mani res) effectuer des op rations entre TABLEAUX : comparaison de TABLEAUX , multiplication.

2 Traitements op rant sur des TABLEAUX TABLEAUX 17/02/2013 3 5 13 25 -21 3 -2 100 1 2 3 4 5 6 Tab Nom du tableau Indice du tableau Contenu du tableau A H M E D 1 2 3 4 5 Nom TABLEAUX Remarques : Indices : en g n ral, d marrage 1, mais en C++, d marrage 0 Nombre d octets occup s : d pend du type des valeurs enregistr es 6 VAR tabl : TABLEAU [ ] d'entiers nom du tableau mot cl indices min et max (taille) type des l ments TABLEAUX D claration d'un tableau Exemple : d claration d'un tableau pouvant contenir jusqu' 35 entiers Autre exemple : d claration d'un tableau qui contiendra les fr quences des temp ratures comprises entre 40 C et 50 C VAR Temperatures : TABLEAU [ ] de REEL Temperatures [-30] Fr quence temp -30 C VAR Temperatures : TABLEAU [ ] de REEL Avec Temperatures [1] correspond la fr quence de la temp rature -40 c Question: la fr quence de la temp rature 25 c Temperatures [ ?]

3 ] 17/02/2013 4 7 Exemple : d claration d'un nouveau type Mot, tableau de 10 caract res TYPE Mot = TABLEAU [ ] de caract res VAR nom, verbe : Mot TYPE <Nom> = <description> TABLEAUX D finition d'un type tableau 8 Utilisation d un tableau : par les indices Acc s en lecture : - x T[2] /*le contenu du tableau l indice 2 est plac dans x */ - Ecrire (T[4]) /*le contenu du tableau l indice 4 est affich l cran*/ Acc s en criture : -T[3] 18 /*la valeur 18 est plac e dans le tableau l indice 3*/ -Lire (T[5]) /*la valeur entr e par l utilisateur est enregistr e dans le tableau l indice 5*/ TABLEAUX 17/02/2013 5 9 PROCEDURE SAISIR( VAR T : TABL;N :ENTIER) VAR i : ENTIER DEBUT POUR i DE 1 A N Lire (T[i]) FINPOUR FIN CONST TAILLE=50 TYPE TABL= TABLEAU [ ] d'ENTIER TABLEAUX PROCEDURE AFFICHER (T :TABL; N :ENTIER) VAR i :ENTIER DEBUT POUR i DE 1 A N ECRIRE (T[i]) FINPOUR FIN Ecrire la PROCEDURE SAISIR(.)

4 Qui permet de saisir un tableau T de N l ments ( N TAILLE ) Ecrire la PROCEDURE AFFICHER(..) qui permet d'afficher un tableau T de N l ments ( N TAILLE ) 10 VAR tabl : TABLEAU [ ] d'entiers nom du tableau mot cl indices min et max (taille) type des l ments TABLEAUX D claration d'un tableau Exemple : d claration d'un tableau pouvant contenir jusqu' 35 entiers 17/02/2013 6 11 Exemple : d claration d'un nouveau type Mot, tableau de 10 caract res TYPE Mot = TABLEAU [ ] de caract re VAR nom, verbe : Mot TYPE <Nom> = <description> TABLEAUX D finition d'un type tableau 12 PROCEDURE SAISIR(VAR T : TABL;N :entier) VAR i : entier DEBUT POUR i DE 1 A N Lire (T[i]) FINPOUR FIN CONST TAILLE=50 TYPE TABL= TABLEAU [ ] d'entiers TABLEAUX PROCEDURE AFFICHER (T :TABL; N :entier) VAR i :entier DEBUT POUR i DE 1 A N ECRIRE (T[i]) FINPOUR FIN Ecrire la PROCEDURE SAISIR(.)

5 Qui permet de saisir un tableau T de N l ments ( N TAILLE ) Ecrire la PROCEDURE AFFICHER(..) qui permet d'afficher un tableau T de N l ments ( N TAILLE ) 17/02/2013 7 Trier des objets est la fois un probl me fondamental de l algorithmique, comme tape de pr traitement d algorithmes plus complexes ou pour ordonner des structures de donn es ( quoi servirait un annuaire non tri ) Nous pr sentons ici des tris simples possibles sur les TABLEAUX : par s lection TRI TABLEAUX par Insertion bulle L id e du tri consiste chaque tape rechercher le plus petit l ment non encore tri et le placer la suite des l ments d j tri s. A une tape i, les i 1 plus petits l ments sont en place, et il nous faut s lectionner le i me l ment mettre en position i. ALGORITHME de tri par s lection TRI TABLEAUX Tri par S lection 1. Chercher le plus petit l ment du tableau restant 2.

6 Echanger cet l ment avec l' l ment en position i 2 12 32 33 63 43 1 2 i-1 i ? D j tri Reste trier 17/02/2013 8 2 12 32 33 63 43 1 2 i-1 i ? D j tri Reste trier ALGORITHME TriS lection CONST TAILLE=50 TYPE TABL=TABLEAU[ ] d'ENTIER VAR T: TABL N,i, pos :ENTIER DEBUT ECRIRE(" Entrer le nombre d' l ment du tableau < = ",TAILLE) LIRE(N) SAISIR(T,N) POUR i DE 1 A N -1 FAIRE /* Etapes de l ALGORITHME */ pos TROUVERMIN(T ,i,N) /* Plus petit l ment du tableau restant*/ ECHANGER(T,i,pos) /* ECHANGER avec l' l ment en position i*/ FINPOUR AFFICHER(T,N) FIN TRI TABLEAUX 2 12 32 33 1 2 i-1 i ? D j tri Reste trier FONCTION TROUVERMIN( T: TABL i,N: ENTIER ):ENTIER VAR i_Min :ENTIER DEBUT i_Min i POUR j DE i_Min +1 A N FAIRE SI T [j] < T[i_Min] ALORS i_Min j FINSI FINPOUR Retourner( i_Min) FIN PROCEDURE ECHANGER(Var T: TABL; i,j: ENTIER) VAR Aux :ENTIER DEBUT Aux T[i] T[i] T[j] T[j] Aux FIN TRI TABLEAUX 43 63 17/02/2013 9 2 12 32 33 43 63 1 2 i-1 i ?

7 D j tri Reste trier TRI TABLEAUX PROCEDURE ECHANGER(VAR T: TABL; i,j: ENTIER) VAR Aux :ENTIER DEBUT Aux T[i] T[i] T[j] T[j] Aux FIN FONCTION TROUVERMIN( T: TABL i,N: ENTIER ):ENTIER VAR i_Min :ENTIER DEBUT i_Min i POUR j DE i_Min +1 A N FAIRE SI T [j] < T[i_Min] ALORS i_Min j FINSI FINPOUR Retourner( i_Min) FIN TRI TABLEAUX crire la Procedure TRI_INSERTION qui utilise la Procedure INSERER pour trier par ordre croissant les l ments d'un tableau de N l ments. M thode: Trier le tableau de gauche droite en ins rant chaque fois l' l ment i+1 dans le tableau (d j tri ) des i premiers l ments. 10 50 20 40 15 30 17 32 21 23 12 10 20 40 50 15 30 17 32 21 23 12 D j tri ins rer 10 20 50 40 15 30 17 32 21 23 12 ins rer D j tri D j tri ins rer 17/02/2013 10 PROCEDURE TRI_INSERTION( VAR T :TABL ; N :ENTIER) /* N :taille du tableau trier*/ VAR i, indice :ENTIER Trouve :BOOLEEN DEBUT POUR i DE 2 A N FAIRE indice 1 Trouve Faux TANTQUE (Non Trouve) ET (indice < i) FAIRE SI T[indice] > T[i] ALORS INSERER(T,indice,i) Trouve Vraie FINSI indice indice +1 FINTANTQUE FINPOUR FIN PROCEDURE INSERER(var T :TABL ; indice,i :ENTIER) VAR j :ENTIER DEBUT Aux T[i] POUR j DE i-1 A indice Par pas -1 FAIRE T[j+1] T[j] FINPOUR T[indice] Aux FIN TRI TABLEAUX D calage droite des l ments 10 20 40 50 15 30 17.

8 12 D j tri ins rer PROCEDURE TRI_INSERTION( VAR T :TABL ; N :ENTIER) /* N :taille du tableau trier*/ VAR i, indice :ENTIER Trouve :BOOLEEN DEBUT POUR i DE 2 A N FAIRE indice 1 Trouve Faux TANTQUE (Non Trouve) ET (indice < i) FAIRE SI T[indice] > T[i] ALORS INSERER(T,indice,i) Trouve Vraie FINSI indice indice + 1 FINTANTQUE FINPOUR FIN POUR i DE 2 A N FAIRE indice 1 TANTQUE (T[indice] T[i] ET ( indice < i) FAIRE indice indice +1 FINTANTQUE SI (indice i ) ALORS INSERER(T,indice,i) FINSI TRI TABLEAUX FINPOUR Attention au cas de indice = i Pas d'insertion ! 17/02/2013 11 Au cours d une passe du tableau, les plus grands l ments remontent de proche en proche vers la droite comme des bulles vers la surface. Tri bulle TRI TABLEAUX Le tri bulle consiste parcourir le tableau, par exemple de gauche droite, en comparant les l ments c te c te et en les permutant s' ils ne sont pas dans le bon ordre.)

9 Tant que le tableau n est pas tri 1. Effectuer une passe ! a. Parcourir le tableau b. Si 2 l ments successifs ne sont pas dans le bon ordre, les changer On s arr te d s que l on d tecte que le tableau est tri : si aucune permutation n a t faite au cours d une passe. 10 50 20 40 15 30 17 32 21 23 12 10 20 50 40 15 30 17 32 21 23 12 10 20 40 50 15 30 17 32 21 23 12 10 20 40 15 30 17 32 21 23 50 12 10 20 40 15 30 17 32 21 23 12 50 Une passe Nouveau tableau : Borne -1 Maximum 10 50 20 40 15 30 17 32 21 23 12 1 Borne .. 2 10 20 50 40 15 30 17 32 21 23 12 10 20 40 50 15 30 17 32 21 23 12 10 20 40 15 50 30 17 32 21 23 12 10 20 40 15 30 17 32 21 23 12 50 17/02/2013 12 10 20 40 15 30 17 32 21 23 12 50 Une 2 me passe Nouveau tableau : @borne -1 10 20 15 40 30 17 32 21 23 12 50 10 20 15 30 40 17 32 21 23 12 50 10 20 15 30 17 32 21 23 12 40 50 M me m thode !

10 ! Pour le nouveau tableau de taille borne -1 10 20 15 40 30 17 32 21 23 12 50 10 20 15 30 40 17 32 21 23 12 50 10 20 15 30 17 40 32 21 23 12 50 ALGORITHME TriBulle CONST TAILLE=50 TYPE TABL=TABLEAU [ ] d'ENTIER VAR T : TABL i,N,borne :ENTIER Est_trie :BOOLEEN DEBUT ECRIRE(" Entrer le nombre d' l ment du tableau < = ",TAILLE) LIRE(N) SAISIR(T,N) Est_trie faux /*D tecte si le tableau est tri */ borne N TANTQUE Non(Est_trie ) /* It ration sur les passes*/ FAIRE Est_Trie vrai /* Initialisation avant une passe*/ POUR i DE 1 A borne-1 /* Effectue une passe*/ Si T[i] > T[i+1] /* Compare 2 l ments successifs*/ Alors ECHANGER(T,i,i+1) Est_trie faux FinSi FINPOUR borne borne-1 FINTANTQUE AFFICHER(T,N) FIN