Tableaux

Définitions

Les tableaux sont une structure de données qui à un indice i compris entre une borne inférieure a et une borne supérieure b associe une valeur notée t[i].

La taille d’un tableau est théoriquement fixée une fois pour toute (c’est b - a + 1). De cette façon, la taille qu’il occupera dans la mémoire de la machine est fixée au départ, comme pour les variables de type simple. Cependant, dans les langages à typage dynamique (Python, Lua, javascript, …), les tableaux sont en général extensibles.

On peut imaginer un tableau comme un tableau composé de cellules, chaque cellule se comportant comme une variable à part entière. Une restriction existe cependant : toutes les cellules sont du même type. On peut ainsi avoir des tableaux d’entiers, des tableaux de booléens ou même des tableaux de tableaux de caractères.

En java et dans de nombreux autres langages, les cases d’un tableau sont numérotées à partir de 0. Notons que c’est une convention qui n’est pas partagée partout : en lua, les tableaux sont indexés à partir de 1.

Utilisation

On déclare un tableau en précisant le type de ses cellules :

int[] t;

Et on précise le nombre de cases de ce tableau :

t = new int[17];

On peut créer un tableau pré-rempli à l’aide d’une notation particulière :

int[] t2 = {2, 3, 5, 7, 11}

On accède à l’élément du tableau dans la case indexée par i en écriture et en écriture sous la forme t[i] :

t[3] = 0
System.out.println(t[1])

Le champ length permet de calculer la taille du tableau :

System.out.println(t2.length);

Exercices

Exercice 1

Écrire un programme demandant à l’utilisateur d’entrer des valeurs pour les mettre dans un tableau. Le programme devra dans un premier temps demander le nombre de cases du tableau, puis les valeurs de chaque case.

Exercice 2

Écrire un algorithme qui affiche sous la forme [ 1, 2, 3, 4 ] un tableau qui est obtenu par l’exercice 1.

Exercice 3

Écrire un algorithme qui renverse un tableau. Celle-ci doit prendre comme entrée un tableau et renvoyer le tableau de même taille ayant les valeurs dans l’ordre inverse.

Le tester avec un tableau donné par l’utilisateur.

Exercice 4

Écrire un algorithme calculant la somme des éléments d’un tableau d’entiers.

Le tester avec un tableau donné par l’utilisateur.

Exercice 5

Écrire un algorithme calculant le plus petit élément d’un tableau.

Exercice 6

Que fait le code suivant ?

int[] t1 = {1, 2, 3, 4};
int[] t2;
t2 = t1;
t2[1] = 7;
System.out.println(t2[1]);
System.out.println(t1[1]);

Écrire un algorithme clone qui copie un tableau.

Exercice 7

Écrire un algorithme triant un tableau dans l’ordre croissant.

  1. Implémenter le tri bulle qui consiste, tant que le tableau n’est pas trié à parcourir le tableau et si deux éléments consécutifs sont dans le mauvais ordre, les inverser.
  2. Implémenter le tri sélection : trouver le minimum du tableau de départ, le mettre dans le tableau resultat ; fabriquer un tableau qui sera le tableau initial privé de ce minimum ; dans ce deuxième tableau, trouver le minimum et l’ajouter au tableau resultat ; fabriquer un tableau qui sera le tableau initial privé de ce minimum ; …

Exercice 8

Écrire un algorithme carrétab qui prend un tableau d’entiers et renvoie le tableau des carrés de ces entiers.

Exercice 9

Une matrice entière peut être représentée par un tableau de tableaux d’entiers.

Concevoir deux matrices 2x2 et calculer leur somme (qui est aussi une matrice 2x2). Afficher cette somme.

Exercice 10 : Primalité

  1. Écrire un algorithme qui fabrique le tableau des n premiers nombres premiers.

  2. Écrire un algorithme qui fabrique le tableau des nombres premiers plus petits qu’un p donné.

  3. Écrire un algorithme qui fabrique le tableau des nombres premiers plus petits qu’un p donné en utilisant le crible d’Érathostène.

    Pour cela on créera un tableau de booléens estPremier dont le but sera que estPremier[n] vaut vrai si et seulement si n est premier. Au départ ce tableau contiendra vrai partout (jusqu’à preuve du contraire, les nombres sont premiers). Puis, pour chaque nombre premier supérieur à 2, on va mettre faux dans les cases associées à tous ses multiples.

Exercice 11 : Triangle de Pascal

Le triangle de Pascal permet de calculer le nombre de combinaisons de k éléments parmi n (pour les calculs de probabilités). Sa construction est basée sur la formule C_{n+1}^{k+1} = C_n^k + C_n^{k+1}

On sait de plus que pour tout n, C_n^0 = 1. Ce qui fait que l’on peut construire le tableau suivant où la case de la ligne n, colonne k vaut C_n^k :

1 0 0 0 0 0
1 1 0 0 0 0
1 2 1 0 0 0
1 3 3 1 0 0
1 4 6 4 1 0
1 5 10 10 5 1

