2  Structures de données

Exercice 2.1 - Listes

Une liste est une structure permettant de stocker des éléments hétérogènes:

list0 = [0, 5.4, "chaîne", True]

Les listes sont mutables, c’est-à-dire qu’il est possible d’y modifier un élément, d’en rajouter un ou d’en supprimer un sans avoir à redéfinir toute la liste.

list0[3] = False # remplace True par False
list0.append("nouveau") # ajoute la chaîne de caractères "nouveau" à la liste
list0.insert(2, 34) # insère 34 à la place 2
list0.remove(0) # enlève 0
list0

[5.4, 34, 'chaîne', False, 'nouveau']

En particulier, il faut faire attention en copiant une liste. Si l’on exécute le code suivant:

list1 = list0
list1[2] = "change"
list0

[5.4, 34, 'change', False, 'nouveau']

alors list0 est aussi modifié et est égal à list1. Pour créer une vraie copie, il faut utiliser le code suivant:

list2 = list0.copy()
list2[2] = "rechange"
list0

[5.4, 34, 'change', False, 'nouveau']

qui ne modifie pas list0. À noter qu’il est possible de modifier les éléments d’une liste à l’intérieur d’une fonction:

def f(l):
    l[0] = 0
f(list0)
list0

[0, 34, 'change', False, 'nouveau']

Enfin il est possible de créer des listes à l’aide de la compréhension de listes:

list1 = [2*i+1 for i in range(10)]
list1

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

a. Chercher dans la documentation la syntaxe pour concaténer deux listes.

b. Chercher dans la documentation la syntaxe pour extraire une tranche d’une liste, c’est-à-dire: si a est par exemple une liste de longueur 10, retourner les éléments de 6 à 9.

c. Chercher dans la documentation la syntaxe pour retourner la longueur d’une liste.

d. Écrire une fonction fibonacci(N) qui retourne la liste des \(N\geq2\) premiers termes de la suite de Fibonacci définie par \(u_{n+2} = u_{n+1}+u_n\) avec \(u_0=0\) et \(u_1=1\).

e. Écrire une fonction pascal(N) qui retourne la \(N\)-ième ligne du triangle de Pascal:

f. Soit les suites \((u_n)_{n\in\mathbb{N}}\) et \((v_n)_{n\in\mathbb{N}}\) définies par \(u_0=1\), \(v_0=1\), et

\[ \begin{align*} u_{n+1} &= u_n + v_n \,, & v_{n+1} &= 2u _n - v_n \,, \end{align*} \]

pour \(n\geq0\). Calculer \(u_{100}\) et \(v_{100}\).

g. Écrire une fonction vk(n0,K), qui pour deux entiers \(n_0\) et \(K\geq1\) calcule la suite des valeurs \(v_k\) définies par \(v_0 = n_0\) et

\[v_{k+1}=\begin{cases} 3v_{k}+1 & \text{si $v_{k}$ est impair},\\ \frac{v_{k}}{2} & \text{si $v_{k}$ est pair}, \end{cases}\]

pour \(0 \leq k < K\). Pour \(K = 1 000\) et diverses valeurs de \(n_0 \in \{10, 100, 1 000, 10 000\}\), afficher les cinq dernières valeurs calculées, c’est-à-dire \((v_{K-4},v_{K-3},v_{K-2},v_{K-1},v_K)\).

Exercice 2.2 - Tuples

Les tuples permettent tout comme les listes de stocker des éléments hétérogènes:

tuple0 = (0, 5.4, "chaîne", True)

Mais au contraire des listes, les tuples ne sont pas mutables. Il n’est pas possible d’y modifier un élément, d’en rajouter un ou d’en supprimer un sans redéfinir tout le tuple. L’avantage d’un tuple sur une liste est qu’il tuple est hashable, c’est-à-dire qu’il peut être utilisé comme clef dans un dictionnaire.

Enfin il est possible d’affecter des variables à l’intérieur d’un tuple, par exemple:

(a,b) = (1,9)

Cela est en particulier très utile pour échanger deux variables sans avoir à utiliser une variable supplémentaire:

(a,b) = (b,a)

a. Vérifier qu’un tuple est bien immutable.

b. Définir une fonction mdlast(lst,val) ayant pour argument une liste de tuples d’entiers lst et un entier val et retourner la liste de tuples avec le dernier élément de chaque tuple remplacé par val. Par exemple si lst = [(10, 20), (30, 40, 50, 60), (70, 80, 90)] alors mdlast(lst,100) doit retourner [(10, 100), (30, 40, 50, 100), (70, 80, 100)].

c. Comment convertir un tuple en liste et réciproquement ?

Exercice 2.3 - Ensembles

Les ensembles permettent de stocker des éléments hétérogènes au sens mathématique de la théorie des ensembles:

set0 = {0, 5.4, "chaîne", True}

Il est possible de tester si un élément appartient à un ensemble:

if "chaîne" in set0:
    print("dedans")

dedans

