{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "46bf4ba0",
   "metadata": {},
   "source": [
    "# TP : La Récursivité et le Diviser pour Régner\n",
    "\n",
    "## Objectifs :\n",
    "- Comprendre le principe de la récursivité.\n",
    "- Appliquer la récursivité pour résoudre des problèmes simples.\n",
    "- Approfondir la méthode du **diviser pour régner** à travers des exemples concrets.\n",
    "- Compléter un algorithme de **tri fusion**.\n",
    "\n",
    "### Rappel sur la récursivité :\n",
    "La récursivité est une méthode où une fonction s'appelle elle-même pour résoudre un problème. Chaque appel de la fonction permet de simplifier le problème jusqu'à atteindre une condition de base (appelée **cas de base**) qui permet de terminer la récursion.\n",
    "\n",
    "**Exemple classique :** Calcul de la factorielle d'un nombre entier positif `n`.\n",
    "```python\n",
    "def factorielle(n):\n",
    "    if n == 0:\n",
    "        return 1  # Cas de base\n",
    "    else:\n",
    "        return n * factorielle(n-1)  # Appel récursif\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab363a2d",
   "metadata": {},
   "source": [
    "### Exercice 1 : Fonction récursive `traduire_romain`\n",
    "**But :** Écrire une fonction récursive `traduire_romain` qui prend en paramètre une chaîne de caractères non vide représentant un nombre écrit en chiffres romains, et qui renvoie son écriture décimale.\n",
    "\n",
    "**Consignes :**\n",
    "- Chaque chiffre romain a une valeur : `I=1, V=5, X=10, L=50, C=100, D=500, M=1000`.\n",
    "- Si un chiffre plus petit précède un chiffre plus grand (ex : IV), cela signifie qu'il faut soustraire la valeur du chiffre plus petit.\n",
    "  \n",
    "**Exemple :**\n",
    "```python\n",
    "traduire_romain(\"IX\")  # Renvoie 9\n",
    "traduire_romain(\"MCMXCIV\")  # Renvoie 1994\n",
    "```\n",
    "\n",
    "**Indication :** Utilisez la récursion pour traiter un caractère à la fois, et soustrayez ou ajoutez en fonction de la position relative des caractères.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8e5b99eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Commencez à écrire la fonction traduire_romain ici :\n",
    "def traduire_romain(chaine):\n",
    "    pass\n",
    "\n",
    "# Exemple de test\n",
    "print(traduire_romain(\"IX\"))  # Doit afficher 9\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24c596a6",
   "metadata": {},
   "source": [
    "### Exercice 2 : Compléter un Tri Fusion\n",
    "**But :** Compléter l'algorithme du tri fusion.\n",
    "\n",
    "Le tri fusion est un exemple typique de la méthode de **diviser pour régner**. L'idée est de diviser le tableau en deux, de trier chaque moitié, puis de fusionner les deux moitiés triées.\n",
    "\n",
    "Voici un code partiellement écrit que vous devez compléter :\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4672ddfc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def tri_fusion(tab):\n",
    "    if len(tab) <= 1:\n",
    "        return tab  # Cas de base\n",
    "    milieu = len(tab) // 2\n",
    "    gauche = tri_fusion(tab[:milieu])  # Appel récursif\n",
    "    droite = tri_fusion(tab[milieu:])  # Appel récursif\n",
    "    return fusionner(gauche, droite)\n",
    "\n",
    "def fusionner(gauche, droite):\n",
    "    tableau_fusionne = []\n",
    "    i, j = 0, 0\n",
    "    # Complétez la fonction pour fusionner les deux sous-tableaux ici :\n",
    "    # ---------------------------------------------\n",
    "\n",
    "    # ---------------------------------------------\n",
    "    # Ajoutez ici les éléments restants des sous-tableaux\n",
    "    tableau_fusionne ...\n",
    "    tableau_fusionne ...\n",
    "    return tableau_fusionne\n",
    "\n",
    "# Test de la fonction tri_fusion\n",
    "print(tri_fusion([38, 27, 43, 3, 9, 82, 10]))  # Doit afficher une liste triée\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a42b282",
   "metadata": {},
   "source": [
    "### Exercice 3 : Diviser pour Régner — Recherche d'un élément dans un tableau\n",
    "**But :** Implémenter la recherche d'un élément dans un tableau trié en utilisant la méthode de **diviser pour régner** (recherche dichotomique).\n",
    "\n",
    "La recherche dichotomique consiste à diviser le tableau en deux parties à chaque étape :\n",
    "- Si l'élément recherché est au milieu, vous avez terminé.\n",
    "- Si l'élément est plus petit que l'élément du milieu, il se trouve dans la première moitié du tableau.\n",
    "- Sinon, il se trouve dans la deuxième moitié.\n",
    "\n",
    "Voici un squelette à compléter :\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b4ced24d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def recherche_dichotomique(tab, element, debut=0, fin=None):\n",
    "    if fin is None:\n",
    "        fin = len(tab) - 1\n",
    "    if debut > fin:\n",
    "        return -1  # L'élément n'est pas dans le tableau\n",
    "    milieu = ...\n",
    "    if tab[milieu] == element:\n",
    "        return ...  # L'élément est trouvé\n",
    "    # Complétez ici avec les appels récursifs manquants :\n",
    "    # --------------------------------------------------\n",
    "    \n",
    "    # --------------------------------------------------\n",
    "    \n",
    "# Test de la fonction\n",
    "tab = [3, 9, 10, 27, 38, 43, 82]\n",
    "element = 27\n",
    "print(recherche_dichotomique(tab, element))  # Doit afficher l'index de l'élément trouvé\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b7d4ec9",
   "metadata": {},
   "source": [
    "### Exercice 4 : "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6669740",
   "metadata": {},
   "source": [
    "On considère des tableaux de nombres dont tous les éléments sont présents exactement trois fois à la suite, sauf un élément qui est présent une unique fois et que l'on appelle « l'intrus ». \n",
    "\n",
    "Voici quelques exemples :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1fd8e3e5",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "tab_a = [3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5,\n",
    "5, 5]\n",
    "#l'intrus est 7\n",
    "tab_b = [8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3]\n",
    "#l'intrus est 8\n",
    "tab_c = [5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8]\n",
    "#l'intrus est 3\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39e0af5b",
   "metadata": {},
   "source": [
    "On remarque qu'avec de tels tableaux :\n",
    "- pour les indices multiples de 3 situés strictement avant l'intrus, l'élément\n",
    "correspondant et son voisin de droite sont égaux,\n",
    "- pour les indices multiples de 3 situés après l'intrus, l'élément correspondant et\n",
    "son voisin de droite - s'il existe - sont différents.\n",
    "\n",
    "\n",
    "Ce que l'on peut observer ci-dessous en observant les valeurs des paires de voisins\n",
    "marquées par des caractères ^ :"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b18edcb",
   "metadata": {},
   "source": [
    "[3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5]\n",
    "\n",
    "\n",
    "^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^\n",
    "\n",
    "\n",
    "0 3 6 9 12 15 18 21 "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec77719b",
   "metadata": {},
   "source": [
    "Dans des listes comme celles ci-dessus, un algorithme récursif pour trouver l'intrus consiste alors à choisir un indice i multiple de 3 situé approximativement au milieu des indices parmi lesquels se trouve l'intrus.\n",
    "\n",
    "\n",
    "Puis, en fonction des valeurs de l'élément d'indice i et de son voisin de droite, à appliquer récursivement l'algorithme à la moitié droite ou à la moitié gauche des indices parmi lesquels se trouve l'intrus."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8eadcb1",
   "metadata": {},
   "source": [
    "Par exemple, si on s’intéresse à l’indice 12, on voit les valeurs 2 et 4 qui sont différentes : l’intrus est donc à gauche de l’indice 12 (indice 12 compris).\n",
    "\n",
    "\n",
    "En revanche, si on s’intéresse à l’indice 3, on voit les valeurs 9 et 9 qui sont identiques : l’intrus est donc à droite des indices 3-4-5, donc à partir de l’indice 6."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46e17050",
   "metadata": {},
   "source": [
    "Compléter la fonction récursive **trouver_intrus** proposée page suivante qui met\n",
    "en œuvre cet algorithme."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "38558d62",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trouver_intrus(tab, g, d):\n",
    " '''Renvoie la valeur de l'intrus situé entre les indices g et d dans la liste tab où : tab vérifie les conditions de l'exercice, g et d sont des multiples de 3.\n",
    " \n",
    " '''\n",
    " if g == d:\n",
    "   return ...\n",
    " else:\n",
    "   nombre_de_triplets = (d – g) // ...\n",
    "   indice = g + 3 * (nombre_de_triplets // 2)\n",
    "   if ... :\n",
    "    return ...\n",
    "   else:\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ddc432d3",
   "metadata": {},
   "outputs": [],
   "source": [
    ">>> trouver_intrus([3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4,\n",
    "4, 4, 8, 8, 8, 5, 5, 5], 0, 21)\n",
    "7\n",
    ">>> trouver_intrus([8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3],\n",
    "0, 12)\n",
    "8\n",
    ">>> trouver_intrus([5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8,\n",
    "8, 8], 0, 15)\n",
    "3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "952a09c8",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "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.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}