Masar
Masar
Bac Tunisie
Informatique/SD-A
Entraîner la reconnaissance
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).

  1. É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.
  2. Écrire une fonction `NbOccurrences(T, N, val)` qui retourne le nombre d'occurrences de `val` dans T. Combien de fois `7` apparaît-il ?
  3. É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 FN Maximum(T : tableau ; N : entier) : entier
Variables i, max, indMax : 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
Retourner indMax { ou max selon l'énoncé }
Fin
```

Application sur `T = [4, 7, 2, 7, 9, 3, 7, 1]` (N=8) : max=9, indMax=5. On retourne la valeur 9 et l'indice 5. Pour la dernière occurrence, utiliser `≥` au lieu de `>`.

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.

Équivalent Python (extrait).
```python
from array import array
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
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)O(n). On retourne l'indice ou −1-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é.