Les tableaux

Cours complet · OCaml (option informatique), chapitre 5 · prépas MPSI et MP, option informatique

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>5.1 Introduction et motivation

La liste (chapitre 2) est la structure naturelle du style fonctionnel, mais elle a un défaut : accéder à son $i$ -ème élément coûte un parcours, proportionnel à $i$ . Quand on a besoin d'un accès direct — lire ou écrire la case d'indice $i$ en temps constant — on emploie le tableau. C'est une structure mutable et de taille fixe, cousine de la liste Python, et qui se marie naturellement avec les boucles du chapitre précédent.

iRemarqueNiveau A.2 : un rappel sera toujours fourni

Les tableaux et les fonctions du module Array relèvent des éléments « utilisables après rappel » du programme : en épreuve, leur documentation est fournie. On les présente donc ici avec leur signature, qu'il n'est pas exigé de mémoriser, mais qu'il faut savoir lire et utiliser.

5.2 Créer et lire un tableau

Un tableau littéral s'écrit entre [| et |], éléments séparés par des points-virgules. Son type est 'a array, et comme une liste il est homogène.


# let t = [| 10; 20; 30 |];;
val t : int array = [|10; 20; 30|]
# t.(0);;
- : int = 10
# Array.length t;;
- : int = 3

On accède à la case d'indice i par t.(i), en temps constant. Les indices vont de 0 à Array.length t - 1.

Attention

Un accès t.(i) avec i hors de l'intervalle $[0, longueur - 1]$ lève l'exception Invalid_argument "index out of bounds" à l'exécution. Comme en Python, la moitié des bogues sur les tableaux sont des erreurs d'indice : on relit chaque borne en se demandant « la dernière case est-elle t.(n) ou t.(n-1) ? » — c'est t.(n-1).

5.3 Modifier un tableau

C'est la grande différence avec la liste : un tableau est mutable. L'instruction t.(i) <- v remplace le contenu de la case i par v ; sa valeur est ().


# let t = [| 10; 20; 30 |];;
# t.(1) <- 99;;
- : unit = ()
# t;;
- : int array = [|10; 99; 30|]

5.3.1 Construire un tableau

iRemarqueRappel des constructeurs (A.2)

