Exercices TD Python Tableaux
Télécharger PDFLes tableaux
En Python, les tableaux peuvent être représentés par des listes. Une liste est une collection ordonnée et modifiable d’éléments éventuellement hétérogènes.
1- Tableau simple dimension
a- Initialisation
Exemple 1 :
>>> T = [5, 38, 10, 25] >>> T [17, 38, 10, 25]
Exemple 2 :
>>> A = 4 * [0] >>> A [0, 0, 0, 0]
b- Traitement
Saisir 10 nombres entiers dans un tableau T, puis afficher leur somme.
T = 10 * [0] # initialisation de la liste
# saisie des éléments de la liste
for i in range(0, 10):
T[i] = int(input('donner T[%d]:' % (i)))
# calculer puis afficher la somme des éléments de la liste
S = 0
for i in range(0, 10):
S += T[i]
print('s=', S)
Version 2 :
T = [] # liste vide
# saisie des éléments de la liste
for i in range(0, 10):
e = int(input('donner T[%d]:' % (i)))
T += [e]
# calculer puis afficher la somme des éléments de la liste
s = 0
for x in T:
s += x
print('s=', s)
Exercice 1:
Écrire une fonction qui retourne la valeur maximale d’un tableau.
def Maximum(L):
Max = L[0]
for i in range(0, len(L)):
if L[i] > Max:
Max = L[i]
return Max
2- Tableaux double dimension
Un tableau double dimension est un tableau dont chaque élément est un tableau. On appelle L le nombre de lignes du tableau et C le nombre de colonnes du tableau. L et C sont alors les deux dimensions du tableau. Un tableau à deux dimensions contient donc L*C composantes.
En Python, un tableau double dimension est une liste dont chaque élément est une liste.
Exemples :
>>> A = [10 * [0] for i in range(10)] # Tableau de 10 lignes et 10 colonnes d’entiers >>> B = [20 * [0.0] for i in range(2)] # Tableau de 2 lignes et 20 colonnes de réels >>> C = [3 * [False] for i in range(3)] # Tableau de 3 lignes et 3 colonnes booléens >>> D = [3 * [''] for i in range(5)] # Tableau de 5 lignes et 3 colonnes de chaînes >>> M = [2 * [0] for i in range(3)] >>> M [[0, 0], [0, 0], [0, 0]] >>> D = [3 * [''] for i in range(5)] >>> D [['', '', ''], ['', '', ''], ['', '', ''], ['', '', ''], ['', '', '']] >>> C = [3 * [False] for i in range(3)] >>> C [[False, False, False], [False, False, False], [False, False, False]]
Accès aux composantes
Soit le tableau T initialisé comme suit :
T = [4 * [0] for i in range(6)]
Exemple de traitement :
Saisir les éléments d’un Tableau 2D (Matrice)
n = int(input('Donner le nombre de lignes :'))
m = int(input('Donner le nombre de colonnes :'))
A = n * [m * [0]]
A = [m * [0] for i in range(n)]
for i in range(0, n):
for j in range(0, m):
A[i][j] = int(input('Elément de la ligne %d et de la colonne %d :' % (i + 1, j + 1)))
Exercice 2:
Écrire un programme Python qui calcule la somme de deux matrices A et B ayant 3 lignes et 3 colonnes. Le programme doit contenir les fonctions suivantes :
- saisirMatrice(n, m) : qui crée une matrice de n x m, la saisir par clavier puis la retourner.
- AfficheMatrice(M) : qui affiche les éléments de la matrice M.
- SommeMatrice(M1, M2) : qui retourne la somme des matrices M1 et M2.
3- Tri d’un tableau simple dimension
Le tri consiste à ordonner les éléments du tableau dans l’ordre croissant ou décroissant. Il existe plusieurs algorithmes connus pour trier les éléments d’un tableau :
- Le tri par sélection
- Le tri par insertion
- Le tri à bulles
- ...
A- Tri par sélection
Principe : On cherche le plus petit élément du tableau et on le place en premier, puis on cherche le plus petit dans ce qui reste et on le met en second, etc…
Exemple :
0 1 2 3 4 9 4 1 7 3
Étape 1: on cherche le plus petit parmi les 5 éléments du tableau. On l’identifie en troisième position, et on l’échange alors avec l’élément 1 :
0 1 2 3 4 1 4 9 7 3
Étape 2: on cherche le plus petit élément, mais cette fois à partir du deuxième élément. On le trouve en dernière position, on l'échange avec le deuxième:
0 1 2 3 4 1 3 9 7 4
Étape 3:
0 1 2 3 4 1 3 4 7 9
Fonction de tri par sélection.
def tri_Selection(T):
n = len(T)
for i in range(0, n - 1):
pmin = i # position du minimum
for j in range(i + 1, n):
if T[j] < T[pmin]:
pmin = j
T[i], T[pmin] = T[pmin], T[i] # inverser T[i] et T[pmin]
B- Tri à bulles
Principe : L’algorithme consiste à comparer chaque paire d’éléments consécutifs, si ces éléments sont dans l’ordre, on passe à la paire suivante, sinon on procède à leur échange avant de traiter la paire suivante.
Fonction de tri à bulles.
def tri_Bull(T):
n = len(T)
i = 1
trier = False
while not trier:
trier = True # on suppose que le tableau est trié
for i in range(0, n - 1):
if T[i] > T[i + 1]:
T[i], T[i + 1] = T[i + 1], T[i]
trier = False # le tableau n'est plus trié
C- Tri par insertion
Principe : Le tri par insertion consiste à insérer successivement chaque élément dans l’ensemble des éléments déjà triés. C’est souvent ce que l’on fait quand on trie un jeu de cartes ou un paquet de copies.
Le tri par insertion d’un tableau T consiste à insérer successivement chaque élément T[k] dans la portion du tableau T[0:k] déjà triée.
Exemple :
Illustrons cette idée sur un tableau T de cinq entiers contenant initialement [5, 2, 3, 1, 4].
Soit le tableau d'entiers suivant :
0 1 2 3 4 5 2 3 1 4
Au départ, T[0:1] = 5 est déjà trié :
On insère 2 dans T[0:1]
5 2 3 1 4
On insère 3 dans T[0:2]
2 5 3 1 4
On insère 1 dans T[0:3]
2 3 5 1 4
On insère 4 dans T[0:4]
1 2 3 5 4
1 2 3 4 5
def tri_Insertion(T):
n = len(T)
for i in range(1, n):
e = T[i]
j = i
while j > 0 and T[j - 1] > e:
T[j] = T[j - 1]
j -= 1
T[j] = e
4- Recherche d’un élément dans un tableau
A- Recherche séquentielle (linéaire)
On dispose d’un tableau T et on souhaite savoir si une valeur x fait partie de ce tableau.
def cherche(x, T):
for e in T:
if e == x:
return True
return False
Remarque :
L’utilisation de l’instruction return à l’intérieur de la boucle pour interrompre son exécution.
On peut également écrire une fonction renvoyant le premier indice où la valeur x apparaît dans le tableau T. Comme dans la fonction précédente, return fait sortir de la fonction dès que la valeur x est trouvée. Si on sort de la boucle, on renvoie None pour signaler un échec de la recherche.
def indice(x, T):
for k in range(len(T)):
if x == T[k]:
return k
return None
Remarque :
Bien évidemment, Python dispose d’instructions prédéfinies pour rechercher un élément dans une liste.
- L’expression x in T est évaluée à True si un objet x appartient à une liste T et à False sinon.
- La méthode index renvoie l’indice du premier élément de la liste égal à cet objet. Une erreur survient si l’élément n’appartient pas à la liste.
B- Recherche dichotomique
On suppose qu’on dispose d’un tableau T d’éléments rangés par ordre croissant. On veut à nouveau savoir si un élément x appartient à ce tableau.
Le principe de la recherche dichotomique consiste à comparer x avec l’élément T[milieu] :
- si x == T[milieu], on a trouvé une solution et la recherche s’arrête ;
- si x < T[milieu], x ne peut se trouver que dans la moitié gauche du tableau T puisque celle-ci est triée par ordre croissant ; on poursuit alors la recherche de la même manière uniquement dans la moitié gauche du tableau ;
- si x > T[milieu], x ne peut se trouver que dans la moitié droite du tableau T ; on poursuit alors la recherche uniquement dans la moitié droite du tableau.
A chaque fois, on poursuit donc la recherche en diminuant de moitié le nombre d’éléments restant à traiter.
La fonction suivante renvoie, si elle existe, la position d'une occurrence de x dans T supposé trié, et None sinon.
def recherche_dichotomique(x, T):
g = 0
d = len(T) - 1
while g <= d:
m = (g + d) // 2
if T[m] == x:
return m
if T[m] < x:
g = m + 1
else:
d = m - 1
return None
FAQ
1. Comment initialiser un tableau en Python ?
Pour initialiser un tableau en Python, vous pouvez utiliser des listes. Par exemple, pour initialiser un tableau de 10 éléments tous à 0, vous pouvez écrire :
T = 10 * [0]
2. Qu'est-ce que le tri par sélection ?
Le tri par sélection est un algorithme de tri qui consiste à chercher le plus petit élément du tableau et à le placer en premier, puis à chercher le plus petit dans ce qui reste et à le mettre en second, et ainsi de suite.
3. Comment rechercher un élément dans un tableau trié ?
Pour rechercher un élément dans un tableau trié, vous pouvez utiliser la recherche dichotomique. Cette méthode consiste à comparer l'élément recherché avec l'élément au milieu du tableau, puis à réduire la recherche à la moitié gauche ou droite du tableau en fonction du résultat de la comparaison.