Listes et chaînes de caractères

É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.

É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.

É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.

1. Écrire un jeu de tests.
2. En utilisant la fonction max, implémenter la fonction demandée. On pourra initialiser une variable à la valeur None.
3. Proposer une nouvelle implémentation dmax qui ne parcourt la liste qu'une seule fois.
4. Écrire une variante dmax_bis qui renvoie le maximum si la liste contient au moins deux fois cet élément, avec un seul parcours.

É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.

À l'aide d'appels append successifs, construire la liste

1. des 100 premiers carrés d'entiers naturels (c'est-à-dire les $n^2$, pour $n\in\N$).
2. des entiers naturels $\leq 100$ qui ne sont pas divisibles par $3$.

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]))

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 ?

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$.

1. Écrire deux versions de mult, l'une utilisant concatene, l'autre utilisant etendre.
2. 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.
3. Écrire une troisième version, sans utiliser les deux fonctions précédentes.

É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.

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.

1. Proposer une première implémentation.
2. Proposer une seconde implémentation, en copiant la liste initiale.

assert(miroir([1,2,3,4]) == [4,3,2,1]).

É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.

É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 ?

É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.

1. Écrire une fonction with_removed qui prend en argument un élément e et une liste l et qui renvoie une nouvelle liste, contenant les mêmes éléments que l, mais en retirant toutes les occurrences de e.
2. Écrire une fonction remove qui prend en argument un élément e et une liste l et qui modifie la liste l en lui retirant toutes les occurrences de e.

Écrire des fonctions prenant un entier $n$ en argument et affichant les figures ci-dessous, de taille $n$.

É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)

1. É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ère None en utilisant l'instruction return None, ce qui revient à ne pas mettre d'instruction return.

• assert(indice_lettre("Bonjour", "o") == 1).
• assert(indice_lettre("Bonjour", "a") == None)

2. Écrire une fonction indice_lettre_bis, qui renvoie le dernier indice.
3. É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).

1. Écrire une fonction collection qui prend en argument une liste l et qui renvoie une nouvelle liste, qui contient les mêmes éléments que la liste l, 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 liste l.
2. 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.