2015-12-03 - TD16 - Récursivité et tableaux.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Préambule :** nous avons commencé le TD par un rappel sur la récursivité et nous avons fait plusieurs exercices sur Pythontutor de sorte à ce que vous visualisiez la pile d'exécution et que vous compreniez bien comment sont effectués les appels récursifs et les instructions situées après un appel récursif dans le corps d'une méthode. \n",
    "\n",
    "**Attention, important :** vous devez travailler par vous-mêmes et essayer de comprendre ce que font les algorithmes que vous lisez et que vous écrivez. N'hésitez pas à prendre un crayon et une feuille de brouillon pour dérouler, étape par étape, ce qui se passe dans l'ordinateur. N'hésitez pas non plus à refaire des simulations avec Python Tutor de sorte à mieux comprendre ce qui se passe lorsque vous déclenchez un appel récursif. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercice 1.** Écrire un algorithme récursif qui permet de vérifier si une chaîne contient un caractère. Rappel : nous avons déjà écrit la solution de cet exercice en itératif. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%load_ext doctestmagic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n",
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "def rechercheRecursive (chaine,carac,i):\n",
    "    '''\n",
    "    :entree: chaine (string)\n",
    "    :entree: caractère (string)\n",
    "    :entree: i (int) \n",
    "    :sortie: present (booleen)\n",
    "    :pre-conditions: i doit être fixé à 0 lors de l'appel, carac doit être un caractère seul, la chaîne peut être vide.\n",
    "    :post-condions: le booléen est fixé à vrai si la chaîne contient le caractère et à faux sinon (y compris dans le cas de la chaîne vide)\n",
    "    >>> rechercheRecursive(\"Bonjour\", \"j\", 0)\n",
    "    True\n",
    "    >>> rechercheRecursive(\"Bonjour\", \"r\", 0)\n",
    "    True\n",
    "    >>> rechercheRecursive(\"\", \"j\", 0)\n",
    "    False\n",
    "    >>> rechercheRecursive(\"Bonjour\", \"a\", 0)\n",
    "    False\n",
    "    '''\n",
    "    if i==len(chaine):\n",
    "        present=False\n",
    "    elif chaine[i]==carac:\n",
    "        present=True\n",
    "    else:\n",
    "        present=rechercheRecursive(chaine,carac,i+1)\n",
    "    return present\n",
    "print(rechercheRecursive(\"bonjour\",'a',0))\n",
    "print(rechercheRecursive(\"bonjour\",'j',0))\n",
    "print(rechercheRecursive(\"\",'j',0))\n",
    "print(rechercheRecursive(\"bonjour\",'r',0))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ran 4 tests in 1 objects, 0 tests failed.\n"
     ]
    }
   ],
   "source": [
    "%doctest rechercheRecursive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La solution précédente est valide mais elle a l'inconvénient d'utiliser un indice en passage de paramètre, indice qui doit systématiquement être fixé à 0 lors de l'appel de la méthode. Une solution consisterait à \"encapsuler\" l'appel de cette méthode dans une autre méthode qui aurait une spécification plus simple, mais c'est un peu \"trop facile\". La solution ci-dessous est nettement plus élégante, même si elle a l'inconvénient de construire une nouvelle chaîne de caractères à chaque appel récursif. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def rechercheRecursiveBis(chaine,carac):\n",
    "    '''\n",
    "    :entree: chaine (string)\n",
    "    :entree: caractère (string)\n",
    "    :sortie: present (booleen)\n",
    "    :pre-conditions: carac doit être un caractère seul, la chaîne peut être vide.\n",
    "    :post-condions: le booléen est fixé à vrai si la chaîne contient le caractère et à faux sinon (y compris dans le cas de la chaîne vide)\n",
    "    >>> rechercheRecursiveBis(\"Bonjour\", \"j\")\n",
    "    True\n",
    "    >>> rechercheRecursiveBis(\"Bonjour\", \"r\")\n",
    "    True\n",
    "    >>> rechercheRecursiveBis(\"\", \"j\")\n",
    "    False\n",
    "    >>> rechercheRecursiveBis(\"Bonjour\", \"a\")\n",
    "    False\n",
    "    '''\n",
    "    if len(chaine)==0:\n",
    "        a=False\n",
    "    elif chaine[0]==carac:\n",
    "        a=True\n",
    "    else: \n",
    "        a=rechercheRecursiveBis(chaine[1:],carac)\n",
    "    return a\n",
    "print(rechercheRecursiveBis(\"bonjour\",'a'))\n",
    "print(rechercheRecursiveBis(\"bonjour\",'j'))\n",
    "print(rechercheRecursiveBis(\"bonjour\",'r'))\n",
    "print(rechercheRecursiveBis(\"\",\"r\"))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercice 2.** Écrire une méthode récursive pour calculer la somme des éléments d'une liste. Vous écrirez également le contrat. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "0\n",
      "82.2\n",
      "Ran 3 tests in 1 objects, 0 tests failed.\n"
     ]
    }
   ],
   "source": [
    "def sommeRec(l):\n",
    "    '''\n",
    "    :entree l: une liste de nombres (entiers ou flottants)\n",
    "    :sortie somme: la somme des éléments de la liste\n",
    "    :pre-conditions: la liste peut être vide\n",
    "    :post-condition: somme contient la somme des éléments de la liste, et est donc du même type que les éléments. \n",
    "    >>> sommeRec([1, 2, 3])\n",
    "    6\n",
    "    >>> sommeRec([])\n",
    "    0\n",
    "    >>> sommeRec([6, 42.2, 34])\n",
    "    82.2\n",
    "    '''\n",
    "    somme=0\n",
    "    if len(l)>1:\n",
    "        somme=l[0]+sommeRec(l[1:])\n",
    "    elif len(l)==1:\n",
    "        somme+=l[0]\n",
    "    return somme\n",
    "print(sommeRec([1, 2, 3]))\n",
    "print(sommeRec([]))\n",
    "print(sommeRec([6, 42.2, 34]))\n",
    "\n",
    "%doctest sommeRec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Encore une fois, la solution ci-dessus est correcte mais elle est loin d'être \"simple\" et facile à lire pour quelqu'un d'autre que celui ou celle qui a écrit l'algorithme. On va donc (ci-dessous) proposer une ré-écriture plus simple. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "0\n",
      "82.2\n",
      "Ran 3 tests in 1 objects, 0 tests failed.\n"
     ]
    }
   ],
   "source": [
    "def sommeRecBis(tab):\n",
    "    '''\n",
    "    :entree l: une liste de nombres (entiers ou flottants)\n",
    "    :sortie somme: la somme des éléments de la liste\n",
    "    :pre-conditions: la liste peut être vide\n",
    "    :post-condition: somme contient la somme des éléments de la liste, et est donc du même type que les éléments. \n",
    "    >>> sommeRecBis([1, 2, 3])\n",
    "    6\n",
    "    >>> sommeRecBis([])\n",
    "    0\n",
    "    >>> sommeRecBis([6, 42.2, 34])\n",
    "    82.2\n",
    "    '''\n",
    "    \n",
    "    if len(tab) == 0:\n",
    "        somme = 0\n",
    "    else:\n",
    "        somme = tab[0]+sommeRecBis(tab[1:])\n",
    "    return somme\n",
    "\n",
    "print(sommeRecBis([1, 2, 3]))\n",
    "print(sommeRecBis([]))\n",
    "print(sommeRecBis([6, 42.2, 34]))\n",
    "\n",
    "%doctest sommeRecBis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exerice 3.** Écrire un algorithme qui permet de rechercher un nombre dans un tableau trié. Proposez une solution récursive et une solution non récursive. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "-1\n",
      "4\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "def rechercheTab(tab,a):\n",
    "    '''\n",
    "    :entree tab: un tableau de nombres (entiers ou flottants) triés\n",
    "    :entree a: le nombre recherché\n",
    "    :sortie i: l'indice de la case du tableau dans laquelle se trouve le nombre. \n",
    "    :pré-conditions: le tableau est trié par ordre croissant de valeur.\n",
    "    :post-condition: l'indice de la première occurrence trouvée du nombre est renvoyé. \n",
    "     Si le nombre n'est pas présent dans le tableau, on retourne -1. \n",
    "    :Remarque : on appelle ce type de recherche \"recherche par dichotomie\". \n",
    "    >>> rechercheTab([0,1,2,3,4],1)\n",
    "    1\n",
    "    '''\n",
    "    i=-1\n",
    "    b=len(tab)//2\n",
    "    if tab[b]==a:\n",
    "        i=b\n",
    "    elif b == 0:\n",
    "        i = -1\n",
    "    elif tab[b]>a: # Si la valeur du milieu du tableau est plus grande que la valeur recherchée, on recherche dans la partie gauche du tableau\n",
    "        i=rechercheTab(tab[:b],a)\n",
    "    else: # Sinon, on recherche dans la partie droite et on gère le décalage des indices. \n",
    "        i=rechercheTab(tab[b:],a)\n",
    "        if i != -1:\n",
    "            i = i+b\n",
    "    return i\n",
    "\n",
    "print(rechercheTab([0,1,2,3,4],1))\n",
    "print(rechercheTab([0,1,2,3,4],5))\n",
    "print(rechercheTab([0,1,2,3,4],4))\n",
    "print(rechercheTab([0,1.3,2.7,3.4],0))\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Devoirs à faire à la maison :**\n",
    "- Pratiquer la récursivité en déroulant les algos à la main et / ou en utilisant Python Tutor ;\n",
    "- Relire la page d'exercices sur les tris (dans le manuel d'exercices) ;\n",
    "- Préparer la liste des exercices / notions que vous voulez revoir dans les prochains TD."
   ]
  }
 ],
 "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}