Les ensembles sont mutables, il est donc possible de rajouter ou retirer un élément d’un ensemble:

set0.add(18) # ajoute 18 à l'ensemble
set0.add(0) # ajoute 0 à l'ensemble (ne fait rien car 0 est déjà dedans)
set0.remove("chaîne") # retire "chaîne de l'ensemble

En revanche les ensembles ne peuvent contenir que des éléments hashables, c’est-à-dire immutables. En particulier un ensemble ne peut pas contenir un autre ensemble:

set1 = { {1,2}, {3}, {4} }

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[23], line 1
----> 1 set1 = { {1,2}, {3}, {4} }

TypeError: cannot use 'set' as a set element (unhashable type: 'set')

À noter qu’il existe également en Python des ensembles immutables frozenset:

frozenset0 = frozenset([0, 5.4, "chaîne", True])

Une chaîne de caractères peut être transformée en ensemble:

set1 = set('abracadabra')

Comme pour les listes, il est possible de faire des compréhensions d’ensembles:

set2 = {x for x in 'abracadabra' if x not in 'abc'}

Dans cet exemple, les chaînes de caractères sont automatiquement transformées en ensemble. À noter que l’ensemble vide est défini par set().

a. Définir une fonction divisible(n) qui retourne l’ensemble des nombres entiers divisibles par n inférieurs ou égaux à 100.

b. Chercher dans la documentation comment faire l’intersection, l’union et la différence de deux ensembles. Déterminer les nombres inférieurs ou égaux à 100 qui sont non divisibles par 2 mais divisibles par 3 et 5.

Exercice 2.4 - Dictionnaires

Les dictionnaires sont une structure permettant de stocker des éléments hétérogènes indexés par des clefs (elles aussi hétérogènes):

dict0 = {"pommes": 0, "poires": 4, 12: 2}

Les éléments d’un dictionnaire sont accessibles par les clefs:

dict0["pommes"]
dict0[12]

2

Un dictionnaire peut être vu comme un tableau associatif associant à chaque clef une valeur. La liste des clefs et celle des valeurs sont accessibles respectivement avec dict0.keys() et dict0.values(). Les dictionnaires sont mutables, il est donc possible de modifier une association clef-valeur et d’en rajouter ou supprimer une:

dict0["pommes"] = 3 # modifie la valeur associée à pommes
dict0["oranges"] = "beaucoup" # rajoute oranges comme clef avec la valeur "beaucoup"
del dict0["poires"] # supprime le couple clef-valeur associé à poires
dict0.pop("pommes") # supprime le couple clef-valeur associé à pommes

3

Bien qu’un dictionnaire soit mutable, les clefs qui le composent doivent être des objets hashables, c’est-à-dire immutables. Ainsi une liste ou un ensemble ne peuvent pas servir de clefs dans un dictionnaire:

dict0[list0] = "test"
dict0[set0] = "retest"

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[33], line 1
----> 1 dict0[list0] = "test"
      2 dict0[set0] = "retest"

TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

En revanche il est possible d’avoir un tuple ou un frozenset comme clef:

dict0[tuple0] = "test"
dict0[frozenset0] = "rest"

d’où l’intérêt des frozensets. Comme pour les listes et les ensembles, il est possible de faire des compréhensions de dictionnaires:

dict1 = {x: x**2 for x in range(5)}

Finalement une chose intéressante avec les dictionnaires est l’unpaking illustré par l’exemple suivant:

def add(a=0, b=0):
    return a + b
d = {'a': 2, 'b': 3}
add(**d)

5

a. Comment définir un dictionnaire vide ?

b. Comment concaténer plusieurs dictionnaires entre eux ?

c. On considère une liste de mots:

mots = ['Abricot', 'Airelle', 'Ananas', 'Banane', 'Cassis', 'Cerise', 'Citron', 'Clémentine', 'Coing', 'Datte', 'Fraise', 'Framboise', 'Grenade', 'Groseille', 'Kaki', 'Kiwi', 'Litchi', 'Mandarine', 'Mangue', 'Melon', 'Mirabelle', 'Nectarine', 'Orange', 'Pamplemousse', 'Papaye', 'Pêche', 'Poire', 'Pomme', 'Prune', 'Raisin']

Écrire une fonction position(mots, x, n) qui retourne la liste des mots ayant le caractère x comme n-ième lettre (en commençant à partir de zéro comme en Python).

d. En imaginant que la liste des mots soit très longue, alors à chaque évaluation de la fonction position l’ensemble des mots est parcouru, ce qui prend pas mal de temps. Pour améliorer cela, construire un dictionnaire mots_dict ayant pour clefs les tuples (x,n) et comme valeurs la liste des mots ayant le caractère x comme n-ième lettre, c’est-à-dire tel que mots_dict[x,n] retourne la même chose que position(mots, x , n) à l’ordre près. Ainsi la liste mots n’est parcourue qu’une seule fois lors de la construction du dictionnaire et ensuite l’évaluation du dictionnaire est extrêmement rapide pour n’importe quelle requête.