Tableaux
Introduit| English | Sens |
|---|---|
| array/əˈreɪ/ | tableau |
| element/ˈelɪmənt/ | élément |
| index/ˈɪndeks/ | indice |
| lower bound/ˈləʊə baʊnd/ | borne inférieure |
| upper bound/ˈʌpə baʊnd/ | borne supérieure |
| dimension/daɪˈmenʃn/ | dimension |
| nested loops/ˈnestɪd luːps/ | boucles imbriquées |
| linear search/ˈlɪnɪə sɜːtʃ/ | recherche linéaire |
| bubble sort/ˈbʌbl sɔːt/ | tri à bulles |
Siège 14C
- Un cinéma possède 300 places. Son système de réservation n'utilise pas 300 variables nommées
Seat1A,Seat1B,Seat1C. Il utilise un seul tableau, et votre billet est une adresse vers celui-ci : rangée 14, place C. - Un nom, des centaines de valeurs, chacune trouvée par un nombre. Ajoutez une rangée et le code ne change pas ; bouclez sur les nombres et vous avez vérifié chaque place.
- Presque tout algorithme Paper 2 parcourt un tableau : le cherche, le somme, le trie, trouve sa plus grande valeur.
- Cette leçon est le vocabulaire, les déclarations et les quatre algorithmes demandés par l'examinateur en pseudocode et en mots.
Le vocabulaire
- Un tableau est une structure de données contenant un nombre fixe d'éléments du même type de données sous un identificateur unique, chacun étant accessible par un index.
- La borne inférieure et la borne supérieure sont le premier et le dernier index valide. Le nombre d'éléments est borne supérieure − borne inférieure + 1.
- La dimension est le nombre d'indices nécessaires à un élément : un pour une liste, deux pour une table.
- Dans
ThisArray[n] ← 42le tableau a une dimension, l'index est la variableINTEGERn, et l'élément à cet index reçoit42.

Un identifiant, un index pour chaque élément, des bornes aux deux extrémités
Un tableau stocke :
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Un tableau est une collection ordonnée d'éléments de même type accédés par index. (Un enregistrement regroupe des types différents.)
Un tableau est une structure de données contenant de nombreuses valeurs du type ______ sous un même nom.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Chaque valeur est accessible par son index.
DECLARE Marks : ARRAY[0:99] OF INTEGER déclare un tableau de ____ éléments.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Borne supérieure moins borne inférieure plus un : 99 − 0 + 1 = 100. Les deux bornes sont des indices valides.
Exemple résolu : déclarer le tableau dont une tâche a besoin
- Une déclaration nécessite l'identifiant, les bornes et le type de données.
- 120 relevés pouvant avoir une décimale :
DECLARE Data : ARRAY[1:120] OF REAL - Un tableau de 150 lignes et deux colonnes de texte :
DECLARE Names : ARRAY[1:150, 1:2] OF STRING - Dites le compte si on vous le demande :
[0:99]contient 100 éléments, pas 99.
Quelle déclaration contient un tableau de 150 lignes et 2 colonnes de texte ?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Deux dimensions, chacune avec une borne inférieure et supérieure, et le type d'élément. La deuxième option est une longue liste ; la troisième n'a pas de type ; la quatrième n'a pas de bornes inférieures.
Traitement d'un tableau 1-D
DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"
FOR i ← 1 TO 5
OUTPUT Names[i]
NEXT i
- Une boucle
FORde la borne inférieure à la borne supérieure visite chaque élément une fois. - Pour une somme, un compte, un maximum ou un minimum, initialisez une variable avant la boucle et mettez-la à jour dedans.
Tableaux 2-D
DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99 // row 2, column 3
- Le premier index est la ligne, le second la colonne. Les boucles imbriquées visitent chaque case : la boucle extérieure sur les lignes, l'intérieure sur les colonnes.
- Utilisez 1-D pour une séquence unique et 2-D lorsque les données ont deux dimensions naturelles, comme une grille de sièges ou un tableau de notes par élève et matière.

