COURS/TP 4 : les listes

Introduction

Lors des programmes précédents, nous avons vu qu'il était possible de stocker des valeurs dans une variable, ce qui peut être pratique lorsque l'on veut calculer par exemple le terme d'une suite. Cependant, il est pour l'instant difficile de stocker beaucoup de valeurs. Par exemple, si on considère la suite $(u_n)_{n\in \mathbb{N}}$ définie par : $$ \forall i \in \{0,\cdots,100\}, u_i= i^2, \forall n \in \mathbb{N}, u_{n+101}=\sum_{k=0}^{100}u_{n+k}^2$$

Pour calculer $u_{301}$, il est nécessaire de connaître $u_{200}, u_{201}, u_{202},\cdots,u_{300}$. Ainsi à l'heure actuelle, pour écrire une fonction calculant $u_n$ on devrait utiliser $101$ variables auxiliaires, ce qui peut s'avérer un peu lourd. Pour régler ce problème, il est possible de stocker des valeurs dans des listes.

1. Définition et exemples

Soit $n\in \mathbb{N}$. Une liste de taille $n$ (ou de longueur $n$) est un objet qui contient exactement $n$ éléments. Les éléments peuvent appartenir à différents ensembles. Il existe une liste ne contenant aucun élément : la liste vide.

En Python, une liste $L$ s'écrit $[a_0,a_1,\cdots,a_{n-1}]$ où $a_i$ est le $i+1$-ème élément de la liste $L$ (ou l'élément d'indice $i$). La liste vide s'écrit $[]$.

2. Actions élémentaires sur les listes

2.1. Déterminer la longueur d'une liste

Étant donnée une liste $L$, la longueur de $L$ est le nombre d'éléments de $L$. En Python, elle est donnée par len(L).

2.2. Accéder à un élément

Étant donnée une liste $L$, l'élément d'indice $i$ est donné par L[i]. Attention, l'indexation commence à $0$. Ainsi, le premier élément est indxé par $0$ et le dernier élément par $len(L)-1$. Si on considère un indice non définie par un exemple un $j>len(L)-1$, on obtient une erreur de type "out of range" (dépassement des bornes).

2.3 Ajouter et supprimer d'un élément, concaténer deux listes

Il est possible d'ajouter un élément en fin de liste à l'aide de la commande append. Pour supprimer un élément on pourra utiliser la commande pop. Pour concaténer deux listes (mettre bout à bout deux listes) on utilise l'opérateur +.

2.4 Copier une partie de la liste

Étant donnée une liste $L=[a_0,a_1,\cdots,a_{n-1}]$, il est possible de copier la partie $[a_i,\cdots,a_{j-1}]$ comme suit : $L[i:j]$

2.5 Itérer sur les éléments de listes

Pour parcourir une liste, on peut utiliser une boucle for. Il est également possible de vérifier si un élément est présent dans une liste à l'aide de in.

3. Exemples de programmes

3.1 Tester la présence d'un élément dans une liste

