{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "Ce fichier reflète les énoncés des exercices d'un chapitre du livre *[Programmation Python par la pratique](https://www.dunod.com/sciences-techniques/programmation-python-par-pratique-problemes-et-exercices-corriges)*. Tous les énoncés peuvent être téléchargés au format [Jupyter Notebook](https://python.guillod.org/livre/) ou exécutés directement en ligne sur [GESIS](https://notebooks.gesis.org/binder/v2/gh/guillod/livre-python/v1errata). Les corrigés sont disponibles dans le livre en version papier (ISBN [9782100815142](https://www.dunod.com/sciences-techniques/programmation-python-par-pratique-problemes-et-exercices-corriges)) ou numérique (ISBN [9782100819089](https://www.dunod.com/sciences-techniques/programmation-python-par-pratique-problemes-et-exercices-corriges)) publiés chez Dunod. Ce fichier reflète les exercices tels que publiés dans cet ouvrage et diffère quelque peu des exercices présentés à la page [python.guillod.org](https://python.guillod.org/)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 2 Structures de données" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "Pour représenter des structures de données, Python propose quatre types de base: les listes (type `list`), les tuples (type `tuple`), les ensembles (type `set`) et les dictionnaires (type `dict`). Le but de ce chapitre est de montrer les différences fondamentales entre ces structures de données et d'expliquer à quoi elles sont le plus adaptées. La documentation détaillée sur les structures de données est disponible [ici](https://docs.python.org/fr/3/tutorial/datastructures.html).\n", "\n", "**Concepts abordés:**\n", "\n", "* structures de données (liste, tuple, ensemble, dictionnaire)\n", "\n", "* types mutable et immutable\n", "\n", "* type hashable\n", "\n", "* compréhensions de liste, ensemble et dictionnaire\n", "\n", "* suites numériques\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exercice 2.1: Listes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "Une liste est une structure permettant de stocker des éléments hétérogènes:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [], "source": [ "list0 = [0, 5.4, \"chaîne\", True]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Les listes sont mutables, c'est-à-dire qu'il est possible d'y modifier un élément, d'en rajouter un ou d'en supprimer un sans avoir à redéfinir toute la liste." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [], "source": [ "list0[3] = False # remplace True par False\n", "list0.append(\"nouveau\") # ajoute la chaîne de caractères \"nouveau\" à la liste\n", "list0.insert(2, 34) # insère 34 à la place 2\n", "list0.remove(0) # enlève 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En particulier, il faut faire attention en copiant une liste. Si l'on exécute le code suivant:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [], "source": [ "list1 = list0\n", "list1[2] = \"change\"\n", "list0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "alors `list0` est aussi modifié et est égal à `list1`. Pour créer une vraie copie, il faut utiliser le code suivant:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [], "source": [ "list2 = list0.copy()\n", "list2[2] = \"rechange\"\n", "list0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "qui ne modifie pas `list0`.\n", "À noter qu'il est possible de modifier les éléments d'une liste à l'intérieur d'une fonction:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def f(l):\n", " l[0] = 0\n", "f(list0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Enfin il est possible de créer des listes à l'aide de la compréhension de listes:" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [], "source": [ "list1 = [2*i+1 for i in range(10)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**a)**\n", "Chercher dans la documentation la syntaxe pour concaténer deux listes.\n", "\n", "**Indication.**\n", "Voir la documentation [ici](https://docs.python.org/fr/3/library/stdtypes.html#sequence-types-list-tuple-range).\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "**b)**\n", "Chercher dans la documentation la syntaxe pour extraire une tranche d'une liste, c'est-à-dire: si `a` est par exemple une liste de longueur 10, retourner les éléments de 6 à 9.\n", "\n", "**Indication.**\n", "Voir la documentation [ici](https://docs.python.org/fr/3/library/stdtypes.html#sequence-types-list-tuple-range).\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "**c)**\n", "Chercher dans la documentation la syntaxe pour retourner la longueur d'une liste.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "**d)**\n", "Écrire une fonction `fibonacci(N)` qui retourne la liste des $N\\geq2$ premiers termes de la suite de Fibonacci définie par $u_{n+2} = u_{n+1}+u_n$ avec $u_0=0$ et $u_1=1$.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "**e)**\n", "Écrire une fonction `pascal(N)` qui retourne la $N$-ième ligne du triangle de Pascal:\n", "\n", "
\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "**f)**\n", "Soit les suites $(u_n)_{n\\in\\mathbb{N}}$ et $(v_n)_{n\\in\\mathbb{N}}$ définies par $u_0=1$, $v_0=1$, et" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\begin{align*}\n", "u_{n+1} &= u_n + v_n \\,, & v_{n+1} &= 2u _n - v_n \\,,\n", "\\end{align*}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "pour $n\\geq0$. Calculer $u_{100}$ et $v_{100}$.\n", "\n", "**Réponse.**\n", "$u_{100}=v_{100}=717897987691852588770249$.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "**g)**\n", "Écrire une fonction `vk(n0,K)`, qui pour deux entiers $n_0$ et $K\\geq1$ calcule la suite des valeurs $v_k$ définies par $v_0 = n_0$ et" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "v_{k+1}=\\begin{cases}\n", "3v_{k}+1 & \\text{si $v_{k}$ est impair},\\\\ \n", "\\frac{v_{k}}{2} & \\text{si $v_{k}$ est pair},\n", "\\end{cases}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "pour $0 \\leq k < K$. Pour $K = 1 000$ et diverses valeurs de $n_0 \\in \\{10, 100, 1 000, 10 000\\}$, afficher les cinq dernières\n", "valeurs calculées, c'est-à-dire $(v_{K-4},v_{K-3},v_{K-2},v_{K-1},v_K)$.\n", "\n", "**Réponse.**\n", "Les assertions suivantes sont vraies:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false }, "outputs": [], "source": [ "vk(10,1000) == [1, 4, 2, 1, 4]\n", "vk(100,1000) == [2, 1, 4, 2, 1]\n", "vk(1000,1000) == [1, 4, 2, 1, 4]\n", "vk(10000,1000) == [4, 2, 1, 4, 2]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "\n", "\n", "\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exercice 2.2: Tuples" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "Les tuples permettent tout comme les listes de stocker des éléments hétérogènes:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false }, "outputs": [], "source": [ "tuple0 = (0, 5.4, \"chaîne\", True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Mais au contraire des listes, les tuples ne sont pas mutables. Il n'est pas possible d'y modifier un élément, d'en rajouter un ou d'en supprimer un sans redéfinir tout le tuple. L'avantage d'un tuple sur une liste est qu'il tuple est hashable, c'est-à-dire qu'il peut être utilisé comme clef dans un dictionnaire.\n", "\n", "Enfin il est possible d'affecter des variables à l'intérieur d'un tuple, par exemple:" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": false }, "outputs": [], "source": [ "(a,b) = (1,9)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Cela est en particulier très utile pour échanger deux variables sans avoir à utiliser une variable supplémentaire:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [], "source": [ "(a,b) = (b,a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**a)**\n", "Vérifier qu'un tuple est bien immutable.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "**b)**\n", "Définir une fonction `mdlast(lst,val)` ayant pour argument une liste de tuples d'entiers `lst` et un entier `val` et retourner la liste de tuples avec le dernier élément de chaque tuple remplacé par `val`. Par exemple si `lst = [(10, 20), (30, 40, 50, 60), (70, 80, 90)]` alors `mdlast(lst,100)` doit retourner `[(10, 100), (30, 40, 50, 100), (70, 80, 100)]`.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "**c)**\n", "Comment convertir un tuple en liste et réciproquement ?\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exercice 2.3: Ensembles" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "Les ensembles permettent de stocker des éléments hétérogènes au sens mathématique de la théorie des ensembles:" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": false }, "outputs": [], "source": [ "set0 = {0, 5.4, \"chaîne\", True}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il est possible de tester si un élément appartient à un ensemble:" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "collapsed": false }, "outputs": [], "source": [ "if \"chaîne\" in set0:\n", " print(\"dedans\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Les ensembles sont mutables, il est donc possible de rajouter ou retirer un élément d'un ensemble:" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "collapsed": false }, "outputs": [], "source": [ "set0.add(18) # ajoute 18 à l'ensemble\n", "set0.add(0) # ajoute 0 à l'ensemble (ne fait rien car 0 est déjà dedans)\n", "set0.remove(\"chaîne\") # retire \"chaîne de l'ensemble" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En revanche les ensembles ne peuvent contenir que des éléments hashables, c'est-à-dire immutables. En particulier un ensemble ne peut pas contenir un autre ensemble:" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "collapsed": false }, "outputs": [], "source": [ "set1 = {{1,2},{3},{4}}\n", "TypeError: unhashable type: 'set'" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "À noter qu'il existe également en Python des ensembles immutables `frozenset`:" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "collapsed": false }, "outputs": [], "source": [ "frozenset0 = frozenset([0, 5.4, \"chaîne\", True])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Une chaîne de caractères peut être transformée en ensemble:" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "collapsed": false }, "outputs": [], "source": [ "set1 = set('abracadabra')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Comme pour les listes, il est possible de faire des compréhensions d'ensembles:" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "collapsed": false }, "outputs": [], "source": [ "set2 = {x for x in 'abracadabra' if x not in 'abc'}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dans cet exemple, les chaînes de caractères sont automatiquement transformées en ensemble.\n", "À noter que l'ensemble vide est défini par `set()`.\n", "\n", "**a)**\n", "Définir une fonction `divisible(n)` qui retourne l'ensemble des nombres entiers divisibles par `n` inférieurs ou égaux à 100.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "**b)**\n", "Chercher dans la documentation comment faire l'intersection, l'union et la différence de deux ensembles. Déterminer les nombres inférieurs ou égaux à 100 qui sont non divisibles par 2 mais divisibles par 3 et 5.\n", "\n", "**Indication.**\n", "Voir la documentation de `set` [ici](https://docs.python.org/fr/3/library/stdtypes.html#set).\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exercice 2.4: Dictionnaires" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "Les dictionnaires sont une structure permettant de stocker des éléments hétérogènes indexés par des clefs (elles aussi hétérogènes):" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "collapsed": false }, "outputs": [], "source": [ "dict0 = {\"pommes\": 0, \"poires\": 4, 12: 2}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Les éléments d'un dictionnaire sont accessibles par les clefs:" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "collapsed": false }, "outputs": [], "source": [ "dict0[\"pommes\"]\n", "dict0[12]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Un dictionnaire peut être vu comme un tableau associatif associant à chaque clef une valeur. La liste des clefs et celle des valeurs sont accessibles respectivement avec `dict0.keys()` et `dict0.values()`.\n", "Les dictionnaires sont mutables, il est donc possible de modifier une association clef-valeur et d'en rajouter ou supprimer une:" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "collapsed": false }, "outputs": [], "source": [ "dict0[\"pommes\"] = 3 # modifie la valeur associée à pommes\n", "dict0[\"oranges\"] = \"beaucoup\" # rajoute oranges comme clef avec la valeur \"beaucoup\"\n", "del dict0[\"poires\"] # supprime le couple clef-valeur associé à poires\n", "dict0.pop(\"pommes\") # supprime le couple clef-valeur associé à pommes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Bien qu'un dictionnaire soit mutable, les clefs qui le composent doivent être des objets hashables, c'est-à-dire immutables. Ainsi une liste ou un ensemble ne peuvent pas servir de clefs dans un dictionnaire:" ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "collapsed": false }, "outputs": [], "source": [ "dict0[list0] = \"test\"\n", "TypeError: unhashable type: 'list'\n", "dict0[set0] = \"retest\"\n", "TypeError: unhashable type: 'set'" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En revanche il est possible d'avoir un tuple ou un frozenset comme clef:" ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "collapsed": false }, "outputs": [], "source": [ "dict0[tuple0] = \"test\"\n", "dict0[frozenset0] = \"rest\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "d'où l'intérêt des frozensets.\n", "Comme pour les listes et les ensembles, il est possible de faire des compréhensions de dictionnaires:" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "collapsed": false }, "outputs": [], "source": [ "dict1 = {x: x**2 for x in range(5)}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finalement une chose intéressante avec les dictionnaires est l'unpaking illustré par l'exemple suivant:" ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def add(a=0, b=0):\n", " return a + b\n", "d = {'a': 2, 'b': 3}\n", "add(**d)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**a)**\n", "Comment définir un dictionnaire vide ?\n", "\n", "**b)**\n", "Comment concaténer plusieurs dictionnaires entre eux ?\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "**c)**\n", "On considère une liste de mots:" ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "collapsed": false }, "outputs": [], "source": [ "mots = ['Abricot', 'Airelle', 'Ananas', 'Banane', 'Cassis', 'Cerise', 'Citron', 'Clémentine', 'Coing', 'Datte', 'Fraise', 'Framboise', 'Grenade', 'Groseille', 'Kaki', 'Kiwi', 'Litchi', 'Mandarine', 'Mangue', 'Melon', 'Mirabelle', 'Nectarine', 'Orange', 'Pamplemousse', 'Papaye', 'Pêche', 'Poire', 'Pomme', 'Prune', 'Raisin']" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Écrire une fonction `position(mots, x, n)` qui retourne la liste des mots ayant le caractère `x` comme `n`-ième lettre.\n", "\n", "**Réponse.**\n", "Par exemple `position(mots,'e',4)` doit retourner la liste:" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "collapsed": false }, "outputs": [], "source": [ "['Clémentine', 'Datte', 'Groseille', 'Pêche', 'Poire', 'Pomme', 'Prune']" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "**d)**\n", "En imaginant que la liste des mots soit très longue, alors à chaque évaluation de la fonction `position` l'ensemble des mots est parcouru, ce qui prend pas mal de temps. Pour améliorer cela, construire un dictionnaire `mots_dict` ayant pour clefs les tuples `(x,n)` et comme valeurs la liste des mots ayant le caractère `x` comme `n`-ième lettre, c'est-à-dire tel que `mots_dict[x,n]` retourne la même chose que `position(mots, x , n)` à l'ordre près. Ainsi la liste `mots` n'est parcourue qu'une seule fois lors de la construction du dictionnaire et ensuite l'évaluation du dictionnaire est extrêmement rapide pour n'importe quelle requête.\n", "\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }