Programmation Python pour les scientifiques

Listes et autres structures de données - Cours avec exercices corrigés

Jean-Philippe PREAUX

Ce cours a été préparé pour le niveau CPGE MPSI, il est enseigné au Lycée Thiers. Retrouvez les exercices corrigés accompagnant ce cours à la fin de chaque partie.

Retrouvez également les deux premières parties du cours.

- Premier contact

- Premiers programmes

Les commentaires et les suggestions d'amélioration sont les bienvenus, alors, après votre lecture, n'hésitez pas. Commentez

- Titre : Programmation Python pour les scientifiques

- Auteur : Jean-Philippe PREAUX

- Parution : 12 novembre 2014

- Public visé :

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2014 Jean-Philippe PREAUX. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Voir également :

- Premier contact

- Premiers programmes

Sommaire

- I. Les listes en Python

- I-A. Présentation

- I-B. La fonction range

- I-C. La boucle for

- I-D. Exemples

- I-D-1. Exemple 1 : liste des carrés

- I-D-2. Exemple 2 : la suite de Fibonacci

- I-D-3. Exemple 3 : calcul intégral - méthode des trapèzes

- II. Approfondissement sur les listes

- II-A. Les méthodes de la classe list

- II-B. Saucissonnage ou slicing

- II-C. Copie de liste

- II-D. Listes définies par compréhension

- III. Structures de données séquentielles

- III-A. Opérations communes

- III-B. Les chaînes de caractères

- III-C. Les structures de données tuple

- IV. Les dictionnaires

- IV-A. Les dictionnaires

- IV-B. Opérations sur les dictionnaires

- IV-C. Exemples

- IV-C-1. Exemple 1 : liste constituée d'un dictionnaire

- IV-C-2. Exemple 2 : conversion majuscules

- IV-C-3. Exemple 3 : découpage en mots

- IV-C-4. Exemple 4 : conversion de dates

- IV-C-5. Exemple 5 : le crible d'Ératosthène

- V. Énoncés des exercices

- V-A. Suite arithmétique

- V-B. Moyenne et variance

- V-C. Listes définies en compréhension

- V-D. Chiffrement de César

- V-E. Triangle de Pascal

- VI. Corrigés des exercices

- VI-A. Suite arithmétique : solution

- VI-B. Moyenne et variance : solution

- VI-C. Listes définies en compréhension : solution

- VI-D. Chiffrement de César : solution

- VI-E. Triangle de Pascal : solution

- VII. Remerciements Developpez

I - Les listes en Python

I-A - Présentation

Dès que l'on commence à manipuler en Python un grand nombre de données, l'usage de variables devient insuffisant. Exemple : imaginons que l'on veuille stocker les notes des élèves d'une classe pour calculer leur moyenne et leur écart-type. On peut imaginer d'utiliser N variables de type float (N étant le nombre d'élèves de la classe), puis d'écrire des fonctions moyenne() et ecart_type() prenant N paramètres ; fastidieux lorsque N=47, et il faudra la réécrire pour chaque nouvel effectif…

def moyenne47(n1, n2, ..., n47) :
return (n1 + n2 + ... + n47) / 47.0

En Python, la structure de données qui va nous aider est la liste. C'est un objet de type list qui permet de collecter des éléments : données de type quelconque : int, float, str, bool, d'autres listes, etc.

Exemple :

>>> liste = [1, 2, 3, 'toto']

>>> print liste
[1, 2, 3, 'toto']

>>> type(liste)
<type 'list'>

>>> len(liste)
4

>>> liste[0], liste[1], liste[len(liste) - 1]
(1, 2, 'toto')

Une liste est créée à l'aide d'une affectation. Ses éléments sont entre crochets […]. La fonction len() prend en argument une liste et retourne son nombre d'éléments. Les éléments d'une liste s'obtiennent grâce à leur indice entre crochets. Attention, le premier élément a pour indice 0 !

Exemple : reprenons notre problème de calcul de la moyenne des notes. Mettons à profit ce que nous avons vu sur les listes ainsi que la fonction sum() qui prend en argument une liste et retourne, lorsque c'est possible, le résultat de l'opération '+' sur ses éléments.

Saisissons la liste des notes :

>>> liste_notes = [10, 12, 14, 6, 8, 15, 3, 17]   # la liste de notes

Définition de la fonction moyenne() qui s'applique à toute liste non vide de nombres :

>>> def moyenne(liste) : # fonction moyenne()
return sum(liste) / float(len(liste))

>>> moyenne(liste_notes)
10.625

On obtient le résultat attendu, la moyenne est de 10,625. Sans la conversion en float d'un des arguments de la division, le résultat retourné aurait été 10 (quotient de la division entière) sous Python 2 (mais pas sous Python 3).

