{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"toc": "true"
},
"source": [
"# Table of Contents\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TP 1 - Programmation pour la préparation à l'agrégation maths option info\n",
"\n",
"## Remarques sur le style\n",
"Ici, pour vous montrer, j'ai utilisé :\n",
"- En Python 3, avec des annotations de types.\n",
"- Notez que ce ne sont que des annotations.\n",
"- Pour plus, il faudrait utiliser [quelque chose comme `beartype`](https://stackoverflow.com/a/37961120/2809027).\n",
"\n",
"Notez que ce n'est absolument *pas nécessaire*, c'était juste pour montrer que ce genre d'annotations peut aider à passer de Caml à Python."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Fonctions"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 4"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"def successeur(i : int) -> int:\n",
" assert isinstance(i, int), \"Erreur : i = {} doit etre entier.\".format(i)\n",
" assert i >= 0, \"Erreur : i = {} doit etre >= 0.\".format(i)\n",
" return i + 1"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
},
{
"ename": "AssertionError",
"evalue": "Erreur : i = 2.5 doit etre entier.",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mAssertionError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0msuccesseur\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0msuccesseur\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m2\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0msuccesseur\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m2.5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36msuccesseur\u001b[0;34m(i)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0msuccesseur\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m \u001b[0;34m:\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m->\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"Erreur : i = {} doit etre entier.\"\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0mi\u001b[0m \u001b[0;34m>=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"Erreur : i = {} doit etre >= 0.\"\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mi\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mAssertionError\u001b[0m: Erreur : i = 2.5 doit etre entier."
]
}
],
"source": [
"successeur(3)\n",
"successeur(2 * 2)\n",
"successeur(2.5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 5"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"def produit3(x, y, z):\n",
" return x * y * z\n",
"\n",
"produit3_2 = lambda x, y, z: x * y * z\n",
"\n",
"produit3_3 = lambda x: lambda y: lambda z: x * y * z"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"....(z)>"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"produit3(1, 2, 3)\n",
"produit3_2(1, 2, 3)\n",
"produit3_3(1)(2) # lambda z : 1 * 2 * z\n",
"f = produit3_3(1)(2) # lambda z : 1 * 2 * z\n",
"f(3)\n",
"produit3_3(1)(2)(3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 6"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"def exercice6(n : int) -> None:\n",
" for i in range(1, n + 1):\n",
" print(i)\n",
" for i in range(n, 0, -1):\n",
" print(i)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1\n",
"2\n",
"3\n",
"4\n",
"4\n",
"3\n",
"2\n",
"1\n"
]
}
],
"source": [
"exercice6(4)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Récursivité\n",
"\n",
"C'est simple. Pas besoin d'un mot clé `rec` quand on définit une fonction récursive en Python."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 7"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"def factorielle(n : int) -> int:\n",
" if n <= 0:\n",
" return 0\n",
" elif n == 1:\n",
" return 1\n",
" else:\n",
" return n * factorielle(n - 1)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0! = 0\n",
"1! = 1\n",
"2! = 2\n",
"3! = 6\n",
"4! = 24\n",
"5! = 120\n",
"6! = 720\n",
"7! = 5040\n"
]
}
],
"source": [
"for i in range(8):\n",
" print(\"{}! = {:>5}\".format(i, factorielle(i)))\n",
" # Note : ce {:>5} signifie que l'affichage utilise au moins\n",
" # 5 caractères, pour avoir un joli alignement :"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 8\n",
"\n",
"Pour ce genre de fonction, j'aime bien afficher les appels récursifs. On peut rendre ça optionnel, avec comme ici un argument nommé `log`, à valeur par défaut `log=False`."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"def pgcd(x : int, y : int, log: bool=False) -> int:\n",
" if log: print(\"x = {:>7}, y = {:>7}\".format(x, y))\n",
" assert x >= 0 and y >= 0\n",
" if y == 1:\n",
" return 1\n",
" elif y == x or y == 0:\n",
" return x\n",
" if x < y:\n",
" return pgcd(x, y % x, log=log)\n",
" else:\n",
" return pgcd(y, x % y, log=log)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pgcd(10, 5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On peut faire des essais pour afficher notre calcul de PGCD, sur des entiers aléatoires entre $1$ et $100$.\n",
"\n",
"Pour se rassurer, on peut chercher dans la bibliothèque standard, à partir de Python 3.6 il y a la fonction `math.gcd` pour calculer le PGCD, sinon `fractions.gcd` ou encore dans le module (non standard) SymPy `sympy.gcd`."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 61 ^ 61 = 61\n",
" 44 ^ 85 = 1\n",
" 48 ^ 79 = 1\n",
" 84 ^ 83 = 1\n",
" 17 ^ 20 = 1\n",
" 39 ^ 2 = 1\n",
" 30 ^ 68 = 2\n",
" 14 ^ 87 = 1\n",
" 46 ^ 63 = 1\n",
" 83 ^ 84 = 1\n"
]
}
],
"source": [
"try:\n",
" from math import gcd\n",
"except ImportError:\n",
" try:\n",
" from fractions import gcd\n",
" except ImportError:\n",
" from sympy import gcd\n",
"\n",
"\n",
"from random import randint\n",
"for _ in range(10):\n",
" x = randint(1, 100)\n",
" y = randint(1, 100)\n",
" d = pgcd(x, y)\n",
" print(\"{:>3} ^ {:>3} = {:>3}\".format(x, y, d))\n",
" assert d == gcd(x, y), \"Erreur : mauvais calcul de pgcd(x={}, y={}) = {}, alors qu'il devrait etre = {}.\".format(x, y, pgcd(x, y), gcd(x, y))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 9\n",
"\n",
"Rien de particulier à faire, la récursivité fonctionne sans réfléchir :"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [],
"source": [
"def fibonacci(n : int) -> int:\n",
" assert n >= 0\n",
" if n == 0 or n == 1:\n",
" return 1\n",
" else:\n",
" return fibonacci(n - 1) + fibonacci(n - 2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Dans IPython (ou Jupyter) on peut facilement mesurer le temps (moyen) d'exécution d'une fonction sur une entrée donnée, avec la *macro* `%timeit`."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"4.92 s ± 90.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
]
}
],
"source": [
"%timeit fibonacci(35)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Dans Python, on peut faire pareil avec `timeit()` du module `timeit`."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"scrolled": true
},
"outputs": [
{
"ename": "KeyboardInterrupt",
"evalue": "",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mtimeit\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mtimeit\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mtimeit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"fibonacci(35)\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mglobals\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mglobals\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m/usr/lib/python3.6/timeit.py\u001b[0m in \u001b[0;36mtimeit\u001b[0;34m(stmt, setup, timer, number, globals)\u001b[0m\n\u001b[1;32m 231\u001b[0m number=default_number, globals=None):\n\u001b[1;32m 232\u001b[0m \u001b[0;34m\"\"\"Convenience function to create Timer object and call timeit method.\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 233\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mTimer\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mstmt\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msetup\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtimer\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mglobals\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtimeit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnumber\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 234\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 235\u001b[0m def repeat(stmt=\"pass\", setup=\"pass\", timer=default_timer,\n",
"\u001b[0;32m/usr/lib/python3.6/timeit.py\u001b[0m in \u001b[0;36mtimeit\u001b[0;34m(self, number)\u001b[0m\n\u001b[1;32m 176\u001b[0m \u001b[0mgc\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdisable\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 177\u001b[0m \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 178\u001b[0;31m \u001b[0mtiming\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minner\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mit\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtimer\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 179\u001b[0m \u001b[0;32mfinally\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 180\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mgcold\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;32m\u001b[0m in \u001b[0;36minner\u001b[0;34m(_it, _timer)\u001b[0m\n",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mfibonacci\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m:\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m->\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m>=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m0\u001b[0m \u001b[0;32mor\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mKeyboardInterrupt\u001b[0m: "
]
}
],
"source": [
"from timeit import timeit\n",
"timeit(\"fibonacci(35)\", globals=globals())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour la version qui est en complexité (temporelle) linéaire dans l'entrée $n$, il suffit de déplier la récursion en calculant $F_{n+1}$ progressivement en partant de $F_0, F_1$."
]
},
{
"cell_type": "code",
"execution_count": 77,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def fibonacci_lin(n : int) -> int:\n",
" un, uns = 1, 1\n",
" for _ in range(n):\n",
" un, uns = uns, un + uns\n",
" return un"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On peut vérifier que cette deuxième implémentation fonctionne comme la première, et ensuite vérifier qu'elle est (bien) plus rapide."
]
},
{
"cell_type": "code",
"execution_count": 79,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"for i in range(10):\n",
" assert fibonacci(i) == fibonacci_lin(i)"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1.79 µs ± 27.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
]
}
],
"source": [
"%timeit fibonacci_lin(35)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Voilà la différence."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 10\n",
"\n",
"Aucune hypothèse n'est faite sur les arguments de la fonction, on supposera seulement qu'elle est itérable sur sa sortie."
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from types import FunctionType # inutile, juste pour faire joli\n",
"\n",
"# première version, f : type x -> type x (simple)\n",
"def itere(f : FunctionType, n : int) -> FunctionType:\n",
" def fn(x):\n",
" for _ in range(n):\n",
" x = f(x)\n",
" return x\n",
" return fn"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"11"
]
},
"execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"itere(lambda x: x + 1, 10)(1)"
]
},
{
"cell_type": "code",
"execution_count": 119,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# deuxième version, f : tuple -> tuple (simple)\n",
"def itere2(f : FunctionType, n : int) -> FunctionType:\n",
" def fn(*args):\n",
" for _ in range(n):\n",
" if isinstance(args, tuple):\n",
" args = f(*args)\n",
" else:\n",
" args = f(args)\n",
" if isinstance(args, tuple) and len(args) == 1:\n",
" return args[0]\n",
" else:\n",
" return args\n",
" return fn"
]
},
{
"cell_type": "code",
"execution_count": 132,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"11"
]
},
"execution_count": 132,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"(1024, 2048)"
]
},
"execution_count": 132,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def plusun(x):\n",
" return x + 1\n",
"\n",
"itere2(plusun, 10)(1)\n",
"\n",
"def foisdeux(x, y):\n",
" return x * 2, y * 2\n",
"\n",
"itere2(foisdeux, 10)(1, 2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 11\n",
"\n",
"C'est assez naturel, on affiche la suite de mouvement à faire, comme une suite de `\"T1 -> T2\"` par exemple."
]
},
{
"cell_type": "code",
"execution_count": 144,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def hanoi(x : str, y : str, z : str, n : int) -> None:\n",
" def hanoiaux(orig : str, dest : str, inter : str, n : int):\n",
" if n == 0:\n",
" return 0\n",
" c1 = hanoiaux(orig, inter, dest, n - 1)\n",
" print(\"{} -> {}\".format(orig, dest))\n",
" c2 = hanoiaux(inter, dest, orig, n - 1)\n",
" return c1 + 1 + c2\n",
" return hanoiaux(x, z, y, n)"
]
},
{
"cell_type": "code",
"execution_count": 145,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"T1 -> T3\n"
]
},
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 145,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hanoi(\"T1\", \"T2\", \"T3\", 1)"
]
},
{
"cell_type": "code",
"execution_count": 146,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"T1 -> T2\n",
"T1 -> T3\n",
"T2 -> T3\n"
]
},
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 146,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hanoi(\"T1\", \"T2\", \"T3\", 2)"
]
},
{
"cell_type": "code",
"execution_count": 148,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"T1 -> T3\n",
"T1 -> T2\n",
"T3 -> T2\n",
"T1 -> T3\n",
"T2 -> T1\n",
"T2 -> T3\n",
"T1 -> T3\n",
"T1 -> T2\n",
"T3 -> T2\n",
"T3 -> T1\n",
"T2 -> T1\n",
"T3 -> T2\n",
"T1 -> T3\n",
"T1 -> T2\n",
"T3 -> T2\n",
"T1 -> T3\n",
"T2 -> T1\n",
"T2 -> T3\n",
"T1 -> T3\n",
"T2 -> T1\n",
"T3 -> T2\n",
"T3 -> T1\n",
"T2 -> T1\n",
"T2 -> T3\n",
"T1 -> T3\n",
"T1 -> T2\n",
"T3 -> T2\n",
"T1 -> T3\n",
"T2 -> T1\n",
"T2 -> T3\n",
"T1 -> T3\n"
]
},
{
"data": {
"text/plain": [
"31"
]
},
"execution_count": 148,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hanoi(\"T1\", \"T2\", \"T3\", 5) # 31 = 2^5 - 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Listes\n",
"## Exercice 12\n",
"Les listes en Python sont des `list`.\n",
"\n",
"Elles ne fonctionnent **pas** comme des listes simplement chaînées comme en Caml : ce sont des tableaux, donc l'accès à `T[i]` pour n'importe quel `i` est en $\\mathcal{O}(1)$ pour n'importe quel `i` et `n`."
]
},
{
"cell_type": "code",
"execution_count": 152,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def concatene(liste1 : list, liste2 : list) -> list:\n",
" # return liste1 + liste2 # solution facile\n",
" n1, n2 = len(liste1), len(liste2)\n",
" res = []\n",
" for i in range(n1 + n2):\n",
" if i < n1:\n",
" res.append(liste1[i])\n",
" else:\n",
" res.append(liste2[i - n1])\n",
" return res"
]
},
{
"cell_type": "code",
"execution_count": 153,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 2, 3, 4, 5]"
]
},
"execution_count": 153,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"concatene([1, 2, 3], [4, 5])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 13"
]
},
{
"cell_type": "code",
"execution_count": 163,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from types import FunctionType\n",
"\n",
"def applique(f : FunctionType, liste : list) -> list:\n",
" res = [f(x) for x in liste] # solution facile\n",
" res = map(f, liste) # encore plus facile\n",
" # en itérant la liste :\n",
" res = [ ] # tableau vide\n",
" for x in liste:\n",
" res.append(f(x))\n",
" # en itérant ses valeurs :\n",
" res = [ ] # tableau\n",
" for i in range(len(liste)):\n",
" res.append(f(liste[i]))\n",
" return res"
]
},
{
"cell_type": "code",
"execution_count": 164,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2, 3, 4]"
]
},
"execution_count": 164,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"applique(lambda x : x + 1, [1, 2, 3])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 14"
]
},
{
"cell_type": "code",
"execution_count": 165,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def liste_carree(liste : list) -> list:\n",
" return applique(lambda x: x**2, liste)"
]
},
{
"cell_type": "code",
"execution_count": 167,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 4, 9]"
]
},
"execution_count": 167,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"liste_carree([1, 2, 3])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 15"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"def miroir_quad(liste : list) -> list:\n",
" # pour le faire naïvement en Python\n",
" # on fait une concaténation de liste\n",
" if liste:\n",
" return miroir_quad(liste[1:]) + [ liste[0] ]\n",
" else:\n",
" return []\n",
"\n",
"def miroir_lin(liste : list) -> list:\n",
" return [liste[-i] for i in range(1, len(liste) + 1)]"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[3, 2, 1]"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"miroir_quad([1, 2, 3])"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3.13 ms ± 93.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
]
}
],
"source": [
"%timeit miroir_quad(list(range(1000)))"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[3, 2, 1]"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"miroir_lin([1, 2, 3])"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"77.2 µs ± 7.47 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
]
}
],
"source": [
"%timeit miroir_lin(list(range(1000)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 16"
]
},
{
"cell_type": "code",
"execution_count": 186,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def insertion_dans_liste_triee(entiers : list, x : int) -> list:\n",
" i = 0\n",
" while i < len(entiers) and entiers[i] < x:\n",
" i += 1\n",
" return entiers[:i] + [x] + entiers[i:]"
]
},
{
"cell_type": "code",
"execution_count": 187,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 2, 4, 5, 6]"
]
},
"execution_count": 187,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"insertion_dans_liste_triee([1, 2, 5, 6], 4)"
]
},
{
"cell_type": "code",
"execution_count": 190,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def tri_insertion(entiers : list) -> list:\n",
" assert all([isinstance(i, int) for _ in entiers])\n",
" def trix(e : list, acc : list) -> list:\n",
" if len(e) == 0: return acc\n",
" else: return trix(e[1:], insertion_dans_liste_triee(acc, e[0]))\n",
" return trix(entiers, [])"
]
},
{
"cell_type": "code",
"execution_count": 191,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 2, 4, 5, 6]"
]
},
"execution_count": 191,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tri_insertion([5, 2, 6, 1, 4])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 17"
]
},
{
"cell_type": "code",
"execution_count": 193,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def ordre_decroissant(x, y):\n",
" return x > y"
]
},
{
"cell_type": "code",
"execution_count": 195,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from types import FunctionType\n",
"\n",
"def insertion_dans_liste_triee2(entiers : list, x : int, ordre : FunctionType) -> list:\n",
" i = 0\n",
" while i < len(entiers) and ordre(entiers[i], x):\n",
" i += 1\n",
" return entiers[:i] + [x] + entiers[i:]"
]
},
{
"cell_type": "code",
"execution_count": 196,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[6, 5, 4, 2, 1]"
]
},
"execution_count": 196,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"insertion_dans_liste_triee2([6, 5, 2, 1], 4, ordre_decroissant)"
]
},
{
"cell_type": "code",
"execution_count": 197,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def tri_insertion2(entiers : list, ordre : FunctionType) -> list:\n",
" assert all([isinstance(i, int) for _ in entiers])\n",
" def trix(e : list, acc : list) -> list:\n",
" if len(e) == 0: return acc\n",
" else: return trix(e[1:], insertion_dans_liste_triee2(acc, e[0], ordre))\n",
" return trix(entiers, [])"
]
},
{
"cell_type": "code",
"execution_count": 200,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 2, 4, 5, 6]"
]
},
"execution_count": 200,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"[6, 5, 4, 2, 1]"
]
},
"execution_count": 200,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tri_insertion([5, 2, 6, 1, 4])\n",
"tri_insertion2([5, 2, 6, 1, 4], ordre_decroissant)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Exponentiation rapide\n",
"## Exercice 18\n",
"\n",
"Une approche naïve :"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def exp(x : int, n : int) -> int:\n",
" res = 1\n",
" for _ in range(n):\n",
" res *= x\n",
" return res"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 3 ** 0 = 1\n",
" 3 ** 1 = 3\n",
" 3 ** 2 = 9\n",
" 3 ** 3 = 27\n",
" 3 ** 4 = 81\n",
" 3 ** 5 = 243\n",
" 3 ** 6 = 729\n",
" 3 ** 7 = 2187\n"
]
}
],
"source": [
"x = 3\n",
"for n in range(8):\n",
" print(\" {} ** {} = {:>5}\".format(x, n, exp(x, n)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 19\n",
"\n",
"Une approche maline (optimale, en fait)."
]
},
{
"cell_type": "code",
"execution_count": 201,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def exp2(x : int, n : int) -> int:\n",
" assert n >= 0\n",
" if n == 0:\n",
" return 1\n",
" elif n == 1:\n",
" return x\n",
" elif n % 2 == 0:\n",
" return exp2(x ** 2, n // 2)\n",
" elif n % 2 == 1:\n",
" return exp2(x ** 2, (n - 1) // 2) * x"
]
},
{
"cell_type": "code",
"execution_count": 205,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 3 ** 0 = 1\n",
" 3 ** 1 = 3\n",
" 3 ** 2 = 9\n",
" 3 ** 3 = 27\n",
" 3 ** 4 = 81\n",
" 3 ** 5 = 243\n",
" 3 ** 6 = 729\n",
" 3 ** 7 = 2187\n"
]
}
],
"source": [
"x = 3\n",
"for n in range(8):\n",
" print(\" {} ** {} = {:>5}\".format(x, n, exp2(x, n)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 20\n",
"On ne dispose pas de typage pour faire ça aussi joliment qu'en Caml..."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def mult_float(x : float, y : float) -> float:\n",
" return x * y\n",
"\n",
"monoide_flottants = {\n",
" 'mult': mult_float, # (*.) en Caml\n",
" 'neutre': 1.\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"\n",
"def mult_ndarray(A : np.array, B : np.array) -> np.array:\n",
" return np.dot(A, B)\n",
"\n",
"# Pas possible d'avoir un neutre pour une taille quelconque !\n",
"monoide_nparray = lambda n, m: {\n",
" 'mult': mult_ndarray,\n",
" 'neutre': np.eye(n, m)\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[4, 6],\n",
" [4, 6]])"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mult_ndarray([[1, 1], [1, 1]], [[1, 2], [3, 4]])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Manuellement ce n'est pas trop dur :"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def mult_mat(A : list, B : list) -> list:\n",
" n, m = len(A), len(A[0]) # A est (n, m)\n",
" m2, p = len(B), len(B[0]) # B est (m2, p)\n",
" assert m == m2\n",
" C = [[0 for _ in range(p)] for _ in range(n)] # C est (n, p)\n",
" for i in range(n):\n",
" for j in range(p):\n",
" for k in range(m):\n",
" C[i][j] += A[i][k] * B[k][j]\n",
" return C\n",
"\n",
"# Pas possible d'avoir un neutre pour une taille quelconque !\n",
"monoide_mat = lambda n, m: {\n",
" 'mult': mult_mat,\n",
" 'neutre': [[int(i==j) for j in range(m)] for i in range(n)] # I est (n, m)\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[4, 6], [4, 6]]"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mult_mat([[1, 1], [1, 1]], [[1, 2], [3, 4]])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 21"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def exp_rapide(monoide : dict, x, n : int):\n",
" mult = monoide['mult']\n",
" assert n >= 0\n",
" if n == 0:\n",
" return monoide['neutre']\n",
" elif n == 1:\n",
" return x\n",
" elif n % 2 == 0:\n",
" return exp_rapide(monoide, mult(x, x), n // 2)\n",
" elif n % 2 == 1:\n",
" return mult(exp_rapide(monoide, mult(x, x), (n - 1) // 2), x)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 22"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def exp_rapide_float(x : float, n : int) -> float:\n",
" return exp_rapide(monoide_flottants, x, n)"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"256.0"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"exp_rapide_float(2.0, 8)"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2.560000000000002e-06"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"exp_rapide_float(0.2, 8)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et pour les matrices, un petit piège à cause des tailles :"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def exp_rapide_mat(A : list, k : int) -> float:\n",
" n, m = len(A), len(A[0])\n",
" mono = monoide_mat(n, m)\n",
" return exp_rapide(mono, A, k)"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[1, 0], [0, 1]]"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"[[1, 1], [1, 1]]"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"[[2, 2], [2, 2]]"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"[[4, 4], [4, 4]]"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"[[8, 8], [8, 8]]"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"for k in range(5):\n",
" exp_rapide_mat([[1, 1], [1, 1]], k)"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[1, 0, 0], [0, 1, 0], [0, 0, 1]]"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"[[0, 1, 2], [0, 0, 1], [0, 0, 0]]"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"[[0, 0, 1], [0, 0, 0], [0, 0, 0]]"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"[[0, 0, 0], [0, 0, 0], [0, 0, 0]]"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"[[0, 0, 0], [0, 0, 0], [0, 0, 0]]"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"for k in range(5): # nilpotente\n",
" exp_rapide_mat([[0, 1, 2], [0, 0, 1], [0, 0, 0]], k)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 23"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [],
"source": [
"from operator import mul\n",
"\n",
"def exp_rapide_2(x, n : int):\n",
" def mul_par_x(y):\n",
" return x * y\n",
" return itere(mul_par_x, n)(x)"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"512.0"
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"exp_rapide_2(2.0, 8)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Formule du calcul propositionnel\n",
"\n",
"**Spoiler alert** : en Python, c'est chaud.\n",
"\n",
"**ATTENTION** Il faut un peut d'habitude et d'idées pour réussir à faire tout ça aussi efficacement (enfin presque) qu'en OCaml.\n",
"\n",
"On va faire des choses non typées, avec des dictionnaires, pour bidouiller.\n",
"\n",
"## Exercice 24"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"``(not p ^ ((q ^ not p) v (r v q)))`` s'écrit en Caml `` (Conj(Not(V(\"p\")),Disj(Conj(V(\"q\"),Not(V(\"p\"))),Disj(V(\"r\"),V(\"q\")))))``.\n",
"\n",
"On va imbriquer des dictionnaires, les types, `V`, `Not`, `Conj` et `Disj` seront des clés, et les valeurs seront des formules ou couples de formules.\n",
"Mais on va cacher ça et l'utilisateur verra exactement la même chose qu'en Caml !"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'Conj': ({'Not': {'V': 'p'}},\n",
" {'Disj': ({'Conj': ({'V': 'q'}, {'Not': {'V': 'p'}})},\n",
" {'Disj': ({'V': 'r'}, {'V': 'q'})})})}"
]
},
"execution_count": 63,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"V = lambda x: {'V': x}\n",
"Not = lambda x: {'Not': x}\n",
"Disj = lambda x, y: {'Disj': (x, y)}\n",
"Conj = lambda x, y: {'Conj': (x, y)}\n",
"\n",
"p = V('p')\n",
"r = V('r')\n",
"q = V('q')\n",
"not_p = Not(p)\n",
"\n",
"f = Conj(Not(p), Disj(Conj(q, not_p), Disj(r, q)))\n",
"f"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'Conj': ({'Not': {'V': 'p'}},\n",
" {'Disj': ({'Conj': ({'V': 'q'}, {'Not': {'V': 'p'}})},\n",
" {'Disj': ({'V': 'r'}, {'V': 'q'})})})}"
]
},
"execution_count": 59,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(Conj(Not(V(\"p\")),Disj(Conj(V(\"q\"),Not(V(\"p\"))),Disj(V(\"r\"),V(\"q\")))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 25"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ensuite on fait une filtration \"à la main\" sur les clés du dictionnaire (de niveau 1, on ne récurse pas quand on teste `'V' in formule`)."
]
},
{
"cell_type": "code",
"execution_count": 79,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def taille(formule : dict) -> str:\n",
" if 'V' in formule:\n",
" return 0\n",
" elif 'Not' in formule:\n",
" return 1 + taille(formule['Not'])\n",
" elif 'Conj' in formule:\n",
" x, y = formule['Conj']\n",
" return 1 + taille(x) + taille(y)\n",
" elif 'Disj' in formule:\n",
" x, y = formule['Disj']\n",
" return 1 + taille(x) + taille(y)"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 69,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"taille(f)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 26"
]
},
{
"cell_type": "code",
"execution_count": 109,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def formule_to_string(formule : dict) -> str:\n",
" if 'V' in formule:\n",
" return formule['V']\n",
" elif 'Not' in formule:\n",
" return \"~\" + formule_to_string(formule['Not'])\n",
" elif 'Conj' in formule:\n",
" x, y = formule['Conj']\n",
" return \"(\" + formule_to_string(x) + \" ^ \" + formule_to_string(y) + \")\"\n",
" elif 'Disj' in formule:\n",
" x, y = formule['Disj']\n",
" return \"(\" + formule_to_string(x) + \" V \" + formule_to_string(y) + \")\""
]
},
{
"cell_type": "code",
"execution_count": 110,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def affiche(formule):\n",
" print(formule_to_string(formule))"
]
},
{
"cell_type": "code",
"execution_count": 111,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(~p ^ ((q ^ ~p) V (r V q)))\n"
]
}
],
"source": [
"affiche(f)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et voilà. Pas tellement plus dur hein !"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 27\n",
"Les valeurs des variables seront données comme un dictionnaire associant nom de variable à valeurs booléennes.\n",
"Et comme on veut frimer, on prend un [`defaultdict`](https://docs.python.org/3/library/collections.html#collections.defaultdict)."
]
},
{
"cell_type": "code",
"execution_count": 115,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 115,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"False"
]
},
"execution_count": 115,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"False"
]
},
"execution_count": 115,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from collections import defaultdict\n",
"\n",
"d = defaultdict(lambda: False, {'p': True, 'q': False})\n",
"d['p'] # -> True car présent et True\n",
"d['q'] # -> False car présent et False\n",
"d['x'] # -> False car absent"
]
},
{
"cell_type": "code",
"execution_count": 113,
"metadata": {},
"outputs": [],
"source": [
"valeurs_1 = defaultdict(lambda: False, {'p': True})"
]
},
{
"cell_type": "code",
"execution_count": 114,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"valeurs_2 = defaultdict(lambda: False, {'r': True})"
]
},
{
"cell_type": "code",
"execution_count": 89,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def eval(valeurs : dict, formule : dict) -> bool:\n",
" if 'V' in formule:\n",
" return valeurs[formule['V']]\n",
" elif 'Not' in formule:\n",
" return not eval(valeurs, formule['Not'])\n",
" elif 'Conj' in formule:\n",
" x, y = formule['Conj']\n",
" return eval(valeurs, x) and eval(valeurs, y)\n",
" elif 'Disj' in formule:\n",
" x, y = formule['Disj']\n",
" return eval(valeurs, x) or eval(valeurs, y)"
]
},
{
"cell_type": "code",
"execution_count": 90,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"execution_count": 90,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"eval(valeurs_1, f)"
]
},
{
"cell_type": "code",
"execution_count": 91,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 91,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"eval(valeurs_2, f)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 28"
]
},
{
"cell_type": "code",
"execution_count": 93,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def extrait_variables_x(formule : dict) -> list:\n",
" if 'V' in formule:\n",
" return [formule['V']]\n",
" elif 'Not' in formule:\n",
" return extrait_variables_x(formule['Not'])\n",
" elif 'Conj' in formule:\n",
" x, y = formule['Conj']\n",
" return extrait_variables_x(x) + extrait_variables_x(y)\n",
" elif 'Disj' in formule:\n",
" x, y = formule['Disj']\n",
" return extrait_variables_x(x) + extrait_variables_x(y)\n",
"\n",
"# on enlève les doublons\n",
"def extrait_variables(formule : dict) -> list:\n",
" return list(set(extrait_variables_x(formule)))"
]
},
{
"cell_type": "code",
"execution_count": 94,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['p', 'r', 'q']"
]
},
"execution_count": 94,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"extrait_variables(f)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On trouve facilement les $n$ variables d'une formule.\n",
"\n",
"Ensuite, un [`itertools.product`](https://docs.python.org/3/library/itertools.html#itertools.product) permet de générer les $2^n$ valuations."
]
},
{
"cell_type": "code",
"execution_count": 98,
"metadata": {},
"outputs": [],
"source": [
"from itertools import product\n",
"\n",
"def toutes_valeurs(variables):\n",
" for valeurs in product([False, True], repeat=len(variables)):\n",
" yield defaultdict(lambda: False, {k:v for k,v in zip(variables, valeurs)})"
]
},
{
"cell_type": "code",
"execution_count": 103,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[defaultdict(.>,\n",
" {'p': False, 'q': False, 'r': False}),\n",
" defaultdict(.>,\n",
" {'p': False, 'q': True, 'r': False}),\n",
" defaultdict(.>,\n",
" {'p': False, 'q': False, 'r': True}),\n",
" defaultdict(.>,\n",
" {'p': False, 'q': True, 'r': True}),\n",
" defaultdict(.>,\n",
" {'p': True, 'q': False, 'r': False}),\n",
" defaultdict(.>,\n",
" {'p': True, 'q': True, 'r': False}),\n",
" defaultdict(.>,\n",
" {'p': True, 'q': False, 'r': True}),\n",
" defaultdict(.>,\n",
" {'p': True, 'q': True, 'r': True})]"
]
},
"execution_count": 103,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(toutes_valeurs(extrait_variables(f)))"
]
},
{
"cell_type": "code",
"execution_count": 106,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def str_of_bool(x : bool) -> str:\n",
" # return str(int(x))\n",
" return '1' if x else '0'"
]
},
{
"cell_type": "code",
"execution_count": 116,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def table_verite(formule : dict) -> None:\n",
" variables = extrait_variables(formule)\n",
" # D'abord la formule\n",
" for k in variables:\n",
" print(k, end=' ')\n",
" print('| ', end='')\n",
" affiche(f)\n",
" # Puis toutes ces valeurs possibles\n",
" for valeurs in toutes_valeurs(variables):\n",
" for k in variables:\n",
" print(str_of_bool(valeurs[k]), end=' ')\n",
" print('| ', end='')\n",
" print(str_of_bool(eval(valeurs, formule)))"
]
},
{
"cell_type": "code",
"execution_count": 117,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"p r q | (~p ^ ((q ^ ~p) V (r V q)))\n",
"0 0 0 | 0\n",
"0 0 1 | 1\n",
"0 1 0 | 1\n",
"0 1 1 | 1\n",
"1 0 0 | 0\n",
"1 0 1 | 0\n",
"1 1 0 | 0\n",
"1 1 1 | 0\n"
]
}
],
"source": [
"table_verite(f)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note : ce code est encore plus concis que celui donné dans la solution en Caml.\n",
"\n",
"> On peut vérifier, par exemple sur [Wolfram|Alpha](https%3A%2F%2Fwww.wolframalpha.com%2Finput%2F%3Fi%3D%28%7Ep%2B%2526%2B%28%28q%2B%2526%2B%7Ep%29%2B%257C%2B%28r%2B%257C%2Bq%29%29%29) que l'on obtient bien le bon résultat..."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"\n",
"# Conclusion\n",
"\n",
"Comme vous le voyez, on arrive à répondre aux mêmes questions dans les deux langages, et il n'y a pas de grosses différences en pratique dans la mise en oeuvre.\n",
"\n",
"Là où Caml excelle pour les types définis, le filtrage et la récursion, Python gagne en simplicité sur l'affichage, sa librairie standard et les dictionnaires et ensembles..."
]
}
],
"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.6.8"
},
"toc": {
"colors": {
"hover_highlight": "#DAA520",
"running_highlight": "#FF0000",
"selected_highlight": "#FFD700"
},
"moveMenuLeft": true,
"nav_menu": {
"height": "365px",
"width": "251px"
},
"navigate_menu": true,
"number_sections": true,
"sideBar": true,
"threshold": 4,
"toc_cell": true,
"toc_position": {
"height": "523px",
"left": "0px",
"right": "1068px",
"top": "116px",
"width": "212px"
},
"toc_section_display": "block",
"toc_window_display": true
},
"varInspector": {
"cols": {
"lenName": 16,
"lenType": 16,
"lenVar": 40
},
"kernels_config": {
"python": {
"delete_cmd_postfix": "",
"delete_cmd_prefix": "del ",
"library": "var_list.py",
"varRefreshCmd": "print(var_dic_list())"
},
"r": {
"delete_cmd_postfix": ") ",
"delete_cmd_prefix": "rm(",
"library": "var_list.r",
"varRefreshCmd": "cat(var_dic_list()) "
}
},
"types_to_exclude": [
"module",
"function",
"builtin_function_or_method",
"instance",
"_Feature"
],
"window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}