On veut écrire une fonction est_present(x,L) qui renvoit True si $x$ est un élément de $L$ et False sinon (On n'utilisera pas la commande in dans un premier temps).

3.2 Trouver le maximum d'une liste

On veut écrire une fonction maxi(L) qui trouve le plus grand élément d'une liste non vide.

3.3 Calcul des termes de la suite $(u_n)$ donnée en introduction

4. Travaux pratiques

Exercice 1

Écrire une fonction moyenne(L) qui prend en argument une liste de nombres et qui renvoit la moyenne des éléments de $L$.

Exercice 2

Écrire une fonction mini(L) qui prend en argument une liste de nombres et qui renvoit la valeur la plus petite de la liste. On n'utilisera pas la fonction min native de Python.

Exercice 3

Écrire une fonctionrang_max(L) qui prend en argument une liste de nombres et qui renvoit le premier indice $i$ pour lequel $L[i]$ est égal au maximum de $L$.

Exercice 4

Écrire une fonction indice(x,L) qui renvoit la liste des indices $i$ vérifiant $L[i]=x$. Dans le cas où $x$ n'est pas un élément de $L$ la liste renvoyée est vide.

Exercice 5

Étant donnée une liste $L=[a_0,\cdots,a_{n-1}]$, on dit que $L$ est triée dans l'ordre croissant si $a_0\leq a_1 \leq \cdots \leq a_{n-1}$. Écrire une fonction est_croissante(L) qui renvoit True si $L$ est triée dans l'ordre croissant et False sinon.

Exercice 6

Étant donnée une liste $L=[a_0,\cdots,a_{n-1}]$, le renversé de $L$ est la liste $[a_{n-1},a_{n-2},\cdots,a_0]$. Écrire une fonction renverse(L) qui prend en argument une liste $L$ et qui renvoit le renversé de $L$.

Exercice 7

Pour deux entiers positifs $n$ et $d$, on rappelle que $d$ divise $n$ s'il existe $k\in \mathbb{N}$ vérifiant $n = kd$. Écrire une fonction diviseurs(n) qui prend en argument un entier naturel non nul $n$ et qui renvoit la liste de ses diviseurs.

Exercice 8

Écrire une fonction est_somme(S,L) prenant en argument un entier $S$ et une liste d'entiers $L$ et qui renvoit True s'il existe $i\neq j$ vérifiant $L[i]+L[j]=S$ et False sinon.

Exercice 9

Soit $L$ une liste d'entiers de taille $n$. Soient $0\leq i<j\leq n-1$. On dit que $(i,j)$ est une inversion si $L[i]>L[j]$. Écrire une fonction inversions(L) qui prend en argument une liste d'entiers et qui renvoit le nombre d'inversions de la liste $L$.

Exercice 11

Écrire une fonction contient(L,M) qui prend en arguments deux listes et qui renvoit True si $L$ contient tous les éléments de $M$ et False sinon.

Exercice 12

Écrire une liste divise(L,x) qui prend en arguments une liste de réels $L$ et un réel $x$ et qui renvoie une liste de la forme [L1, L2] où $L1$ est la liste des éléments de $L$ plus petits ou égaux à $x$ et $L2$ est la liste des éléments de $L$ qui sont plus grands strictement à $x$.

Pour les plus rapides

Exercice 13

On considère le problème suivant : $n$ personnes forment un cercle. Les personnes énoncent dans l'ordre les nombres de $1$ à $k$ puis reprennent à $1$ et ainsi de suite. Si une personne énonce $k$, elle sort directement du cercle. L'objectif est de trouver le rang de la dernière personne restant dans le cercle. Par exemple, pour $n = 8$ et $k=3$, on a :

1,2,3,4,5,6,7,8 (configuration initiale)

1,2,4,5,6,7,8 (3 énonce 3)

1,2,4,5,7,8 (6 énonce 3)

2,4,7,8 (1 énonce 3)

2,4,8 (7 énonce 3)

2,8 (4 énonce 3)

2 (8 énonce 3)

Donc 2 est le rang de la dernière personne restant dans le cercle.

Écrire une fonction restant(n,k) qui renvoit le rang de la dernière personne restante à l'issue de toutes les suppressions.

Exercice 14

On définit la suite $(u_n)_{n\in \mathbb{N}}$ par : $$u_0=1, \forall n \in \mathbb{N}, u_{n+1}=\sum_{k=0}^n u_k u_{n-k}.$$ Écrire une fonction suite(n) qui prend en argument un entier $n$ et qui renvoit la valeur de $u_n$.

Exercice 15

Étant donnée une liste $L=[a_0,a_1,...,a_{n-1}]$, on dit qu'elle est alternante si $a_0<a_1,a_1>a_2,...,a_{2k}<a_{2k+1},a_{2k+1}>a_{2k+2}...$. Écrire une fonction est_alternante(L) prenant en argument une liste de nombres et qui renvoie True si $L$ est alternante et False sinon.

Exercice 16

Écrire une fonction tri_croissant(L) qui prend en argument une liste $L$ et qui renvoie une liste contenant les mêmes valeurs que $L$ et ordonnée dans l'ordre croissant.