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 : chaque cellule est d’un 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 python 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 :

-- t : tableau d'entiers

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

t = {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
print(t[1])

L’opérateur # (croisillon) permet de calculer la taille du tableau :

print(#t)

Enfin, l’ajout d’une case se fait avec le même syntaxe que la modification d’icelle :

t[6] = 13
-- ajoute une case contenant 13 au tableau t

Exercices

Exercice 1

Écrire un programme demandant à l’utilisateur d’entrer des valeurs pour les mettre dans un tableau. Le programme pourra 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 ?

t1 = {1, 2, 3, 4}
t2 = t1
print(tostring(t1[1]) .. "\t et \t" .. tostring(t2[1]))
t2[1] = 7
print(tostring(t1[1]) .. "\t et \t" .. tostring(t2[1]))


Écrire un algorithme clone qui copie un tableau.

Exercice 7

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

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

  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é.

Exercice 17 : 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 Python. On pourra mettre des 0 pour les valeurs inconnues.
  • Écrire un algorithme affichant une grille de sudoku.
  • Écrire une fonction vérifiant que chaque ligne ne comporte pas deux fois le même chiffre (hors 0).
  • Écrire une fonction vérifiant que chaque colonne ne comporte pas deux fois le même chiffre.
  • Écrire une fonction qui pour chaque carré 3x3 vérifie que le même chiffre n’apparaît pas deux fois.
  • Écrire une fonction qui vérifie si la grille ne contient aucune incohérence. Si la grille est complète, cette fonction permet de tester si la grille est ou non correcte.
  • Écrire une fonction énumérant les cases n’ayant pas encore de valeur.
  • Écrire une fonction énumérant les possibilités pour remplir les cases n’ayant pas encore de valeurs. Par exemple, s’il y a deux cases sans valeurs, les possibilités seront : [1, 1], [1, 2], [1, 3], .., [1, 9], [2, 1], [2, 2], …, [9, 9].
  • Résoudre la grille de sudoku.