{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercices sur la récursivité et la programmation dynamique\n",
    "\n",
    "## Évolution des abonnements\n",
    "\n",
    "Un youtuber constate chaque mois qu'il recrute 3000 nouveaux abonnés mais dans le même temps la lassitude pousse 2% de ses fidèles à se désabonner. Ce mois-ci (n=0) il compte 100000 abonnés et il souhaite pouvoir calculer les prédictions de ses abonnés pour démarcher des sponsors dans les mois à venir. Écrivez récursivement la fonction `prev_abo` qui calcule le nombre d'abonné au mois n.\n",
    "\n",
    "Utilisez votre fonction `prev_abo` pour calculer le nombre d'abonnés dans les mois à venir.\n",
    "\n",
    "D'après vous, le youtuber peut-il prétendre à ces sponsors qu'il va bientôt atteindre les 200000 abonnés ? Utilisez votre programme pour constater l'évolution des abonnés à long terme."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sans maitrise la puissance n'est rien\n",
    "\n",
    "Écrivez par récurence une function `puissance(x: float, n: int) -> float` qui calcule $x^n$ pour n >= 0 en utilisant uniquement des multiplications et la valeur de $x^0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def puissance(x:float, n:int) -> float:\n",
    "    \"\"\" n must be >= 0\n",
    "    >>> puissance(0,0)\n",
    "    1\n",
    "    >>> puissance(1,0)\n",
    "    1\n",
    "    >>> puissance(1,1)\n",
    "    1\n",
    "    >>> puissance(1,3)\n",
    "    1\n",
    "    >>> puissance(2,3)\n",
    "    8\n",
    "    >>> puissance(10,5)\n",
    "    100000\n",
    "    \"\"\"\n",
    "\n",
    "import doctest\n",
    "doctest.testmod(optionflags=doctest.ELLIPSIS | doctest.NORMALIZE_WHITESPACE, verbose = False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Un PGCD pour l'examen ?\n",
    "\n",
    "Écrivez une fonction `pgcd` qui calcule le PGCD entre 2 nombres entiers avec l'algorithme d'Euclide qui dit ceci :\n",
    "- Le pgcd de a (a > 0) et b est le même que le pgcd de b et c avec c qui est le reste de la division entière (en python le modulo  :**%**) de a par b. \n",
    "- Le pgcd de a par 0 est a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Réduction de fraction\n",
    "\n",
    "Utiliser le pgcd précédent pour écrire une fonction `reduc` qui réduit les fractions entières comme ceci : `reduc(12,8)` retourne `(3,2)` car $\\dfrac{12}{8} = \\dfrac{3}{2}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Suite de Syracuse\n",
    "\n",
    "Programmez par **récursivité** la fonction `syracuse(u0: int, n: int)` qui calcule la [suite de Syracuse](https://fr.wikipedia.org/wiki/Conjecture_de_Syracuse#Suite_de_Syracuse) définie **pour des entiers** comme ceci :\n",
    "\n",
    "u<sub>{n+1}</sub> = \n",
    "\\begin{cases} \n",
    "    U_n / 2 & \\text{si } U_n \\text{ est pair} \\\\\n",
    "    3U_n + 1 & \\text{sinon}\n",
    "\\end{cases}\n",
    "\n",
    "💡 **Si vous appelez récursivement plusieurs fois la fonction avec les mêmes paramètres, il vaut mieux faire 1 seul appel et mettre le résultat dans une variable. Vous limiterez ainsi considérablement le nombre d'appels.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def syracuse(u0: int, n: int) -> int:\n",
    "    \"\"\" Return Syracuse suite value\n",
    "    u0 must be > 0 ; n must be >= 0\n",
    "    >>> syracuse(1, 0)\n",
    "    1\n",
    "    >>> syracuse(15, 7)\n",
    "    160\n",
    "    >>> syracuse(15, 4)\n",
    "    35\n",
    "    >>> syracuse(15, 17)\n",
    "    1\n",
    "    \"\"\"\n",
    "\n",
    "import doctest\n",
    "doctest.testmod(optionflags=doctest.ELLIPSIS | doctest.NORMALIZE_WHITESPACE, verbose = False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour l'appel de la fonction `syracuse(15, 3)` comptez au brouillon combien de fois la fonction `syracuse` se lance en écrivant l'arbre des appels.\n",
    "\n",
    "Vérifiez cela en modifiant votre programme, puis trouvez le nombre d'appel pour calculer `syracuse(15, 5)`, `syracuse(15, 10)`, `syracuse(15, 15)` et `syracuse(15, 20)`. Que pensez vous de ces derniers résultats ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une **conjecture encore non démontrée** en mathématique affirme que pour **tout N entier > 0 il existe toujours un terme de la suite pour lequel $u_n = 1$**.\n",
    "\n",
    "Écrivez un programme qui montre cette conjecture pour les valeurs de N allant jusqu'à 30."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A ce stade, suivant le code de votre fonction `syracuse`, tout se passe bien (**1 seul appel récursif par fonction**), ou vous avez dû interrompre le programme car sa **compléxité** est telle qu'il ne peut pas répondre dans un temps raisonnable (**3 appels récursifs par fonction**) !\n",
    "\n",
    "Écrivez maintenant votre programme de recherche du rang pour lequel $u_n=1$ pour un N donné en utilisant un algorithme **itératif (avec une boucle)**. Testez votre code en trouvant les rangs recherchés pour N jusqu'à 100."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recherche dichotomique récursive !\n",
    "\n",
    "Écrivez maintenant une fonction `find_dicho_recur` de recherche dichotomique dans une liste triée qui répond `True` ou `False` en fonction du résultat de la recherche. Vous pouvez utiliser les **slices** pour accéder à une sous-liste.\n",
    "\n",
    "💡 La technique qui consiste à résoudre un problème en résolvant plusieurs parties plus petite du problème s'appelle : **diviser pour régner**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_dicho_recur(liste: list, value: int) -> bool:\n",
    "    \"\"\" liste must be sorted\n",
    "    >>> find_dicho_recur([], 0)\n",
    "    False\n",
    "    >>> find_dicho_recur([1], 0)\n",
    "    False\n",
    "    >>> find_dicho_recur([1], 1)\n",
    "    True\n",
    "    >>> find_dicho_recur([1, 2], 1)\n",
    "    True\n",
    "    >>> find_dicho_recur([1, 2], 2)\n",
    "    True\n",
    "    >>> find_dicho_recur([1, 2], 3)\n",
    "    False\n",
    "    >>> find_dicho_recur([1, 2], -1)\n",
    "    False\n",
    "    >>> find_dicho_recur([1,2,3], 0)\n",
    "    False\n",
    "    >>> find_dicho_recur([1,2,3], 5)\n",
    "    False\n",
    "    >>> find_dicho_recur([1,2,3], 1)\n",
    "    True\n",
    "    >>> find_dicho_recur([1,2,3], 2)\n",
    "    True\n",
    "    >>> find_dicho_recur([1,2,3], 3)\n",
    "    True\n",
    "    >>> find_dicho_recur([1,2,3,4], 1)\n",
    "    True\n",
    "    >>> find_dicho_recur([1,2,3,4], 2)\n",
    "    True\n",
    "    >>> find_dicho_recur([1,2,3,4], 3)\n",
    "    True\n",
    "    >>> find_dicho_recur([1,2,3,4], 4)\n",
    "    True\n",
    "    >>> find_dicho_recur([1,2,3,4], -1)\n",
    "    False\n",
    "    >>> find_dicho_recur([1,2,3,4], 10)\n",
    "    False\n",
    "    \"\"\"\n",
    "\n",
    "import doctest\n",
    "doctest.testmod(optionflags=doctest.ELLIPSIS | doctest.NORMALIZE_WHITESPACE, verbose = False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rendu de monnaie optimal !\n",
    "\n",
    "Nous avons programmé le [rendu de monnaie](https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_rendu_de_monnaie) avec un **algorithme glouton** qui est optimal pour les **systèmes de monnaies cannoniques** (comme l'euro).\n",
    "\n",
    "Mais si nous disposons des pièces : **4, 3 et 1**, pour un rendu de 6, l'algorithme glouton rendra 3 pièces (4+1+1) alors qu'une solution en 2 pièces existe (3+3).\n",
    "\n",
    "Nous allons programmer une fonction `rendu_monnaie` **récursive** pour trouver la **solution optimale et explorant toutes les possibilités**.\n",
    "\n",
    "L'idée est de lancer une recherche récursive en choisissant 1 pièce et de garder seulement la solution qui demande le moins de pièces pour la somme restante. Voici un exemple avec [4,3,1] et 8 :\n",
    "- Je vais utiliser 1 pièce à tour de rôle : 4 puis je lance récursivement ma fonction avec [4,3,1] et 8-4 = 4. Puis je fais pareil avec les pièces 3 puis 1.\n",
    "- Je sais ainsi que le nombre de pièces total pour chaque possibilité est le résultat de l'appel récursif + 1. Il me suffit donc de choisir la branche qui retourne le moins de pièces.\n",
    "\n",
    "💡 Et comme le programme est **récursif toutes les possibilités seront automatiquement explorée** pour donner une solution optimale."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def rendu_monnaie(pieces: list, somme: int) -> list:\n",
    "    \"\"\" Return optimal coin's count for money back\n",
    "        Return None if no solution exists\n",
    "        pieces : list of int\n",
    "        >>> rendu_monnaie([], 5) is None\n",
    "        True\n",
    "        >>> rendu_monnaie([4,3], 1) is None\n",
    "        True\n",
    "        >>> rendu_monnaie([4,3], -1) is None\n",
    "        True\n",
    "        >>> rendu_monnaie([4,3], 5) is None\n",
    "        True\n",
    "        >>> rendu_monnaie([4,3], 6)\n",
    "        [3, 3]\n",
    "        >>> rendu_monnaie([4,3], 8)\n",
    "        [4, 4]\n",
    "        >>> rendu_monnaie([4,3,1], 6)\n",
    "        [3, 3]\n",
    "        >>> rendu_monnaie([4,3,1], 5)\n",
    "        [4, 1]        \n",
    "    \"\"\"\n",
    "\n",
    "import doctest\n",
    "doctest.testmod(optionflags=doctest.ELLIPSIS | doctest.NORMALIZE_WHITESPACE, verbose = False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rendu de monnaie optimal et dynamique !\n",
    "\n",
    "La solution ci-dessus qui explore **toutes les possibilités** récursivement est séduisante mais si vous lancez `rendu_monnaie([4,3,1], 25)` avec l'affichage des appels vous allez constater que le nombre d'appels est considérable. Ce qui explique pourquoi `rendu_monnaie([4,3,1], 53)` a du mal à répondre dans un temps raisonnable...\n",
    "\n",
    "Nous allons donc améliorer notre algorithme en écrivant une fonction `rendu_dyn` avec la technique de la **programmation dynamique** en mémorisant les solutions déjà calculées pour les réutiliser au cours du calcul."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rendu_dyn(pieces: list, somme: int) -> list:\n",
    "    \"\"\" Return optimal coin's count for money back\n",
    "        Return [] if no solution exists\n",
    "        pieces : list of POSITIVE int    \n",
    "        >>> rendu_dyn([], 5)\n",
    "        []\n",
    "        >>> rendu_dyn([4,3], 1)\n",
    "        []\n",
    "        >>> rendu_dyn([4,3], 0)\n",
    "        []\n",
    "        >>> rendu_dyn([4,3], 5)\n",
    "        []\n",
    "        >>> rendu_dyn([4,3], 6)\n",
    "        [3, 3]\n",
    "        >>> rendu_dyn([4,3], 8)\n",
    "        [4, 4]\n",
    "        >>> rendu_dyn([4,3,1], 6)\n",
    "        [3, 3]\n",
    "        >>> rendu_dyn([4,3,1], 5)\n",
    "        [4, 1]\n",
    "    \"\"\"\n",
    "\n",
    "import doctest\n",
    "doctest.testmod(optionflags=doctest.ELLIPSIS | doctest.NORMALIZE_WHITESPACE, verbose = False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Diviser pour régner : rotation d'une image d'un quart de tour en temps constant\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "👏👏👏 Bravo ! 👏👏👏"
   ]
  }
 ],
 "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.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}