Les listes sont des objets modifiables (on dit aussi mutables) : on peut modifier leurs éléments.

>>> liste = [1, 2, 3, 'toto'] # une liste

>>> liste[0] = 'le début'
>>> liste[2] = [-1, -2, -3]
>>> print liste
['le début', 2, [-1,- 2, -3], 'toto']

>>> print liste[-1], liste[-2]
'toto' [-1, -2, -3]
>>> print liste[-5], liste[4]

IndexError: list index out of range

On modifie un élément de la liste en lui affectant une nouvelle valeur (de n'importe quel type, simple ou complexe). L'indice -1 permet d'obtenir le dernier élément. C'est plus simple que liste[len(liste) - 1]. L'indice -2 permet d'obtenir l'avant-dernier élément, etc. Un indice qui n'est pas compris entre -len(liste) et len(liste)-1 produit une erreur IndexError.

>>> print liste
['le début', 2, [-1,- 2, -3], 'toto']

>>> type(liste[0]), type(liste[1]), type(liste[2])
(<type 'str'>, <type 'int'>, <type 'list'>

>>> print liste[2][0] # liste[2] est une liste
-1

Les éléments d'une liste sont des valeurs de différents types, celles qu'on lui a affectées.

Une liste de listes permet de constituer un tableau bi-dimensionnel.

>>> l=[['a', 'b'], ['c', 'd']]
>>> print l[0][0], l[0][1], l[1][0], l[1][1]
a b c d

I-B - La fonction range

Avec un argument entier n, range(n) retourne la liste des n premiers entiers.

>>> print range(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Avec deux arguments entiers m, n, range(m,n) retourne la liste des max(0, n−m) entiers consécutifs qui sont compris entre m (inclus) et n (exclu).

>>> print range(0,10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> print range(-1,11)
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 10]

Avec trois arguments entiers m, k, n, range(m, n, k) retourne la liste des entiers de la forme , avec p entier naturel, et qui sont compris entre m (inclus) et n (exclu).

>>> print range(0, 10, 2)
[0, 2, 4, 6, 8]
>>> print range(10,0,-2)
[10, 8, 6, 4, 2]

Un argument non entier provoque un message d'erreur TypeError.

I-C - La boucle for

L'instruction for permet de répéter une séquence d'instructions, en boucle, pour une variable qui décrit une liste d'éléments.

On l'écrit en langage algorithmique :

Pour tout i dans liste faire :
Instruction 1
...
Instruction N

Bien sûr la variable i peut apparaître dans le bloc d'instructions (comme variable locale : c'est une « copie », la modifier n'affecte pas la liste).

for i in liste :
# instruction 1
# ...
# instruction N

produit un résultat identique à la boucle while :

L = len(liste)    # L est la longueur de la liste
j = 0             # j est l'indice
while (j < L) :   # tant que l'indice ne dépasse pas
i=liste[j]    # i est l'élément d'indice j
# instruction 1
# ...
# instruction N
j = j + 1     # incrémenter l'indice j

Une boucle while est plus générale. On a le droit de modifier la longueur de la liste dans la boucle while ; on n'en a pas le droit dans la boucle for (on peut toujours modifier les éléments de la liste). Dans une boucle for, le nombre de répétitions de la boucle est fixée à l'entrée dans la boucle, ici c'est len(liste).

I-D - Exemples

I-D-1 - Exemple 1 : liste des carrés

Nous souhaiterions créer la liste des carrés des entiers compris entre 0 et 20. Pour cela, on utilisera la méthode list.append() appliquée aux objets de type liste qui permet d'ajouter un élément en queue de liste :

>>> liste_vide=[ ]
>>> liste_vide.append('toto')
>>> print liste_vide
['toto']
>>> liste_vide.append('le héros')
>>> print liste_vide
['toto', 'le héros']

Solution : cliquez sur l'icône .

Liste des carrés

>>> liste_carres = [ ]              # initialisation
>>> for i in range(21) :
liste_carres.append(i ** 2) # actualisation

>>> print liste_carres
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400]

I-D-2 - Exemple 2 : la suite de Fibonacci

Écrire une fonction fibonacci() qui prend en argument un entier N et retourne une liste contenant les N premiers termes de la suite de Fibonacci : .

Solution : cliquez sur l'icône .

Fibonacci

>>> def fibonacci(N) :
result = [0, 1] # Initialisation
for k in range(2, N) :
result.append(result[k - 1] + result[k - 2])
return result

La définition de la fonction est proche de la définition par récurrence de la suite, la boucle for jouant le rôle de la relation de récurrence.

>>> fibonacci(16)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

I-D-3 - Exemple 3 : calcul intégral - méthode des trapèzes

Soit l'application définie sur .

Écrire une fonction trapeze() qui prend en argument deux réels et et retourne une approximation de l'intégrale de de à par la méthode des trapèzes. Comparer son résultat avec la valeur quasi-exacte.

Méthode des trapèzes : si est continue,

soit (ainsi ). Si est assez grand :

Cliquez sur l'icône .

Méthode des trapèzes

def trapeze(a, b) :
if a > b :
return -trapeze(b,a)
n = 100
pas = (b-a) / float(n)
res = (a**2+b**2) / 2.
for k in range(1,n) :
res += (a + k*pas)**2
res *= pas
return res

la boucle for permet de calculer la somme.

- L'instruction '+=' : a += b donne le même résultat que a = a + b. Elle lui est préférable, car plus rapide : dans le premier cas, la valeur de b vient s'ajouter à celle de a, dans le deuxième, les valeurs de a et b sont d'abord dupliquées en mémoire avant d'être additionnées entre elles puis le résultat est affecté à la variable a. On dispose aussi des opérateurs : '-=', '*=', '\=', etc.

On peut améliorer la fonction en prenant la fonction à intégrer et le pas en paramètres : trapeze(f, a, b, n).

La fonction à intégrer est définie par :

def carre(x) :
return x**2

Cliquez sur l'icône .

def carre(x):
return x**2

def trapeze(f, a, b, n) :
if a > b :
return -trapeze(f, b, a, n)
pas = (b-a) / float(n)
res = (f(a)+f(b)) / 2.
for k in range(1,n) :
res += f(a + k*pas)
res *= pas
return res

À l'exécution :

II - Approfondissement sur les listes

II-A - Les méthodes de la classe list

Voir More on Lists.

Méthode

Action

liste.append(x)

Pour ajouter x à la fin de la liste liste.

liste.extend(liste2)

Pour ajouter la liste liste2 à la suite de la liste liste.

liste.insert(i,x)

Pour insérer l'élément x en position i dans liste.

liste.pop()

Pour retirer et renvoyer le dernier élément dans liste.

liste.pop(i)

Pour retirer et renvoyer l'élément en position i dans liste.

liste.remove(x)

Pour retirer la première occurrence de x dans liste.

liste.index(x)

Renvoie la 1re position de x dans liste. Message d'erreur si aucune.

liste.count(x)

Renvoie le nombre d'occurrences de x dans liste.

liste.sort()

Trie la liste par ordre croissant.

liste.reverse()

Renverse l'ordre des éléments de la liste.

II-B - Saucissonnage ou slicing

>>> liste = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']

>>> liste1 = liste[2:5] # tranche (slice) de la liste
>>> print liste1
['c', 'd', 'e']

L'instruction liste1 = liste[2:5] crée une nouvelle liste liste1 dont les éléments sont ceux de liste allant de l'indice 2 (inclus : le 3e élément) à l'indice 5 (exclu : jusqu'au 5e élément, celui d'indice 4). On l'appelle une tranche (slice en anglais) de la liste.

Les indices entre crochets peuvent sortir de la plage d'indices de la liste :

>>> liste2 = liste[0:100] # tranche des indices de 0 à 100
>>> print liste2
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']

Un troisième paramètre définit un pas :

>>> liste3 = liste[6:2:-1] # tranche des indices de 6 à 2 par pas de -1
>>> print liste3
['g', 'f', 'e', 'd']

Les ':' séparent les champs qui sont optionnels.

LISTE[indice départ (inclus) : indice arrivée (exclu) : pas]

Python crée la tranche en copiant l'élément de LISTE d'indice indice de départ, puis tous les éléments obtenus en ajoutant successivement pas à l'indice, tant qu'on ne dépasse pas indice d'arrivée. Par défaut : pas = 1.

- Si pas>0 : indice départ = 0 ; indice arrivée = len(LISTE)

- Si pas<0 : indice départ = len(LISTE)-1 ; indice arrivée = -1

>>> liste4 = liste[::2]    # slicing par pas de 2
>>> print liste4
['a', 'c', 'e', 'g', 'i']
>>> liste5 = liste[::-1]   # slicing par pas de -1
['i', 'h', 'g', 'f', 'e', 'd', 'c', 'b', 'a']

>>> liste5 = liste[3::2] # départ de l'indice 3, par pas de 2
>>> print liste5
['d', 'f', 'h']
>>> liste6 = liste[:3:-1]    # départ de la fin par pas de -1, arrêt avant l'indice 3
>>> print liste6
['i', 'h', 'g', 'f', 'e']

>>> liste7 = liste[:] # Pour copier une liste
>>> print liste7
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']

II-C - Copie de liste

Il faut prendre garde à la façon dont Python copie une liste. Illustrons cela sur un exemple.

- Copie d'une liste : jusqu'ici tout va bien.

>>> liste = ['a', 'b', 'c'] # définition d'une liste
>>> copie = liste           # puis copie de la liste
>>> print copie
['a', 'b', 'c']

- Modification d'un élément de la liste originelle. Tout se passe comme prévu.

>>> liste[0] = 'modifié'    # Modifions un élément dans liste
>>> print liste
['modifié', 'b', 'c']

- Mais, ô surprise, la copie aussi a été modifiée… contrairement à ce qu'on aurait pu attendre.

>>> print copie             # regardons ce qu'est devenue la copie
['modifié', 'b', 'c']

Explication : en fait, une liste en Python ne contient que l'adresse mémoire où sont stockés ses éléments ; c'est ce que l'on appelle un pointeur.

Quand on copie liste dans copie, c'est cette adresse mémoire qui est copiée. C'est un alias qui est créé.

Quand on modifie un élément d'une liste, il est alors aussi modifié dans la copie. L'avantage étant qu'on encombre moins la mémoire centrale puisque les éléments de la liste ne figurent qu'en un seul emplacement mémoire.

Pour preuve, on peut utiliser la fonction intégrée id() qui retourne un entier long étant l'image de l'adresse mémoire où est stocké l'objet passé en argument. Les deux objets ont le même « identifiant ».

>>> print id(liste), id(copie)
139807842040576 139807842040576

On peut contourner ce problème grâce à copie = liste[:] qui fait une « copie superficielle » :

>>> liste = ['a', 'b', 'c'] # définition d'une liste
>>> copie = liste[:]        # puis copie superficielle de la liste
>>> print copie
['a', 'b', 'c']
>>> liste[0] = 'modifié'    # Modifions un élément dans liste
>>> print liste
['modifié', 'b', 'c']
>>> print copie             # regardons ce qu'est devenue la copie
['a', 'b', 'c']

Python fait une copie des éléments de la liste, mais c'est l'adresse mémoire des objets qui est copiée. Aussi, si l'un des éléments de la liste est aussi une liste, on retombe sur le même problème :

>>> liste = ['a', 'b', [0, 1]]  # définition d'une liste
>>> copie = liste[:]            # puis copie superficielle de la liste
>>> liste[0] = 'modifié'        # Modifions un élément dans liste
>>> liste[2][0] = 'MODIF'       # et un élément dans liste[2]
>>> print liste; print copie    # regardons ce qu'est devenue la copie
['modifié', 'b', ['MODIF',1]]
['a', 'b', ['MODIF',1]]

Pour contourner totalement le problème, utilisez la méthode liste.deepcopy() du module standard copy qui effectue une « copie profonde »:

>>> from copy import deepcopy
>>> copie = deepcopy(liste)

II-D - Listes définies par compréhension

On peut définir une liste à l'aide des mots-clés for, in et if comme on définit un ensemble en mathématiques « en compréhension » :

[f(x) for x in liste] correspond à .

Exemple :

>>> liste = range(10)             # définition de la liste des entiers de 0 à 9
>>> liste_carres = [x**2 for x in liste] # liste des carrés des éléments de liste
>>> print liste_carres
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

[f(x) for x in liste if Condition(x)] correspond à .

Exemples :

>>> liste = [x**2 for x in liste if (x % 2 == 0)] # Carrés des éléments pairs
>>> print liste
[0, 4, 16, 36, 64]

- Liste des multiples de 12 entre 0 et 100 :

>>> liste = [x for x in range(101) if x % 12 == 0] # Multiples de 12
>>> print liste
[0, 12, 24, 36, 48, 60, 72, 84, 96]

- Liste des diviseurs d'un entier naturel n :

>>> n = 120
>>> diviseurs = [x for x in range(1,n+1) if (n % x == 0)] # Diviseurs de n
>>> print diviseurs
[1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]

On peut réécrire la méthode des trapèzes précédente en utilisant une liste en compréhension :

def trapeze2(f, a, b, n):    # version 2 avec liste en compréhension
if a > b :
return -trapeze2(f, b, a, n)
pas = (b-a) / float(n)
res = (f(a)+f(b)) / 2.
res += sum([f(a + k*pas) for k in range(1,n)])
res *= pas
return res

III - Structures de données séquentielles

III-A - Opérations communes

Les types int, float, bool sont des types scalaires. Les types list (listes) et str (chaînes de caractères) sont des structures de données séquentielles. Tous les objets de type séquentiel ont en commun les opérations suivantes :

Opération

Résultat

s[i]

élément d'indice i de s

s[i:j]

Tranche de i (inclus) à j (exclu)

s[i:j:k]

Tranche de i à j par pas de k

len(s)

Longueur de s

max(s), min(s)

Plus grand et plus petit élément de s

x in s

True si x est dans s, False sinon

x not in s

True si x n'est pas dans s, False sinon

s+t

Concaténation de s et t

s*n, n*s

Concaténation de n copies de s

s.index(x)

Indice de la 1re occurrence de x dans s

s.count(x)

Nombre d'occurrences de x dans s

où s et t sont des objets séquentiels de même type, et i, j, k, n sont des entiers.

III-B - Les chaînes de caractères

Les objets de type str, chaînes de caractères, sont des structures de données séquentielles :

>>> chaine = 'Amanda'
>>> len(chaine)
6
>>> print chaine[::-1]
adnamA
>>> chaine.count('a')
2
>>> print chaine*2
AmandaAmanda
>>> max(chaine) # minuscules sont > majuscules puis ordre alphabétique
'n'

Ce ne sont pas des objets modifiables : changer un élément produit une erreur TypeError :

>>> chaine[0] = 'Z'

TypeError: 'str' object does not support item assignment

Exemple : écrire une fonction qui teste si une chaîne est un palindrome (cliquez sur l'icône ).

>>> def palindrome(c):
return (c == c[::-1])
>>>
>>> palindrome('kayak')
True
>>> palindrome('radar')
True
>>>

Exemple : la recherche d'un mot dans une chaîne de caractères est un problème essentiel en informatique qui admet des algorithmes élaborés et efficients (temps d'exécution, utilisation de la mémoire). Donner une solution naïve et peu efficiente n'est pas difficile :

def contient(chaine, mot):
m = len(chaine)
n = len(mot)
for i in range(m-n+1):
if (mot == chaine[i:i+n]): # comparaison du mot et de la tranche de longueur n
return True
return False

Le résultat est lent et coûteux en mémoire, car la fonction doit effectuer jusqu'à (N-n) copies d'une liste de longueur n, et pour chacune des n comparaisons, soit de l'ordre de opérations et fois l'emplacement nécessaire au stockage d'un caractère utilisé.

III-C - Les structures de données tuple

En français t-uplet. Ce sont des objets séquentiels. On les définit par la liste de leurs éléments, comme pour une liste, mais entre parenthèses (…).

>>> seq = (0,1,2,3)
>>> print seq
(0, 1, 2, 3)
>>> print seq[0]
0
>>> print seq*2
(0, 1, 2, 3, 0, 1, 2, 3)
>>> seq[0] = 1

TypeError: 'tuple' object does not support item assignment

Ils diffèrent des listes surtout en ce que ce sont des objets non-modifiables (non mutables) : seq[0] = 1 produit une erreur TypeError. Les parenthèses sont optionnelles :

>>> a = 2
>>> 2*a, 3*a, 4*a  # retourne un t-uplet
(4, 6, 8)

IV - Les dictionnaires

IV-A - Les dictionnaires

Ce sont des structures de données qui ne sont pas séquentielles : un élément n'est plus repéré à l'aide d'un indice, mais à l'aide d'un nom (sa clef). C'est un champ : couple d'une clef et de sa valeur. La valeur peut être de type quelconque, la clef un nombre, une chaîne ou un t-uplet.

Cette structure de données s'appelle en Python un « dictionnaire » et dans d'autres langages un enregistrement.

Un dictionnaire se définit entre accolades {…}, par la suite des champs (la clef suivie de la valeur, séparées par un deux-points ':').

France = {'Capitale' : 'Paris', 'Superficie' : 674800, 'Population' : 65000000, 'Langue' : 'Français'}

C'est identique à :

France = {}
France['Capitale'] = 'Paris'
France['Superficie'] = 674800
France['Population'] = 65000000
France['Langue'] = 'Français'

L'accès à un élément se fait à l'aide de sa clef :

>>> France['Capitale']
'Paris'

Pour ajouter un champ, affectez une valeur à une nouvelle clef. Pour supprimer un champ, utilisez la fonction del().

>>> France['Continent'] = 'Europe' # ajout d'un champ
>>> del(France['Capitale'])        # suppression d'un champ
>>> print France
{'Continent' : 'Europe', 'Superficie' : 674800, 'Population' : 65000000, 'Langue' : 'Français'}

IV-B - Opérations sur les dictionnaires

Les dictionnaires admettent les méthodes suivantes :

dict.keys()

retourne la liste des clefs du dictionnaire dict

dict.values()

retourne la liste des valeurs du dictionnaire dict

dict.items()

retourne la liste des champs (key, value) de dict

dict.copy()

retourne une copie du dictionnaire

IV-C - Exemples

IV-C-1 - Exemple 1 : liste constituée d'un dictionnaire

Pour enregistrer une liste constituée d'un dictionnaire pour chaque élève d'une classe d'effectif 47 élèves, chaque dictionnaire comportant des champs pour les nom, prénom, âge et seconde langue :

eleves = []
for i in range(47):
dico = {}
dico['Nom'] = raw_input('Nom ? ')
dico['Prénom'] = raw_input('Prénom ? ')
dico['Age'] = int(raw_input('Age ? '))
dico['LV2'] = raw_input('Seconde Langue ?')
eleves.append(dico)

Remarque : le dictionnaire dico est une variable locale, une nouvelle est créée à chaque passage dans la boucle for qui n'a plus rien à voir avec les définitions de dico précédentes. Écrivons maintenant une fonction qui recherche si un élève de nom donné est dans la classe et si oui, retourne son dictionnaire.

def search(nom):
for e in eleves :  # pour chaque élément de la liste
if e['Nom'] == nom :
return e
return False

IV-C-2 - Exemple 2 : conversion majuscules

Écrire une fonction qui convertit une chaîne de caractères de minuscule à majuscule.

On utilisera la table de caractères ASCII : des caractères codés par un nombre entre 0 et 255 (0x00 et 0xFF, un octet) :

- chr(n) retourne le caractère ASCII de code n ;

- ord('a') renvoie le code ASCII du caractère 'a' ;

- Les lettres minuscules (et majuscules) sont rangées dans l'ordre alphabétique.

À partir du code ASCII ord('x') d'un caractère 'x', le code ASCII du caractère converti en majuscule est : ord('x')+ord('A')-ord('a').

Réponse : cliquez sur l'icône .

def majuscule(s):   # convertit une chaîne en majuscule
n = len(s)  # n= longueur de la chaîne
result = '' # result initialement chaîne vide
for i in range(n):
if ord('a') <= ord(s[i]) <= ord('z') :
result += chr(ord(s[i]) + ord('A') - ord('a'))
else : result += s[i]
return result

Exemple d'appel de la fonction majuscule() :

>>> majuscule("Bonjour l'Univers")
"BONJOUR L'UNIVERS"

Encore une fois, nous réinventons la roue à titre d'exercice puisque le module standard string nous propose une méthode upper(s):

>>> from string import upper
>>> upper("Bonjour l'Univers")
"BONJOUR L'UNIVERS"

IV-C-3 - Exemple 3 : découpage en mots

Écrire une fonction qui prend en paramètre une chaîne de caractères et retourne la liste de ces mots. Les mots sont délimités par les limites de la liste et par les espaces.

Réponse : cliquez sur l'icône .

def tranche(s):
n = len(s)          # n longueur de la chaîne s
result = []         # initialement result est la liste vide
mot = ''            # initialement mot est la chaine vide
for i in range(n):  # on parcourt la chaîne s
if s[i] != ' ':      # si le caractère lu n'est pas un espace
mot += s[i]       # on l'ajoute à la fin de mot
flag = True       # et on en garde le souvenir
else :               # si le caractère lu est un espace
if flag :          # si le caractère précédent n'était pas un espace
result.append(mot) # ajouter mot à la liste result
mot = ''           # réinitialisation de mot
flag = False       # on se souvient qu'il s'agissait d'un espace
if flag : result.append(mot) # à la sortie de for ajouter le dernier mot
return result

Exemple :

>>> tranche('Quels sont les mots de cette longue phrase?')
['Quels', 'sont', 'les', 'mots', 'de', 'cette', 'longue', 'phrase?']

Depuis le temps, Python a aussi la méthode split() en magasin, beaucoup plus élaborée :

>>> "Quels sont les mots de cette longue phrase?".split()
['Quels', 'sont', 'les', 'mots', 'de', 'cette', 'longue', 'phrase?']

IV-C-4 - Exemple 4 : conversion de dates

Écrire un programme qui convertit une date saisie sous la forme « 3 décembre 2013 » en « 3/12/2013 ». On utilisera les fonctions que l'on vient d'écrire.

Réponse : cliquez sur l'icône .

def conversion_date(s):
dico = {'JANV': '01', 'FEVR':'02', 'MARS':'03', 'AVRI':'04', 'MAI':'05',\
'JUIN':'06', 'JUIL':'07', 'AOUT':'08', 'SEPT':'09', 'OCTO':'10', \
'NOVE':'11', 'DECE':'12'}
mots = tranche(s)       # retourne la liste des mots
mois = mots[1]          # mot contient le mois
mois = majuscule(mois[0:4]) # slicing (4 lettres) puis conversion majuscule
return mots[0] + '/' + dico[mois] + '/' + mots[2]

un backslash permet d'écrire une instruction sur plusieurs lignes.

Exemple :

>>> conversion_date('3 janvier 2013')
'3/01/2013'

fonctionne même en présence de plusieurs espaces successifs (voir tranche()) ou de différentes casses.

Pour la manipulation des dates, vous trouverez de nombreuses fonctions et méthodes dans les modules standards datetime et calendar.

IV-C-5 - Exemple 5 : le crible d'Ératosthène

Écrire une fonction qui prend en paramètre un entier positif n et retourne la liste des nombres premiers inférieurs ou égaux à n en appliquant le crible d'Ératosthène.

Ératosthène, philosophe, géographe, astronome et mathématicien grec du IIIe siècle avant J.C. est célèbre pour son calcul de la circonférence de la Terre, ainsi que pour son crible, un des premiers tests de primalité.

Le crible d'Ératosthène commence à barrer dans la liste des entiers de 2 à n tous les multiples stricts des nombres non barrés qui sont successivement lus. À la fin, tous les nombres non barrés sont premiers.

Réponse : cliquez sur l'icône .

def erathostene(n):
liste = range(2,n+1) # listes des entiers de 2 à n
for i in range(n-1): # parcours de la liste par indice (pour la modifier)
if liste[i] != 0: # si le nombre est premier
k = 2
while k*liste[i] <= n :
liste[i+(k-1)*liste[i]] = 0 # Mettre à 0 les multiples
k += 1
return [p for p in liste if p!=0]       # retourne les éléments non nuls

Exemple :

>>> erathostene(100)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

V - Énoncés des exercices

V-A - Suite arithmétique

Écrire deux fonctions de paramètre N entier naturel, et qui retournent la liste des n premiers termes de la suite arithmétique de raison 12 et de premier terme 1 :

par deux méthodes différentes :

- à l'aide d'une boucle ;

- en compréhension de liste.

Évaluer la rapidité des deux fonctions en utilisant la fonction magique %timeit dans une console IPython.

Solution

V-B - Moyenne et variance

1. Écrire une fonction moyenne() prenant en paramètre une liste de nombres et qui retourne sa moyenne.

2. Écrire une fonction variance() prenant en paramètre une liste de nombres et qui retourne sa variance.

On pourra les tester sur des listes de nombres aléatoires que l'on aura créées à l'aide de la fonction random() du module random qui renvoie un décimal (float) aléatoire dans [0,1[.

Solution

V-C - Listes définies en compréhension

Construire par compréhension de liste les listes suivantes :

1. La liste des logarithmes népériens (ln) des entiers compris entre 1 et 20 ;

2. La liste des entiers compris entre 0 et 100 qui sont pairs et qui ne sont pas des multiples de 3 ;

3. La liste ['@-@', '@--@', '@---@', '@----@', '@-----@'] ;

4. La liste des couples d'entiers entre 0 et 10 dont la somme est un multiple de 5 ;

5. Écrire une fonction qui prend pour paramètre un entier n et retourne sous forme d'une liste de listes la matrice identité de rang n.

Solution

V-D - Chiffrement de César

C'est une méthode très simple de chiffrement de messages en un texte crypté pour le rendre « illisible » à qui n'en a pas la clef. Dans un message en lettres majuscules, supprimer tous les espaces et symboles, puis changer chaque lettre par sa Nième lettre suivante dans l'ordre alphabétique (après 'z' on reprend à 'a'), où N est un entier entre 1 et 25.

1. Écrire une fonction cesar_crypt() qui prend deux paramètres, la clef de chiffrement N et une chaîne de caractères en majuscules sans symbole ni espace, et renvoie le chiffrement de César de la chaîne.

2. Écrire une fonction cesar_decrypt() qui prend deux paramètres, un texte crypté et la clef, puis retourne le texte décrypté.

Solution

V-E - Triangle de Pascal

Écrire une fonction pascal_triangle() qui prend en paramètre un entier et retourne une liste constituée de listes, la liste contenant les coefficients binomiaux .

Par exemple pour le résultat retourné devrait être : [[1], [1, 1], [1, 2, 1]].

Pour cela, on appliquera : et la relation de Pascal :

Solution

VI - Corrigés des exercices

VI-A - Suite arithmétique : solution

À l'aide d'une boucle :

def suite1(n) :
result = []
for i in range(n) :
result.append(12*i+1)
return result

En compréhension de liste :

def suite2(n) :
return [12*i+1 for i in range(n)]

Dans une console IPython :

%timeit(suite1(1000000))
1 loops, best of 3: 140 ms per loop

%timeit(suite2(1000000))
10 loops, best of 3: 93.4 ms per loop

La fonction avec la définition de la liste en compréhension est plus rapide.

VI-B - Moyenne et variance : solution

- Calcul de la moyenne :

def moyenne(liste):
if (liste != []) :
return float(sum(liste)) / len(liste)

>>> from random import random
>>> L = [random() for i in range(100)]
>>> moyenne(L)
0.49407951863783545

- Calcul de la variance, à l'aide de la définition

def variance(liste) :
if (liste != []) :
esp = moyenne(liste)
liste2 = [(x-esp)**2 for x in liste]
return moyenne(liste2)

- Calcul de la variance, à l'aide de la formule de König-Huygens :

def variance(liste) :
return moyenne([x**2 for x in liste]) - moyenne(x)**2

VI-C - Listes définies en compréhension : solution

1. La liste des logarithmes népériens (ln) des entiers compris entre 1 et 20 :

>>> from math import log # import de log du module math
>>> liste1 = [log(n) for n in range(1,21)]
>>> print liste1
[0.0, 0.6931471805599453, 1.0986122886681098, 1.3862943611198906, 1.6094379124341003, 1.791759469228055, 1.9459101490553132, 2.0794415416798357, 2.1972245773362196, 2.302585092994046, 2.3978952727983707, 2.4849066497880004, 2.5649493574615367, 2.6390573296152584, 2.70805020110221, 2.772588722239781, 2.833213344056216, 2.8903717578961645, 2.9444389791664403, 2.995732273553991]

2. La liste des entiers compris entre 0 et 100 qui sont pairs et qui ne sont pas des multiples de 3 :

>>> liste2 = [n for n in range(0,101) if (n % 2 == 0) and (n % 3 != 0)]
>>> print liste2
[2, 4, 8, 10, 14, 16, 20, 22, 26, 28, 32, 34, 38, 40, 44, 46, 50, 52, 56, 58, 62, 64, 68, 70, 74, 76, 80, 82, 86, 88, 92, 94, 98, 100]

3. Une alternative plus rapide :

>>> liste2 = [n for n in range(0,101,2) if (n % 3 != 0)]
>>> print liste2
[2, 4, 8, 10, 14, 16, 20, 22, 26, 28, 32, 34, 38, 40, 44, 46, 50, 52, 56, 58, 62, 64, 68, 70, 74, 76, 80, 82, 86, 88, 92, 94, 98, 100]

4. La liste ['@-@', '@--@', '@---@', '@----@', '@-----@'] :

>>> ['@' + '-' * n + '@' for n in range(1,6)]
['@-@', '@--@', '@---@', '@----@', '@-----@']

5. La liste des couples d'entiers entre 0 et 10 dont la somme est un multiple de 5 :

>>> [(i, j) for i in range(11) for j in range(11) if (i+j) % 5 == 0]
[(0, 0), (0, 5), (0, 10), (1, 4), (1, 9), (2, 3), (2, 8), (3, 2), (3, 7), (4, 1), (4, 6), (5, 0), (5, 5), (5, 10), (6, 4), (6, 9), (7, 3), (7, 8), (8, 2), (8, 7), (9, 1), (9, 6), (10, 0), (10, 5), (10, 10)]

6. Écrire une fonction qui prend pour paramètre un entier n et retourne sous forme d'une liste de listes la matrice identité de rang n :

def IdMat(n):
return [[0 for j in range(k)]+[1]+[0 for j in range(n-1-k)] for k in range(n)]

>>> IdMat(2)
[[1, 0], [0, 1]]
>>> IdMat(3)
[[1, 0, 0], [0, 1, 0], [0, 0, 1]]
>>> IdMat(4)
[[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]

VI-D - Chiffrement de César : solution

- Fonction de chiffrement :

>>> def cesar_crypt(ch, n) :
...     result = ''
...     for i in range(len(ch)) :
...         result += chr((ord(ch[i]) + n-ord('A')) % 26 + ord('A'))
...     return result
...
>>> print cesar_crypt('BONJOUR',1)
CPOKPVS

- Fonction de déchiffrement :

>>> def cesar_decrypt(ch, n) :
...     return cesar_crypt(ch, -n)
...
>>> cesar_decrypt('CPOKPVS',1)
'BONJOUR'

VI-E - Triangle de Pascal : solution

def pascal_triangle(n) :
result = []
for i in range(n+1) :
temp = []
for k in range(i+1):
if k == 0:
temp.append(1)
elif k == i:
temp.append(1)
else:
temp.append(result[i-1][k-1] + result[i-1][k])
result.append(temp)
return result

Exemple d'utilisation :

>>> liste = pascal_triangle(6)
>>> for x in liste :
...     print x
...
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]

VII - Remerciements Developpez

Nous remercions Jean-Philippe Préaux pour la publication de ces cours avec exercices sur Developpez. Merci à toute l'équipe de rédaction ayant contribué à cette publication et particulièrement à f-leb. Un grand merci également à milkoseck pour ses corrections orthographiques.