Grid[row, column], toujours dans cet ordre
Indexez un tableau 2D par [ligne, colonne]
Un tableau 2D est une grille. Grid[ligne, colonne] accède exactement à une cellule — changez la ligne et la colonne pour voir quelle valeur vous atterrissez.
Dans Grid[2, 3], quelle cellule est accédée ?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Le premier index est la ligne, le second la colonne — donc ligne 2, colonne 3.
Exemple résolu : une recherche linéaire capable de dire "non trouvé"
- Une recherche linéaire examine chaque élément successivement, du premier au dernier, jusqu'à ce que la cible soit trouvée ou l'extrémité atteinte.
FoundAt ← -1
FOR i ← 1 TO n
IF A[i] = Target THEN
FoundAt ← i
ENDIF
NEXT i
IF FoundAt = -1 THEN
OUTPUT "Not found"
ELSE
OUTPUT "Found at ", FoundAt
ENDIF
-1ne peut jamais être un index valide, donc cela signifie "non trouvé". Initialisez-le avant la boucle et testez-le après. Une recherche qui ne dit jamais "non trouvé" perd une marque.
Une recherche linéaire trouve une valeur en :
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Une recherche linéaire examine les éléments un par un depuis le début jusqu'à trouver la cible (ou atteindre la fin).
Définir FoundAt à -1 avant une recherche linéaire permet au programme de signaler « non trouvé » après la boucle.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
-1 n'est jamais un index valide, donc s'il reste inchangé après la boucle, la cible n'était pas dans le tableau.
Plus grande valeur, et où elle se trouve
Largest ← A[1]
Position ← 1
FOR i ← 2 TO n
IF A[i] > Largest THEN
Largest ← A[i]
Position ← i
ENDIF
NEXT i
OUTPUT Largest, " at ", Position
- Commencez
Largestau premier élément, jamais à 0 : le tableau pourrait être entièrement négatif. - La même forme compte ou affiche les éléments non vides : comparez chaque élément avec le marqueur d'inutilisé,
""ou-1, et ne comptez que ceux qui diffèrent.
Tri bulle
- Un tri à bulles effectue des passages répétés dans le tableau en comparant les paires adjacentes et en échangeant celles qui sont mal ordonnées, jusqu'à ce qu'un passage ne provoque aucun échange.
- Après chaque passage, la plus grande valeur non triée a remonté à la fin, donc le passage suivant peut s'arrêter une position plus tôt.
REPEAT
Swapped ← FALSE
FOR Index ← 1 TO Limit - 1
IF Data[Index] > Data[Index + 1] THEN
Temp ← Data[Index]
Data[Index] ← Data[Index + 1]
Data[Index + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT Index
Limit ← Limit - 1
UNTIL Swapped = FALSE

Chaque passage emmène la plus grande valeur restante à la fin
Remettez les étapes d'une passe de tri bulle, et sa fin, dans l'ordre.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Réinitialiser le drapeau, balayer et échanger, réduire la limite, s'arrêter quand une passe entière n'a fait aucun échange.
Exemple résolu : où se trouvent les marques du tri bulle
- La boucle extérieure qui répète jusqu'à ce qu'un passage ne fasse aucun échange ; le drapeau
Swappedréinitialisé àFALSEau début de chaque passage et mis àTRUEà l'intérieur duIF. - L'échange de trois lignes via une variable temporaire. Deux lignes font perdre une valeur.
- La limite décroissante, d'une unité de moins à chaque passage, car la plus grande valeur a déjà atteint la fin.
- En mots, pour une question de raffinement progressif : répéter jusqu'à ce que ce soit trié ; à chaque passage comparer les paires adjacentes ; échanger toute paire hors ordre ; après chaque passage, la plus grande valeur non triée est à la fin.
Quelles caractéristiques rapportent des points dans un tri bulle efficace ? Sélectionnez toutes celles qui s'appliquent.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Drapeau, échange avec une variable temporaire, limite décroissante : ce sont là les points. Copier le tableau ne fait pas partie de l'algorithme.
Exemple résolu : supprimer et insérer
- Supprimer un élément : trouver son index avec une recherche linéaire ; déplacer tous les éléments suivants d'une position vers le début pour combler le vide ; marquer le dernier élément comme inutilisé, ou réduire le compte.
- Insérer dans un tableau trié : trouver le premier index dont l'élément est plus grand ; déplacer cet élément et tous les suivants d'une position vers la fin, en commençant par le dernier ; stocker la nouvelle valeur dans le vide.
- Déplacez depuis la fin quand vous ouvrez un vide et depuis le début quand vous le fermez, sinon vous écrasez la valeur que vous allez déplacer.
Un tableau contient de nombreux éléments du MÊME type accessibles par index, tandis qu'un enregistrement regroupe des champs de types (éventuellement) DIFFÉRENTS accessibles par nom.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Un tableau 2D convient pour une grille (lignes × colonnes) ; un enregistrement convient pour une entité décrite par plusieurs champs nommés.
Points qui glissent
[0:99]contient 100 éléments. Comptez les deux bornes.- Un index est un
INTEGER; une déclaration nécessite le type ainsi que les bornes. Grid[row, column]: ligne d'abord. Les inverser lit la mauvaise cellule à chaque boucle imbriquée.- Un swap nécessite une variable temporaire ; une recherche nécessite un chemin « non trouvé » ; un tri à bulles se termine lorsqu'un passage ne fait aucun swap, et non après un nombre fixe de passages.
Vous avez compris
- Un tableau contient un nombre fixe d'éléments de même type sous un seul identifiant, accessibles par un index compris entre la borne inférieure et la borne supérieure ; count = upper − lower + 1
- Le 1-D est une liste, le 2-D est une table
[row, column]parcourue par des boucles imbriquées ; déclarer avec des bornes et un type - Recherche linéaire :
FoundAt ← -1, boucle, stocker l'index, tester après la boucle ; valeur maximale : commencer àA[1], garder la position - Tri à bulles : passes de comparaison-échange adjacentes avec une variable temporaire, un indicateur
Swapped, une limite décroissante, jusqu'à ce qu'un passage ne fasse aucun swap