{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Prise en main de Python\n",
"\n",
"Dans ce TP nous allons voir les bases du langage Python.\n",
"C'est ce langage qui est choisi comme interface à la collection de logiciel Sagemath.\n",
"\n",
"Ce TP est présenté dans un *notebook* Jupyter. Chaque cellule de code peut être évaluée à l'aide du raccourci \n",
"```Shift+Enter```. Les exercices sont donc à faire directement dans le *notebook*. Pour vérifier que vous avez\n",
"correctement répondu à la question il vous est systématiquement fourni des tests à évaluer.\n",
"\n",
"__Les fondements__\n",
"- [ ] [Éléments impératifs de base](#basic)\n",
" - [ ] [Exercice 1](#exo-1)\n",
" - [ ] [Exercice 2](#exo-2)\n",
" - [ ] [Exercice 3](#exo-3)\n",
"- [ ] [Les structures de données](#data-structure)\n",
" - [ ] [Exercice 4](#exo-4)\n",
" - [ ] [Exercice 5](#exo-5)\n",
" - [ ] [Exercice 6](#exo-6)\n",
" - [ ] [Exercice 7](#exo-7)\n",
" - [ ] [Exercice 8](#exo-8)\n",
" - [ ] [Exercice 9](#exo-9)\n",
" - [ ] [Exercice 10](#exo-10)\n",
" - [ ] [Exercice 11](#exo-11)\n",
" - [ ] [Exercice 12](#exo-12) <- Une cannette à gagner\n",
"- [ ] [La programmation fonctionnelle en Python](#functional)\n",
" - [ ] [Exercice 13](#exo-13)\n",
" - [ ] [Exercice 13.5](#exo-13.5)\n",
" - [ ] [Exercice 14](#exo-14)\n",
" - [ ] [Exercice 15](#exo-15)\n",
" - [ ] [Exercice 16](#exo-16) <- Une cannette à gagner\n",
"- [ ] [La POO en Python](#poo)\n",
" - [ ] [Exercice 17](#exo-17)\n",
"- [ ] [En vrac](#vrac)\n",
"\n",
"__Les bonus__\n",
"- [ ] [Les itérateurs](#iterators)\n",
" - [ ] [Exercice 18](#exo-18)\n",
"- [ ] [Les générateurs](#generators)\n",
" - [ ] [Exercice 19](#exo-19)\n",
" - [ ] [Exercice 20](#exo-20)\n",
"\n",
"Pour suivre votre progression dans le TP vous pouvez éditer cette cellule (en double-cliquant dessus)\n",
"et cocher les cases (```[ ] -> [x]```) au fur et à mesure.\n",
"\n",
"## Tests\n",
"\n",
"Tous les exercices sont suivis de tests permettant de voir si votre solution est valide.\n",
"Ces tests sont effectués dans la fonction ```assert``` qui ne fait rien si le test passe et déclenche une \n",
"erreur sinon."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"## Éléments impératifs de base\n",
"\n",
"En Python, on retrouve tous les éléments de la programmation impérative classique :\n",
"\n",
"* affectations\n",
"\n",
"```python\n",
"a = 42\n",
"b = \"une chaîne de caractère\"\n",
"c = 23.6\n",
"```\n",
"\n",
"* structures conditionnelles\n",
"\n",
"```python\n",
"if a == 1:\n",
" print(\"a == 1\")\n",
"elif not(a % 2 == 0):\n",
" print(f\"{a} est impair\")\n",
"else:\n",
" print(f\"{a} est impair\")\n",
"```\n",
"\n",
"* boucles\n",
"\n",
"```python\n",
"for i in range(5):\n",
" print(i)\n",
" \n",
"for i in range(4,17,5): #i = 4,9,14\n",
" print(i)\n",
" \n",
"for i in range(5,0,-1): #i = 5,4,3,2,1\n",
" print(i)\n",
" \n",
"i = 0\n",
"while i < 8:\n",
" i += 1\n",
"```\n",
" \n",
"* fonctions\n",
"\n",
"```python\n",
"def my_function(x, y):\n",
" z = x + y\n",
" return z\n",
"```\n",
"\n",
"\n",
"# ATTENTION à l'indentation\n",
"\n",
"En python l'indentation délimite les blocs (fonctions, conditions, boucles, etc) comme les accolade '{' et '}' en C ou Java.\n",
"Faites donc attention à l'indentation de vos programmes !\n",
"Jupyter vous aide pour cela en indentant automatiquement après un ':' suivi d'un saut de ligne."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 1\n",
"\n",
"Évaluez les différentes expressions Python ci-dessous"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"\"Hello\" + \" \" + \"World\""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"str(42)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"chr(42)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"ord('*')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"True and False"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"True or False"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"True ^ False # xor"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"True ^ True"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"int(\"33\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"7/2"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"7//2"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"7%2"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"7**2"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"min(1,2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"min(1,2,2,3,4,5,6)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"max(3,6,8,9,4,5,45,4,41)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"int(\"11001\",2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"0b11001"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"bin(25)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"0x19"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"hex(25)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for i in range(10):\n",
" print(i)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for i in range(10):\n",
" if i > 5:\n",
" break\n",
" print(i)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for i in range(10):\n",
" if i < 5:\n",
" continue\n",
" print(i)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Prise en main de jupyter:\n",
"\n",
"+ Cliquez sur une cellule\n",
"+ Appuyez sur la touche ```Échap``` de votre clavier\n",
"+ Appuyez sur la touche ```b``` de votre clavier, pour ajouter une cellule en dessous de la cellule sélectionnée\n",
"+ Appuyez sur la touche ```a``` de votre clavier, pour ajouter une cellule au dessus de la cellule sélectionnée\n",
"+ Fouillez dans les menus !"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 2\n",
"\n",
"Donnez le code de la fonction ```repeat_str(s:str, n:int)``` qui renvoie la chaîne de caractères ```s``` \n",
"répétées ```n``` fois si ```n``` est positif et la chaîne vide sinon."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def repeat_str(s:str, n:int):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(repeat_str(\"ab\",5) == \"ababababab\")\n",
"assert(repeat_str(\"ab\",1) == \"ab\")\n",
"assert(repeat_str(\"ab\", 0) == \"\")\n",
"assert(repeat_str(\"ab\", -17) == \"\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 3\n",
"\n",
"Donnez le code de la fonction ```div_euclid(a:int, b:int)``` qui calcule la division euclidienne ```a//b```, __sans utiliser l'opérateur ```//```__."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def div_euclid(a:int, b:int):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(div_euclid(17,2) == 17//2)\n",
"assert(div_euclid(17,17) == 1)\n",
"assert(div_euclid(9658761576,13434) == 9658761576//13434)\n",
"assert(div_euclid(4554344,4343134635431) == 0)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"## Les structures de données\n",
"\n",
"Python propose nativement plusieurs structures de données différentes. Il est important de comprendre\n",
"les spécifités de chacune afin d'implémenter des algorithmes __correctement__ et __efficacement__."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Les listes\n",
"\n",
"Les listes sont des structures de données __mutables__ et linéaires (c-à-d indexés par des entiers).\n",
"\n",
"__Attention :__ Malgé leur non les listes Python ne sont pas des listes chaînées mais des tableaux dynamiques,\n",
"cela signifie que certaines opérations telles que l'insertion sont coûteuses mais d'autres sont rapides comme \n",
"l'accès à un élément "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = list()\n",
"l"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = []\n",
"l"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = [1,2,3,4,5,6,7,8,9]\n",
"l"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"len(l)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"min(l)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"max(l)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l[0]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l[-1]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l + [10,11,12]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l[2:5]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l[:5]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l[5:]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l[1:9:2]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l[::-1]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l.append(10)\n",
"l"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l[0] = 42\n",
"l"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"del l[0]\n",
"l"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"del l[2:4]\n",
"l"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for e in l:\n",
" print(e)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Attention :__ on ne modifie jamais une liste sur laquelle on est entrain d'itérer !"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l_copy = l\n",
"l_copy.append(11)\n",
"l"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l_copy = l.copy()\n",
"l_copy.append(12)\n",
"l"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = [[1,2],[3,4]]\n",
"l_copy = l.copy()\n",
"l_copy[0][0] = 5\n",
"l"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from copy import deepcopy\n",
"\n",
"l = [[1,2],[3,4]]\n",
"l_copy = deepcopy(l)\n",
"l_copy[0][0] = 5\n",
"l"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 4\n",
"\n",
"Définissez la fonction ```min2(l)``` qui renvoie une liste contenant les __deux__ plus petits éléments de la liste ```l``` __dans l'ordre décroissant__\n",
"\n",
"On pourra utiliser les fonctions ```min``` et ```max```."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def min2(l):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(min2([0,1,2,3,4,5,6,7]) == [1,0])\n",
"assert(min2([6,2,3,1,7,0,5,4]) == [1,0])\n",
"assert(min2([8,-1,6,42,3,-7,5,-3]) == [-3,-7])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 5\n",
"\n",
"Définissez la fonction ```sort(l)``` qui trie une liste ```l``` d'entiers __en place__ (en la modifiant), sans utiliser la fonction ```sorted``` de Python."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def sort(l):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from random import sample, choices\n",
"\n",
"l = sample(range(-100,101), k=17)\n",
"assert(sorted(l) == sort(l))\n",
"\n",
"l = choices(range(-5,6), k=20)\n",
"assert(sorted(l) == sort(l))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 6 (moyen)\n",
"\n",
"Définissez la fonction ```sum_all(l)``` qui somme tous les éléments contenus dans des listes imbriquées (voir les tests ci-dessous).\n",
"On pourra utiliser ```isinstance(x,list)``` pour tester si ```x``` est une liste."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def sum_all(l):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(sum_all([]) == 0)\n",
"assert(sum_all([1,1,1,1,1,1,1,1,1,1]) == 10)\n",
"assert(sum_all([[1,1],1,1,1,[[1,1,1],1],1]) == 10)\n",
"assert(sum_all([[],1,[1,[],[1,[1,[1,[],[],[1,[1,[1,[1,[1]]]]]]]]]]) == 10)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Les tuples \n",
"\n",
"Les tuples sont des structures de données __immutables__ et linéaires."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = tuple()\n",
"t"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = (1,2,3,4,5,6,7,8,9)\n",
"t"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = 1,2,3,4,5,6,7,8,9\n",
"t"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for e in t:\n",
" print(e)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t + (10,11,12) + (13,)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = 1,2\n",
"a,b = t # Déconstruction de tuple"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"b"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Le \"swap\" en Python\n",
"l = [1,2,3,4,5]\n",
"l[0], l[1] = l[1], l[0]\n",
"l"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour bien comprendre la ligne précédente :\n",
"+ ce qui se trouve à droite du ```=``` est d'abord évaluer et donc le tuple ```l[1], l[0]``` est construit\n",
"+ puis il est déconstruit à cause de l'expression à gauche\n",
"+ les valeurs sont alors affectés dans les cases ```l[0], l[1]```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = tuple(range(10))\n",
"t"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a,b,*c = t # l'opérateur d'unpacking *"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"c"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def f(a,b,*t):\n",
" print(f\"mes arguments sont {a}, {b}, {t}\")\n",
" return\n",
"\n",
"f(1,2,3,4,5,6,7)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"f(*range(10))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Les tuples sont aussi des structures indexés (on peut écrire ```mon_tuple[i]```) mais ce n'est\n",
"pas très \"pythonesque\""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t[0]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t[1:9:2]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t[0] = 4"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Les ensembles\n",
"\n",
"Les ensembles sont des structures de données __mutables__ et __non-linéaires__."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s = set()\n",
"s"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s1 = {1,2,3,4,5,6,7,8,9}\n",
"s1"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for e in s1:\n",
" print(e)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"len(s1)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"3 in s1"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"17 not in s1"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s2 = {4,5,6,7,8,9,10,11,12,13}\n",
"s2"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s1 | s2 # ou s1.union(s2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s1 & s2 # ou s1.intersection(s2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s1 - s2 # ou s1.difference(s2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s1 ^ s2 # ou s1.symmetric_difference(s2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s1.add(10)\n",
"s1"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s1.remove(5)\n",
"s1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 7\n",
"\n",
"Donnez la défintion de la fonction ```uniq(l)``` qui prend une liste ```l``` en argument et renvoie une liste\n",
"contenant les éléments de ```l``` dans n'importe quel ordre et __sans doublons__."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def uniq(l):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = list(range(4))*3\n",
"assert(len(uniq(l)) == len(range(4)))\n",
"\n",
"l = [1,1,3,2,3,1,2,1,3,4,5,1,3,4,5]\n",
"assert(len(uniq(l)) == 5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 8 (difficile)\n",
"\n",
"Donnez la définition de la fonction ```partitions(s, k)``` qui prend en argument un ensembles ```s``` et un entier ```k``` et qui renvoie la liste des sous ensembles de taille ```k``` de ```s```.\n",
"\n",
"Par exemple, les sous-ensembles de longueur $4$ de l'ensemble $\\{1,2,3,4,5\\}$ sont $\\{1,2,3,4\\}$, $\\{1,2,3,5\\}$, $ \\{1,2,4,5\\}$, $\\{1,3,4,5\\}$ et $\\{2,3,4,5\\}$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def partitions(s,k):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(len(partitions({1,2,3,4}, 1)) == 4)\n",
"assert(len(partitions({1,2,3,4}, 4)) == 1)\n",
"\n",
"p = partitions({1,2,3,4}, 2)\n",
"assert(len(p) == 6)\n",
"assert({1,2} in p)\n",
"assert({1,3} in p)\n",
"assert({1,4} in p)\n",
"assert({2,3} in p)\n",
"assert({2,4} in p)\n",
"assert({3,4} in p)\n",
"\n",
"n = 10\n",
"s = set(range(n))\n",
"assert(sum(len(partitions(s,i+1)) for i in range(len(s))) == 2**n-1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Les dictionnaires\n",
"\n",
"Les dictionnaires sont des __tables de hachages__."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"d = dict()\n",
"d"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"d = {\"a\":1, \"b\":2, \"c\":3, \"d\":4, \"e\":5}\n",
"d"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"d[\"a\"]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"d[\"f\"] = 6\n",
"d"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(d.keys())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(d.values())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(d.items())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"\"a\" in d"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"del d[\"a\"]\n",
"d"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"\"a\" in d"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for e in d:\n",
" print(e)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Un mot sur les ```collections``` Python\n",
"\n",
"En plus des structures de données présentées jusqu'ici, Python en propose d'autres dans le module ```collections```.\n",
"Il est à noté que la plupart de ces collections sont ```Iterable``` c'est-à-dire que l'on peut écrire :\n",
"```python\n",
"for elem in c:\n",
" f(elem)\n",
"```\n",
"où ```c``` est une liste, un ensemble ou encore un dictionnaire (```elem``` parcourt alors les clés)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for key in d:\n",
" print(key)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for x in [\"a\",\"b\",\"c\"]:\n",
" print(x)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 9\n",
"\n",
"Définissez la fonction ```to_index(l)``` qui prend en entrée une liste et renvoie un dictionnaire associant les éléments de la liste à leur position dans la liste"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def to_index(l):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(to_index([\"a\",2,{4,5,6},(1,\"c\")]) == {0: 'a', 1: 2, 2: {4, 5, 6}, 3: (1, 'c')})\n",
"assert(to_index([]) == dict())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 10\n",
"\n",
"On représente une carte routière par un dictionnaire dont les clés sont des noms de villes et les valeurs sont \n",
"un ensemble des villes accessibles directement depuis cette ville. Un exemple est donné ci-dessous.\n",
"\n",
"Définissez la fonction ```cities(d)``` qui renvoie __l'ensemble__ des villes présentes dans la carte."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"roadmap = {\n",
" \"Caen\" : {\"Rouen\", \"Bayeux\", \"Ifs\"},\n",
" \"Bayeux\" : {\"Cherbourg\", \"Caen\", \"Saint-Lô\"},\n",
" \"Saint-Lô\" : {\"Vire\", \"Bayeux\"},\n",
" \"Falaise\" : {\"Vire\", \"Ifs\"},\n",
" \"Belfast\" : set(),\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def cities(d):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(cities(roadmap) == {\"Belfast\", \"Rouen\", \"Bayeux\", \"Ifs\", \"Cherbourg\", \"Caen\", \"Saint-Lô\", \"Vire\", \"Falaise\"})"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 11\n",
"\n",
"On reprend le même encodage de carte que dans l'exercice précédent.\n",
"Donnez la définition de la fonction ```complete_map(d)``` qui renvoie une version complétée de la \n",
"carte ```d``` en y ajoutant toutes les villes présentes dans ```d``` comme clés."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def complete_map(d):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"complete_roadmap = {\n",
" \"Caen\" : {\"Rouen\", \"Bayeux\", \"Ifs\"},\n",
" \"Bayeux\" : {\"Cherbourg\", \"Caen\", \"Saint-Lô\"},\n",
" \"Saint-Lô\" : {\"Vire\", \"Bayeux\"},\n",
" \"Falaise\" : {\"Vire\", \"Ifs\"},\n",
" \"Vire\" : {\"Saint-Lô\", \"Falaise\"},\n",
" \"Ifs\" : {\"Falaise\", \"Caen\"},\n",
" \"Rouen\" : {\"Caen\"},\n",
" \"Cherbourg\" : {\"Bayeux\"},\n",
" \"Belfast\" : set(),\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(complete_map(roadmap) == complete_roadmap)\n",
"assert(complete_map(roadmap) is not roadmap)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 12 (difficile)\n",
"\n",
"On reprend le même encodage de carte que dans l'exercice précédent.\n",
"Définissez la fonction ```journey(A, B, d)``` qui renvoie une liste :\n",
"+ vide, si il n'y a pas de trajet entre les villes ```A``` et ```B``` dans la carte ```d```\n",
"+ une liste représentant un trajet entre ```A``` et ```B``` dans la carte ```d```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def journey(A, B, d):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(journey(\"Caen\", \"Vire\", roadmap)[0] == \"Caen\")\n",
"assert(journey(\"Caen\", \"Vire\", roadmap)[-1] == \"Vire\")\n",
"assert(len(journey(\"Caen\", \"Falaise\", roadmap)) >= 3)\n",
"assert(journey(\"Caen\", \"Belfast\", roadmap) == [])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercice 12' (très difficile)\n",
"\n",
"Même exercice que précédemment mais la fonction doit renvoyer le plus court trajet.\n",
"\n",
"__Défi__ : J'offre une cannette de son choix au premier ou à la première réussissant cet exercice."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"roadmap = {0: {28, 13},\n",
" 1: {19, 22, 7, 8, 26, 12, 15},\n",
" 3: {16, 18, 19, 13},\n",
" 9: {17, 2, 19, 7, 15},\n",
" 14: {21, 7, 26},\n",
" 15: {1, 17, 2, 19, 21, 9, 26},\n",
" 16: {2, 18, 3, 20, 13},\n",
" 18: {16, 3, 4, 6, 26, 13},\n",
" 19: {1, 17, 3, 9, 26, 11, 29, 15},\n",
" 20: {16, 5, 7, 25, 26, 28},\n",
" 21: {17, 4, 11, 28, 13, 14, 15},\n",
" 22: {1, 26, 12},\n",
" 23: {6, 11},\n",
" 24: {5},\n",
" 26: {1, 2, 18, 19, 20, 6, 22, 7, 10, 13, 14, 15},\n",
" 27: {17, 10, 28, 13, 29}}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(len(journey(24,23,roadmap)) == 6)\n",
"assert(len(journey(12,25,roadmap)) == 5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"## La programmation fonctionnelle en Python\n",
"\n",
"Python fournit plusieurs éléments de programmation fonctionnelle parmi lesquels :\n",
"\n",
"+ les fonctions sont des citoyennes de première classe\n",
"\n",
"```python\n",
"def my_func():\n",
" pass\n",
"\n",
"a = my_func\n",
"a()\n",
"```\n",
"\n",
"+ les fonctions anonymes\n",
"\n",
"```python\n",
"add_int = lambda a, b: a + b\n",
"add_int(2,3)\n",
"```\n",
"\n",
"+ l'expression conditionnelle\n",
"\n",
"```python\n",
"a = 2 if True else 17\n",
"```\n",
"\n",
"+ les fonctionnelles ```map``` et ```functools.reduce```\n",
" + ```map(f, l)``` est équivalent à ```[f(l[0]), f(l[1]), ..., f(l[-1])]```\n",
" + ```reduce(f, l, acc)``` est équivalent à ```f(... f(f(acc,l[0])),l[1]),l[2]) ... ,l[-1])```\n",
"\n",
"+ les compréhensions de listes, ensembles et dictionnaires\n",
"\n",
"```python\n",
"[x*2 for x in range(10)]\n",
"{x*2 for x in range(10)}\n",
"{x:x*2 for x in range(10)}\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 13\n",
"\n",
"Exécuter les cellules suivantes"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = 2 if True else 17\n",
"a"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = 2 if False else 17\n",
"a"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(map(lambda x: x*2, [1,2,3,4,5]))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from functools import reduce\n",
"reduce(lambda acc, x : acc * x, [1,2,3,4,5], 1)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"reduce(lambda acc, x : x ^ acc, [True, True, True, True, False, True], False)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def update_dict(d, t):\n",
" k, v = t\n",
" d[k] = v\n",
" return d\n",
"\n",
"reduce(update_dict, [(\"a\",1), (\"b\", 2), (\"c\", 3)], dict())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[x*2 for x in range(10)]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"{x*2 for x in range(10)}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"{x:x*2 for x in range(10)}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[x//2 for x in range(20) if x%2 == 0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 13.5\n",
"\n",
"En utilisant `map` ou une compréhension donnez la définition de la fonction `cube(l)` qui calcule\n",
"le cube ($x \\rightarrow x^3$) des éléments de `l`.\n",
"\n",
"Utilisez la fonction `reduce` pour définir la donction `sum_firsts_cubes(n)` qui \n",
"calcule la somme des $n$ premiers entiers $\\sum_{0 \\leq k\\leq n} k^3$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def cube(l):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(list(cube(range(4))) == [0,1,8,27])\n",
"assert(list(cube([-2,9,11,-7])) == [-8, 729, 1331, -343])"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"from functools import reduce\n",
"\n",
"def sum_firsts_cubes(n):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(sum_firsts_cubes(3) == 36)\n",
"assert(sum_firsts_cubes(6) == 441)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 14\n",
"\n",
"En utilisant ```reduce```, donnez la définition de la fonction ```is_prime(n)``` qui renvoie ```True```\n",
"si l'entier ```n``` est premier (divisible que par 1 et par lui même) et ```False``` sinon."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def is_prime(n):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(is_prime(2))\n",
"assert(is_prime(23))\n",
"assert(not is_prime(9))\n",
"assert(not is_prime(0))\n",
"assert(not is_prime(1))\n",
"assert(not is_prime(-5))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 15\n",
"\n",
"Refaire [l'exercice 10](#exo-10) en utilisant ```reduce```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from functools import reduce\n",
"\n",
"def cities_with_reduce(d):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"roadmap = {\n",
" \"Caen\" : {\"Rouen\", \"Bayeux\", \"Ifs\"},\n",
" \"Bayeux\" : {\"Cherbourg\", \"Caen\", \"Saint-Lô\"},\n",
" \"Saint-Lô\" : {\"Vire\", \"Bayeux\"},\n",
" \"Falaise\" : {\"Vire\", \"Ifs\"},\n",
" \"Belfast\" : set(),\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(cities_with_reduce(roadmap) == {\"Belfast\", \"Rouen\", \"Bayeux\", \"Ifs\", \"Cherbourg\", \"Caen\", \"Saint-Lô\", \"Vire\", \"Falaise\"})"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 16 (très difficile)\n",
"\n",
"On représente un arbre généalogique par un tuple contenant une personne et la liste des\n",
"arbres généalogiques de ses descendants directs (exemple ci-dessous).\n",
"\n",
"En utilisant ```map``` et ```reduce```, donnez la définition de la fonction ```tree_size(t)``` qui renvoie le nombre de personnes présentes dans l'arbre.\n",
"\n",
"__Indication :__ Les fonctions Python peuvent être récursives.\n",
"\n",
"__Défi :__ J'offre une cannette de son choix au premier ou à la première réussissant cet exercice\n",
"__en une seule ligne de code__ (pour le corps de la fonction)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"genealogic_tree = (\"Arrière Grand Mère\", [\n",
" (\"Grand Père 1\", [\n",
" (\"Mère 1\", [\n",
" (\"Fils 1\", []),\n",
" (\"Fille 1\", [])\n",
" ]),\n",
" (\"Mère 2\", [\n",
" (\"Fille 2\", []) \n",
" ])]\n",
" ),\n",
" (\"Grand Mère 1\", [\n",
" (\"Père 1\", [\n",
" (\"Fils 2\", []),\n",
" (\"Fils 3\", [])\n",
" ])\n",
" ]),\n",
" (\"Grand Père 2\", [])\n",
" ])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from functools import reduce\n",
"\n",
"def tree_size(t):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(tree_size((\"Moi\", [])) == 1)\n",
"assert(tree_size(genealogic_tree) == 12)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"## La POO en Python\n",
"\n",
"De fait Python est un langage objet : tout est objet en Python.\n",
"Il est donc assez naturel de définir ses propres classes (voir exemple ci-dessous).\n",
"La POO étant très similaire aux langages objets \"classiques\" (comme Java ou C++),\n",
"je ne donne pas de détails dans le TP mais n'hésitez pas à me poser des questions sur le sujet.\n",
"Quelques point important à noter :\n",
"+ Toutes les méthodes d'une classe prennent comme __premier argument__ une instance de cette classe \n",
" (le ```this``` de Java ou C++) que l'on nomme (par convention) ```self```\n",
"+ Les attributs ne sont pas déclarés statiquement (cf. dernière cellule de cette section)\n",
"+ Tout est public __(donc on ne fait pas de \"getter\" et de \"setter\")__\n",
"+ Par convention, les méthodes dont le nom commence par un '_' sont \"privées\"\n",
"\n",
"De plus, chaque classe Python hérite de la classe ```object``` et expose les méthodes suivantes dites\n",
"*méthodes magiques* :\n",
"+ ```__repr__``` : renvoie une ```str```, appellée quand l'objet est affiché dans le *REPL* (read-eval-print loop)\n",
"+ ```__hash__``` : renvoie un *hash* de l'objet, nécessaire pour être stocké dans un ```set``` ou un ```dict```\n",
"+ ```__str__``` : renvoie une ```str```, appellée lors d'un *cast* en ```str``` (dans un ```print``` par exemple)\n",
"+ ```__lt__``` : opérateur de comparaison ```<```\n",
"+ ```__le__``` : opérateur de comparaison ```<=```\n",
"+ ```__eq__``` : opérateur de comparaison ````==```\n",
"+ ```__ne__``` : opérateur de comparaison ````!=```\n",
"+ ```__gt__``` : opérateur de comparaison ````>```\n",
"+ ```__ge__``` : opérateur de comparaison ````>=```\n",
"+ ```__dir__``` : renvoie la liste des noms des méthodes et attributs de l'objet\n",
"+ ```__class__``` : renvoie la classe de l'objet\n",
"+ ```__doc__``` : renvoie la documentation de l'objet, aussi accessible avec ```?obj```\n",
"\n",
"En plus de ces méthodes communes à toutes les classes, on peut retrouver des méthodes magiques \n",
"correspondantes aux opérateurs arithmétiques ```__add__, __mul__, ...```, à l'accès dans un tableau \n",
"```__getitem__, __setitem__, __contains__, ...``` ou encore à l'appel de fonction ```__call__```.\n",
"\n",
"__Attention__ : on n'appelle jamais directement les méthodes magiques d'un objet, elle sont appelées\n",
"automatiquement"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class A:\n",
" \"\"\"Ceci est la docstring de la classe A\"\"\"\n",
" def __init__(self):\n",
" \"\"\"Le constructeur\"\"\"\n",
" self.a = 42\n",
" \n",
" def __repr__(self):\n",
" return 'repr A'\n",
" \n",
" def __str__(self):\n",
" return 'str A'\n",
" \n",
" def __call__(self, x):\n",
" print(f\"Qui m'a appelé avec {x}\")\n",
" \n",
" def method(self):\n",
" \"\"\"Une méthode\"\"\"\n",
" return self.a"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"A?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = A()\n",
"print(a)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a.__class__"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a.method?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a.method()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a(\"lol\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a.__dir__()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"isinstance(a, A)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"isinstance(3, int)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a.new_attribute = \"lol\"\n",
"a.__dir__()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 17\n",
"\n",
"Le but de cet exercice est d'implémentez une classe ```RationalNumber``` permettant de manipuler des\n",
"nombre rationnels __en utilisant uniquement des opérations sur les entiers__.\n",
"\n",
"Les différentes méthodes accepteront des ```int``` ou des ```RationalNumber```."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from math import gcd\n",
"\n",
"class RationalNumber:\n",
" def __init__(self, numerator, denominator=1):\n",
" # La fraction devra être stockée sous forme réduite (pas de facteurs communs et dénominateur > 0)\n",
" pass\n",
" \n",
" def __add__(self, number):\n",
" #Addition\n",
" pass\n",
" \n",
" def __sub__(self, number):\n",
" # Soustraction\n",
" pass\n",
" \n",
" def __mul__(self, number):\n",
" # Multiplication\n",
" pass\n",
" \n",
" def __truediv__(self, number):\n",
" # Division\n",
" pass\n",
" \n",
" def __eq__(self, number):\n",
" # Égalité\n",
" pass\n",
" \n",
" def __lt__(self, number):\n",
" \"\"\"Tests if self < number\"\"\"\n",
" pass\n",
" \n",
" def __ge__(self, number):\n",
" \"\"\"Tests if self >= number\"\"\"\n",
" pass\n",
" \n",
" def _latex_(self):\n",
" return \"\\frac{\" + str(self.numerator) + \"}{\" + str(self.denominator) + \"}\"\n",
" \n",
" def __repr__(self):\n",
" return f\"RationalNumber({self.numerator}, {self.denominator})\"\n",
"\n",
" def __str__(self):\n",
" return f\"{self.numerator}/{self.denominator}\""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = RationalNumber(3,2)\n",
"b = RationalNumber(17, 34)\n",
"assert(b == RationalNumber(1,2))\n",
"assert(a*2 == RationalNumber(3))\n",
"assert(a+b == 2)\n",
"assert(RationalNumber(1,5) > RationalNumber(1,6))\n",
"assert(RationalNumber(0,5) == RationalNumber(0,6))\n",
"assert(RationalNumber(-2,3) == RationalNumber(2,-3))\n",
"assert(RationalNumber(-6,3) == -2)\n",
"assert(RationalNumber(3,10) <= RationalNumber(5,8))\n",
"assert(RationalNumber(-3,10) >= RationalNumber(5,-8))\n",
"assert(RationalNumber(5,2) != 10)\n",
"assert(RationalNumber(5,2) < 9)\n",
"assert(RationalNumber(5,2) < RationalNumber(-7,-2))\n",
"assert(RationalNumber(5,2) >= RationalNumber(5,2))\n",
"\n",
"from random import randrange\n",
"from fractions import Fraction\n",
"for _ in range(10000):\n",
" a, b, c, d = randrange(-10,10), randrange(-10,10), randrange(-10,10), randrange(-10,10)\n",
" while b == 0 or d == 0:\n",
" a, b, c, d = randrange(-10,10), randrange(-10,10), randrange(-10,10), randrange(-10,10)\n",
" assert((RationalNumber(a,b) == RationalNumber(c,d)) == (Fraction(a,b) == Fraction(c,d)))\n",
" assert((RationalNumber(a,b) <= RationalNumber(c,d)) == (Fraction(a,b) <= Fraction(c,d)))\n",
" assert((RationalNumber(a,b) > RationalNumber(c,d)) == (Fraction(a,b) > Fraction(c,d)))\n",
" assert((RationalNumber(a,b) + RationalNumber(c,d)) == (Fraction(a,b) + Fraction(c,d)))\n",
" assert((RationalNumber(a,b) - RationalNumber(c,d)) == (Fraction(a,b) - Fraction(c,d)))\n",
" assert((RationalNumber(a,b) * RationalNumber(c,d)) == (Fraction(a,b) * Fraction(c,d)))\n",
" if c != 0:\n",
" assert((RationalNumber(a,b) / RationalNumber(c,d)) == (Fraction(a,b) / Fraction(c,d)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"## En vrac"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Les modules\n",
"\n",
"L'organisation du code en modules est similaire à celle de Java.\n",
"Chaque fichier est un module dont le nom est le nom du fichier sans le suffixe ```.py```.\n",
"Prenons un exemple, voici le fichier ```moduleA.py```:\n",
"\n",
"```python\n",
"def a():\n",
" pass\n",
"\n",
"def b():\n",
" pass\n",
"\n",
"def _c():\n",
" pass\n",
"```\n",
"On peut importter le module :\n",
"```python\n",
"import moduleA\n",
"\n",
"moduleA.a()\n",
"moduleB._c()\n",
"```\n",
"\n",
"On peut importer seulement ce que l'on veut :\n",
"```python\n",
"from moduleA import a, b\n",
"\n",
"a()\n",
"b()\n",
"```\n",
"\n",
"On peut importer tout ce qui ne commence pas par un '_' :\n",
"```python\n",
"from moduleA import *\n",
"\n",
"a()\n",
"b()\n",
"```\n",
"\n",
"Pour plus de détails voire la doc : [https://docs.python.org/3.6/](https://docs.python.org/3.6/)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Différence entre ```==``` et ```is```\n",
"\n",
"Comme dans plusieurs langages de haut niveau, en Python on distingue l'égalité structurelle (les valeurs)\n",
"de l'égalité physique (les pointeurs).\n",
"La première se teste avec l'opérateur ```==``` et la seconde avec l'opérateur ```is```."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[1,2,3] == [1,2,3]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[1,2,3] is [1,2,3]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"2 is 2"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"\"2\" == \"2\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Attention :__ Python fait le malin dans la gestion des ```str```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"\"2\" is \"2\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### ```format``` et les ```f-string```\n",
"\n",
"Comme de nombreux langage de scripts, Python propose de l'interpolation de chaîne de caractères :\n",
"remplacer un nom de variable par (l'appel à ```__str__``` de) sa valeur dans une chaîne de caractères.\n",
"\n",
"Il y a deux manières de faire ça : une vieille avec ```format``` et une plus récente avec les ```f-string```."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(f\"{a} est un objet de type {type(a)}\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(\"{} est un objet de type {}\".format(a, type(a)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Voir [https://docs.python.org/fr/3.6/library/string.html#formatspec](https://docs.python.org/fr/3.6/library/string.html#formatspec) pour les détails"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Les arguments de fonction\n",
"\n",
"On peut déclarer des arguments de fonction comme optionnel en leur donnant une valeur par défaut"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def f(a, b=2, c=-10):\n",
" return a + b + c"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"f(5)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"f(5,3,2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"f(5,c=7,b=-7)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"f(4,1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Il est aussi courant que des fonctions prennent un nombre variable d'arguments nommés ou non."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def g(*args):\n",
" print(args)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"g(1,2,3)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"g(1)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def h(*args, **kwargs):\n",
" print(args)\n",
" for k in kwargs:\n",
" print(f\"kwargs[{k}] = {kwargs[k]}\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"h(1,2,3,lol=17,pouet=42)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"## Les itérateurs\n",
"\n",
"Les itérateurs sont un *pattern* de programmation maintenant présent dans la plupart des langages.\n",
"Ils permettent simplement et efficacement d'effectuer des __compositions__ d'opérations sur des séquences\n",
"de valeurs.\n",
"\n",
"En Python, on distingue les objets ```iterable``` des ```iterator```.\n",
"\n",
"Les objets ```iterable``` renvoient un ```iterator``` à l'appel de leur méthode ```__iter__``` \n",
"(par la fonction ```iter``` ou lors d'une boucle ```for``` par exemple).\n",
"\n",
"Les ```iterator``` sont des objets ```iterable``` dont l'appel à ```__iter__``` renvoie ```self```.\n",
"Ils possèdent aussi une méthode ```__next__``` permettant d'obtenir le prochain élément de la séquence\n",
"ou qui lance une exception si il arrive au bout de la séquence.\n",
"\n",
"Nous avons déjà vu plusieurs exemples d'objets ```iterable``` et ```iterator``` :\n",
"+ ```list, tuple, dict, set``` sont ```iterable```\n",
"+ ```range, map``` renvoient des itérateurs\n",
"\n",
"Il est bien sûr possible d'implémenter sa classe ```iterable``` ou ```iterator```, mais c'est rarement\n",
"nécessaire. En Python, on privilégie un style plus fonctionnel où l'on composer les ```iterator``` \n",
"grâce au module ```itertools``` : [https://docs.python.org/3.6/library/itertools.html?highlight=itertools](https://docs.python.org/3.6/library/itertools.html?highlight=itertools)\n",
"\n",
"On notera aussi les ```iterator``` *builtins* ```map, enumerate, zip``` et ```filter```\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from itertools import *\n",
"from functools import reduce"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"integers = count(0)\n",
"for _ in range(10):\n",
" print(next(integers))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for _ in range(10):\n",
" print(next(integers))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(map(lambda x: x*2, range(10)))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(accumulate(range(10)))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(combinations(range(5), 3))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(permutations(range(3)))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(enumerate([\"a\",\"b\",\"c\",\"d\"]))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(zip(range(4), [\"a\",\"b\",\"c\",\"d\"]))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(filter(lambda x : x < 0, range(-5,5)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 18\n",
"\n",
"Donnez la définition de la fonction ```divisors(n)``` qui renvoie un itérateur des diviseurs de ```n```."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def divisors(n):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(list(divisors(17)) == [1, 17])\n",
"assert(list(divisors(36)) == [1, 2, 3, 4, 6, 9, 12, 18, 36])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"## Les générateurs\n",
"\n",
"Une autre manière de construire des ```iterator``` est d'utiliser des générateurs.\n",
"Les générateurs Python sont des fonctions qui contiennent le mot clé ```yield```."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def integers():\n",
" i = 0\n",
" while True:\n",
" yield i\n",
" i += 1"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"ints = integers()\n",
"type(ints)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[next(ints) for _ in range(10)]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Comme on peut le voir sur cet exemple quand ```yield``` est rencontré la valeur en cours est délivrée\n",
"par un appel à ```next``` et le générateur est mis en suspension jusqu'au prochain appel de ```next```."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 19\n",
"\n",
"Définissez le générateur ```primes()``` qui génère les nombres premiers.\n",
"\n",
"On pourra utiliser la réponse à [l'exercice 14](#exo-14)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def primes():\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"assert(list(islice(primes(),0,25)) == [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])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Exercice 20 (difficile)\n",
"\n",
"On représente les arbres binaires par des tuples ```(racine, fils_gauche, fils_droit)```.\n",
"\n",
"Définissez le générateur ```prefix_order(tree)``` qui donne un parcours préfixe de l'arbre ```tree```.\n",
"\n",
"__Indication :__ On pourra utiliser l'instruction ```yield from``` (exemple ci-dessous)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def zeros():\n",
" yield 0\n",
" yield from zeros()\n",
"\n",
"z = zeros()\n",
"[next(z) for i in range(10)]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def prefix_order(tree):\n",
" pass"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"tree = (1,(2,(3,tuple(),tuple()), (4,tuple(),tuple())),(5,tuple(),tuple()))\n",
"assert(list(prefix_order(tree)) == [1,2,3,4,5])"
]
}
],
"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.6"
}
},
"nbformat": 4,
"nbformat_minor": 2
}