3.4.3. Complément sur les tableaux#
Dans certains langage comme le C, la structure élémentaire de données est le tableau. Il est de taille fixé lors de sa création et celle-ci ne peut changer (contrairement aux listes). En toute rigeur, le type des données est donné également à la création du tableau et ne peut être changé. Ici, ça ne sera pas le cas, même si nous tâcherons d’avoir des données de même type au sein d’un tableau.
Comme dans les cas précédents, j’ai regroupé les objets utiles dans un module, qu’on importe ici.
from cours.structures import Tableau
On crée un premier tableau en précisant la taille.
t = Tableau(10)
On peut afficher le contenu du tableau. Cette possibilité n’existe ici qu’à des fins pédagogiques et n’est pas présente dans tous les langages utilisant des tableaux.
t
[None, None, None, None, None, None, None, None, None, None]
Le choix ici est d’initialiser toutes les valeurs du tableau à None.
On peut accéder à la valeur d’un élément, avec une notation qui ressemble à celles des list.
t[0]
Ici, t[0] n’affiche rien et c’est «normal».
t[0] = 1
On peut affecter une valeur à un des éléments du tableau, avec une notation compatible avec les notations sur les list.
t[0]
1
t[10]
---------------------------------------------------------------------------
IndexError Traceback (most recent call last)
Cell In[7], line 1
----> 1 t[10]
File /builds/lamadone/informatique/terminale-nsi/cours/structures.py:19, in Tableau.__getitem__(self, index)
17 return self.__L[index]
18 else:
---> 19 raise IndexError("L'indice demandé est en dehors du tableau")
IndexError: L'indice demandé est en dehors du tableau
Si on cherche à accéder à un indice qui n’existe pas, on obtient une erreur.
t.append('5')
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
Cell In[8], line 1
----> 1 t.append('5')
AttributeError: 'Tableau' object has no attribute 'append'
Le tableau ayant une taille fixe, il ne peut pas être étendu avec .append().
t1 = Tableau(1)
t2 = Tableau(1)
t1[0] = 1
t2[0] = 2
t1 + t2
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
Cell In[9], line 5
3 t1[0] = 1
4 t2[0] = 2
----> 5 t1 + t2
TypeError: unsupported operand type(s) for +: 'Tableau' and 'Tableau'
Il n’y a pas non plus d’opérateur d’addition/concaténation.
t1 = Tableau(1)
t2 = Tableau(1)
t3 = Tableau(2)
t1[0] = 1
t2[0] = 2
t3 = t1 + t2
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
Cell In[10], line 6
4 t1[0] = 1
5 t2[0] = 2
----> 6 t3 = t1 + t2
TypeError: unsupported operand type(s) for +: 'Tableau' and 'Tableau'
Même en déclarant le nouveau tableu à l’avance.
3.4.3.1. Exercices d’application avec des tableaux#
On se donne une liste test triée, qu’on convertit en tableau.
tableau = Tableau(8)
for k,v in enumerate([1,2,3,12,13,22,45,57]):
tableau[k] = v
Dans les deux exercices suivants, on indiquera une valeur en dehors de la liste avec \(\infty\) qu’on peut représenter en Python par float('inf') (norme IEEE 754 sur la représentation des nombres).
Écrire une fonction itérative qui, pour un tableau trié, renvoie l’indice d’une valeur donnée, en utilisant l’algorithme de dichotomie.
def dicho(tab, x) -> int:
### BEGIN SOLUTION
mil = len(tab) // 2
while x != tab[mil]:
newtab = Tableau(mil)
for k in range(mil):
newtab[k] = tab[k]
tab = newtab
mil = len(tab) // 2
return mil
else:
return float('inf')
### END SOLUTION
dicho(tableau, 7)
2
assert dicho(tableau, 2) == 1
assert dicho(tableau, 1) == 0
assert dicho(tableau, 57) == 7
assert dicho(tableau, 100) == float('inf')
assert dicho(tableau, 0) == float('inf')
---------------------------------------------------------------------------
AssertionError Traceback (most recent call last)
Cell In[14], line 1
----> 1 assert dicho(tableau, 2) == 1
2 assert dicho(tableau, 1) == 0
3 assert dicho(tableau, 57) == 7
AssertionError:
Écrire une fonction récursive qui, pour un tableau trié, renvoie l’indice d’une valeur donnée, en utilisant l’algorithme de dichotomie.
def dichoREC(tab, x) -> int:
### BEGIN SOLUTION
if len(tab)==0 :
return float('inf') # ou None cest cette ligne qui ne va pas car -1 se propage
else :
mil=len(tab)//2
if tab[mil] == x :
#print("trouvé",mil)
return mil
elif tab[mil]>x :
# on garde la partie de gauche du tableau
newtab = Tableau(mil)
for k in range(mil):
newtab[k] = tab[k]
tab = newtab
return dichoREC(tab,x)
else:
newtab = Tableau(mil)
for k in range(mil):
newtab[k] = tab[k+mil]
tab = newtab
return mil + dichoREC(tab,x)
### END SOLUTION
assert dichoREC(tableau, 2) == 1
assert dichoREC(tableau, 1) == 0
assert dichoREC(tableau, 57) == 7
assert dichoREC(tableau, 100) == float('inf')
assert dichoREC(tableau, 0) == float('inf')
https://www.cours-gratuit.com/cours-lisp/cours-lisp-les-fonctions-de-base-quote-car-cdr-cons