Listes et chaînes de caractères
Table des matières
1. Listes
Le type list
en Python
permet de travailler avec une liste d'objets. Elle est représentée par la liste de ces objets, encadrée par des crochets, par exemple : [1,2,3]
. La liste vide ne contenant aucun objet est notée []
.
Ces objets peuvent être des entiers, des flottants, ou même d'autres listes. Habituellement, tous les objets d'une liste sont du même type, mais ce n'est pas forcément le cas.
In [1]: a = [1,2,3] In [2]: type(a) Out[2]: list
In [3]: b = ["a","ab","abc"] In [4]: type(b) Out[4]: list
In [5]: c = [1, "abc", [1,2,3]] # La liste c contient 3 objets In [6]: type(b) Out[6]: list
On peut tester si une liste l
est vide via l == []
ou len(l) == 0
.
1.1. Indexation
La fonction len
(pour length) permet de déterminer la longueur d'une liste (c'est-à-dire son nombre d'éléments).
On peut accéder au $i$−ème caractère d'une liste l
par l'indexation l[i-1]
(pour $i$ inférieur ou égal à la longueur de la chaîne). En informatique l'indexation commence toujours par $0$. Le premier élément d'une liste est à l'indice $0$, et le dernier élément d'une liste de longueur $\l$ est à l'indice $\l-1$.
In [1]: l = [0] * 8 # Création d'une liste de 0 In [2]: l Out[2]: [0, 0, 0, 0, 0, 0, 0, 0] In [3]: len(l) Out[3]: 8
In [4]: lc = [1,4,9,16] # Liste des carrés In [5]: lc[0] Out[5]: 1 In [6]: lc[len(lc)-1] Out[6]: 16
In [7]: s = 0 # On calcule la somme des carrés : In [8]: for e in lc: ...: s += e ...: s Out[8]: 30 # 1+4+9+16
Écrire une fonction qui prend en argument une liste l
et qui renvoie True
si la liste est non vide, et si ses premier et dernier éléments sont égaux, et False
sinon.
On peut indexer une liste par des entiers négatifs : l[-1]
renvoie le dernier caractère, l[-2]
l'avant-dernier, etc.
1.2. Itération
Il y a deux façons d'itérer sur les éléments d'une liste l
, ou bien sur les indices, avec for i in range(len(l))
, ou bien sur les valeurs, avec for e in l
. Les deux extraits suivants sont équivalents, et affichent tous les éléments d'une liste l
.
# i prend les valeurs de 0 à \texttt{len(l)} − 1 for i in range(len(l)): print(l[i])
# e prend toutes les valeurs des éléments de \texttt{l} for e in l: print(e)
Par valeurs ou par indices
Écrire une fonction somme
qui prend en argument une liste l
et renvoie la somme de ses éléments. On écrira deux versions, une en utilisant une boucle for e in l
et une autre en utilisant for i in range(...)
.
Écrire une fonction appartient
qui prend deux arguments : un élément e
et une liste l
et qui renvoie True
si l'élément appartient à la liste, et False
sinon.
Dans le pire des cas, la fonction précédente réalise $n$ comparaisons, où $n$ est la longueur de la liste. On dit que la complexité est linéaire.
Pour tester si un élément appartient à une liste, on peut directement utiliser l'instruction e in l
qui renvoie True
si e
appartient à l
et False
sinon. Pour évaluer cette expression, Python
procède comme pour la fonction appartient
écrite plus haut. En particulier, la complexité est linéaire.
Écrire une fonction qui prend en argument une liste non vide et renvoie le premier indice i
pour lequel l[i] > l[0]
. Si un tel indice n'existe pas, on renverra la valeur spéciale None
.
Écrire une fonction respecte_parite
qui prend en argument une liste l
d'entiers et renvoie True
si les éléments d'indices pairs de l
sont pairs et les éléments d'indices impairs de l
sont impairs.
Recherche du minimum
Les fonctions suivantes prennent en argument une liste non vide d'entiers ou de flottants.
Écrire une fonction
minimum
qui renvoie l'élément minimum de la liste.On utilisera une variable
m
, initialisée àl[0]
. Caractériser la valeur dem
au fil de l'exécution.- Sans utiliser
minimum
, écrire une fonctionpremier_indice_min
qui renvoie le premier indice où le minimum est atteint, et une variantedernier_indice_min
. Écrire une fonction
unique_minimum
qui renvoieTrue
ssi l'élément minimum de la liste n'est présent qu'une unique fois.On pourra proposer une deuxième implémentation qui ne parcourt la liste qu'une seule fois.
Étant donnés $n\geq 2$ et $x_1,\dots,x_n$ des nombres, on s'intéresse à la quantité $\max (|x_1-x_2|, |x_2-x_3|, \dots, |x_{n-1}-x_n|)$. Écrire une fonction plus_grand_ecart
qui prend en argument une liste l
de nombres et qui renvoie cette quantité, ou la valeur spéciale None
si la longueur de la liste est $\leq 1$.
On veut écrire une fonction deuxieme_max
qui prend en argument une liste l
non vide d'entiers et qui renvoie, s'il existe, le plus grand élément qui soit strictement inférieur au maximum de la liste l
. S'il n'existe pas, on renverra None
.
- Écrire un jeu de tests.
- En utilisant la fonction
max
, implémenter la fonction demandée. On pourra initialiser une variable à la valeurNone
. - Proposer une nouvelle implémentation
dmax
qui ne parcourt la liste qu'une seule fois. - Écrire une variante
dmax_bis
qui renvoie le maximum si la liste contient au moins deux fois cet élément, avec un seul parcours.
Autres
Écrire une fonction nb_pos_deb
qui prend en argument une liste d'entiers l
, et renvoie le nombre d'éléments positifs de l
d'affilée, à partir du début. Par exemple, pour [2, 1, -1, 3]
, on renverra $2$.
Proposer une seconde version utilisant une boucle while
.
Écrire une fonction est_croissante
qui prend en argument une liste d'entiers l
et renvoie True
si la liste est triée par ordre croissant, et False
sinon. Par convention, la liste vide est croissante.
Proposer une seconde version utilisant une boucle while
.
Écrire une fonction est_monotone
qui prend en argument une liste d'entiers l
et renvoie True
si la liste est triée par ordre croissant ou par ordre décroissant, et False
sinon. Par convention, la liste vide est monotone. Écrire une seconde version qui ne parcours la liste qu'une seule fois.
1.3. Création de listes
La méthode l.append(e)
modifie la liste l
, en lui ajoutant l'élément e
à la fin.
In [1]: l = [1, 2, 3] # Création d'une liste In [2]: l.append(4) # On ajoute un élément à la fin # Cet appel ne renvoie rien In [3]: l Out[3]: [1, 2, 3, 4]
Des appels successifs à la méthode append
(dans une boucle par exemple) permettent de construire des listes à partir de la liste vide []
.
Construction de listes
À l'aide d'appels append
successifs, construire la liste
- des 100 premiers carrés d'entiers naturels (c'est-à-dire les $n^2$, pour $n\in\N$).
- des entiers naturels $\leq 100$ qui ne sont pas divisibles par $3$.
des 100 premiers nombres triangulaires qui ne sont pas divisibles par $4$.
Les nombres triangulaires sont les nombres de la forme $\frac{n(n+1)}{2}$, pour $n\in\N$.
Écrire une fonction sommes_partielles
qui prend en argument une liste $\texttt{l} = [x_1,\dots,x_n]$ de longueur n
et renvoie une nouvelle liste de longueur n
contenant les $S_k = \sum_{i=1}^k x_i$.
assert(sommes_partielles([1,2,4]) == [1,3,7]))
Construire la liste de taille 100 suivante : l = [1,2,2,3,3,3,4,4,4,4,...]
.
Syntaxe en compréhension
Le language Python
propose une syntaxe propre à la création de listes, qui permet l'initialisation de listes en une seule ligne.
- La syntaxe
[k**2 for k in range(100)]
crée la liste des éléments $k^2$, pour $k\in\db{0, 99}$. - La syntaxe
[k for k in range(101) if k % 3 != 0]
crée la liste des entiers $k\in\db{0,100}$ qui ne sont pas divisibles par $3$. - La syntaxe
[0 for k in range(n)]
, ou[0 for _ in range(n)]
crée une liste avec $n$ éléments $0$.
Concaténation
- L'opérateur
+
permet de concaténer deux listes. - L'opérateur
*
permet de répéter une même liste plusieurs fois.
In [1]: [1, 2, 3] + [4, 5, 6] Out[1]: [1, 2, 3, 4, 5, 6]
In [2]: [1, 2] * 3 Out[2]: [1, 2, 1, 2, 1, 2]
Réimplémenter la concaténation, sous la forme d'une fonction concatene
qui prend en argument deux listes, et en renvoie une nouvelle.
Quel est le nombre d'opérations élémentaires effectuées, en fonction des longueurs des deux listes ?
Écrire une fonction etendre
qui prend en argument deux listes l1
et l2
et qui modifie la première liste, en lui rajoutant à la fin les éléments de la seconde, dans le même ordre. Si l=[1,2,3]
, après l'appel etendre(l,[4,5])
, la liste l
vaudra [1,2,3,4,5]
.
Quel est le nombre d'opérations élémentaires effectuées ?
Attention à la spécification des questions/exercices sur des listes. Deux schémas sont possibles.
- Ou bien on demande de modifier une liste en argument, auquel cas on ne renvoie rien.
- Ou bien on demande de renvoyer une liste, auquel cas il est sous-entendu que la liste à renvoyer est une «nouvelle» liste, et pas une liste en argument que vous avez modifié.
La modification d'une liste passée en argument est appelé un effet de bord. Il est très mal vu pour une fonction d'avoir des effets de bords sans que ceux-ci n'apparaissent clairement dans sa spécification (en l'occurrence, sans que ceux-ci n'apparaissent clairement dans la question). Imaginez si la fonction min
de la librairie Python
(pour le calcul du minimum d'une liste) avait des effets de bords non documentés…
On veut réimplémenter l'opérateur *
, sous la forme d'une fonction mult
avec en argument une liste l
et un entier $n$.
- Écrire deux versions de
mult
, l'une utilisantconcatene
, l'autre utilisantetendre
. - Donner, pour chaque version, le nombre d'opération élémentaires effectuées, en fonction de la longueur $\l$ de
l
, et de l'entier $n$ ? On cherchera à l'optimiser. - Écrire une troisième version, sans utiliser les deux fonctions précédentes.
Modification versus réaffectation
Si l
est une liste (ou plutôt une variable pointant vers une liste), les instruction l.append(2)
et l = l + [2]
peuvent sembler avoir le même effet (avec nos implémentations précédentes, elles sont équivalentes à etendre(l, 2)
et l = concatene(l, [2])
).
En fait, elles diffèrent à deux titres.
Elles n'ont pas la même complexité. L'appel
l.append(2)
est une opération élémentaire, qui s'exécute en un temps constante, alors que le calcul del + [2]
passe par la création d'une nouvelle liste, et recopie entièrement la listel
. Le nombre d'opérations élémentaires est donc de $n+1$, où $n$ est la longueur del
.À ce titre, l'instruction
l = l + [2]
est à proscrire.Plus subtilement, l'instruction
l.append(2)
modifie la liste sous-jacente, alors que l'instructionl = l + [2]
réaffecte la variablel
, sans modifier la liste d'origine.La différence est illustrée dans les extraits suivants.
In [1]: def f_modif(l): ...... l.append(2) # Effet de bord In [2]: l = [1] In [3]: f_modif(l) In [4]: l Out[4]: [1, 2]
In [1]: def f_affecte(l): ...... l = l + [2] # Réaffectation locale In [2]: l = [1] In [3]: f_affecte(l) In [4]: l Out[4]: [1]
Copie d'une liste
La méthode l.copy()
renvoie une nouvelle liste, contenant les mêmes éléments que la liste d'origine. Elle est équivalente à [l[i] for i in range(len(l))]
.
L'instruction lbis = l
n'est pas équivalente à la copie de la liste l
. Après celle-ci, les deux variables lbis
et l
pointent vers la même liste. Toute modification de la liste sous-jacente via l'une ou l'autre des variables affectera aussi l'autre variable.
In [1]: l = [1,2,3] In [2]: lbis = l # pas une vrai copie In [3]: lbis.append(4) # on modifie lbis In [4]: l Out[4]: [1, 2, 3, 4] # l a été modifiée !
In [1]: l = [1,2,3] In [2]: lbis = l.copy() In [3]: lbis.append(4) In [4]: l Out[4]: [1, 2, 3] # l n'a pas été modifiée
1.4. Modification de listes
Les opérations élémentaires de modification d'une liste sont
- la modification du $i$−ème élément d'une liste
- la méthode
append
- la méthode
pop
, qui retire et renvoie le dernier élément de la liste.
In [1]: l = [1,2,3] # Création d'une liste In [2]: l[1] = 4 # On modifie le deuxième élément In [3]: l Out[3]: [1, 4, 3]
In [6]: l.pop() # On retire un élément à la fin Out[6]: 3 # L'élément est renvoyé In [7]: l # la liste a été modifiée Out[7]: [1, 4]
Pour simplifier, on peut imaginer que les éléments d'une liste sont «enregistrés» dans des cases consécutives de la mémoire de l'ordinateur, et que la liste elle-même est la donnée de l'adresse de la case mémoire où se situe le premier élément et de la longueur de la liste. La modification du $i$-ème élément de la liste revient à modifier la valeur dans la $i$-ème case. L'ajout ou le retrait d'un élément à la fin de la liste, revient à modifier la case en question, et la longueur de la liste.
On comprend en particulier qu'il n'est pas simple de supprimer un élément qui se trouve au milieu de la liste.
Échange d'éléments
Si l
est la liste [3, 5]
. Que vaut-elle après l'exécution des extraits suivants ?
l = [3,5] l[0] = l[1] l[1] = l[0] # l = ??
l = [3,5] z = l[0] l[0] = l[1] l[1] = z # l = ??
Le deuxième extrait permet donc d'échanger les valeurs de l
aux indices $0$ et $1$.
Plus concise, l'instruction l[i], l[j] = l[j], l[i]
permet d'échanger les deux éléments d'indice i
et j
de la liste l
, sans utiliser de variable intermédiaire. Les deux extraits suivants sont équivalents.
z = l[0] l[0] = l[1] l[1] = z
l[0], l[1] = l[1], l[0]
Renverse et miroir
Écrire une fonction renverse
qui prend en argument une liste l
et la modifie en inversant l'ordre de ses éléments : Si l=[1,2,3,4]
, l'appel de la fonction renverse(l)
la modifie en [4,3,2,1]
. La fonction renverse
ne renverra rien.
Cette fonctionnalité est déjà présente en Python
sous la forme d'une méthode reverse
. Si l
est une liste, l'appel l.reverse()
modifie la liste l
comme la fonction précédente.
On veut écrire une fonction miroir
qui prend en argument une liste l
et renvoie une nouvelle liste, contenant les mêmes éléments que l
, mais dans l'ordre inverse. On ne modifiera pas la liste donnée en argument, et on ne la copiera pas.
- Proposer une première implémentation.
- Proposer une seconde implémentation, en copiant la liste initiale.
assert(miroir([1,2,3,4]) == [4,3,2,1])
.
Utilisation d'un tableau de booléens
Écrire une fonction manquants
qui prend en argument une liste l
dont les éléments appartiennent tous à $\db{0,9}$, et qui renvoie la liste des éléments de $\db{0, 9}$ qui n'apparaissent pas dans l
.
On proposera une version ne lisant la liste l
qu'une seule fois, et utilisant une liste de booléens t
, initialisé avec t = [False] * 10
.
Suppression/insertion d'un élément
Écrire une fonction supprime_ind
qui prend en argument une liste l
et un indice i
et modifie la liste l
, en supprimant et renvoyant l'élément présent à l'indice i
, et préservant l'ordre des autres éléments de l
. Quelle est la complexité de votre fonction ?
Cette fonctionnalité est déjà implémentée en Python
, sous la forme d'un argument facultatif à la méthode pop
: l'instruction l.pop(i)
retire et renvoie l'élément d'indice i
de l
. Elle a une complexité linéaire.
Écrire une fonction ajoute_debut
qui prend en argument une liste l
et un élément e
, et modifie la liste l
, en ajoutant l'élément e
au début de la liste.
- Écrire une fonction
with_removed
qui prend en argument un élémente
et une listel
et qui renvoie une nouvelle liste, contenant les mêmes éléments quel
, mais en retirant toutes les occurrences dee
. - Écrire une fonction
remove
qui prend en argument un élémente
et une listel
et qui modifie la listel
en lui retirant toutes les occurrences dee
.
2. Chaînes de caractères
En Python
, l'objet "Hello World"
est une chaîne de caractères, de type str
(pour string en anglais). Une chaîne de caractères est formée d'une suite de caractères, encadrés par des guillemets, ou des apostrophes. La chaîne ""
, qui ne contient aucun caractère, est appelée la chaîne vide.
In [1]: "Hello World" Out[1]: 'Hello World'
In [2]: type("Hello World") Out[2]: str
In [3]: print("Hello World") Hello World
Le caractère \
est utilisé pour «échapper» («escape» en anglais) d'autres caractères :
- Pour représenter un retour à la ligne, utiliser le caractère spécial
\n
. - Pour représenter le caractère
"
dans une chaîne délimitée par des guillemets, il faut utiliser\"
. - Pour représenter le caractère
\
dans une chaîne de caractère, il faut utiliser\\
.
In [1]: print("Hello\nWorld") Hello World
In [2]: print("Hello \"World\"") Hello "World"
In [3]: print("Un antislash : \\") Un antislash : \
Par défaut, la fonction print
rajoute un retour à la ligne "\n"
à la fin de ce qu'elle imprime. Ce comportement peut être changé en donnant une autre valeur à l'argument facultatif end
.
In [1]: print("Hello"); \ ...: print("World") Hello # retour à la ligne World
In [2]: print("Hello", end=""); \ ...: print("World") HelloWorld
In [2]: print("Hello", end=" "); \ ...: print("World") Hello World
2.1. Construction de chaînes
2.1.1. Concaténation
L'opérateur +
permet de concaténer (= coller) des chaînes de caractères :
In [1]: "" + "Hello" + " " + "World" Out[1]: "Hello World"
L'opérateur *
permet de répéter une chaîne plusieurs fois :
In [2]: "Hello" * 3 Out[2]: "HelloHelloHello"
In [3]: "#" * 30 Out[3]: "##############################"
Écrire des fonctions prenant un entier $n$ en argument et affichant les figures ci-dessous, de taille $n$.
In [1]: triangle1(5) * ** *** **** *****
In [2]: triangle2(5) ***** **** *** ** *
In [3]: triangle3(5) * ** *** **** *****
Écrire une fonction croix
prenant un entier $n$ en argument et imprime la figure ci-contre, de taille $n$. On utilisera deux boucles imbriquées.
In [4]: croix(9) * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2.1.2. Conversion de types
On peut obtenir une chaîne de caractères représentant l'écriture décimale d'un entier (ou d'un flottant) grâce à la fonction str
:
In [1]: str(123) Out[1]: "123"
In [1]: str(7**7) Out[1]: "823543"
Dans l'autre sens, on peut transformer une chaîne représentant une écriture décimale en un entier en utilisant int
. Cette conversion de type peut échouer.
In [1]: a = str(123) # a = "123" In [2]: b = str(456) # b = "456" In [3]: int(a+b) Out[3]: 123456 # a+b = "123456"
In [4]: int("abc") --------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-4-2dda1cc00c48> in <module> ----> 1 int("abc") ValueError: invalid literal for int() with base 10: 'abc'
Écrire une fonction cinq_fois
qui prend en entrée un entier n
et renvoie l'entier m
dont l'écriture décimale est de la forme $xxxxx$ où $x$ est l'écriture décimale de $n$.
assert(cinq_fois(3) == 33333)
assert(cinq_fois(12) == 1212121212)
Opérateur in
On peut tester si une chaîne de caractère est une sous-chaîne d'une autre chaîne grâce à l'opérateur in
:
assert("jour" in "Bonjour")
assert(not("baba" in "bambou"))
Déterminer le plus petit entier $n$ tel que l'écriture décimale de $2^n$ contienne votre année de naissance.
2.2. Indexation
La fonction len
et l'indexation fonctionnent comme pour les listes. Si c
est une chaîne, l'indexation c[i]
renvoie une chaîne, contenant un seul caractère.
In [1]: a = "Bonjour" In [2]: len(a) Out[2]: 7
In [3]: a[0] Out[3]: "B" In [4]: a[6] Out[4]: "r"
In [5]: a[7] ---------------------------------------------------------------- IndexError: string index out of range
Compléter les extraits suivants, avec ce que renvoient les instructions.
In [1]: a = "Salut" In [2]: a[3] + a[2] + a[1] Out[2]:
In [3]: b = "A B CD" In [4]: b[1] + b[3] + b[5] Out[4]:
In [5]: b[len(a)] Out[5]: In [6]: b[len(b)-1] Out[6]:
En Python
les chaînes de caractères sont immutables : contrairement aux listes, il n'est pas possible de modifier un caractère particulier dans la chaîne, ou de l’agrandir. Dans le premier cas, il faut construire une nouvelle chaîne et dans le second, les opérateurs de concaténation créent également une nouvelle chaîne.
Écrire une fonction str_egales
qui prend en arguments deux chaînes de caractères c1, c2
et qui renvoie True
si elles sont égales. Quel est, en fonction des longueurs $\l_1$ et $\l_2$ de c1
et c2
, le nombre de comparaison effectuées dans le pire des cas ?
En fait, on peut tester l'égalité de deux chaînes de caractères avec l'instruction c1 == c2
. Cette instruction a une complexité linéaire en le minimum des longueurs, comme l'implémentation précédente.
On imagine la chaîne de caractère infinie "12345678910111213..."
. Déterminer le millionième chiffre (caractère) de cette chaîne.
Itération sur les caractères d'une chaîne
On peut écrire une boucle qui énumère les caractères d'une chaîne des deux façons équivalentes suivantes.
ch = "Bonjour" # Chaîne de longueur ℓ for i in range(len(ch)): # i∈〚0,ℓ−1〛 print(ch[i])
ch = "Bonjour" for car in ch: # car prend les valeurs "B", "o", ... print(car)
- Écrire une fonction
indice_lettre
qui prend en arguments deux chaînes de caractères, la deuxième étant une lettre et qui renvoie le premier indice où la lettre se trouve dans le mot. Si le mot ne contient pas cette lettre, on renverra une la valeur particulièreNone
en utilisant l'instructionreturn None
, ce qui revient à ne pas mettre d'instructionreturn
.
assert(indice_lettre("Bonjour", "o") == 1)
.assert(indice_lettre("Bonjour", "a") == None)
- Écrire une fonction
indice_lettre_bis
, qui renvoie le dernier indice. - Écrire une fonction
liste_indices
qui renvoie la liste des indices.
Écrire une fonction affiche_miroir
qui prend en argument une chaîne de caractères et affiche les caractères de la chaîne, dans l'ordre inverse : affiche_miroir("Bonjour")
affichera ruojnoB
. On utilisera des appels de la forme print(char, end="")
, pour éviter l'ajout de retour à la ligne (caractère \n
).
2.3. Exercices
Écrire une fonction long_prefixe_commun
qui prend en argument deux chaînes de caractères et renvoie la longueur du plus long préfixe commun.
assert(long_prefixe_commun("Bonjour", "Bonsoir") == 3)
: le plus long préfixe commun est "Bon"
.
- Écrire une fonction
palindrome
qui prend en argument une chaîne de caractères et renvoieTrue
si c'est un palindrome etFalse
sinon. Un palindrome est une chaîne de caractères qui peut se lire indifféremment de gauche à droite ou de droite à gauche, comme les mots"kayak"
et"ressasser"
. - ★ Écrire une seconde version, qui marche également pour des phrases avec des espaces. Par exemple
"engage le jeu que je le gagne"
est un palindrome.
Écrire une fonction vacances
qui prend en entrée une chaîne de caractères représentant une date au format jj/mm/aaaa
, et qui renvoie True
si cette date est pendant les vacances d'été (du premier juillet au 31 août), et False
sinon.
assert(vacances("15/07/2022"))
assert(not(vacances("30/06/2022")))
Écrire une fonction avant_dict
qui prend en argument deux chaînes de caractères et qui renvoie True
si la première précède la seconde pour l'ordre du dictionnaire, et False
sinon.
Pour comparer l'ordre de deux lettres, on utilisera la fonction ord
qui associe à chaque lettre un entier. Si a
et b
sont deux lettres, l'instruction ord(a) <= ord(b)
donne True
si et seulement si la lettre a
précède b
dans l'ordre alphabétique.
En fait, les opérateurs de comparaison <,>,<=,>=
fonctionnent pour des chaînes de caractères, et correspondent à l'ordre lexicographique du dictionnaire.
3. Autres parcours sur les listes
3.1. Parcours quadratiques
Écrire une fonction aucun_doublon
qui prend en argument une liste et renvoie True
si cette liste ne contient pas deux fois le même élément.
Si la liste est de longueur $n$, combien de comparaisons effectuez-vous dans le pire des cas ? Essayer d'optimiser (sans trier la liste).
Étant données deux listes $\texttt{l}_1$ et $\texttt{l}_2$ contenant chacune des éléments distincts.
Écrire une fonction
nb_elems_communs
qui renvoie le nombre d'éléments en commun de ces deux listes.Quelle est la complexité en fonction des longueurs $n_1$ et $n_2$ des deux listes ?
- ★ Sous l'hypothèse supplémentaire que les deux listes soient triées par ordre croissant, écrire une nouvelle version de la fonction précédente, avec une complexité linéaire.
Écrire une fonction valeur_majoritaire
qui prend en argument une liste l
non vide et renvoie un élément de l
qui apparaît le plus souvent.
Écrire une fonction produit_max
qui prend en argument une liste de longueur $\geq 2$ et qui renvoie la valeur maximale du produit de deux éléments de la liste d'indices distincts. Quel est le nombre (en ordre de grandeur) d'opérations effectuées par votre algorithme, en fonction de la longueur $n$ de la liste ?
assert(produit_max([1,5,3,4,1]) == 20)
.
Utilisation naïve d'une liste comme ensemble
- Écrire une fonction
collection
qui prend en argument une listel
et qui renvoie une nouvelle liste, qui contient les mêmes éléments que la listel
, mais sans doublons. Préciser la complexité de votre implémentation (éventuellement dans le pire des cas), en fonction de la longueur $n$ de la listel
. - Sous l'hypothèse supplémentaire que tous les éléments de la liste appartiennent à $\db{0,100}$, écrire une nouvelle version qui réalise de l'ordre de $n + 100$ opérations.
3.2. Parcours linéaires non triviaux
Écrire une fonction longueur_degarnie
qui prend en argument une liste l
et qui renvoie la longueur de la liste obtenue en retirant tous les $0$ au début et à la fin de l
.
assert(longueur_degarnie([0, 0, 1, 2, 0, 5, 0]) == 4)
Une suite finie $x_1,\dots,x_n$ est dite unimodale s'il existe un indice $k\in\db{1,n}$ tel que $x_1,\dots,x_k$ soit croissante et $x_k,\dots,x_n$ soit décroissante.
Écrire une fonction unimodale
qui prend en argument une liste et renvoie True
ssi la suite de valeurs qu'elle représente est unimodale.
Écrire une fonction longueur_max_plateau
qui prend en argument une liste et renvoie le plus grand entier $k$ tel que la liste contienne $k$ éléments consécutifs égaux. On veut une implémentation avec une complexité linéaire.
assert(longueur_max_plateau([0,1,1,1,0,0,1,0]) == 3)
.
Le relief d'une montagne est représenté par une liste des altitudes $\texttt{l} = [\l_0, \dots, \l_{n-1}]$ tous les 100 mètres. Un promeneur avec un parapente est situé à l'indice $i$, donc à l'altitude $\l_i$. On dit qu'un indice $k\in\db{0,n-1}$ est atteignable à partir de $i$ si toutes les altitudes entre les indices $k$ (inclus) et $i$ (exclus) sont $\lt \l_i$.
- Écrire une fonction
largeur_atteignable
qui prend en argument la listel
et l'indice $i$, et renvoie le nombre d'indices atteignables à partir de $i$. - ★ Écrire une fonction
largueur_atteignable_max
qui prend en argument la listel
et renvoie la valeur maximale renvoyée par la fonction précédente avec une complexité en $O(n)$, puis éventuellement, en ne parcourant la liste qu'une seule fois.
4. Exercices
Écrire une fonction extremes
qui prend une liste l
en argument et renvoie la somme du premier et du dernier élément de l
. Si la liste est vide, on renverra 0
, et si la liste ne contient qu'un seul élément, on renverra cet élément.
Écrire une fonction produit_scalaire
qui prend en argument deux listes de même longueur et renvoie le produit scalaire de ces deux listes. Le produit scalaire des listes $[a_1,\dots,a_n]$ et $[b_1,\dots,b_n]$ est $\sum_{k=1}^n a_k b_k = a_1b_1 + a_2 b_2 + \dots + a_n b_n$.
Écrire une fonction ind_liste
qui prend en arguments une liste et un élément e
et renvoie la liste des indices auquel cet élément est atteint : assert(ind_liste[-3,5,8,-3], -3) == [0,3])
Écrire une fonction evalue_polynome
qui prend en argument une liste $\texttt{l} = [a_0, a_1, \dots,a_n]$ et un flottant $x$ et renvoie la valeur $a_0 + a_1 x + \dots + a_n x^n$.
Écrire une fonction parite_constante
qui prend en argument une liste d'entier et qui renvoie True
si tous les éléments de l
ont la même parité, et False
sinon. Si la liste est vide, on renverra True
.
Créer la liste des $100$ premiers nombres de Fibonacci, c'est-à-dire des 100 premiers termes de la suite définie par $F_0=F_1=1$ et $\forall n\in\N,\,F_{n+2} = F_{n+1} + F_n$.
Écrire une fonction somme_listes
qui prend deux listes en argument et renvoie une nouvelle liste de taille égale au maximum des deux tailles et dont l'élément d'indice $i$ est la somme des éléments d'indice $i$ des deux listes ; si une des listes n'a pas d'élément d'indice $i$, elle compte comme $0$. Par exemple, somme_listes [1,2] [1,2,3]
renverra [2,4,3]
.
Écrire une fonction cycle
qui prend en argument une liste et qui permute cycliquement l'ordre de ses éléments : si l
vaut [1,2,3,4]
, après l'appel cycle(l)
, l
vaudra [2,3,4,1]
.
La variance $V$ d'une série statistique $x_1,\dots,x_n$ dont la moyenne est $m$ est donnée par la formule
$$V = \frac{1}{n} \sum_{i=1}^n (x_i - m)^2 = \frac{1}{n}\left((x_1 - m)^2 + (x_2-m)^2 + \dots + (x_n - m)^2\right).$$
Écrire une fonction variance
qui prend en argument une liste non vide d'entiers ou de flottants et qui renvoie sa variance.
Écrire des fonctions qui prennent une liste d'entiers l
en argument et renvoient
- la liste formée des éléments pairs de
l
. - la liste formée des éléments d'indices pairs de
l
. - la liste des 10 derniers éléments de
l
. Si la longueur del
est $\lt 10$, renvoyer tous les éléments del
.
La fonction randint
du module random
(à importer) prend deux arguments entiers a,b
et renvoie un entier aléatoire entre a
(inclus) et b
(exclus).
- Écrire une fonction qui renvoie une liste de taille 100 contenant 100 entiers aléatoires compris entre 0 et 99 (inclus).
- Écrire une fonction qui prend en argument une liste d'entiers et renvoie le nombre d'éléments de $\db{1,99}$ qui appartiennent à cette liste.
- En répétant l'expérience aléatoire, estimer le nombre moyen d’éléments de $\db{1,99}$ distincts obtenus lorsqu'on tire 100 fois un nombre aléatoire entre 0 et 99.
- Comparer à la valeur théorique $100 - 100 \left(\frac{99}{100}\right)^{100}$.
Écrire une fonction
médiane
qui prend une liste d'entiers en argument et renvoie une médiane de cette liste sans trier la liste.Si $\texttt{l}$ est de taille $n$, une médiane de $\texttt{l}$ est un élément $m$ de $\texttt{l}$ tel qu'au moins $\frac{n}{2}$ des éléments de $\texttt{l}$ soit $\geq m$, et au moins $\frac{n}{2}$ des éléments soit $\leq m$.
- Réécrire une fonction
médiane_bis
qui utilise la méthodesort
. Sil
est une liste, l'appell.sort()
trie la liste (donc la modifie).
Écrire une fonction prenant en argument un entier $n$ et renvoyant la liste des entiers $N$ qui peuvent s'écrire d'au moins deux façons différentes comme $N = xy$, où $1\lt x\lt y$ et $x+y \lt n$.
Écrire une fonction triangle
qui prend un entier en argument et imprime la figure ci-contre.
In [1]: triangle(5)
1
23
456
7891
01112
Un couloir est éclairé par 100 bulbes numérotés de 1 à 100. À l'origine, tous les bulbes sont éteints. On commence par actionner tous les interrupteurs. Puis on actionne tous les interrupteurs pairs, à partir du second. Puis on actionne tous les trois interrupteurs, à partir du troisième, et ainsi de suite jusqu'à 100 (compris).
- À l'aide de
Python
, déterminer quels sont les bulbes allumés à la fin. - Conjecturer le résultat si l'on remplace $100$ par $n$ quelconque, et le démontrer.
- En utilisant une liste de booléens de taille $n$, implémenter le crible d'Ératosthène et imprimer la liste des nombres premiers inférieurs à $n$.
- Quel est le nombre d'opérations élémentaires ?
On considère la suite de Conway dont les premiers termes sont $1, 11, 21, 1211, 111221, \dots$. Chaque terme est obtenu en lisant le précédent à haute voix.
- Afficher les 20 premiers termes de la suite de Conway.
- Conjecturer et démontrer une propriété remarquable de cette suite.
- Étudier expérimentalement la convergence
- de la fréquence d'apparition de chaque chiffre dans le $n$−ième terme de la suite de Conway.
- du quotient de la longueur du $n$−ième terme par la longueur du précédent.
Les entiers de Hamming sont les entiers naturels qui n'admettent aucun diviseur premier autre que $2,3$ et $5$.
- Déterminer le nombre d'entiers de Hamming inférieurs ou égaux à $10^{10}$.
- Déterminer le 2000ᵉ nombre de Hamming.
Étant donnée une liste $\texttt{l} = [\l_0,\dots,\l_{n-1}]$ dont les éléments sont des entiers positifs que l'on représente sous la forme d'un histogramme, déterminer l'aire maximale d'un rectangle de côtés entiers posé entre les abscisses $0$ et $n$ qui reste sous la courbe de $\texttt{l}$.