Écrire un programme qui prend deux entiers n et k, construit un tableau bi-dimensionnel à n+1 lignes et n+1 colonnes, le remplit avec la formule de Pascal et enfin affiche la valeur de C_n^k.

Exercice 12 : Nombre d’occurences

Écrire un programme qui prend en entrée un tableau d’entiers et une valeur entière et renvoie combien de fois cette valeur apparaît dans le tableau.

Exercice 13 : Classement de Ligue 1

Un championnat de sport comporte 4 équipes (par exemple Paris, Lille, Lyon et Marseille) qui ont chacune un certain nombre de points (par exemple 45, 25, 23 et 32).

Comment stocker ces informations ?

Écrire un programme qui prend ces données et affiche le classement du championnat. Ici

1. Paris 45
2. Marseille 32
3. Lille 25
4. Lyon 23

Exercice 14 : Décomposition d’une somme d’argent aux USA

Pour décomposer une valeur en cents en le nombre minimum de pièces de 25, 10 et 1 cents, l’algorithme utilisé pour les euros n’es pas optimal (pour 30 cents, il utilise 6 pièces : 1 de 25 et 5 de 1 alors qu’une décomposition en 3 pièces de 10 est possible).

Nous allons faire de la programmation dynamique pour résoudre ce problème. Nous allons fabriquer pour chaque valeur un tableau à 4 cases contenant respectivement :

  • le nombre minimal de pièces
  • le nombre de pièces de 25 dans cette répartition
  • le nombre de pièces de 10 dans cette répartition
  • le nombre de pièces de 1 dans cette répartition.

Pour trouver la répartition optimale pour une valeur n donnée en entrée, on fabriquera un tableau à n+1 cases, chaque case contenant le tableau à 4 cases décrit précédemment.

Pour l’entrée 11, le tableau ressemblera à

{{0, 0, 0, 0},
 {1, 0, 0, 1},
 {2, 0, 0, 2},
 ...
 {9, 0, 0, 9},
 {1, 0, 1, 0},
 {2, 0, 1, 1}}

Puis on affichera la répartition (pour l’entrée 11, “0 pièces de 25, 1 pièces de 10, 1 pièces de 1).

Plus de précisions sur le fonctionnement de cet algorithme

Exercice 15 : Problème du sac à dos

Écrire un programme qui prend en entrée un tableau de valeurs entières (les poids) et un entier (la capacité du sac) et renvoie un tableau des poids des objets que l’on peut mettre ensemble dans le sac à dos en étant le plus proche de la capacité sans la dépasser.

Par exemple avec les poids {9, 12, 7, 5, 4} et la capacité 13, le meilleur choix est 9+4.

Indices

Exercice 16 : pièces de Tetris

Les pièces de Tetris sont composés de 4 carrés qui se touchent. On peut leur appliquer une rotation dans le sens horaire ou direct. Pour représenter ça, chaque pièce est définie dans une grille 4x4 dans laquelle on peut représenter la pièce avant et après rotation.

Par exemple le T peut être représenté comme suit avant et après rotation horaire :

{{0, 0, 0, 0},
 {0, 1, 1, 1},
 {0, 0, 1, 0},
 {0, 0, 0, 0}}

{{0, 0, 0, 0},
 {0, 0, 1, 0},
 {0, 1, 1, 0},
 {0, 0, 1, 0}}

Écrire un programme qui permet d’afficher une pièce (on utilisera des espaces pour les vides et des '#' pour les pleins).

Demander à l’utilisateur s’il veut une rotation horaire ou directe, créer une nouvelle pièce contenant la pièce après rotation et afficher cette pièce.

L’essayer sur le T et sur d’autres pièces.

Exercice 17 : Tetris

Une grille de Tetris comporte 10 colonnes et 25 lignes. Écrire un programme qui stocke une grille (sous la forme d’un tableau de 25 tableaux de 10 entiers). Ce programme va devoir stocker les 7 pièces possibles. Faites lui tirer au sort une pièce, l’afficher, la faire tourner un nombre de fois fourni par l’utilisateur puis tomber jusqu’au fond de la grille avant de retirer une pièce.

Pour tirer un nombre entier au hasard entre 0 et 7, on utilisera :

Random hasard = new Random();
int entierAleatoire = hasard.nextInt(7);

Exercice 99 : Sudoku

Une grille de sudoku est un tableau de 9 tableaux de 9 entiers.

-------------------------------
|       9 |         |         |
|    2    |    8  3 |         |
|    5    | 4       |         |
-------------------------------
|         | 8  4    | 1  5    |
| 6       |    9    |         |
|    1    |       2 |       7 |
-------------------------------
|    6    |         |    7    |
|         | 5     9 |    4  3 |
|       3 | 2       |       9 |
-------------------------------
  • Représenter la grille ci-dessus en Java. On pourra mettre des 0 pour les valeurs inconnues.
  • Écrire un algorithme affichant une grille de sudoku.