Array.make n v : int -> 'a -> 'a array — un tableau de n cases, toutes initialisées à v ;
Array.init n f : int -> (int -> 'a) -> 'a array — un tableau de n cases, la case i valant f i ;
Array.copy t : 'a array -> 'a array — un nouveau tableau qui contient les mêmes éléments que t : copie superficielle, donc pour une matrice les lignes restent partagées (copier chaque ligne avec Array.map Array.copy m).


# Array.make 4 0;;
- : int array = [|0; 0; 0; 0|]
# Array.init 5 (fun i -> i * i);;
- : int array = [|0; 1; 4; 9; 16|]

AttentionLe piège de la valeur partagée

Array.make n v place la même valeur v dans toutes les cases. Pour une valeur immuable (un entier), aucun problème. Mais si v est elle-même mutable — typiquement un tableau — les n cases pointent vers le même objet : modifier l'une les modifie toutes. Ainsi Array.make 2 (Array.make 3 0) crée deux lignes qui sont le même tableau. Pour un tableau de tableaux, on utilise Array.make_matrix (voir plus loin) ou Array.init.

5.4 Parcourir un tableau

Le parcours par indices avec une boucle for est l'idiome de base : il donne accès à l'indice et à la valeur, et permet la modification en place.

Exemple 5.1Somme des éléments


let somme t =
  let s = ref 0 in
  for i = 0 to Array.length t - 1 do
    s := !s + t.(i)
  done;
  !s

On accumule dans une référence en parcourant les indices 0 à Array.length t - 1 inclus. (Le module Array n'offre pas de fonction de sommation au programme : on écrit la boucle.)

iRemarqueRappel des fonctions de parcours (A.2)

Quand on n'a pas besoin des indices, ces fonctions d'ordre supérieur sont plus concises :

Array.iter f t : ('a -> unit) -> 'a array -> unit — applique f à chaque case pour son effet ;
Array.map f t : ('a -> 'b) -> 'a array -> 'b array — le tableau des f t.(i) (nouveau tableau) ;
Array.mem x t : 'a -> 'a array -> bool — x figure-t-il dans t ?
Array.exists p t et Array.for_all p t : ('a -> bool) -> 'a array -> bool — un élément vérifie p ? / tous le vérifient ?


# Array.map (fun x -> x * x) [| 1; 2; 3 |];;
- : int array = [|1; 4; 9|]
# Array.for_all (fun x -> x > 0) [| 1; 2; 3 |];;
- : bool = true

5.5 Les matrices (tableaux à deux dimensions)

Une matrice est un tableau de tableaux. On la crée proprement avec Array.make_matrix, qui évite le piège de la valeur partagée.

iRemarqueRappel (A.2)

Array.make_matrix lignes colonnes v : int -> int -> 'a -> 'a array array crée une matrice lignes $\times$ colonnes dont chaque case (et chaque ligne) est indépendante, toutes initialisées à v.

On accède à la case (ligne i, colonne j) par m.(i).(j), et on la modifie par m.(i).(j) <- v. Le parcours se fait par deux boucles imbriquées.

Exemple 5.2Remplir une table d'addition


let table_addition n =
  let m = Array.make_matrix (n + 1) (n + 1) 0 in
  for i = 0 to n do
    for j = 0 to n do
      m.(i).(j) <- i + j
    done
  done;
  m

La boucle externe parcourt les lignes, l'interne les colonnes. make_matrix garantit des lignes distinctes — avec Array.make (n+1) (Array.make (n+1) 0), toutes les lignes auraient été le même tableau, et le remplissage aurait été faux.

5.6 Tableaux et listes : que choisir ?

	Liste `'a list`	Tableau `'a array`
Accès à l'indice $i$	$Θ (i)$ (parcours)	$Θ (1)$ (direct)
Modification d'une case	impossible (immuable)	`t.(i) <- v`, $Θ (1)$
Taille	variable (`::` en tête)	fixe à la création
Ajout en tête	`x :: l`, $Θ (1)$	coûteux (recopie)
Traitement naturel	récursion / filtrage	boucle `for` sur les indices

Important

On choisit le tableau quand on a besoin d'accès direct par indice ou de modification en place (algorithmes numériques, matrices, cases à mettre à jour), et la liste quand la taille évolue et qu'on traite les éléments séquentiellement par récursion. Ce ne sont pas des rivales : ce sont deux outils pour deux besoins.

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>5.7 Exercices résolus

Niveau $⋆$ (application directe du cours)

Exercice 1 : Type et valeur

Donner le type et la valeur affichés.


[| true; false |] ;;   Array.length [| 1; 2; 3; 4 |] ;;   Array.make 3 5 ;;

Puis : que vaut t après let t = [| 0; 0; 0 |] in t.(2) <- 7; t ?

Démonstration


- : bool array = [|true; false|]
- : int = 4
- : int array = [|5; 5; 5|]

Pour la dernière : t.(2) <- 7 modifie la case d'indice $2$ , donc t vaut [|0; 0; 7|].

Exercice 2 : Somme d'un tableau

Écrire somme t avec une boucle for.

Démonstration


let somme t =
  let s = ref 0 in
  for i = 0 to Array.length t - 1 do
    s := !s + t.(i)
  done;
  !s

La borne haute est Array.length t - 1 (dernier indice valide). Sur le tableau vide, la boucle ne tourne pas et la somme vaut 0.

Exercice 3 : Maximum d'un tableau

Écrire maximum t (précondition : t non vide).

Démonstration


let maximum t =
  let m = ref t.(0) in
  for i = 1 to Array.length t - 1 do
    if t.(i) > !m then m := t.(i)
  done;
  !m

On initialise le maximum courant à la première case, puis on parcourt à partir de l'indice 1. La précondition « non vide » est nécessaire : sur le tableau vide, t.(0) lèverait Invalid_argument.

Niveau $⋆ ⋆$ (raisonnement intermédiaire)

Exercice 4 : Construire avec `Array.init`

Écrire carres n renvoyant [| 0; 1; 4; ...; (n-1)*(n-1) |] en une ligne avec Array.init.

Démonstration


let carres n = Array.init n (fun i -> i * i)

Array.init n f construit un tableau de n cases, la case i valant f i. Ici carres 5 donne [|0; 1; 4; 9; 16|]. C'est plus concis et plus sûr qu'une boucle de remplissage.

Exercice 5 : Renverser en place

Écrire renverse t qui inverse t sur place (sans créer de nouveau tableau).

Démonstration


let renverse t =
  let n = Array.length t in
  for i = 0 to n / 2 - 1 do
    let tmp = t.(i) in
    t.(i) <- t.(n - 1 - i);
    t.(n - 1 - i) <- tmp
  done

On échange la case i avec sa symétrique n-1-i, pour i allant jusqu'au milieu (n / 2 - 1) : au-delà, on déferait les échanges. La variable tmp retient une valeur le temps de l'échange. La fonction renvoie () : elle agit par effet de bord.

Exercice 6 : Recherche avec `option`

Écrire indice x t renvoyant Some i (première position de x) ou None, par une boucle qui s'arrête dès qu'on a trouvé.

Démonstration


let indice x t =
  let n = Array.length t in
  let i = ref 0 and trouve = ref None in
  while !i < n && !trouve = None do
    if t.(!i) = x then trouve := Some !i;
    i := !i + 1
  done;
  !trouve

La condition !i < n && !trouve = None (paresseuse) garantit deux choses : on ne déborde pas, et on cesse dès la première occurrence. Le type option évite une valeur sentinelle comme -1.

Exercice 7 : Les fonctions du module `Array`

À l'aide de Array.for_all, Array.exists et Array.map, écrire tous_positifs t, contient_zero t et doubles t (tableau des doubles).

Démonstration


let tous_positifs t = Array.for_all (fun x -> x > 0) t
let contient_zero t = Array.exists (fun x -> x = 0) t
let doubles t = Array.map (fun x -> 2 * x) t

Ces fonctions d'ordre supérieur dispensent d'écrire la boucle quand l'indice n'importe pas. map renvoie un nouveau tableau sans modifier t ; for_all/exists renvoient un booléen.

Niveau $⋆ ⋆ ⋆$ (approfondissement)

Exercice 8 : Le piège de la valeur partagée

Donner le contenu final de m dans chaque cas, et expliquer.


(* A *)                                  (* B *)
let m = Array.make 2 (Array.make 2 0)    let m = Array.make_matrix 2 2 0
in m.(0).(0) <- 1; m                     in m.(0).(0) <- 1; m

Démonstration

(A) donne [|[|1; 0|]; [|1; 0|]|] : les deux « lignes » sont le même tableau (créé une seule fois par Array.make 2 0), si bien que modifier m.(0).(0) modifie aussi m.(1).(0).

(B) donne [|[|1; 0|]; [|0; 0|]|] : make_matrix crée des lignes indépendantes, donc seule la case visée change.

(Morale : pour un tableau de tableaux, jamais Array.make n (Array.make ...) ; toujours make_matrix ou Array.init n (fun _ -> Array.make ...).)

Exercice 9 : Transposée d'une matrice

Écrire transpose m qui renvoie la transposée d'une matrice d'entiers lignes $\times$ colonnes (rectangulaire, non vide).

Démonstration


let transpose m =
  let lignes = Array.length m in
  let colonnes = Array.length m.(0) in
  let t = Array.make_matrix colonnes lignes 0 in
  for i = 0 to lignes - 1 do
    for j = 0 to colonnes - 1 do
      t.(j).(i) <- m.(i).(j)
    done
  done;
  t

La transposée a colonnes lignes et lignes colonnes : on crée t de la bonne forme, puis on recopie m.(i).(j) dans t.(j).(i). Le nombre de colonnes se lit sur la première ligne m.(0) (d'où l'hypothèse « rectangulaire non vide »).

Exercice 10 : Le crible d'Ératosthène

Écrire crible n renvoyant un tableau de booléens où la case i indique si i est premier (pour 0 <= i <= n).

Démonstration


let crible n =
  let est_premier = Array.make (n + 1) true in
  est_premier.(0) <- false;
  if n >= 1 then est_premier.(1) <- false;
  for d = 2 to n do
    if est_premier.(d) then begin
      let m = ref (d * d) in
      while !m <= n do
        est_premier.(!m) <- false;
        m := !m + d
      done
    end
  done;
  est_premier

On part de « tout est premier », on élimine 0 et 1, puis pour chaque d encore marqué premier, on barre tous ses multiples à partir de dd (les plus petits ont déjà été barrés par des facteurs plus petits). Le tableau de booléens est l'outil idéal : accès et mise à jour en temps constant. (Variant de la boucle while : n - !m, qui décroît de d à chaque tour.)*

Synthèse du chapitre (à retenir)

Un tableau 'a array : littéral [| ... |], homogène, taille fixe, mutable. Accès t.(i) et écriture t.(i) <- v en $Θ (1)$ ; indices 0 à Array.length t - 1 (hors borne $\Rightarrow$ exception).
Construire : Array.make n v, Array.init n f, Array.copy t. Piège : Array.make n v partage v ; pour un tableau de tableaux, Array.make_matrix.
Parcours par for i = 0 to Array.length t - 1. Sans indices : Array.iter, Array.map, Array.mem, Array.exists, Array.for_all (rappel A.2).
Matrices : Array.make_matrix l c v, accès m.(i).(j), deux boucles imbriquées.
Tableau vs liste : accès direct et mutation $Θ (1)$ mais taille fixe (tableau) ; immuable, extensible en tête, traité par récursion (liste).

5.8 Exercices d'entraînement

Légende : $⋆$ application directe, $⋆ ⋆$ raisonnement intermédiaire, $⋆ ⋆ ⋆$ approfondissement ; $⧫$ signale un classique incontournable. La numérotation prolonge celle des dix exercices résolus.

Thème A — Accès, écriture, construction.

[11.] $⋆$ Donner le type et la valeur de [| 1; 2 |], Array.make 2 true, Array.init 4 (fun i -> i + 1).
[12.] $⋆$ Écrire remplir t v qui met v dans toutes les cases de t (par effet de bord).
[13.] $⋆ ⋆$ $⧫$ Écrire copie t sans Array.copy, à l'aide de Array.init.

Thème B — Parcours et accumulation.

[14.] $⋆$ Écrire minimum t (précondition : non vide).
[15.] $⋆ ⋆$ Écrire compte p t (nombre de cases vérifiant le prédicat p) avec une boucle.
[16.] $⋆ ⋆$ $⧫$ Écrire produit_scalaire u v de deux tableaux d'entiers de même longueur.

Thème C — Modifications en place.

[17.] $⋆ ⋆$ Écrire decale_droite t qui décale toutes les cases d'un cran vers la droite (la dernière sort, la première devient 0).
[18.] $⋆ ⋆ ⋆$ Écrire tri_bulles t qui trie t en place (échanges de voisins mal ordonnés, répétés) ; donner un variant de la boucle externe.
[19.] $⋆ ⋆ ⋆$ Écrire est_trie t (le tableau est-il croissant ?) en s'arrêtant au premier défaut.

Thème D — Matrices.

[20.] $⋆ ⋆$ Écrire somme_matrice m (somme de toutes les cases d'une matrice d'entiers).
[21.] $⋆ ⋆ ⋆$ Écrire identite n renvoyant la matrice identité $n \times n$ (des 1 sur la diagonale, des 0 ailleurs).
[22.] $⋆ ⋆ ⋆$ $⧫$ Écrire produit_matriciel a b de deux matrices d'entiers compatibles, avec trois boucles imbriquées.

Continuer sur Adloun : animation, QCM, fiches, exercices

Les tableaux

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>5.1 Introduction et motivation

5.2 Créer et lire un tableau

5.3 Modifier un tableau

5.3.1 Construire un tableau

5.4 Parcourir un tableau

5.5 Les matrices (tableaux à deux dimensions)

5.6 Tableaux et listes : que choisir ?

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>5.7 Exercices résolus

Niveau ⋆ (application directe du cours)

Niveau ⋆⋆ (raisonnement intermédiaire)

Niveau ⋆⋆⋆ (approfondissement)

5.8 Exercices d'entraînement

Thème A — Accès, écriture, construction.

Thème B — Parcours et accumulation.

Thème C — Modifications en place.

Thème D — Matrices.

Niveau $⋆$ (application directe du cours)

Niveau $⋆ ⋆$ (raisonnement intermédiaire)

Niveau $⋆ ⋆ ⋆$ (approfondissement)