Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithmique Licence 2 IRT Année académique 2020-2021 GBEDEVI A. Yvette ESGIS

Algorithmique Licence 2 IRT Année académique 2020-2021 GBEDEVI A. Yvette ESGIS 1 Chapitre 4 : Les tableaux Lorsque les données sont nombreuses et de même nature, au lieu de manipuler un grand nombre de variables, il est plus pratique de ranger ces variables dans un tableau. Dans la plupart des langages de programmation existe la notion de tableau indexé par des entiers ; des langages comme le PASCAL permettent de plus l’indexation par des éléments d’autres types, pas tout à fait n’importe lesquels mais les types dits types ordinaux. Nous allons nous intéresser dans ce chapitre aux tableaux indexes par des entiers. La notion de tableau (array en anglais) est une notion courante très utilisée, pas seulement en informatique. Il s’agit la plupart du temps de tableaux à deux dimensions avec des lignes et des colonnes. Mais on peut aussi considérer des tableaux à une seule dimension (ce sont plutôt des listes dans le langage courant) ou à plusieurs dimensions (plus difficilement représentables de façon graphique à partir de la quatrième dimension). Voyons, d’une part, comment mettre en œuvre les tableaux en programmation et, d’autre part, leur intérêt pour les problèmes de programmation. Nous allons étudier les tableaux à une dimension, les tableaux à deux dimensions puis les tableaux à plusieurs dimensions. 1.1 Tableaux à une dimension 1.1.1. Notion Notion intuitive : Un tableau à une dimension est formé d’éléments tous de même nature et repérés par un index. Représentation graphique : Un tableau à une dimension est souvent représenté comme une suite de cases avec un index pointant sur une case. Algorithmique Licence 2 IRT Année académique 2020-2021 GBEDEVI A. Yvette ESGIS 2 i Formalisation mathématique : Nous avons dit que tous les éléments d’un tableau sont de même nature, ce qui veut dire qu’ils appartiennent à un même ensemble A. Un tableau à une dimension est un n-uplet sur l’ensemble A, donc de la forme (x1,x2,...,xn). L’entier naturel n est appelé la dimension du tableau. L’ensemble des tableaux (à une seule dimension) de dimension n à éléments dans l’ensemble A est donc la puissance cartésienne An = A × A × ... × A. Si x = (x1,x2,...,xn) est un tel tableau, l’élément d’index i, avec i entier naturel compris entre 1 et n, où n est la dimension du tableau, est la i-ième projection de x, à savoir xi = pri(x). 1.1.2. Mise en place d’un tableau à une dimension en C 1.1.2.1. Nom d’un tableau Un tableau (à une dimension) porte un nom qui est, comme d’habitude, un identificateur non déjà utilisé pour autre chose, par exemple tab. Il s’agit plus exactement d’une variable de tableaux. 1.1.2.2. Déclaration d’un tableau Syntaxe : La déclaration d’un tableau suit la syntaxe suivante : type Nom [Entier]; où Type est un type, Nom un identificateur (non utilisé pour autre chose) et Entier une expression constante entière positive. Sémantique Type est le type des élements du tableau, Nom le nom du tableau et Entier le nombre (maximum) d’ éléments du tableau. Exemple : On déclare un tableau tab de cinq réels de la façon suivante : float tab [5]; Algorithmique Licence 2 IRT Année académique 2020-2021 GBEDEVI A. Yvette ESGIS 3 1.1.2.3. Accès à un élément du tableau Syntaxe : L’accès à un élément du tableau de Nom se fait en désignant cet élément de la façon suivante : Nom[index] où index est une expression entière positive. Sémantique : Ceci permet de désigner l’élément du tableau dont l’index est celui désigné. En langage C, comme en général en informatique et contrairement à ce qui se passe en mathématiques, l’indexation commence à 0 (et non à 1). La valeur de l’index doit donc être comprise entre 0 et Entier − 1. Exemple Si on veut accéder au troisième élément du tableau déclaré ci-dessus, donc celui d’index 2, il suffit d’ écrire tab[2]. Ceci conduit à des instructions du genre : tab[3] = 4.5; x = 3*tab[i] + 2*tab[i+5]; à condition, bien sur, que la variable x soit déclarée d’un type convenable et que i et i+5 prennent leurs valeurs parmi les index possibles. Remarque : En langage C, comme dans la plupart des langages informatiques, il n’y a pas de vérification pour savoir si la valeur de l’index est bien comprise entre 0 et Entier − 1. Si on sort de l’intervalle d’indexation, on risque de récupérer des valeurs sans signification (en cas de lecture) ou, pire, de détruire une partie du contenu de la mémoire vive (en cas d’écriture). Il faut donc être extrêmement vigilant à l’ égard de ce problème. Algorithmique Licence 2 IRT Année académique 2020-2021 GBEDEVI A. Yvette ESGIS 4 1.1.3. Exemple Introduction Nous allons traiter un premier exemple montrant l’intérêt de la notion de tableau pour des problèmes de programmation. Le problème suivant est suffisamment courant et exemplaire pour qu’on s’y intéresse. Problème Les élèves d’une classe ont obtenu chacun une note à un certain examen. Nous voulons déterminer combien d’entre eux ont une note supérieure à la moyenne de la classe. 1.1.3.1. Algorithme sans tableau Un premier algorithme Le premier algorithme auquel on peut penser est le suivant : • Demander le nombre n d’élèves ; • Saisir les n notes tout en calculant la somme de ces notes ; • Diviser la somme par n pour obtenir la moyenne de la classe ; • Mettre à zéro le compteur des notes supérieures à la moyenne de la classe ; • Redemander les n notes et comparer chacune d’elles à la moyenne de la classe afin d’incrémenter le compteur des notes supérieures à la moyenne de la classe ; • Afficher le résultat. Exercice 1. Implémenter cet algorithme en langage C Inconvénient de cet algorithme Cet algorithme possède un inconvénient majeur pour l’utilisateur : il faut saisir l’ensemble des notes deux fois. On comprend que l’ordinateur ne peut pas deviner les notes et qu’il faut donc les saisir une fois, mais l’ordinateur ne pourrait-il pas retenir les notes ? Algorithmique Licence 2 IRT Année académique 2020-2021 GBEDEVI A. Yvette ESGIS 5 1.1.3.2. Algorithme avec tableau Un meilleur algorithme : Soit n le nombre d’élèves. On peut : • saisir les n notes et les conserver ; • calculer la moyenne de ces n notes ; • déterminer combien, parmi ces n notes, sont supérieures à la moyenne ainsi obtenue. La notion de tableau est bien adaptée pour conserver les notes. Programme : Ceci nous conduit au programme suivant en supposant qu’il y ait 70 : /* Programme note_1.c */ #include <stdio.h> void main(void) { int i, s; float m; float note[70]; /* Saisie des notes */ for (i=0 ; i < 70 ; i++) { printf("\nQuelle est la note numero %d : ",i+1); scanf("%f", &note[i]); } /* Calcul de la moyenne */ m =0; for (i = 0 ; i < 70 ; i++) m = m + note[i]; m = m/70; printf("\nLa moyenne est de : %4.2f", m); /* Calcul du nombre de notes superieures a la * moyenne */ Algorithmique Licence 2 IRT Année académique 2020-2021 GBEDEVI A. Yvette ESGIS 6 s = 0; for (i = 0 ; i < 70 ; i++) if (note[i] >= m) s = s+1; printf("\nLe nombre de notes superieures a la"); printf("\nmoyenne de la classe est de : %d", s); } Avantage et inconvénient de cet algorithme On voit tout de suite l’avantage de cet algorithme par rapport au précédent pour l’utilisateur. Cependant il présente également un inconvénient (on ne peut pas gagner sur tous les tableaux !, et ce n’est pas que pour faire un jeu de mots) : le nombre d’élèves doit être connu au moment de la programmation alors, que pour le premier algorithme, il était demandé à l’utilisateur. 1.1.4. Dimension maximum et dimension effective Introduction On peut contourner en général l’inconvénient que nous venons de constater pour l’utilisation des tableaux. On déclare une dimension maximum du tableau puis on demande une dimension effective à l’utilisateur, ce qui détermine la partie du tableau réellement utilisée. Exemple : Ceci nous conduit, par exemple, au programme suivant, en supposant qu’il y a au plus 150 élèves par classe : /* Programme note_2.c */ #include <stdio.h> void main(void) { const int max = 150; int n, i, s; float m; float note [max]; /* Determination du nombre effectif d’eleves */ printf("Quel est le nombre d\’eleves ? : "); scanf("%d", &n); Algorithmique Licence 2 IRT Année académique 2020-2021 GBEDEVI A. Yvette ESGIS 7 /* Saisie des notes */ for (i=0; i < n; i++) { printf("\nQuelle est la note numero %d : ",i+1); scanf("%f", &note[i]); } /* Calcul de la moyenne */ m = 0; for (i = 0 ; i < n ; i++) m = m + note[i]; m = m/n; printf("\nLa moyenne est de : %4.2f", m); /* Calcul du nombre de notes superieures a la * moyenne */ s = 0; for (i = 0 ; i < n ; i++) if (note[i] >= m) s = s+1; printf("\nLe nombre de notes superieures uploads/s3/ chapitre4-algo-tableaux.pdf