{
 "metadata": {
  "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.7.3-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python37364bit201329ed7ee849b4a43ad7bb610f5989",
   "display_name": "Python 3.7.3 64-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "source": [
    "# ALGORITHMIQUE : RECHERCHE DANS UN TABLEAU\n",
    "\n",
    "Ce notebook accompagne le cours d'algorithmique de 1ère NSI\n",
    "\n",
    "## 1- RECHERCHE D'OCCURRENCE(S) DANS UN TABLEAU NON TRIÉ :\n",
    "\n",
    "### 1.1- Recherche de la première occurrence d'un élément :\n",
    "\n",
    "L'algorithme de cette recherche est décrit de façon visuelle dans le diaporama \"diaporama_algo_occurrence.odp\" (à ouvrir avec LibreOffice)\n",
    "\n",
    "Compléter la fonction cherche(valeur, tableau) en remplaçant les ??? par le code qui convient\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def cherche(valeur, tableau):\n",
    "    \"\"\" fonction qui recherche la première occurrence de 'valeur' dans 'tableau'\n",
    "    :param valeur: (any) la valeur à rechercher dans le tableau\n",
    "    :param tableau: (list) tableau à scruter\n",
    "    :return: (int) l'indice de la première occurrence trouvée pour 'valeur' ; si pas trouvée : -1\n",
    "    Exemples :\n",
    "    >>> cherche(3, [4, 5, 3, 2])\n",
    "    2\n",
    "    >>> cherche(8, [4, 5, 3, 2])\n",
    "    -1\n",
    "    >>> cherche(5, [4, 5, 3, 5, 2])\n",
    "    1\n",
    "    \"\"\"\n",
    "    for i in range(???):\n",
    "        if ??? == ???:      # si on trouve l'élément recherché\n",
    "            return ???\n",
    "    return -1\n",
    "\n",
    "# tests de la fonction : on réalisera des tests correspondants aux différents cas de figure possible\n",
    "# avec la liste tab ci-dessous :\n",
    "tab = [9, 13, 4, 12, 7, 13, 18, 3, 7, 10, 14, 7, 2]\n",
    "\n",
    "# faire rechercher un élément qui existe dans tab :\n",
    "print(???)\n",
    "\n",
    "# faire rechercher un élément qui existe aux extrémités de tab (cela permet de vérifier que\n",
    "# notre fonction est capable de travailler sur TOUTE la longueur du tableau)\n",
    "print(???)\n",
    "print(???)\n",
    "\n",
    "# faire rechercher un élément qui n'existe pas dans le tableau :\n",
    "print(???)\n",
    "\n",
    "# faire rechercher un élément qui possède plusieurs occurrences dans le tableau et vérifier\n",
    "# que notre fonction renvoie bien l'indice de la PREMIÈRE occurrence trouvée :\n",
    "print(???)\n",
    "\n",
    "# tests de la fonction avec une listee de chaînes de caractères :\n",
    "animaux = ['chien','chat', 'oiseau', 'poisson', 'mouche', 'chat', 'chat', 'poisson', 'scarabée','ver']\n",
    "print(???)\n",
    "print(???)\n"
   ]
  },
  {
   "source": [
    "### 1.2- Recherche du nombre d'occurrences d'un élément dans un tableau :\n",
    "\n",
    "On souhaite maintenant repérer TOUTES les occurrences d'un élément dans un tableau.\n",
    "Comme il peut y avoir plusieurs occurrences on doit donc envisager de stocker dans une structure de données, tous les indices trouvés. On choisit de les stocker dans une liste. \n",
    "\n",
    "Ecrire la fonction cherche_occurrences(valeur, tableau) qui répond à ce cahier des charges :\n",
    "\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cherche_occurrences(valeur, tableau):\n",
    "    \"\"\" fonction qui recherche toutes les  occurrence de 'valeur' dans 'tableau'\n",
    "    :param valeur: (any) la valeur à rechercher dans le tableau\n",
    "    :param tableau: (list) tableau à scruter\n",
    "    :return: (list) une liste donnant les indices de chacune des occurrences trouvées pour 'valeur' ; si pas trouvée renvoie une liste vide []\n",
    "    Exemples :\n",
    "    >>> cherche(3, [4, 5, 3, 2])\n",
    "    [2]\n",
    "    >>> cherche(8, [4, 5, 3, 2])\n",
    "    []\n",
    "    >>> cherche(5, [4, 5, 3, 5, 2, 5])\n",
    "    [1, 3, 5]\n",
    "    \"\"\"\n",
    "    result = []         # liste provisoire pour récupérer les indices des différentes occurrences\n",
    "    for i in range(???):\n",
    "        if tableau[???] == ???:\n",
    "            result.???          # à chaque fois que l'on trouve l'élément, on ajoute\n",
    "                                # son indice dans la liste provisoire 'result'\n",
    "    return result\n",
    "\n",
    "# la liste de nombres 'tab' ci-dessous contient des éléments ayant des doublons :\n",
    "tab = [9, 13, 4, 12, 7, 13, 18, 3, 7, 10, 14, 7, 2]\n",
    "\n",
    "# tester la fonction sur des éléments en doublon ou pas :\n",
    "print(???)\n",
    "print(???)\n",
    "print(???)\n",
    "\n",
    "# utilisation dans une liste de chaîne de caractères :\n",
    "animaux = ['chien','chat', 'oiseau', 'poisson', 'mouche', 'chat', 'chat', 'poisson', 'scarabée','ver']\n",
    "print(???)\n",
    "print(???)"
   ]
  },
  {
   "source": [
    "### 1.3- Application : \"nettoyage\" de données\n",
    "\n",
    "On souhaite nettoyer une liste de tous les doublons qu'elle comporte de façon à n'avoir dedans que des éléments uniques.\n",
    "\n",
    "On souhaite donc disposer d'une fonction **nettoyer(tableau)** qui va rechercher tous les doublons présents dans une liste pour les en extraire.\n",
    "\n",
    "Une liste comme : \n",
    "\n",
    "**tab = \\[9, 13, 4, 12, 7, 13, 18, 3, 7, 10, 14, 7, 2]**\n",
    "\n",
    "deviendra après application de **nettoyer(tab)**:\n",
    "\n",
    "**tab = \\[9, 13, 4, 12, 7, 18, 3, 10, 14, 2]**\n",
    "\n",
    "ou bien la liste :\n",
    "\n",
    "**animaux = \\['chien','chat', 'oiseau', 'poisson', 'mouche', 'chat', 'chat', 'poisson', 'scarabée','ver']**\n",
    "\n",
    "deviendra :\n",
    "\n",
    "**animaux = \\['chien','chat', 'oiseau', 'poisson', 'mouche', 'scarabée','ver']**\n",
    "\n",
    "Remarque : Pour écrire le code de cette fonction, on pourra avoir besoin d'utiliser :\n",
    "\n",
    " - la fonction recherche_occurrences(val, tableau) écrite précédemment \n",
    " - la méthode pop()\n",
    " - l'instruction del   (voir le cours sur les listes)\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nettoyer(tableau):\n",
    "    \"\"\" fonction qui élimine les doublons dans un tableau\n",
    "    :param tableau: (list) le tableau à nettoyer\n",
    "    :return: (list) le tableau initial débarassé de ses doublons\n",
    "    :side effect: modifie le tableau passé en argument\n",
    "    Exemple:\n",
    "    >>> tab = [9, 13, 4, 12, 7, 13, 18, 3, 7, 10, 14, 7, 2]\n",
    "    >>> nettoyer(tab)\n",
    "    >>> print(tab)\n",
    "    >>> tab = [9, 13, 4, 12, 7, 18, 3, 10, 14, 2]\n",
    "    \"\"\"\n",
    "    # tout le code de cette fonction est à rédiger :\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    return tableau\n",
    "\n",
    "# test de la fonction sur une liste de nombres :\n",
    "tab = [9, 13, 4, 12, 7, 13, 18, 3, 7, 10, 14, 7, 2]\n",
    "nettoyer(tab)\n",
    "print(tab)\n",
    "\n",
    "# test de la fonction sur une liste de mots :\n",
    "animaux = ['chien','chat', 'oiseau', 'poisson', 'mouche', 'chat', 'chat', 'poisson', 'scarabée','ver']\n",
    "nettoyer(animaux)\n",
    "print(animaux)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "source": [
    "## 2- Recherche d'extremum dans un tableau non trié\n",
    "\n",
    "### 2.1- Recherche d'un maximum dans un tableau non trié\n",
    "\n",
    "Prenons cette liste Python:\n",
    "\n",
    "\\>>> tab = \\[9, 4, 12, 7, 13, 18, 3, 10, 14, 2]\n",
    "\n",
    "Avec le langage Python, il serait très simple de trouver la valeur maximum dans cette liste :\n",
    "\n",
    "\\>>> max(tab)\n",
    "\n",
    "\\>>> 18\n",
    "\n",
    "... mais en fait on souhaite écrire un algorithme de recherche du maximum. Un tel algorithme pourrait ensuite être implémenté dans un langage de programmation quelconque (pour nous ce sera ici Python qui est le seul langage que l'on a étudié).\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cherche_maxi(tableau):\n",
    "    \"\"\" fonction qui cherche la valeur maximum dans un tableau\n",
    "    :param tableau: (list) le tableau à scruter\n",
    "    :return: (any) la valeur maximum trouvée dans 'tableau'\n",
    "    Exemple:\n",
    "    >>> tab = [9, 4, 12, 7, 13, 18, 3, 10, 14, 2]\n",
    "    >>> cherche_maxi(tab)\n",
    "    >>> 18\n",
    "    \"\"\"\n",
    "    i_max = 0\n",
    "    for i in range(???, len(tableau)):\n",
    "        if ??? > tableau[i_max]:\n",
    "            i_max = ???\n",
    "    return ???\n",
    "\n",
    "tab = [9, 4, 12, 7, 13, 18, 3, 10, 14, 2]\n",
    "print(cherche_maxi(tab))\n"
   ]
  },
  {
   "source": [
    "## 2.2- Recherche d'un minimum dans un tableau non trié :\n",
    "\n",
    "On peut aussi vouloir trouver la valeur minimum dans un tableau :\n",
    "\n",
    "Reprenons cette liste Python:\n",
    "\n",
    "\\>>> tab = \\[9, 4, 12, 7, 13, 18, 3, 10, 14, 2]\n",
    "\n",
    "Après avoir écrit le code d'une fonction **cherche_mini(tableau)** son application sur la liste tab donnerait :\n",
    "\n",
    "\\>>> cherche_mini(tab)\n",
    "\\>>> 2\n",
    "\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cherche_mini(tableau):\n",
    "    \"\"\" fonction qui cherche la valeur minimum dans un tableau\n",
    "    :param tableau: (list) le tableau à scruter\n",
    "    :return: (any) la valeur miniimum trouvée dans 'tableau'\n",
    "    Exemple:\n",
    "    >>> tab = [9, 4, 12, 7, 13, 18, 3, 10, 14, 2]\n",
    "    >>> cherche_mini(tab)\n",
    "    >>> 2\n",
    "    \"\"\"\n",
    "    # Le code de cette fonction doit pouvoir se déduire facilement de celui de la recherche du maximum !\n",
    "\n",
    "tab = [9, 4, 12, 7, 13, 18, 3, 10, 14, 2]\n",
    "print(cherche_mini(tab))"
   ]
  },
  {
   "source": [
    "## 2.3- Recherche du min-max dans un tableau\n",
    "\n",
    "Il s'agit maintenant d'écrire une fonction qui renvoie un tuple constitué de la valeur minimum et de la valeur maximum trouvées dans un tableau\n",
    "\n",
    "\\>>> tab = \\[9, 4, 12, 7, 13, 18, 3, 10, 14, 2]\n",
    "\n",
    "Après avoir écrit le code d'une fonction **minmax(tableau)** son application sur la liste tab donnerait :\n",
    "\n",
    "\\>>> minmax(tab)\n",
    "\n",
    "\\>>> (2, 18)\n",
    "\n",
    "Ecrire ci-dessous la fonction minmax(tableau) :\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minmax(tableau):\n",
    "    \"\"\" fonction qui recherche la valeur minimum et la valeur maximum d'un tableau\n",
    "    :param tableau: (list) le tableau à scruter\n",
    "    :return: (tuple) un tuple (valeur mini, valeur maxi)\n",
    "    Exemples:\n",
    "    >>> tab = [9, 4, 12, 7, 13, 18, 3, 10, 14, 2]\n",
    "    >>> minmax(tab)\n",
    "    >>> (2, 18)\n",
    "    \"\"\"\n",
    "    # une seule ligne de code pour cette fonction :\n",
    "    return ???, ???\n",
    "\n",
    "tab = [9, 4, 12, 7, 13, 18, 3, 10, 14, 2]\n",
    "print(minmax(tab))\n"
   ]
  },
  {
   "source": [
    "## 2.4- Application : Donald veut suivre la scolarité de ses neveux\n",
    "\n",
    "![image : donald.png](images/donald.jpg)\n",
    "\n",
    "Donald a décidé de suivre la scolarité de ses trois neveux : Fifi, Riri et Loulou.\n",
    "Il a créé une liste contenant les intitulés des différentes matières et une liste des notes correspondantes pour chacun des neveux.\n",
    "\n",
    "matieres = \\['Math', 'Français', 'NSI', 'Hist-Géo', 'Anglais', 'Pêche']\n",
    "\n",
    "Riri = \\[12, 14, 17, 8,15,7]\n",
    "\n",
    "Fifi = \\[7, 11, 10, 12, 9, 15]\n",
    "\n",
    "Loulou = \\[17, 8, 15, 13, 11, 13]\n",
    "\n",
    "Ecrire une fonction **meilleure_note(eleve)** qui renvoie pour un élève un tuple donnant la meilleure note qu'il a obtenue et la matière correspondante.\n",
    "\n",
    "Par exemple, l'application de cette fonction sur Riri donnera : ('NSI', 17)\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "def meilleure_note(eleve):\n",
    "    \"\"\" fonction qui recherche la meilleur note obtenue par un élève et en précise la matière\n",
    "    :param eleve: (list) le tableau des notes obtenues par l'élève\n",
    "    :return: (tuple) : (matière, meilleure note)\n",
    "    Exemlple :\n",
    "    >>> Riri = [12, 14, 17, 8,15,7]\n",
    "    >>> meilleure_note(Riri)\n",
    "    >>> ('NSI', 17)\n",
    "    \"\"\"\n",
    "    matieres = ['Math', 'Français', 'NSI', 'Hist-Géo', 'Anglais', 'Pêche']\n",
    "    note_maxi = ???\n",
    "    # pour écrire la dernière ligne de code : c'est l'indice de la meilleure note obtenue\n",
    "    # qui permet d'associer la matière correspondante :\n",
    "    return matieres[???], ???\n",
    "\n",
    "# Application de la fonction aux résultats de Riri, Fifi et Loulou :\n",
    "Riri = [12, 14, 17, 8,15,7]\n",
    "\n",
    "Fifi = [7, 11, 10, 12, 9, 15]\n",
    "\n",
    "Loulou = [17, 8, 15, 13, 11, 13]\n",
    "\n",
    "print('Riri : ', meilleure_note(Riri))\n",
    "print('Fifi : ', meilleure_note(Fifi))\n",
    "print('Loulou : ', meilleure_note(Loulou))"
   ]
  }
 ]
}