Principaux types de données. Cours et TP.

Types de données
C. Charignon
Table des matières
I
Cours
2
1
Introduction, et types simples
2
2
Listes / tableaux
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Principales commandes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2
3
3
Chaînes de caractères
3.1 Commandes élémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Caractères spéciaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
4
4
4
4
Booléens
4
5
Exemple : recherche d’un mot dans un texte
5
6
Bonus : pièges : types mutables
7
II
Exercices
7
1
Listes
9
2
Chaînes de caractère
9
1
Première partie
Cours
1
Introduction, et types simples
On a besoin d’enregistrer différents types de données sur un ordinateurs. Quelques exemples, vus par un utilisateur
quelconque : nombres, textes, images, vidéos, musiques...
Chaque type de donnée correspondant à une manière de coder l’information en une suite de bits. Cependant, nous
n’avons pas à nous en préoccuper : c’est automatiquement géré par le compilateur. Il faut juste avoir à l’esprit que
certains types de donnée prendront plus de place en mémoire, et seront plus long à manipuler.
Chaque langage de programmation propose un certain nombre de types de données, et permet au programmeur de
créer ses propres types.
Pour commencer, nous allons étudier quelques types simples, disponibles dans la plupart des langages.
En python, pour connaître le type de la donnée enregistrée dans une variable, on utilise type(maVariable).
Les informations à avoir à l’esprit concernant un type sont :
— La place mémoire occupée par la donnée
— Les opérations permises
— La vitesses de ces opérations
— et une subtilité aux limites du programme, présentée dans la dernière partie du cours.
Actuellement, la contrainte de la place mémoire tend à être moins importante que la contrainte de vitesse.
Pour débuter, parlons des types les plus simples, pour enregistrer les nombres :
— Les entiers. Les calculs avec les nombres entiers sont exacts.
— Les flottants (nombres à virgule) : là les calculs sont approchés, il peut y avoir de gros problèmes d’erreurs
d’arrondi dans certains cas.
— Python propose aussi un type pour les nombres complexes (des flottants complexes) ! Rare dans les autres
langages.
Remarque: Python est un langage assez souple : vous avez le droit d’effectuer des opérations mélangeant des entiers
et des flottants. Le résultat sera alors un flottant. De manière générale, Python essaie souvent de deviner ce que vous
avez voulu dire quand vous tapez une instruction bizarre... Lorsqu’il devine mal, ceci crée des erreurs assez dures à
détecter...
Exemple: ’a’*6, [1,2]*6, 1+2.5, "abc"+"xyz"...
Enfin, il existe des fonctions de conversion assez souples également. Par exemple :
— int(maVariable) transforme la variable en entier si possible
— float(maVariable) transforme la variable en flottant si possible
— str(maVariable) transforme la variable en chaîne de caractère si possible
— list(maVariable) transforme la variable en liste si possible
— etc...
Dans un chapitre ultérieur nous étudierons en détail les types entiers et flottants, et surtout la manière dont ils sont
implémentés concrètement.
2
2.1
Listes / tableaux
Introduction
Disons-le tout de suite : Python utilise un amalgame de liste et de tableau qu’il appelle "list". Mais c’est une
exception parmi les langages de programmation.
2
Donc vous ne trouverez pas de type "array" dans python de base. Cependant, en chargeant la bibliothèque "numpy",
on a accès à un tel type.
Les listes et les tableaux sont utilisés lorsqu’on a de nombreuses données à sauvegarder.
Voici les opérations possibles pour chacun de ces deux types :
Listes
Tableaux
— créer une liste vide
— Rajouter ou supprimer des éléments
— Créer un tableau d’un taille fixée
— Lire et modifier un élément du tableau
Bien sûr, étant donné un tableau, si n est sa longueur, il est toujours possible de rajouter un élément : il suffit de
créer un autre tableau d’une taille n + 1, puis de recopier les n premières données du premier vers le second tableau.
Mais cette opération prendra un certain temps... Alors que dans une liste, elle sera quasi instantanée.
Ainsi, le choix d’utiliser un tableau ou une liste permet d’optimiser la vitesse d’exécution selon le type d’opérations
à faire. En gros :
• Si on sait le nombre de données à enregistrer : tableau
• Sinon : liste.
En python, il n’y a pas de vraie liste ! Le type que python appelle "list" est plutôt un tableau, mais un peu modifié
pour permettre de rajouter ou d’enlever des éléments en un temps "raisonnable" (disons 2 fois plus lent qu’une vraie
liste dans un autre langage en moyenne).
Ainsi en programmation python, on utilise le type "list" comme type à tout faire.
2.2
Principales commandes
Voici les principales commandes python. Les listes ou les tableaux sont toujours le type "list", on trie quand même
les commandes ci-dessous selon qu’elles se rapportent plutôt au point de vue liste ou tableau.
1. opérations de type liste :
— Créer une liste vide : maListe=[].
— Ajouter un élément x à la fin de la liste : maListe.append(x).
— Retirer le dernier élément de la liste : maListe.pop().
Plus généralement, maListe.pop(i) enlève l’élément d’indice i.
En outre, ceci renvoie l’élément enlevé : par exemple l’instruction a=maListe.pop() enlève le dernier
élément de la liste et l’enregistre dans a.
— Concaténer deux listes : liste1 + liste2.
2. Opération de type tableau :
Attention : les éléments du tableau sont indicés à partir de 0. Ainsi, si le tableau T contient n éléments, le premier
est T[0] et le dernier est T[n-1]. Notamment, T[n] renvoie une erreur.
Remarque: Pour parcourir tous les éléments du tableau avec une boucle pour, on utilisera donc for i in range(0,n),
ou même for i in range(0, len(T)) on voit une certaine cohérence dans la syntaxe python.
— créer un tableau de longueur n : plusieurs possibilités. Par exemple : monTableau = list( range(0,n)).
Avec cette méthode, le tableau sera prérempli avec tous les nombres de 0 à n − 1.
— longueur du tableau : len(monTableau).
— accéder à l’élément d’indice i : monTableau[i].
— modifier l’élément d’indice i : monTableau[i]=nouvelle valeur.
3
3
Chaînes de caractères
3.1
Commandes élémentaires
Les chaînes de caractère permettent d’enregistrer des textes. Voici les opérations élémentaires, ce sont en fait les
mêmes commandes que pour les listes :
— créer une chaîne : maChaine= "abc" ou maChaine=’abc’
— le mot vide : "" ou ’’.
— longueur de la chaîne : len(maChaine).
— accéder au caractère d’indice i : maChaine[i]
— concaténer deux chaînes : chaine1 + chaine2.
Remarque: Contrairement aux tableaux, il n’est pas possible de modifier une chaîne en place : une commande de type
maChaine[i] = ’x’ renvoie une erreur. On dit qu’une chaîne est "non mutable".
Remarque: Un raccourci python : si L est une liste ou une chaîne, alors L[a:b] renvoie la liste ou la chaîne formée
des éléments d’indice a jusqu’à b − 1.
3.2
Caractères spéciaux
Il existe certains caractères spéciaux, qui sont signalés par une barre contre-oblique (antislash en anglais). Voici
juste les deux plus utiles :
— Aller à la ligne : \n sous linux, \r\n sous windows, et \r sous mac.
— Et pour afficher une contre-oblique ? C’est \\.
Exemple: Pour ouvrir un fichier (en lecture ici), la syntaxe python est monFichier=open("adresse du fichier", r).
Que faut-il taper pour ouvrir le fichier windows C:\nouveau dossier\mon fichier.txt ?
3.3
Commentaires
La façon dont on enregistre un texte s’appelle l’encodage. A l’origine, chaque lettre était encodée sur 1 octet, donc
8 bits, ce qui fait 256 lettres possibles. Cet encodage s’appelle ASCII.
Mais les 256 lettres se sont vite avérées insuffisante lorsqu’on a voulu prendre en comptes les accents et de nombreux symboles spéciaux. Quasiment chaque pays a alors développer un (ou plus) encodage(s) pour sa langue...
Vous avez sûrement déjà reçu un fichier texte qui à l’ouverture affiche des symboles ésotériques au lieu des lettres
accentuées par exemple : c’est que la personne qui a créé le fichier n’utilise pas le même encodage que votre ordinateur.
Le dernier encodage en date est l’utf-8, il est capable d’encoder a priori tous les caractères de toutes les langues.
Une lettre est codée a priori sur 8 octets (d’où le nom), mais si besoin on peut rajouter des octets pour de nouveaux
caractères.
En python, pour préciser l’encodage que vous utilisez en créant votre fichier, vous pouvez indiquer :
# -*- coding: utf-8 -*- au début du fichier.
tant que condition :
à faire tant que la condition est remplie
fin
4
Booléens
Les booléens sont au nombre de deux : "vrai" et "faux". En python : True et False. C’est bien sûr le type qu’on
obtient en résultat d’un test. Et c’est bien sûr le type qu’on utilise dans les tests, et les boucles "tant que".
4
On utilise souvent des fonctions qui renvoient un booléen. Par exemple, écrivons une fonction divise qui prend
deux entiers a et b en entrée et qui renvoie "vrai" si a|b et "faux" sinon (en python ci-dessous) :
def divise(a,b):
if b%a==0:
return(True)
else:
return(False)
Maintenant, nous pouvons utiliser cette fonction pour écrire une autre fonction renvoyant "vrai" si un nombre est
pair, et "faux" sinon :
def estPair(n):
if divise(2,n):
return(True)
else:
return(False)
Vous avez remarqué :
— vrai se note True, et faux False.
— Inutile de préciser divise(2,n)==True pour utilisation dans le test.
Exemple: Recherche dans un tableau : écrire un algorithme prenant en entrée un tableau T et une autre variable a,
et recherchant si a est un élément de T . Amélioration : si a est effectivement dans T , afficher l’indice i tel que T [i] = a.
Exemple: Reprenons l’exercice sur le jeu (ex 2 du TD1), en employant une variable gagné qui vaudra "vrai"
lorsque le joueur a gagné, et "faux" sinon.
Cette méthode est très générale : dès qu’une boucle "tant que" menace d’être un peu compliquée, utiliser une variable qui vaudra "vrai" tant qu’il faut continuer et "faux" dès qu’il faut sortir de la boucle (ou l’inverse). Une telle
variable s’appelle un "drapeau".
5
Exemple : recherche d’un mot dans un texte
Cet algorithme figure dans la liste des exemples classiques du programme officiel. A savoir refaire donc !
Soient t et m deux chaînes de caractères. Le but est de rechercher si m figure dans t. (Penser par exemple que t est
un grand texte, et m un simple mot.)
Pour simplifier la compréhension et l’écriture de l’algorithme, nous allons créer un petit algorithme intermédiaire
ChercheMotALaPlacei qui étant donné un entier i regarde si le mot m est présent dans le texte t à la place i.
Nous prenons donc en entrée les chaînes de caractère t et m ainsi que l’entier i. Et nous renverrons un booléen.
Nous allons parcourir toutes les lettres de m et vérifier à chaque fois si il y a la même lettre à la place correspondante
dans t. Pour tout k entre 0 et longueur de m -1, il s’agit donc de voir si m[k] = t[i + k].
Comme nous pouvons connaître à l’avance le nombre de lettres dans m et donc le nombre d’itération à faire, nous
pouvons utiliser une boucle "pour". Cependant, il serait également pertinent d’utiliser une boucle "tant que", car on
pourrait s’arrêter dès qu’une lettre de m diffère de la lettre correspondante dans t, ce qui fait gagner un peu de temps.
Nous allons utiliser une variable résultat de type booléen, qui devra donc à la fin de l’algorithme contenir Vrai
si et seulement si m est dans t à la place i. Au départ, nous mettrons "Vrai" dans cette variable, et dès qu’une lettre
diffère, nous passerons à "Faux".
Nous pouvons ajouter une petite vérification : pour pouvoir aller jusqu’au bout de m sans dépasser de t, il faut que
longueur(m)+i <longueur(t)
Remarque: Version astucieuse plus courte :
5
ChercheMotALaPlacei :
Entrée : t et m chaînes de caractère, i entier
Sortie : un booléen, indiquant si m est présent dans t débutant à la place i.
Vérifier que longueur(m)+i <longueur(t)
résultat ← Vrai
pour k de 0 à longueur de m-1 :
si m[k],t[k+i] :
résultat ← Faux
fin
fin
renvoyer résultat
ChercheMotALaPlacei :
Entrée : t et m chaînes de caractère, i entier
Sortie : un booléen, indiquant si m est présent dans t débutant à la place i.
Vérifier que longueur(m)+i <longueur(t)
résultat ← Vrai
pour k de 0 à longueur de m-1 :
résultat ← résultat et (m[k]=t[k+i])
fin
renvoyer résultat
ChercheMot :
Entrée : t et m chaînes de caractère
Sortie : un booléen, indiquant si m est présent dans t (à n’importe quelle place).
trouvé ← Faux
pour i de 0 à longueur(t) - longueur(m) -1 :
si chercheMotALaPlacei(t, m, i) :
trouvé ← Vrai
fin
fin
renvoyer trouvé
6
Á présent, il est facile d’écrire l’algorithme final. Attention à faire varier i seulement jusqu’à longueur(t)-longueur(m)1.
Et la version astucieuse :
ChercheMot :
Entrée : t et m chaînes de caractère
Sortie : un booléen, indiquant si m est présent dans t (à n’importe quelle place).
trouvé ← Faux
pour i de 0 à longueur(t) - longueur(m) -1 :
trouvé ← trouvé ou (chercheMotALaPlacei(t, m, i))
fin
renvoyer trouvé
6
Bonus : pièges : types mutables
Effectuer le code suivant :
T=[1,2,3,4]
S=T
S[0]=14
print(S)
print(T)
Que s’est-il passé ?
Les tableaux peuvent contenir un très grand nombre de données, et donc être très lent à recopier. Et il a décidé par
le créateur de python qu’ils ne seraient recopiés qu’un minimum de fois. Ainsi, si T est un tableau, alors l’instruction
T2=T ne recopie pas le tableau pour l’enregistrer dans la variable T2. A la place, elle fait en sorte que T2 représente le
même tableau que T.
Ainsi, toute modification de T 2 entraînera une modification de T !
Pour effecteur une vraie copie "désolidarisée" de T , charger la bibliothèque "copy", et utiliser T2=copy.deepcopy(T).
Deuxième partie
Exercices
7
8
TP : chapitre 2 : types de données
1
Listes
Exercice 1. * ! Crible d’Ératosthène
Voici un algorithme très connu permettant étant donné un entier n de calculer tous les nombres premiers entre 2 et
n.
Voici le principe : on commence par écrire tous les entiers jusqu’à n. Puis on barre les multiples de 2 sauf 2, puis
les multiples de 3 sauf 3, etc... Au final, il ne reste que les nombres premiers.
1. Écrire un algorithme barre prenant en entrée une liste L d’entiers et un entier a et qui "barre" (en pratique qui
mets 0) dans L toutes les cases d’indice multiple de a mais différent de a.
2. Programmer cet algorithme en python.
3. Écrire une fonction initialisation prenant en entrée un entier n et renvoyant une "liste" contenant tous les
entiers de 0 à n. Pour simplifier, faire en sorte que pour tout i ∈ ~0, n, L[i]=i.
4. Écrire un algorithme enleveZero prenant en entrée une liste d’entier L et renvoyant une liste contenant tous
les nombres non nuls de L. Programmer cet algorithme en python.
5. Écrire un algorithme Eratosthene prenant en entrée un entier n et renvoyant la liste des nombres premiers
entre 2 et n. Programmer cet algorithme en python.
Exercice 2. *** Diviseurs d’un entier
Le but est d’écrire un programme calculant la décomposition d’un entier en facteurs premiers.
1. Écrire un programme divise prenant en entrée deux entiers a et b et renvoyant true si a divise b et false
sinon.
Commande python utile : le quotient de la division euclidienne s’obtient par //, et le reste par %.
2. Écrire un programme diviseur prenant en entrée un entier n et calculant le plus petit diviseur positif de n.
Justifier que ce diviseur est premier.
3. Finalement, écrire un programme decomposition qui prend en entrée un entier n et qui renvoie sa décomposition en facteurs premiers. On renverra le résultat sous forme d’une liste.
2
Chaînes de caractère
Exercice 3. * Manipulation de listes et chaînes de caractères : avec la liste des élèves
En partant de la liste des élèves (dans le fichier "listeEleves.py") :
1. Compter le nombre de filles et de garçons.
2. Créer deux listes séparées, l’une contenant les filles, l’autre les garçons.
3. Rajouter avant le nom le numéro dans l’ordre alphabétique.
4. Regrouper les élèves de la classe trois par trois (créer la liste des trinômes autrement dit).
Exercice 4. ** Chercher / Remplacer
1. Écrire un algorithme prenant en entrée une chaîne de caractères t et un caractère c et cherchant si c est présent
dans t.
2. Écrire un algorithme prenant en entrée deux chaînes t et m et cherchant si m est incluse dans t.
3. Écrire un algorithme prenant en entrée trois chaînes t, m1, m2 et remplaçant toutes les occurrences de m2 par
m1.
4. Application : dans la liste des élèves remplacer tous les "Mme" par "Mlle".
9
5. Généralisation : prendre maintenant en entrée une chaîne t et deux listes de chaînes AChercher et ARemplacer.
La première liste contient des mots à rechercher, et la seconde contient les mots par lesquels les remplacer. Pour
tout i, l’élément d’indice i dans AChercher devra être remplacer par l’élément d’indice i dans ARemplacer.
6. Que devra taper un modérateur de forum pour remplacer à l’aide de votre programme dans un message t tous les
"lol" par "votre remarque fine et spirituelle suscite un sentiment certain d’hilarité" et tous les "mdr" par "votre
mot d’esprit est létal" ?
Exercice 5. *** ordre alphabétique
1. Écrire une fonction prenant en entrée deux mots m1 et m2 et renvoyant True si m1 précède m2 dans l’ordre
alphabétique, et False sinon.
2. Écrire une fonction qui trie une liste de mots par ordre alphabétique.
3. Rendre cette fonction plus générale : elle prendra en entrée une liste et une relation d’ordre et triera la liste selon
cette relation d’ordre.
10

Download Report