SD-AStructures de données et modularité

Traitement de tableaux — max/min, occurrences, décalage

Idée directrice

L'énoncé donne un tableau d'entiers et demande d'écrire des sous-programmes classiques : trouver le maximum/minimum et son indice, compter les occurrences d'une valeur, ou effectuer un décalage circulaire. Ces algorithmes se basent tous sur un parcours linéaire avec mise à jour d'une variable accumulatrice.

Signature de reconnaissance — l'énoncé se trahit ainsi

« Écrire une fonction qui retourne le maximum d'un tableau » ; « Écrire une fonction qui compte le nombre d'occurrences de … dans un tableau » ; « Écrire une procédure qui effectue un décalage circulaire » ; « Donner le contenu du tableau après … »

Sujet principal

Exercice — dans l'esprit des sujets du bac

3 questionsCorrigé masqué

Soit T = [4, 7, 2, 7, 9, 3, 7, 1] (N=8).

Écrire une fonction Maximum(T, N) qui retourne la valeur maximale et l'indice de sa première occurrence.
1. Appliquer cette fonction à T. Quel est le résultat ?
2. Modifier la fonction pour retourner l'indice de la dernière occurrence du maximum.
Écrire une fonction NbOccurrences(T, N, val) qui retourne le nombre d'occurrences de val dans T. Combien de fois 7 apparaît-il ?
Écrire une procédure DecalageGauche(T, N) qui effectue un décalage circulaire vers la gauche (le premier élément va en dernière position).
1. Donner le contenu de T après un appel à cette procédure.
2. Comment effectuer un décalage de k positions ?

Voir la correction commentéeAprès avoir posé votre démarche

1. Maximum et première occurrence. Idée : initialiser max ← T[1], indMax ← 1, puis parcourir et mettre à jour si T[i] > max.

TDOL — objets locaux :

i, max, indMax : entier — compteur, valeur maximale, indice de la première occurrence
T : tableau d'entiers ; N : entier — paramètres (Type/Nature)

DEF PROC Maximum(T : tableau ; N : entier ; var max, indMax : entier)
Variables i : entier
Début
  max ← T[1] ; indMax ← 1
  Pour i de 2 à N faire
    Si T[i] > max alors
      max ← T[i] ; indMax ← i
    FinSi
  FinPour
Fin
{ la procédure rend les deux résultats par ses paramètres var : max et indMax }

Application sur T = [4, 7, 2, 7, 9, 3, 7, 1] (N=8) : max=9, indMax=5. On obtient la valeur 9 et l'indice 5 (deux résultats, d'où une procédure à deux paramètres var plutôt qu'une fonction). Pour la dernière occurrence du maximum, remplacer > par ≥ : à égalité, l'indice est écrasé par le plus récent.

2. Nombre d'occurrences de val.

DEF FN NbOccurrences(T : tableau ; N, val : entier) : entier
Variables i, c : entier
Début
  c ← 0
  Pour i de 1 à N faire
    Si T[i] = val alors c ← c + 1 FinSi
  FinPour
  Retourner c
Fin

Pour val = 7 : On retourne 3.

3. Décalage circulaire gauche.

DEF PROC DecalageGauche(var T : tableau ; N : entier)
Variables i, sauv : entier
Début
  sauv ← T[1]
  Pour i de 1 à N-1 faire
    T[i] ← T[i+1]
  FinPour
  T[N] ← sauv
Fin

Après un décalage : [7, 2, 7, 9, 3, 7, 1, 4]. Contrainte : indices i dans [1..N] ; sauvegarder T[1] avant d'écraser.
3.(b) Décalage de k positions. Deux méthodes : appeler DecalageGauche k fois (k ← k mod N d'abord, un décalage de N positions ne changeant rien) ; ou recopier en une passe dans un tableau auxiliaire U[i] ← T[((i-1+k) mod N)+1] puis T ← U. La première est en O(kN), la seconde en O(N).

Équivalent Python (extrait).

def maximum(T, N):
    m, ind = T[0], 0
    for i in range(1, N):
        if T[i] > m:
            m, ind = T[i], i
    return m, ind + 1   # indices Python à partir de 0 : +1 pour retrouver l'indice 5 de l'énoncé
print(maximum([4,7,2,7,9,3,7,1], 8))

Exercices d'entraînement — une nuance à la fois

Entraînement 01 / 03

Drill SD-A.1 — recherche séquentielle dans un tableau

1 questionCorrigé masqué

Soit un tableau T de n entiers. Écrire l'algorithme d'une fonction Recherche(T, n, x) qui renvoie l'indice de x, ou −1 s'il est absent.

Voir la correction commentéeAprès avoir posé votre démarche

TDOL : i entier. Type/Nature : T tableau, n/x entiers.

DEF FN Recherche(T : tableau ; n, x : entier) : entier
Variables i : entier
Début
  Pour i de 1 à n faire
    Si T[i] = x alors Retourner i FinSi
  FinPour
  Retourner -1
Fin

Parcours séquentiel $O(n)$ . On retourne l'indice ou $-1$ ; i dans [1..n].

Entraînement 02 / 03

Drill SD-A.2 — maximum d'un tableau

1 questionCorrigé masqué

Écrire l'algorithme calculant le maximum d'un tableau T de n réels (n ≥ 1).

Voir la correction commentéeAprès avoir posé votre démarche

TDOL : i, max. Type/Nature : T tableau de réels, n entier ≥ 1.

DEF FN Maximum(T : tableau ; n : entier) : réel
Variables i : entier ; max : réel
Début
  max ← T[1]
  Pour i de 2 à n faire
    Si T[i] > max alors max ← T[i] FinSi
  FinPour
  Retourner max
Fin

Initialiser à T[1], pas 0. On retourne le max ; i dans [2..n].

Entraînement 03 / 03

Drill SD-A.3 — tableau à deux dimensions

1 questionCorrigé masqué

Comment déclare-t-on une matrice M à L lignes et C colonnes, et comment somme-t-on tous ses éléments ?

Voir la correction commentéeAprès avoir posé votre démarche

TDOL : i, j, S entiers. Type/Nature : M tableau [1..L][1..C].

DEF FN SommeMatrice(M : tableau ; L, C : entier) : entier
Variables i, j, S : entier
Début
  S ← 0
  Pour i de 1 à L faire
    Pour j de 1 à C faire S ← S + M[i][j] FinPour
  FinPour
  Retourner S
Fin

On retourne la somme ; i dans [1..L], j dans [1..C].

Méthode / Automatismes

Maximum/minimum : initialiser avec T[1], boucle de 2 à N, condition > (max) ou < (min).
Première vs dernière occurrence : > donne la première, >= donne la dernière.
Comptage d'occurrences : compteur initialisé à 0, incrémenté à chaque correspondance.
Décalage circulaire gauche : sauvegarder T[1], décaler T[i]←T[i+1], puis T[N]← sauvegarde.
Décalage de k positions : k appels successifs ou calcul de l'indice modulo N.

Pièges classiques

Pièges fréquents : initialiser max ← 0 au lieu de max ← T[1] (faux si tous les éléments sont négatifs) ; oublier de sauvegarder T[1] avant le décalage ; confondre décalage gauche et décalage droit.

Variantes rencontrées : calcul de la moyenne d'un tableau ; suppression des doublons ; insertion d'un élément à une position donnée dans un tableau trié.