Chapitre 8 — Tableaux à une dimension
Organiser, parcourir et transformer une collection homogène de données
Fiche pédagogique du chapitre
Objectifs d’apprentissage
À la fin de ce chapitre, l’étudiant devra être capable de :
- définir un tableau à une dimension et expliquer son intérêt ;
- distinguer la taille, la capacité, l’indice et la valeur d’un élément ;
- déclarer et initialiser un tableau de valeurs de même type ;
- remplir et afficher un tableau à l’aide d’une boucle ;
- réaliser un parcours complet, partiel ou inverse ;
- modifier un élément en utilisant son indice ;
- calculer une somme, une moyenne, un minimum ou un maximum ;
- compter et rechercher des éléments selon un critère ;
- copier et inverser un tableau ;
- insérer ou supprimer un élément en effectuant les décalages nécessaires ;
- tester les cas particuliers, notamment le tableau vide et le tableau contenant un seul élément.
Prérequis
- maîtriser les variables, les types de données et les affectations ;
- savoir utiliser les structures conditionnelles ;
- maîtriser les boucles Pour, TantQue et Répéter…Jusqu’à ;
- savoir construire une table de trace et tester un algorithme ;
- connaître les opérateurs arithmétiques, relationnels et logiques.
Plan du chapitre
8.1 Définition d’un tableau
8.2 Déclaration et initialisation
8.3 Parcours d’un tableau
8.4 Traitements classiques
8.5 Décalage et insertion
Applications, exercices, corrigés et synthèse
Organisation pédagogique indicative
Activité | Durée indicative | Objectif principal |
|---|---|---|
| Cours | 3 h | Présenter la représentation, les parcours et les traitements classiques. |
| Travaux dirigés | 3 h | Écrire et tracer des algorithmes manipulant des tableaux. |
| Travaux pratiques | 3 h | Implémenter les traitements et vérifier les cas limites. |
| Travail personnel | 2 h | Résoudre des exercices de recherche, d’inversion, d’insertion et de suppression. |
| Idée centrale : un tableau permet de regrouper plusieurs valeurs de même type sous un seul nom. Chaque valeur reste accessible individuellement grâce à un indice. |
Introduction aux tableaux à une dimension
Jusqu’à présent, une variable permettait de mémoriser une seule valeur. Pour stocker les notes de trente étudiants avec des variables simples, il faudrait déclarer trente noms différents, puis répéter les mêmes instructions pour chaque note. Cette organisation devient rapidement lourde, difficile à modifier et propice aux erreurs.
Un tableau à une dimension répond à ce problème. Il rassemble une suite ordonnée de valeurs de même type dans une structure unique. Une boucle peut ensuite traiter automatiquement tous les éléments, quelle que soit la taille du tableau. Cette association entre tableau et boucle constitue l’un des outils fondamentaux de l’algorithmique.
| Convention utilisée dans ce chapitre : les indices commencent à 1 et se terminent à N. Certains langages de programmation, notamment Python, C et Java, commencent les indices à 0. Lors de la traduction, il faut adapter les bornes des boucles. |
8.1 Définition d’un tableau
8.1.1 Ensemble de valeurs de même type
Un tableau à une dimension est une structure de données composée d’un nombre déterminé de cases disposées dans un ordre linéaire. Toutes les cases contiennent des valeurs appartenant au même type : entier, réel, booléen, caractère, chaîne de caractères ou autre type défini.
Le tableau possède un nom unique. Pour accéder à une case particulière, on associe ce nom à un indice. Par exemple, Notes[3] désigne la troisième note du tableau Notes.
Indice | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Valeur de Notes | 12 | 15,5 | 9 | 18 | 14 |
Dans cet exemple, Notes est un tableau de cinq réels. Notes[1] vaut 12, Notes[3] vaut 9 et Notes[5] vaut 14.
8.1.2 Taille du tableau
La taille d’un tableau correspond au nombre de cases qu’il contient. Elle est souvent notée N. Dans de nombreux contextes, cette taille est fixée au moment de la déclaration et ne change pas pendant l’exécution.
- Taille physique ou capacité : nombre maximal de cases réservées en mémoire.
- Taille logique : nombre de cases qui contiennent actuellement des données utiles.
- Tableau plein : la taille logique est égale à la capacité.
- Tableau vide : la taille logique est égale à zéro.
| Exemple : un tableau peut avoir une capacité de 100 étudiants, tout en ne contenant que 27 étudiants à un instant donné. Sa capacité vaut 100 et sa taille logique vaut 27. |
8.1.3 Indice
L’indice est un entier qui indique la position d’un élément dans le tableau. Avec la convention adoptée dans ce cours, les indices valides sont compris entre 1 et N inclus.
Expression | Signification | Validité pour N = 5 |
|---|---|---|
| T[1] | Premier élément du tableau | Valide |
| T[5] | Dernier élément du tableau | Valide |
| T[0] | Case avant le premier élément selon notre convention | Invalide |
| T[6] | Case après le dernier élément | Invalide |
| T[i] | Élément situé à la position contenue dans i | Valide seulement si 1 ≤ i ≤ 5 |
| Erreur fréquente : confondre l’indice avec la valeur. Dans Notes[3] = 9, le nombre 3 représente la position et le nombre 9 représente la valeur stockée. |
8.1.4 Accès à un élément
L’accès à un élément peut être effectué pour lire sa valeur ou pour la modifier. L’expression T[i] peut donc apparaître à droite ou à gauche d’une affectation.
Exemples d’accès
| x <- T[4] // lire la quatrième valeur T[2] <- 25 // remplacer la deuxième valeur par 25 T[i] <- T[i] + 1 // augmenter l’élément d’indice i |
L’accès direct à une case est rapide : l’algorithme n’a pas besoin de parcourir les éléments précédents pour atteindre T[i]. Il doit cependant vérifier que l’indice appartient bien au domaine valide.
8.1.5 Représentation en mémoire
Les cases d’un tableau sont généralement stockées dans des zones mémoire consécutives. Chaque case occupe un espace adapté au type des valeurs. Le système peut ainsi calculer l’adresse d’une case à partir de l’adresse de départ, de l’indice et de la taille d’un élément.
Pour l’apprentissage de l’algorithmique, il n’est pas nécessaire de calculer ces adresses. Il faut néanmoins retenir qu’un tableau réserve plusieurs emplacements et qu’un accès hors limites peut provoquer une erreur d’exécution ou un comportement imprévisible dans certains langages.
8.1.6 Tableau et variables simples
Critère | Variables simples | Tableau |
|---|---|---|
| Nombre de noms | Un nom par valeur | Un seul nom pour toute la collection |
| Type des valeurs | Peut varier d’une variable à l’autre | Identique pour toutes les cases |
| Traitement répétitif | Instructions souvent répétées | Boucle naturelle sur les indices |
| Accès | Par le nom de la variable | Par le nom et un indice |
| Adaptation à N valeurs | Peu pratique lorsque N augmente | Très adaptée |
8.2 Déclaration et initialisation
8.2.1 Déclaration d’un tableau
La déclaration précise le nom du tableau, le type de ses éléments et sa taille ou sa capacité. La syntaxe exacte varie selon les langages. En pseudo-code, on peut utiliser la forme suivante :
Forme générale
| Variables T : Tableau[1..N] d’Entiers Notes : Tableau[1..30] de Réels Noms : Tableau[1..20] de Chaînes |
La déclaration réserve les cases, mais elle ne garantit pas que chaque case contient déjà une valeur utile. Selon le contexte, il faut initialiser explicitement les éléments avant de les utiliser.
8.2.2 Initialisation complète
Initialiser un tableau consiste à attribuer une valeur connue à ses éléments. L’initialisation peut être réalisée lors de la déclaration, par une série d’affectations ou à l’aide d’une boucle.
Initialisation par affectations
| T[1] <- 4 T[2] <- 7 T[3] <- 2 T[4] <- 9 |
Initialisation uniforme à zéro
| Pour i allant de 1 à N Faire T[i] <- 0 FinPour | |
| Pourquoi initialiser ? une case non initialisée peut contenir une valeur indéterminée. Toute somme, comparaison ou recherche fondée sur cette valeur devient incorrecte. |
8.2.3 Remplissage manuel
Le remplissage manuel consiste à demander séparément chaque valeur à l’utilisateur. Cette méthode est acceptable pour un très petit tableau, mais elle devient rapidement répétitive.
Remplissage sans boucle
| Lire(T[1]) Lire(T[2]) Lire(T[3]) |
L’utilisation d’une boucle rend l’algorithme plus court, plus général et plus facile à adapter à une autre taille.
8.2.4 Remplissage à l’aide d’une boucle
| Algorithme Remplir_Tableau Variables T : Tableau[1..N] d’Entiers i : Entier Début Pour i allant de 1 à N Faire Écrire("Saisir l’élément " , i, " :") Lire(T[i]) FinPour Fin |
À chaque itération, i prend un nouvel indice valide. La valeur lue est placée dans la case correspondante. Le même bloc d’instructions fonctionne pour toute taille N positive.
Itération | i | Valeur saisie | Case modifiée |
|---|---|---|---|
| 1 | 1 | 8 | T[1] devient 8 |
| 2 | 2 | 5 | T[2] devient 5 |
| 3 | 3 | 11 | T[3] devient 11 |
| 4 | 4 | 6 | T[4] devient 6 |
8.2.5 Validation pendant le remplissage
Chaque valeur peut être contrôlée avant son stockage. Pour des notes, on répète la saisie tant que la valeur n’est pas comprise entre 0 et 20.
| Pour i allant de 1 à N Faire Répéter Écrire("Note " , i, " :") Lire(T[i]) Si T[i] < 0 OU T[i] > 20 Alors Écrire("La note doit être comprise entre 0 et 20.") FinSi Jusqu’à T[i] >= 0 ET T[i] <= 20 FinPour |
8.2.6 Affichage des éléments
L’affichage d’un tableau est également réalisé par un parcours. Il est utile d’afficher l’indice avec la valeur afin de rendre la lecture plus claire.
| Pour i allant de 1 à N Faire Écrire("T[", i, "] = ", T[i]) FinPour |
Affichage compact | Affichage détaillé |
|---|---|
| 8 5 11 6 | T[1] = 8 |
| — | T[2] = 5 |
| — | T[3] = 11 |
| — | T[4] = 6 |
8.2.7 Taille saisie par l’utilisateur
Lorsque la capacité maximale est fixée mais que le nombre réel d’éléments varie, on demande une taille logique N comprise entre 0 et la capacité maximale.
| Constantes CAPACITE <- 100 Variables T : Tableau[1..CAPACITE] d’Entiers N : Entier Début Répéter Lire(N) Jusqu’à N >= 0 ET N <= CAPACITE // Les éléments utiles seront T[1] à T[N] Fin |
8.3 Parcours d’un tableau
8.3.1 Principe du parcours
Parcourir un tableau signifie visiter successivement certaines de ses cases afin de lire, afficher, tester ou modifier leurs valeurs. Le parcours est généralement contrôlé par une variable entière utilisée comme indice.
Avant d’écrire la boucle, il faut répondre à trois questions : quel est le premier indice à traiter, quel est le dernier indice et dans quel sens les indices évoluent-ils ?
8.3.2 Parcours complet
Un parcours complet visite chaque élément exactement une fois. Il est utilisé pour afficher le tableau, calculer une somme, rechercher un maximum ou compter les valeurs répondant à un critère.
Schéma général
| Pour i allant de 1 à N Faire Traiter(T[i]) FinPour | |
| Invariant utile : au début de l’itération d’indice i, les éléments T[1] à T[i − 1] ont déjà été traités, tandis que T[i] à T[N] restent à traiter. |
8.3.3 Parcours partiel
Un parcours partiel ne visite qu’une portion du tableau. Les bornes peuvent être fixes ou calculées à partir d’un besoin particulier.
Parcours d’un intervalle d’indices
| // Traiter les éléments des positions debut à fin Pour i allant de debut à fin Faire Traiter(T[i]) FinPour |
- parcourir les cinq premiers éléments : indices 1 à 5 ;
- ignorer le premier élément : indices 2 à N ;
- traiter une sous-partie : indices debut à fin ;
- parcourir les éléments d’indice pair : utiliser un pas égal à 2 ;
- s’arrêter dès qu’une valeur recherchée est trouvée.
Éléments dont l’indice est pair
| Pour i allant de 2 à N avec un pas de 2 Faire Écrire(T[i]) FinPour |
8.3.4 Parcours dans l’ordre inverse
Le parcours inverse commence au dernier élément et se termine au premier. Il utilise une décrémentation ou un pas négatif.
| Pour i allant de N à 1 avec un pas de -1 Faire Écrire(T[i]) FinPour |
Ce parcours est utile pour afficher les valeurs à l’envers, pour décaler des éléments vers la droite sans les écraser ou pour rechercher la dernière occurrence d’une valeur.
8.3.5 Modification d’un élément
Une modification remplace la valeur stockée dans une case. Si la position est fournie par l’utilisateur, elle doit être validée avant l’affectation.
| Répéter Écrire("Position à modifier :") Lire(position) Jusqu’à position >= 1 ET position <= N Écrire("Nouvelle valeur :") Lire(nouvelleValeur) T[position] <- nouvelleValeur |
8.3.6 Modification de plusieurs éléments
Une boucle peut transformer toutes les valeurs du tableau. L’ancienne valeur est lue, un calcul est effectué, puis le résultat est réaffecté dans la même case.
| // Ajouter 1 à chaque élément Pour i allant de 1 à N Faire T[i] <- T[i] + 1 FinPour |
Indice | Valeur avant | Calcul | Valeur après |
|---|---|---|---|
| 1 | 4 | 4 + 1 | 5 |
| 2 | -2 | -2 + 1 | -1 |
| 3 | 0 | 0 + 1 | 1 |
| 4 | 9 | 9 + 1 | 10 |
8.3.7 Erreurs fréquentes de parcours
Erreur | Conséquence | Correction |
|---|---|---|
| Commencer à 0 avec une convention 1..N | Accès hors limites | Commencer à 1. |
| Terminer à N + 1 | Accès après la dernière case | Terminer à N. |
| Utiliser T[N] à chaque itération | Toujours traiter la même case | Utiliser T[i]. |
| Oublier le pas négatif dans un parcours inverse | Boucle incorrecte ou vide | Décrémenter i. |
| Modifier l’indice à l’intérieur d’une boucle Pour | Positions sautées ou répétées | Laisser la boucle gérer l’indice. |
8.4 Traitements classiques
8.4.1 Somme des éléments
La somme est calculée avec un accumulateur initialisé à zéro, qui est l’élément neutre de l’addition.
| somme <- 0 Pour i allant de 1 à N Faire somme <- somme + T[i] FinPour |
i | T[i] | somme avant | somme après |
|---|---|---|---|
| 1 | 5 | 0 | 5 |
| 2 | 8 | 5 | 13 |
| 3 | 2 | 13 | 15 |
| 4 | 7 | 15 | 22 |
8.4.2 Moyenne
La moyenne arithmétique est égale à la somme divisée par le nombre d’éléments. Le tableau doit contenir au moins un élément, car la division par zéro est impossible.
| Si N > 0 Alors somme <- 0 Pour i allant de 1 à N Faire somme <- somme + T[i] FinPour moyenne <- somme / N Écrire(moyenne) Sinon Écrire("Moyenne impossible : tableau vide.") FinSi | |
| Type du résultat : même lorsque le tableau contient des entiers, la moyenne peut être réelle. La variable moyenne doit donc être de type Réel. |
8.4.3 Minimum
Pour chercher le minimum, on initialise la variable minimum avec le premier élément du tableau, puis on compare les éléments restants. Cette initialisation fonctionne aussi lorsque toutes les valeurs sont négatives.
| Si N > 0 Alors minimum <- T[1] Pour i allant de 2 à N Faire Si T[i] < minimum Alors minimum <- T[i] FinSi FinPour FinSi | |
| Erreur fréquente : initialiser minimum à zéro. Si toutes les valeurs sont positives, zéro serait annoncé comme minimum alors qu’il n’appartient pas au tableau. |
8.4.4 Maximum et position du maximum
La recherche du maximum suit la même logique. On peut également mémoriser la position du meilleur élément.
| maximum <- T[1] positionMax <- 1 Pour i allant de 2 à N Faire Si T[i] > maximum Alors maximum <- T[i] positionMax <- i FinSi FinPour |
Avec la comparaison stricte >, la position mémorisée correspond à la première occurrence du maximum. Pour obtenir la dernière occurrence, on peut utiliser >=.
8.4.5 Comptage
Compter consiste à augmenter un compteur lorsque la valeur courante satisfait une condition.
Nombre de valeurs paires
| compteur <- 0 Pour i allant de 1 à N Faire Si T[i] MOD 2 = 0 Alors compteur <- compteur + 1 FinSi FinPour |
- compter les valeurs positives ;
- compter les notes supérieures ou égales à 10 ;
- compter les occurrences d’une valeur donnée ;
- compter les éléments appartenant à un intervalle ;
- compter les changements entre deux éléments consécutifs.
8.4.6 Recherche séquentielle
La recherche séquentielle examine les éléments dans l’ordre jusqu’à trouver la valeur recherchée ou atteindre la fin du tableau. Elle ne nécessite pas que le tableau soit trié.
| i <- 1 TantQue i <= N ET T[i] <> valeurRecherchee Faire i <- i + 1 FinTantQue Si i <= N Alors Écrire("Valeur trouvée à la position ", i) Sinon Écrire("Valeur absente") FinSi |
L’ordre des deux sous-conditions est important dans les langages utilisant une évaluation de gauche à droite avec arrêt anticipé : il faut d’abord vérifier i <= N avant de lire T[i].
8.4.7 Recherche de toutes les occurrences
| nombreOccurrences <- 0 Pour i allant de 1 à N Faire Si T[i] = valeurRecherchee Alors nombreOccurrences <- nombreOccurrences + 1 Écrire("Occurrence à la position ", i) FinSi FinPour |
8.4.8 Copie d’un tableau
Une copie élément par élément crée un second tableau indépendant. Modifier la copie ne doit pas modifier l’original dans le modèle algorithmique présenté ici.
| Pour i allant de 1 à N Faire Copie[i] <- T[i] FinPour |
Étape | Original | Copie |
|---|---|---|
| Avant la copie | [4, 7, 1] | [?, ?, ?] |
| Après la copie | [4, 7, 1] | [4, 7, 1] |
| Après Copie[2] <- 99 | [4, 7, 1] | [4, 99, 1] |
8.4.9 Inversion d’un tableau
Inverser un tableau signifie placer le premier élément à la dernière position, le deuxième à l’avant-dernière, et ainsi de suite. Deux méthodes sont possibles.
La première méthode crée un second tableau :
| Pour i allant de 1 à N Faire Inverse[i] <- T[N - i + 1] FinPour |
La seconde méthode inverse le tableau sur place en échangeant les éléments symétriques. Seule la première moitié doit être parcourue.
| Pour i allant de 1 à N DIV 2 Faire temporaire <- T[i] T[i] <- T[N - i + 1] T[N - i + 1] <- temporaire FinPour |
Échange | Tableau après l’échange |
|---|---|
| Initial | [2, 5, 8, 1, 9] |
| Positions 1 et 5 | [9, 5, 8, 1, 2] |
| Positions 2 et 4 | [9, 1, 8, 5, 2] |
| Résultat final | [9, 1, 8, 5, 2] |
8.4.10 Combiner plusieurs traitements
Un seul parcours peut calculer plusieurs informations afin d’éviter des lectures répétées. Par exemple, il est possible de calculer simultanément la somme, le minimum, le maximum et le nombre de valeurs positives.
| somme <- 0 minimum <- T[1] maximum <- T[1] nbPositifs <- 0 Pour i allant de 1 à N Faire somme <- somme + T[i] Si T[i] < minimum Alors minimum <- T[i] FinSi Si T[i] > maximum Alors maximum <- T[i] FinSi Si T[i] > 0 Alors nbPositifs <- nbPositifs + 1 FinSi FinPour |
8.5 Décalage et insertion
8.5.1 Pourquoi décaler les éléments ?
Dans un tableau de taille fixe, les cases sont ordonnées et contiguës. Pour insérer une valeur au milieu, il faut libérer une case en déplaçant les éléments situés à droite de la position. Pour supprimer une valeur, il faut combler le vide en déplaçant les éléments suivants vers la gauche.
Ces opérations utilisent une taille logique N et une capacité maximale CAPACITE. Elles sont possibles seulement si les conditions nécessaires sont respectées.
8.5.2 Insertion d’un élément
Pour insérer une valeur à la position p, le tableau ne doit pas être plein et la position doit appartenir à l’intervalle [1, N + 1]. La position N + 1 correspond à un ajout en fin de tableau.
- Vérifier que N est strictement inférieur à CAPACITE.
- Vérifier que 1 ≤ p ≤ N + 1.
- Décaler vers la droite les éléments des positions p à N.
- Placer la nouvelle valeur dans T[p].
- Augmenter la taille logique N de 1.
| Si N = CAPACITE Alors Écrire("Insertion impossible : tableau plein.") SinonSi p < 1 OU p > N + 1 Alors Écrire("Position invalide.") Sinon Pour i allant de N à p avec un pas de -1 Faire T[i + 1] <- T[i] FinPour T[p] <- valeur N <- N + 1 FinSi | |
| Sens du décalage : le déplacement doit commencer par la fin. Un parcours de gauche à droite écraserait des valeurs avant leur copie. |
Étape | Tableau utile | N |
|---|---|---|
| Avant insertion | [10, 20, 30, 40] | 4 |
| Décaler 40 vers la position 5 | [10, 20, 30, 40, 40] | 4 |
| Décaler 30 vers la position 4 | [10, 20, 30, 30, 40] | 4 |
| Insérer 25 à la position 3 | [10, 20, 25, 30, 40] | 5 |
8.5.3 Suppression d’un élément
Pour supprimer l’élément situé à la position p, le tableau doit contenir au moins un élément et p doit appartenir à [1, N]. Les éléments placés après p sont décalés d’une case vers la gauche.
| Si N = 0 Alors Écrire("Suppression impossible : tableau vide.") SinonSi p < 1 OU p > N Alors Écrire("Position invalide.") Sinon valeurSupprimee <- T[p] Pour i allant de p à N - 1 Faire T[i] <- T[i + 1] FinPour N <- N - 1 Écrire("Valeur supprimée : ", valeurSupprimee) FinSi |
Étape | Tableau utile | N |
|---|---|---|
| Avant suppression | [10, 20, 25, 30, 40] | 5 |
| Copier T[4] dans T[3] | [10, 20, 30, 30, 40] | 5 |
| Copier T[5] dans T[4] | [10, 20, 30, 40, 40] | 5 |
| Après diminution de N | [10, 20, 30, 40] | 4 |
8.5.4 Décalage vers la droite
Le décalage vers la droite copie chaque élément dans la case suivante. Il est effectué en ordre décroissant pour préserver les valeurs non encore déplacées.
| Pour i allant de N à p avec un pas de -1 Faire T[i + 1] <- T[i] FinPour |
8.5.5 Décalage vers la gauche
Le décalage vers la gauche copie chaque élément suivant dans la case courante. Il est effectué en ordre croissant.
| Pour i allant de p à N - 1 Faire T[i] <- T[i + 1] FinPour |
8.5.6 Insertion en début et en fin
Opération | Position | Nombre de déplacements |
|---|---|---|
| Insertion au début | p = 1 | N déplacements |
| Insertion au milieu | 1 < p < N + 1 | N - p + 1 déplacements |
| Insertion en fin | p = N + 1 | Aucun déplacement |
| Suppression au début | p = 1 | N - 1 déplacements |
| Suppression en fin | p = N | Aucun déplacement |
8.5.7 Cas particuliers à tester
- insertion dans un tableau vide ;
- insertion au début, au milieu et à la fin ;
- insertion dans un tableau plein ;
- suppression dans un tableau vide ;
- suppression du premier ou du dernier élément ;
- suppression de l’unique élément ;
- position égale à 0 ou supérieure aux limites autorisées.
Applications guidées
Les applications suivantes réutilisent les schémas fondamentaux du chapitre. Chaque solution précise les cas particuliers à contrôler.
Application 1 — Calculer la moyenne d’une classe
On dispose des notes de N étudiants. Chaque note doit être comprise entre 0 et 20. Le programme remplit le tableau, calcule la somme et affiche la moyenne de la classe.
| Algorithme Moyenne_Classe Constantes CAPACITE <- 100 Variables Notes : Tableau[1..CAPACITE] de Réels N, i : Entiers somme, moyenne : Réels Début Répéter Écrire("Nombre d’étudiants :") Lire(N) Jusqu’à N >= 1 ET N <= CAPACITE somme <- 0 Pour i allant de 1 à N Faire Répéter Écrire("Note de l’étudiant " , i, " :") Lire(Notes[i]) Jusqu’à Notes[i] >= 0 ET Notes[i] <= 20 somme <- somme + Notes[i] FinPour moyenne <- somme / N Écrire("Moyenne de la classe = ", moyenne) Fin |
Notes | Somme | N | Moyenne |
|---|---|---|---|
| [12, 15, 9, 14] | 50 | 4 | 12,5 |
| [20] | 20 | 1 | 20 |
| [0, 0, 0] | 0 | 3 | 0 |
Application 2 — Trouver la meilleure note
Le programme cherche la note maximale et la position du premier étudiant qui l’a obtenue. Le tableau doit contenir au moins une note.
| meilleureNote <- Notes[1] position <- 1 Pour i allant de 2 à N Faire Si Notes[i] > meilleureNote Alors meilleureNote <- Notes[i] position <- i FinSi FinPour Écrire("Meilleure note = ", meilleureNote) Écrire("Premier étudiant concerné = ", position) |
i | Notes[i] | Meilleure avant | Action | Meilleure après |
|---|---|---|---|---|
| 2 | 15 | 12 | 15 > 12, mise à jour | 15 |
| 3 | 9 | 15 | Pas de mise à jour | 15 |
| 4 | 18 | 15 | 18 > 15, mise à jour | 18 |
| 5 | 18 | 18 | Comparaison stricte, position inchangée | 18 |
Application 3 — Compter les notes supérieures à la moyenne
La moyenne doit être connue avant de compter les notes qui lui sont strictement supérieures. Deux parcours sont donc naturellement utilisés : le premier calcule la moyenne et le second réalise le comptage.
| somme <- 0 Pour i allant de 1 à N Faire somme <- somme + Notes[i] FinPour moyenne <- somme / N compteur <- 0 Pour i allant de 1 à N Faire Si Notes[i] > moyenne Alors compteur <- compteur + 1 FinSi FinPour Écrire(compteur, " note(s) au-dessus de la moyenne.") |
Pour Notes = [12, 15, 9, 14], la moyenne vaut 12,5. Les notes 15 et 14 sont strictement supérieures à la moyenne ; le compteur vaut donc 2.
Application 4 — Inverser un tableau
La solution suivante inverse directement le tableau en échangeant les cases symétriques. Elle fonctionne pour une taille paire ou impaire.
| Pour i allant de 1 à N DIV 2 Faire j <- N - i + 1 temporaire <- T[i] T[i] <- T[j] T[j] <- temporaire FinPour |
Entrée | Résultat |
|---|---|
| [1, 2, 3, 4] | [4, 3, 2, 1] |
| [5, 8, 9] | [9, 8, 5] |
| [7] | [7] |
| [] | [] si le cas vide est autorisé |
Application 5 — Séparer les valeurs positives et négatives
On parcourt un tableau T et on place les valeurs strictement positives dans Positifs, les valeurs strictement négatives dans Negatifs et on compte les zéros. Les deux tableaux de sortie possèdent leur propre taille logique.
| nbPos <- 0 nbNeg <- 0 nbZeros <- 0 Pour i allant de 1 à N Faire Si T[i] > 0 Alors nbPos <- nbPos + 1 Positifs[nbPos] <- T[i] SinonSi T[i] < 0 Alors nbNeg <- nbNeg + 1 Negatifs[nbNeg] <- T[i] Sinon nbZeros <- nbZeros + 1 FinSi FinPour |
Tableau initial | Positifs | Négatifs | Nombre de zéros |
|---|---|---|---|
| [-3, 5, 0, -1, 8, 0] | [5, 8] | [-3, -1] | 2 |
| [1, 2, 3] | [1, 2, 3] | [] | 0 |
| [-4, -2] | [] | [-4, -2] | 0 |
| Convention importante : zéro n’est ni strictement positif ni strictement négatif. Il doit être traité séparément ou affecté à un groupe selon une règle explicitement définie. |
Synthèse du chapitre
Règles essentielles à retenir
- un tableau regroupe des valeurs de même type sous un seul nom ;
- chaque élément est repéré par un indice valide ;
- la capacité maximale doit être distinguée de la taille logique ;
- un parcours complet utilise généralement les indices de 1 à N ;
- un tableau vide doit être traité avant une moyenne, un minimum ou un maximum ;
- une somme commence à zéro, tandis qu’un minimum ou un maximum commence généralement au premier élément ;
- une recherche peut s’arrêter dès la première occurrence ou continuer pour toutes les occurrences ;
- l’inversion sur place échange uniquement les éléments de la première moitié avec leurs symétriques ;
- une insertion décale les valeurs vers la droite en commençant par la fin ;
- une suppression décale les valeurs vers la gauche en commençant par la position supprimée ;
- toute position fournie par l’utilisateur doit être validée avant l’accès au tableau.
Schémas algorithmiques réutilisables
Besoin | Initialisation | Traitement dans la boucle |
|---|---|---|
| Somme | somme <- 0 | somme <- somme + T[i] |
| Comptage | compteur <- 0 | Si critère Alors compteur <- compteur + 1 |
| Minimum | minimum <- T[1] | Si T[i] < minimum Alors mise à jour |
| Maximum | maximum <- T[1] | Si T[i] > maximum Alors mise à jour |
| Recherche | i <- 1 ou trouve <- Faux | Comparer T[i] à la valeur recherchée |
| Copie | Tableau destination réservé | Destination[i] <- Source[i] |
Checklist avant de valider un algorithme sur les tableaux
- les indices de départ et de fin sont-ils corrects ? ;
- le cas N = 0 est-il possible et correctement traité ? ;
- le cas N = 1 fonctionne-t-il ? ;
- chaque case utilisée a-t-elle été initialisée ? ;
- la position d’insertion ou de suppression est-elle valide ? ;
- la capacité est-elle suffisante avant une insertion ? ;
- le sens du décalage évite-t-il l’écrasement des données ? ;
- le type du résultat est-il adapté, notamment pour une moyenne ?
Travaux dirigés
Exercice 1 — Représenter un tableau
Représenter le tableau T = [7, 2, 9, 4, 6] avec les indices 1 à 5. Donner T[1], T[4] et la valeur de l’indice i lorsque T[i] = 9.
Exercice 2 — Remplissage et affichage
Écrire un algorithme qui demande N entiers, les stocke dans un tableau puis les affiche dans l’ordre de saisie avec leur indice.
Exercice 3 — Parcours inverse
Écrire un algorithme qui affiche un tableau de N valeurs dans l’ordre inverse sans modifier le tableau.
Exercice 4 — Somme et moyenne
Écrire un algorithme qui calcule la somme et la moyenne d’un tableau de réels. Traiter explicitement le cas du tableau vide.
Exercice 5 — Minimum et maximum
Écrire un seul parcours qui détermine le minimum, le maximum et leurs premières positions dans un tableau non vide.
Exercice 6 — Comptages multiples
Compter dans un tableau d’entiers les valeurs positives, négatives, nulles, paires et impaires. Préciser le traitement de zéro pour la parité.
Exercice 7 — Recherche
Écrire un algorithme qui lit une valeur x, recherche sa première occurrence et affiche sa position ou un message d’absence.
Exercice 8 — Toutes les occurrences
Modifier l’exercice précédent afin d’afficher toutes les positions de x et le nombre total d’occurrences.
Exercice 9 — Copie sélective
Copier dans un second tableau uniquement les valeurs de T qui sont supérieures ou égales à 10. Gérer la taille logique du tableau résultat.
Exercice 10 — Rotation à droite
Décaler circulairement les éléments d’une position vers la droite : le dernier élément devient le premier. Exemple : [1, 2, 3, 4] devient [4, 1, 2, 3].
Exercice 11 — Insertion
Écrire un algorithme qui insère une valeur à une position p dans un tableau disposant d’une capacité suffisante. Contrôler la position et la capacité.
Exercice 12 — Suppression
Écrire un algorithme qui supprime la première occurrence d’une valeur x. Si x est absente, le tableau reste inchangé.
Corrigé indicatif des travaux dirigés
Corrigé de l’exercice 1
Indice | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| T | 7 | 2 | 9 | 4 | 6 |
T[1] = 7, T[4] = 4 et l’indice recherché vaut i = 3.
Corrigé de l’exercice 2
| Pour i allant de 1 à N Faire Lire(T[i]) FinPour Pour i allant de 1 à N Faire Écrire("T[", i, "] = ", T[i]) FinPour |
Corrigé de l’exercice 3
| Pour i allant de N à 1 avec un pas de -1 Faire Écrire(T[i]) FinPour |
Le tableau n’est pas modifié : seul l’ordre d’accès aux cases change.
Corrigé de l’exercice 4
| Si N = 0 Alors Écrire("Tableau vide : moyenne non définie.") Sinon somme <- 0 Pour i allant de 1 à N Faire somme <- somme + T[i] FinPour moyenne <- somme / N Écrire(somme, moyenne) FinSi |
Corrigé de l’exercice 5
| minimum <- T[1] maximum <- T[1] posMin <- 1 posMax <- 1 Pour i allant de 2 à N Faire Si T[i] < minimum Alors minimum <- T[i] posMin <- i FinSi Si T[i] > maximum Alors maximum <- T[i] posMax <- i FinSi FinPour |
Corrigé de l’exercice 6
| nbPos <- 0 nbNeg <- 0 nbNuls <- 0 nbPairs <- 0 nbImpairs <- 0 Pour i allant de 1 à N Faire Si T[i] > 0 Alors nbPos <- nbPos + 1 SinonSi T[i] < 0 Alors nbNeg <- nbNeg + 1 Sinon nbNuls <- nbNuls + 1 FinSi Si T[i] MOD 2 = 0 Alors nbPairs <- nbPairs + 1 Sinon nbImpairs <- nbImpairs + 1 FinSi FinPour |
Zéro est une valeur paire, car 0 MOD 2 = 0.
Corrigé de l’exercice 7
| i <- 1 TantQue i <= N ET T[i] <> x Faire i <- i + 1 FinTantQue Si i <= N Alors Écrire("Première occurrence à la position ", i) Sinon Écrire("Valeur absente") FinSi |
Corrigé de l’exercice 8
| occurrences <- 0 Pour i allant de 1 à N Faire Si T[i] = x Alors occurrences <- occurrences + 1 Écrire(i) FinSi FinPour Écrire("Nombre d’occurrences : ", occurrences) |
Corrigé de l’exercice 9
| M <- 0 Pour i allant de 1 à N Faire Si T[i] >= 10 Alors M <- M + 1 R[M] <- T[i] FinSi FinPour |
M représente la taille logique du tableau résultat R.
Corrigé de l’exercice 10
| Si N > 1 Alors dernier <- T[N] Pour i allant de N - 1 à 1 avec un pas de -1 Faire T[i + 1] <- T[i] FinPour T[1] <- dernier FinSi |
Corrigé de l’exercice 11
| Si N < CAPACITE ET p >= 1 ET p <= N + 1 Alors Pour i allant de N à p avec un pas de -1 Faire T[i + 1] <- T[i] FinPour T[p] <- valeur N <- N + 1 Sinon Écrire("Insertion impossible.") FinSi |
Corrigé de l’exercice 12
| p <- 1 TantQue p <= N ET T[p] <> x Faire p <- p + 1 FinTantQue Si p <= N Alors Pour i allant de p à N - 1 Faire T[i] <- T[i + 1] FinPour N <- N - 1 Sinon Écrire("Valeur absente : aucune suppression.") FinSi |
Glossaire
Terme | Définition |
|---|---|
| Tableau | Structure contenant une suite ordonnée de valeurs de même type. |
| Élément | Valeur stockée dans une case du tableau. |
| Indice | Entier qui identifie la position d’un élément. |
| Capacité | Nombre maximal de cases disponibles. |
| Taille logique | Nombre de cases actuellement utilisées. |
| Parcours | Visite successive de tout ou partie des éléments. |
| Accumulateur | Variable qui rassemble progressivement un résultat, par exemple une somme. |
| Occurrence | Présence d’une valeur à une position donnée. |
| Décalage | Déplacement d’un ensemble d’éléments vers la droite ou vers la gauche. |
| Inversion sur place | Réorganisation inverse réalisée dans le tableau original sans second tableau. |
Auto-évaluation
Répondre par « Oui », « Partiellement » ou « Non » aux affirmations suivantes :
Compétence | Oui | Partiellement | Non |
|---|---|---|---|
| Je sais définir un tableau, sa taille et ses indices. | ☐ | ☐ | ☐ |
| Je sais déclarer, remplir et afficher un tableau. | ☐ | ☐ | ☐ |
| Je sais réaliser un parcours complet, partiel et inverse. | ☐ | ☐ | ☐ |
| Je sais vérifier qu’un indice est valide. | ☐ | ☐ | ☐ |
| Je sais calculer une somme et une moyenne. | ☐ | ☐ | ☐ |
| Je sais rechercher un minimum et un maximum. | ☐ | ☐ | ☐ |
| Je sais compter et rechercher des valeurs. | ☐ | ☐ | ☐ |
| Je sais copier et inverser un tableau. | ☐ | ☐ | ☐ |
| Je sais insérer un élément sans écraser les données. | ☐ | ☐ | ☐ |
| Je sais supprimer un élément et mettre à jour la taille logique. | ☐ | ☐ | ☐ |
| Objectif de maîtrise : être capable de reconnaître le schéma de parcours approprié, de choisir une initialisation correcte et de traiter les limites du tableau sans accès invalide. |