parcours1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Parcours\n",
    "=======\n",
    "Parcourir une structure de données signifie considérer successivement chacun de ses éléments, pour y appliquer éventuellement un traitement.\n",
    "\n",
    "<em>Ronan Charpentier IREM Caen</em> <img src=\"by-nc-sa.png\" alt=\"CC-BY-NC-SA\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parcours d'une liste\n",
    "Nous définissons une liste et examinons quelques façons de la parcourir, dans un premier temps en affichant ses éléments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "liste=[2,3,5,7,11,13,17,19]\n",
    "len(liste)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for element in liste:\n",
    "    print(element)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for indice in range(len(liste)):\n",
    "    print(indice,'--->',liste[indice])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for indice,element in enumerate(liste):\n",
    "    print(indice,'--->',element)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Nous parcourons une liste en effectuant un traitement sur chaque élément."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def occurence(element,liste):\n",
    "    \"\"\"\n",
    "    cette fonction à valeur booléenne teste l'appartenance de l'élément passé en paramètre\n",
    "    à la liste également fournie en paramètre\n",
    "    >>> occurence(12,[2,3,5,7,11,13,17,19])\n",
    "    False\n",
    "    >>> occurence(13,[2,3,5,7,11,13,17,19])\n",
    "    True\n",
    "    \"\"\"\n",
    "    for elt in liste:\n",
    "        if elt==element:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "print(occurence(12,liste))\n",
    "print(occurence(13,liste))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def somme(liste):\n",
    "    \"\"\"\n",
    "    cette fonction ajoute les nombres de la liste passée en paramètre\n",
    "    \"\"\"\n",
    "    s=0\n",
    "    for e in liste:\n",
    "        s+=e\n",
    "    return s\n",
    "\n",
    "print(somme(liste))    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maximum(liste):\n",
    "    \"\"\"\n",
    "    cette fonction renvoie le maximum de la liste\n",
    "    \"\"\"\n",
    "    m=liste[0]\n",
    "    for i in range(1,len(liste)):\n",
    "        if liste[i]>m:\n",
    "            m=liste[i]\n",
    "    return m\n",
    "\n",
    "print(maximum(liste))    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bien sûr les trois fonctions proposés ci-dessus peuvent être efficacemnt remplacées par les **built-ins** correspondantes, `in`, `sum`, `max`.\n",
    "Les trois fonctions sont des exemples d'accumulation (reduce) où on part d'un élément neutre (`False`, `0` et $-\\infty$ respectivement), puis on applique une opération `or`, `+` ou `max` sur la valeur actuelle de l'accumulateur et l'élément suivant de la liste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import inf\n",
    "\n",
    "def maximumAvecInfini(liste):\n",
    "    \"\"\"\n",
    "    fonction qui renvoie le maximum d'une liste en initialisant à -inf\n",
    "    \"\"\"\n",
    "    m=-inf\n",
    "    for e in liste:\n",
    "        if e>m:\n",
    "            m=e\n",
    "    return m\n",
    "\n",
    "print(maximumAvecInfini(liste))\n",
    "print(maximumAvecInfini([]))    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour les accumulations logiques on a respectivement `any` et `all` pour `or` et `and`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "help(any)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "help(all)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parcours récursif\n",
    "L'algorithme d'accumulation se prête particulièrement bien à une programmation récursive, avec une fonction qui s'appelle elle-même sauf sur le cas de base. On pourra utilement aller observer le déroulement pas-à-pas sur <a href=\"https://urlz.fr/eqYJ\">Python Tutor</a>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def occurenceRec(elt,liste):\n",
    "    if liste==[]:\n",
    "        return False\n",
    "    if liste[0]==elt:\n",
    "        return True\n",
    "    return occurenceRec(elt,liste[1:])\n",
    "\n",
    "def sommeRec(liste):\n",
    "    if liste==[]:\n",
    "        return 0\n",
    "    return liste[0]+sommeRec(liste[1:])\n",
    "\n",
    "from math import inf\n",
    "\n",
    "def maximumRec(liste):\n",
    "    if liste==[]:\n",
    "        return -inf\n",
    "    m=maximumRec(liste[1:])\n",
    "    return liste[0] if liste[0]>m else m\n",
    "\n",
    "print(occurenceRec(6,liste))\n",
    "print(occurenceRec(5,liste))\n",
    "\n",
    "print(sommeRec(liste))\n",
    "\n",
    "print(maximumRec(liste))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il arrive parfois qu'on veuille l'indice d'un élément dans une liste, p.ex l'indice de la première occurence (`find`), ou bien l'indice du maximum (pour le tri sélection typiquement)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def trouve(elt,liste):\n",
    "    \"\"\"\n",
    "    renvoie l'indice de la première occurence\n",
    "    renvoie -1 si l'élément n'est pas dans la liste\n",
    "    \"\"\"\n",
    "    for i,e in enumerate(liste):\n",
    "        if elt==e:\n",
    "            return(i)\n",
    "    return -1\n",
    "\n",
    "\n",
    "def indiceMaximum(liste):\n",
    "    \"\"\"\n",
    "    renvoie l'indice du maximum\n",
    "    et pas l'indice maximum (qui est len(liste)-1) !\n",
    "    \"\"\"\n",
    "    i,m=0,liste[0]\n",
    "    for j in range(1,len(liste)):\n",
    "        if liste[j]>m:\n",
    "            i,m=j,liste[j]\n",
    "    return m\n",
    "\n",
    "print(trouve('d','abracadabra'))\n",
    "print(trouve('e','abracadabra'))\n",
    "print(indiceMaximum('abracadabra'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q1.1** Compléter la fonction minimum esquissée ci-dessous."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimum(liste):\n",
    "    \"\"\"\n",
    "    renvoie le minimum d'une liste\n",
    "    >>> mimimum([10,5,13,4,9,11])\n",
    "    4\n",
    "    \"\"\"\n",
    "    # au début on prend comme minimum le premier élément\n",
    "    # pour chaque élément \n",
    "        # on vérifie s'il est plus petit que le minimum déjà trouvé\n",
    "            # auquel cas il devient le nouveau minimum\n",
    "    # on renvoie le minimum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q1.2** Compléter la fonction ci-dessous, qui doit renvoyer des effectifs cumulés croissants. On utlisera la méthode `append`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ECC(liste):\n",
    "    \"\"\"\n",
    "    >>> ECC([1,3,2,8,4,6,7,6])\n",
    "    [1,4,6,14,18,24,31,37]\n",
    "    \"\"\"\n",
    "    s=0\n",
    "    ecc=[]\n",
    "    # pour chaque élément de la liste\n",
    "        # le rajouter à s\n",
    "        # rajouter s à la fin de la liste ecc\n",
    "    # renvoyer ecc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q1.3** Compléter une fonction qui trouve la dernière occurence d'un élément dans une liste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evuort(elt,liste):\n",
    "    \"\"\"\n",
    "    >>> evuort(5,[3,5,6,7,8,5,9,4,1,5,3])\n",
    "    9\n",
    "    >>> evuort(2,[3,5,6,7,8,5,9,4,1,5,3])\n",
    "    -1\n",
    "    \"\"\"\n",
    "    return\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Benny l'escargot narcoleptique\n",
    "\n",
    "Benny est un escargot <a href=\"\">narcoleptique</a>, il est sujet à des endormissements soudains qui peuvent durer plusieurs minutes.\n",
    "\n",
    "C'est fort contrariant, car Benny essaie de se sortir d'un mauvais pas : il est tombé au fond d'un puits, et a besoin de rester éveillé suffisamment longtemps pour sortir du puits.\n",
    "\n",
    "Entre deux endormissements, Benny remonte de plusieurs cm, par contre à chaque fois qu'il s'endort il redescend d'une hauteur plus ou moins importante en fonction de la durée de son sommeil.\n",
    "\n",
    "**Un exemple**\n",
    "\n",
    "L'escargot a commencé par monter de 3 cm avant de s'endormir et de redescendre d'un centimètre, puis il est remonté de 4 cm, etc.\n",
    "`l=[3,-1,4,-2,5,-1,2,-3,5,-6,4,-3,1,-4]`\n",
    "\n",
    "**Quatre questions**\n",
    "\n",
    "**Q2.1** Quelle est la hauteur à laquelle arrive Benny après les déplacements codés dans la liste de l'exemple ?\n",
    "\n",
    "**Q2.2** Quelle est la distance totale parcourue par l'escargot ?\n",
    "\n",
    "**Q2.3** A quelle hauteur maximale est arrivé Benny ?\n",
    "\n",
    "**Q2.4** Benny est-il sorti du puits, dont la hauteur n'est que de 20 cm, et si oui au bout de combien de mouvements ?\n",
    "\n",
    "**Q2.5**\n",
    "On demande de compléter les quatre fonctions dont le prototype est donné ci-dessous. \n",
    "\n",
    "On a utilisé des `doc strings` entre triple guillemets, avec un exemple d'utilisation.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def position_finale(liste):\n",
    "    \"\"\"\n",
    "    La fonction position_finale renvoie la position de Benny\n",
    "    à la fin des déplacements.\n",
    "    L'argument est une liste de déplacements entiers relatifs.\n",
    "    \n",
    "    >>>position_finale([])\n",
    "    0\n",
    "    >>>position_finale([3,-1,4,-2,5,-1,2,-3,5,-6,4,-3,1,-4])\n",
    "    4\n",
    "    \"\"\"\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hauteur(liste):\n",
    "    \"\"\"\n",
    "    La fonction hauteur renvoie la hauteur maximale à laquelle \n",
    "    Benny l'escargot arrive.\n",
    "    Son argument est une liste de déplacements entiers relatifs.\n",
    "    \n",
    "    >>>hauteur([3,-1,4,-2,5,-1,2,-3,5,-6,4,-3,1,-4])\n",
    "    12\n",
    "    \"\"\"\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def temps(liste,profondeur):\n",
    "    \"\"\"\n",
    "    La fonction temps renvoie le temps mis par Benny pour\n",
    "    arriver à la hauteur donnée, ou None si Benny n'y arrive pas.\n",
    "    Son argument liste est une liste de déplacements entiers relatifs,\n",
    "    son argument profondeur est la hauteur à atteindre ou dépasser.\n",
    "    \n",
    "    >>>temps([3,-1,4,-2,5,-1,2,-3,5,-6,4,-3,1,-4],10)\n",
    "    7\n",
    "    >>>temps([3,-1,4,-2,5,-1,2,-3,5,-6,4,-3,1,-4],30)\n",
    "    None\n",
    "    \"\"\"\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(liste):\n",
    "    \"\"\"\n",
    "    La fonction distance renvoie la distance totale parcourue\n",
    "    par Benny.\n",
    "    Son argument est une liste de déplacements entiers relatifs.\n",
    "    \n",
    "    >>>distance([])\n",
    "    0\n",
    "    >>>distance([3,-1,4,-2,5,-1,2,-3,5,-6,4,-3,1,-4])\n",
    "    44\n",
    "    \"\"\"\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On exécutera les instructions ci-dessous pour tester les fonctions sur quelques exemples.\n",
    "On peut aussi utiliser la bibliothèque `doctest`, qui permet de vérifier que les cas d'usages contenus dans la `docstring` renvoient bien les valeurs indiquées."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert(position_finale([])==0)\n",
    "assert(position_finale([3,-1,4,-2,5,-1,2,-3,5,-6,4,-3,1,-4])==4)\n",
    "assert(hauteur([3,-1,4,-2,5,-1,2,-3,5,-6,4,-3,1,-4])==12)\n",
    "assert(temps([3,-1,4,-2,5,-1,2,-3,5,-6,4,-3,1,-4],10)==7)\n",
    "assert(temps([3,-1,4,-2,5,-1,2,-3,5,-6,4,-3,1,-4],30)==None)\n",
    "assert(distance([])==0)\n",
    "assert(distance([3,-1,4,-2,5,-1,2,-3,5,-6,4,-3,1,-4])==44)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parcours de dictionnaires\n",
    "Comme pour les listes, il y a trois façons de parcourir un dictionnaire :\n",
    "    * par clés\n",
    "    * par valeurs\n",
    "    * par items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d={'Nom':'Tournesol','Prénom':'Tryphon','Profession':'Radiesthésiste','Téléphone':'4242',\n",
    "   'Adresse':'Château de Moulinsart'}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for k in d.keys():\n",
    "    print(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for v in d.values():\n",
    "    print(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for k,v in d.items():\n",
    "    print(f\"la valeur associée à la clé {k} est {v}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parcours de listes de dictionnaires (données en table)\n",
    "Voici les 20 films les mieux notés sur la basse de données IMDb ; pour chacun on précisé le rang, le titre, l'année de réalisation, le nom du réalisateur, et la durée en minutes.\n",
    "On se propose de parcourir cette table (liste de dictionnaires qui représentent desp-uplets nommés) pour répondre à quelques questions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "top20imdb =[{'rang':1,'titre':\"Les évadés\",'année':1994,'réalisateur':'Frank Darabont','duree':142},\n",
    "            {'rang':2,'titre':\"Le parrain\",'année':1972,'réalisateur':'Francis Ford Coppola','duree':175},\n",
    "            {'rang':3,'titre':\"Le parrain deuxième partie\",'année':1974,'réalisateur':'Francis Ford Coppola','duree':202},\n",
    "            {'rang':4,'titre':\"The Dark Knight : le chevalier noir\",'année':2008,'réalisateur':'Christopher Nolan','duree':152},\n",
    "            {'rang':5,'titre':\"12 hommes en colère\",'année':1957,'réalisateur':'Sidney Lumet','duree':96},\n",
    "            {'rang':6,'titre':\"La liste de Schindler\",'année':1993,'réalisateur':'Steven Spielberg','duree':195},\n",
    "            {'rang':7,'titre':\"Le seigneur des anneaux : le Retour du Roi\",'année':2003,'réalisateur':'Peter Jackson','duree':201},\n",
    "            {'rang':8,'titre':\"Pulp fiction\",'année':1994,'réalisateur':'Quentin Tarantino','duree':154},\n",
    "            {'rang':9,'titre':\"Le bon, la brute, le truand\",'année':1966,'réalisateur':'Sergio Leone','duree':161},\n",
    "            {'rang':10,'titre':\"Le seigneur des anneaux : la Communauté de l'Anneau\",'année':2001,'réalisateur':'Peter Jackson','duree':178},\n",
    "            {'rang':11,'titre':\"Fight club\",'année':1999,'réalisateur':'David Fincher','duree':139},\n",
    "            {'rang':12,'titre':\"Forrest Gump\",'année':1994,'réalisateur':'Robert Zemeckis','duree':142},\n",
    "            {'rang':13,'titre':\"Inception\",'année':2010,'réalisateur':'Christopher Nolan','duree':148},\n",
    "            {'rang':14,'titre':\"Le seigneur des anneaux : les Deux Tours\",'année':2002,'réalisateur':'Peter Jackson','duree':179},\n",
    "            {'rang':15,'titre':\"L'empire contre attaque\",'année':1980,'réalisateur':'Irvin Kershner','duree':124},\n",
    "            {'rang':16,'titre':\"Matrix\",'année':1999,'réalisateur':'Les frères Warchawski','duree':136},\n",
    "            {'rang':17,'titre':\"Les affranchis\",'année':1990,'réalisateur':'Martin Scorcese','duree':146},\n",
    "            {'rang':18,'titre':\"Vol au-dessus d'un nid de coucou\",'année':1975,'réalisateur':'Milos Forman','duree':133},\n",
    "            {'rang':19,'titre':\"Les sept samouraïs\",'année':1954,'réalisateur':'Akira Kurosawa','duree':207},\n",
    "            {'rang':20,'titre':\"Seven\",'année':1995,'réalisateur':'David Fincher','duree':127}]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q3.1** Que renvoit la séquence ci-dessous ? Que signifie cette réponse ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t=0\n",
    "for d in top20imdb:\n",
    "    if d['année']>2000:\n",
    "        t=t+d['duree']\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q3.2** Compléter la fonction ci-dessous, qui renvoie la liste des titres des films qui durent plus d'un certain temps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def filmsLongs(duree):\n",
    "    liste=[]\n",
    "    for \n",
    "        if\n",
    "            liste.append()\n",
    "    return liste"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "print(filmsLongs(180))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Listes en compréhension\n",
    "\n",
    "On va utiliser ici la construction `[expr(k) for k in iterable if condition]` éventuellement en utilisant `len`, `sum` ou `max`.\n",
    "La même construction s'applique aux dictionnaires et aux tuples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum( d['duree'] for d in top20imdb if d['réalisateur']=='Peter Jackson')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "min(d['année'] for d in top20imdb if 'Akira' not in d['réalisateur'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len([d for d in top20imdb if d['réalisateur']=='David Fincher'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len([d for d in top20imdb if d['année']<2001])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len({d['réalisateur'] for d in top20imdb})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q3.3** Traduire chaque couple question-réponse ci-dessus en Français."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lecture de fichiers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le fichier boxo.csv contient les 100 plus gros succès au box-office en France. Nous allons lire ce fichier à l'aide de la bibliothèque `csv`, puis traiter les données obtenues."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import csv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('boxo.csv','r') as boxo:\n",
    "    table=[]\n",
    "    lecteur=csv.DictReader(boxo,delimiter=';')\n",
    "    for film in lecteur:\n",
    "        table.append(film)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "table[:3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q3.4** Donner la valeur et la signification des expressions suivantes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum(int(film['entrées']) for film in table[:10])/10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len([film for film in table[:42] if 'France' in film['pays']])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[film['titre'] for film in table if 'James' in film['réalisateur'] and int(film['entrées'])>10000000]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q3.5** Comparer le nombre moyen d'entrées des films français avec le nombre moyen d'entrées des films américains pour les films de ce top 100."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q3.6** Combien de films suisses sont présents dans ce top 100 ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Deux tris quadratiques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les algorithmes de tri \"naïfs\" vus en première sont **quadratiques** dans le pire des cas, ce qui signifie qu'un doublement du nombre d'élément à trier se traduit par un quadruplement du nombre de comparaisons effectuées pour le tri. Cette complexité est valable dans le pire des cas, en particulier le tri par inserion présenté ici est linéaire sur des données déjà triées.\n",
    "\n",
    "Les versions présentées ici sont de style impératif, et on trie des tableaux : les accès aux données se font par indice dans des tableaux de taille fixée, on utilise les listes Python comme des tableaux, on n'utilise ni `append` ni d'énumération par `for elt in liste`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def triSelection(tableau):\n",
    "    #pour chaque position du tableau en partant du début\n",
    "    #chercher le minimum du reste du tableau en partant de cette position\n",
    "    #placer ce minimum en tête en l'échangeant avec le premier élément"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def triInsertion(tableau):\n",
    "    #pour chaque élément du tableau\n",
    "    #l'insérer dans le début du tableau en l'échangeant avec l'élément précédent si celui-ci lui est supérieur"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q4.1** Ecrire la fonction `triSelection` à partir des indications données plus haut.\n",
    "\n",
    "**Q4.2** Donner un variant de boucle pour la boucle extérieure, et un invariant de boucle. Qu'est ce que cela permet de prouver ?\n",
    "\n",
    "**Q4.3** Calculer la complexité de la boucle intérieure puis celle de la boucle extérieure, en nombre de comparaison. Est-ce que cette complexité dépend des données ?\n",
    "\n",
    "**Q4.4** Mêmes questions pour la fonction `triInsertion`.\n",
    "\n",
    "**Q4.5** Montrer que la complexité de la boucle intérieure dépend des données qu'on trie. Qule est le meilleur cas ? Le pire cas ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def triSelection(l):\n",
    "    for i in range(len(l)):\n",
    "        j,m=i,l[i]\n",
    "        for k in range(j+1,len(l)):\n",
    "            if l[k]<m:\n",
    "                j,m=k,l[k]\n",
    "        l[i],l[j]=l[j],l[i]\n",
    "\n",
    "liste=[80,76,14,50,35,22,29,56,44]\n",
    "triSelection(liste)  #tri en place, comme la méthode .sort(), paradigme impératif\n",
    "print(liste)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def triInsertion(l):\n",
    "    for i in range(len(l)):\n",
    "        j=i\n",
    "        while j>0 and l[j-1]>l[j]:\n",
    "            l[j-1],l[j]=l[j],l[j-1]\n",
    "            j=j-1\n",
    "\n",
    "liste=[80,76,14,50,35,22,29,56,44]\n",
    "triInsertion(liste)  #tri en place, comme la méthode .sort(), paradigme impératif\n",
    "print(liste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On pourra consulter le déroulement des deux fonctions sur <a href=\"https://pythontutor.com\">Python Tutor</a> (un site indispensable) :\n",
    "<a href=\"http://pythontutor.com/visualize.html#code=def%20triSelection%28l%29%3A%0A%20%20%20%20for%20i%20in%20range%28len%28l%29%29%3A%0A%20%20%20%20%20%20%20%20j,m%3Di,l%5Bi%5D%0A%20%20%20%20%20%20%20%20for%20k%20in%20range%28j%2B1,len%28l%29%29%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20l%5Bk%5D%3Cm%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20j,m%3Dk,l%5Bk%5D%0A%20%20%20%20%20%20%20%20l%5Bi%5D,l%5Bj%5D%3Dl%5Bj%5D,l%5Bi%5D%0A%0Aliste%3D%5B80,76,14,50,35,22,29,56,44%5D%0AtriSelection%28liste%29%20%20%23tri%20en%20place,%20comme%20sorted%28%29,%20paradigme%20imp%C3%A9ratif%0Aprint%28liste%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false\">tri sélection</a> et <a href=\"http://pythontutor.com/visualize.html#code=def%20triInsertion%28l%29%3A%0A%20%20%20%20for%20i%20in%20range%28len%28l%29%29%3A%0A%20%20%20%20%20%20%20%20j%3Di%0A%20%20%20%20%20%20%20%20while%20j%3E0%20and%20l%5Bj-1%5D%3El%5Bj%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20l%5Bj-1%5D,l%5Bj%5D%3Dl%5Bj%5D,l%5Bj-1%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20j%3Dj-1%0A%0Aliste%3D%5B80,76,14,50,35,22,29,56,44%5D%0AtriInsertion%28liste%29%20%20%23tri%20en%20place,%20comme%20sorted%28%29,%20paradigme%20imp%C3%A9ratif%0Aprint%28liste%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false\">tri insertion</a>.\n",
    "\n",
    "Ci-dessous on utilise le magic `%%timeit` pour chronométrer nos deux fonctions sur quelques listes générées aléatoirement ; attention on doit recopier les listes avant de les trier, sinon à partir de la deuxième tentative on trie un eliste déjà triée. On constatera que la recopie prend un temps négligeable devant le tri."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "liste=[randint(1,10000) for k in range(1000)]\n",
    "liste[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "l=liste[:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "l=liste[:]\n",
    "triSelection(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "l=liste[:]\n",
    "triInsertion(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "listetriee=list(range(1000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "l=listetriee[:]\n",
    "triInsertion(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Les $k$ plus proches voisins\n",
    "Le fichier `communes.csv` contient les coordonnées et les noms des communes bas-normandes et de deux départements voisins.\n",
    "\n",
    "Nous écrivons une fonction qui va parcourir la liste de ces communes et ne garder que les $k$ communes les plus proches d'un point donné.\n",
    "\n",
    "Nous effectuons ensuite un vote majoritaire pour proposer le département dans lequel doit se trouver le point proposé."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import pi,cos,sin,acos\n",
    "\n",
    "def distance(pos1,pos2):\n",
    "    lat1=pos1[0]/180*pi\n",
    "    long1=pos1[1]/180*pi\n",
    "    lat2=pos2[0]/180*pi\n",
    "    long2=pos2[1]/180*pi\n",
    "    alpha=acos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(long1-long2))\n",
    "    return 6378137*alpha\n",
    "\n",
    "def trie(liste):\n",
    "    i=len(liste)-1\n",
    "    while i>0 and liste[i-1]>liste[i]:\n",
    "        liste[i-1],liste[i]=liste[i],liste[i-1]\n",
    "        i=i-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def knn(lat0,long0,k=7):\n",
    "    with open('communes.csv','r') as comm:\n",
    "        champs=['nom','code','dpt','lat','long','alt','superficie','population','geometrie']\n",
    "        reader=csv.DictReader(comm,fieldnames=champs,delimiter=\";\")\n",
    "        nn=[]\n",
    "        for commune in reader:\n",
    "            lat,long=float(commune['lat']),float(commune['long'])\n",
    "            d=distance((lat0,long0),(lat,long))\n",
    "            if len(nn)<k:\n",
    "                nn.append((d,commune['nom'],commune['dpt']))\n",
    "                trie(nn)\n",
    "            elif d<nn[k-1][0]:\n",
    "                nn[k-1]=(d,commune['nom'],commune['dpt'])\n",
    "                trie(nn)\n",
    "    return nn\n",
    "\n",
    "knn(48.8512,-0.8896)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compte(liste):\n",
    "    candidats=dict()\n",
    "    for i,t in enumerate(liste):\n",
    "        if t[2] not in candidats:\n",
    "            candidats[t[2]]=(1,1/(1+t[0]))\n",
    "        else:\n",
    "            candidats[t[2]]=(candidats[t[2]][0]+1,candidats[t[2]][1]+1/(1+t[0]))\n",
    "    cc=[(c[0],c[1],c) for c in candidats.keys()]\n",
    "    cc.sort()\n",
    "    return cc[-1][2]\n",
    "\n",
    "compte(knn(48.8512,-0.8896,10))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "knn(48.6361,-1.5114,7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Lison=knn(49.2414,-1.0381,30)\n",
    "for d,v,dpt in Lison:\n",
    "    print(f\"distance {d} de {v} qui est dans le département {dpt}\")\n",
    "print('Conclusion de 30-nn : département ',compte(Lison))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fusionner deux listes : le tri fusion\n",
    "Le tri fusion est un exemple canonique de la méthode diviser pour régner. Il s'agit de trier chaque moitié d'une liste puis de fusionner les deux listes triées en une seule liste, triée elle aussi. \n",
    "\n",
    "La version proposée ci-dessous est **récursive**, avec une approche fonctionnelle comme `sorted()`, sans effet de bord : la liste initiale n'est pas modifiée.\n",
    "\n",
    "On peut visualiser le déroulement de la fonction `fusion` sur l'exemple <a href=\"http://pythontutor.com/visualize.html#code=def%20fusion%28l1,l2%29%3A%0A%20%20%20%20if%20l1%3D%3D%5B%5D%3A%0A%20%20%20%20%20%20%20%20return%20l2%0A%20%20%20%20if%20l2%3D%3D%5B%5D%3A%0A%20%20%20%20%20%20%20%20return%20l1%0A%20%20%20%20if%20l1%5B0%5D%3Cl2%5B0%5D%3A%0A%20%20%20%20%20%20%20%20return%20%5Bl1%5B0%5D%5D%2Bfusion%28l1%5B1%3A%5D,l2%29%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20return%20%5Bl2%5B0%5D%5D%2Bfusion%28l1,l2%5B1%3A%5D%29%0A%0Al1%3D%5B22,29,35,44,56%5D%0Al2%3D%5B14,27,50,61,76%5D%0Aprint%28fusion%28l1,l2%29%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false\">ici</a>, et le tri complet <a href=\"http://pythontutor.com/visualize.html#code=def%20triFusion%28l%29%3A%0A%20%20%20%20if%20len%28l%29%3C2%3A%0A%20%20%20%20%20%20%20%20return%20l%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20return%20fusion%28triFusion%28l%5B%3Alen%28l%29//2%5D%29,triFusion%28l%5Blen%28l%29//2%3A%5D%29%29%0A%0Al%3D%5B80,76,14,50,35,22,29,56,44%5D%0Aprint%28triFusion%28l%29%29%0Aprint%28l%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false\">là</a>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fusion(l1,l2):\n",
    "    if l1==[]:\n",
    "        return l2\n",
    "    if l2==[]:\n",
    "        return l1\n",
    "    if l1[0]<l2[0]:\n",
    "        return [l1[0]]+fusion(l1[1:],l2)\n",
    "    else:\n",
    "        return [l2[0]]+fusion(l1,l2[1:])\n",
    "\n",
    "l1=[22,29,35,44,56]\n",
    "l2=[14,27,50,61,76]\n",
    "print(fusion(l1,l2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def triFusion(liste):\n",
    "    #si la liste est de longueur 0 ou 1, elle est déjà tiée\n",
    "    #sinon trier récursivement la première moitié, puis la deuxième moitié\n",
    "    #et renvoyer la fusion de ces deux moitiés triées"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q4.6** Compléter la fonction `triFusion` en utilisant la fonction `fusion`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def triFusion(l):\n",
    "    if len(l)<2:\n",
    "        return l\n",
    "    else:\n",
    "        return fusion(triFusion(l[:len(l)//2]),triFusion(l[len(l)//2:]))\n",
    "\n",
    "l=[80,76,14,50,35,22,29,56,44]\n",
    "print(triFusion(l))\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parcourir une liste pour la partitionner : le tri rapide\n",
    "L'idée du tri rapide est de choisir un élément de la liste à trier appelé le **pivot**, et de trier séparément la liste des éléments plus petits que le pivot et la liste des éléments plus grands que le pivot.\n",
    "\n",
    "Comme le tri fusion, c'est un exemple canaonique de l'approche diviser pour régner ; contrairement au tri pivot, la division du problème ne se fait pas nécessairement en deux parties (presque) égales, et le tri rapide peut être quadratique dans des cas comme celui d'une liste déjà triée.\n",
    "\n",
    "On propose ci-dessous deux implémentations assez différentes :\n",
    "* la première est fonctionnelle et traduit directement l'idée du tri rapide\n",
    "* la deuxième est impérative, en place (elle ne crée pas de nouvelles structures de données mais travaille dans le tableau initial).\n",
    "\n",
    "Cependant les deux fonctions proposées sont récursives."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def triRapideFonctionnel(liste):\n",
    "    if len(liste)<2:\n",
    "        return liste\n",
    "    else:\n",
    "        return triRapideFonctionnel([k for k in liste[1:] if k<liste[0]])+\\\n",
    "        [liste[0]]+triRapideFonctionnel([k for k in liste[1:] if k>=liste[0]]) #le \\ casse une ligne trop longue\n",
    "\n",
    "liste=[80,76,14,50,35,22,29,56,44]\n",
    "print(triRapideFonctionnel(liste))\n",
    "print(liste)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partitionne(tableau,debut,fin):\n",
    "    j=debut\n",
    "    for i in range(debut,fin):\n",
    "        if tableau[i]<=tableau[fin]:\n",
    "            tableau[i],tableau[j]=tableau[j],tableau[i]\n",
    "            j=j+1\n",
    "    tableau[j],tableau[fin]=tableau[fin],tableau[j]\n",
    "    return j\n",
    "\n",
    "def triRapideImperatif(tableau,debut=0,fin=None):\n",
    "    if fin is None:\n",
    "        fin=len(liste)-1\n",
    "    if debut<fin:\n",
    "        k=partitionne(tableau,debut,fin)\n",
    "        triRapideImperatif(tableau,debut,k-1)\n",
    "        triRapideImperatif(tableau,k+1,fin)\n",
    "        \n",
    "liste=[80,76,14,50,35,22,29,56,44]\n",
    "print(triRapideImperatif(liste))\n",
    "print(liste) #il s'agit d'un tri en place      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mélanger une liste\n",
    "**Q4.7** De quel tri cet algorithme est-il l'inverse ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "#randint(a,b) renvoit un entier entre a et b inclus\n",
    "\n",
    "def knuth(l):\n",
    "    n=len(l)\n",
    "    for i in range(n-1):\n",
    "        j=randint(i,n-1)\n",
    "        l[i],l[j]=l[j],l[i]\n",
    "\n",
    "liste=list(range(1,21))\n",
    "print(liste)\n",
    "knuth(liste)\n",
    "print(liste)\n",
    "knuth(liste)\n",
    "print(liste)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parcours logarithmique : diviser pour régner\n",
    "On peut grandement améliorer le coût d'une recherche d'un élément dans un tableau si ce tableau a été préalablement trié. En comparant la valeur recherchée à la valeur présente au milieu du tableau, si ces deux valeurs ne sont pas égales on sait dans quelle moitié chercher."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q5.1** Compléter la fonction `rechercheDicho` ci-dessous, en prêtant attention aux cas de base."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rechercheDicho(elt,liste):\n",
    "    #si la liste est vide ...\n",
    "    #si elt est égal au terme médian de la liste ...\n",
    "    #sinon en comparant elt à ce terme median faire un appel récursif"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "l=[14,22,29,35,44,50,56,76,80]\n",
    "print(rechercheDicho(61,liste))\n",
    "print(rechercheDicho(22,liste))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une proposition est au bout de ce <a href=\"hhttp://pythontutor.com/visualize.html#code=def%20rechercheDicho%28elt,liste%29%3A%0A%20%20%20%20if%20liste%3D%3D%5B%5D%3A%0A%20%20%20%20%20%20%20%20return%20False%0A%20%20%20%20m%3Dlen%28liste%29//2%0A%20%20%20%20if%20elt%3D%3Dliste%5Bm%5D%3A%0A%20%20%20%20%20%20%20%20return%20True%0A%20%20%20%20elif%20elt%3Cliste%5Bm%5D%3A%0A%20%20%20%20%20%20%20%20return%20rechercheDicho%28elt,liste%5B%3Am%5D%29%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20return%20rechercheDicho%28elt,liste%5Bm%2B1%3A%5D%29%0A%0A%0Al%3D%5B14,22,29,35,44,50,56,76,80%5D%0Aprint%28rechercheDicho%2861,l%29%29%0Aprint%28rechercheDicho%2822,l%29%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false\">lien</a>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}