{
 "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": [
    "# Algorithme glouton\n",
    "\n",
    "![image : glouton.png](images/glouton.png)\n",
    "\n",
    "Le glouton a un problème à résoudre : manger tous les desserts qui sont sur la table. \n",
    "Résoudre ce problème en une seule fois, ce serait manger tous les desserts simultanément… alors il va fragmenter le problème en une multitude de problèmes :\n",
    "- il commence par faire un choix qui lui semble le meilleur : d’abord manger le gâteau au chocolat\n",
    "- maintenant le problème initial est réduit et il recommence à faire un choix qui lui semble le meilleur parmi ce qui reste : la mousse à la framboise\n",
    "- maintenant le problème initial est réduit et il recommence à faire un choix qui lui semble le meilleur parmi ce qui reste : … etc etc\n",
    "\n",
    "Mais si à un moment donné il s’aperçoit que cela aurait été mieux de commencer  par les beignets … et bien c’est trop tard : il ne peut plus revenir en arrière\n",
    "\n",
    "Un algorithme glouton fonctionne ainsi : \n",
    "- **on décompose le problème en sous-problèmes**\n",
    "- **à chaque étape** on fait un **choix que l’on estime optimal** et on avance dans la résolution du problème\n",
    "- ...mais **on ne revient jamais en arrière**\n",
    "\n",
    "Un algorithme glouton, permet de répondre à des **problèmes d’optimisation**, c’est à dire de choisir parmi les multiples possibilités la solution optimale, que l’on suppose être **obtenue par la succession des  \"meilleurs choix\" effectués à chaque étape de la résolution**.\n",
    "\n",
    "## 1- Le problème du rendu de monnaie\n",
    "\n",
    "Un commerçant dispose de monnaie dans sa caisse : 50, 20, 10, 5, 2, 1 (pour simplifier on oublie les centimes : 50, 20, 10, 2, 1 et les billets de 100 et 200).\n",
    "\n",
    "Pour régler un achat de 2€, vous lui donnez un billet de 10€. Il doit vous rendre 8€. \n",
    "\n",
    "Le critère d’optimisation du rendu de monnaie est : \"utiliser le moins possible de pièces ou de billets\" (on appellera par la suite **pièce**, une pièce métallique ou un billet)\n",
    "\n",
    "(On supposera que le commerçant n’est pas limité en nombre de pièces et que donc ce nombre n’apportera pas une contrainte supplémentaire au problème du rendu de monnaie)\n",
    "\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "### 1.1- Travail préparatoire\n",
    "\n",
    "Histoire de \"jouer\" avec les listes et les dictionnaires, on propose de noter dans une liste les types de \"pièces\" disponibles chez le commerçant. Par exemple :\n",
    "\n",
    "caisse = \\[50, 20, 10, 5, 2, 1]\n",
    "\n",
    "La monnaie que le commerçant devra rendre sera placée dans un dictionnaire. Par exemple, s'il doit rendre 47€, ce dictionnaire sera :\n",
    "\n",
    "**{'50': 0, '20': 2, '10': 0, '5': 1, '2': 2, '1': 0}** car il rendra deux billets de 20€, un de 5€ et une pièce de 20€\n",
    "\n",
    "On propose donc d'initialiser ce dictionaire **par compréhension** à partir des types de \"pièces\" dont dispose le commerçant. \n",
    "\n",
    "Sur cet exemple cela donnerait : **monnaie = {'50': 0, '20': 0, '10': 0, '5': 0, '2': 0, '1': 0}**\n",
    "\n",
    "Ensuite l'algorithme devra progressivement alimenter ce dictionnaire avec le nombre de \"pièces\" de chaque sorte à rendre.\n",
    "\n",
    "\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cash = [50, 20, 10, 5, 2, 1]\n",
    "# construire le dictionnaire 'monnaie' par compréhension\n",
    "# résultat attendu : monnaie = {'50': 0, '20': 0, '10': 0, '5': 0, '2': 0, '1': 0}\n",
    "monnaie = ???\n",
    "\n",
    "print(monnaie)\n"
   ]
  },
  {
   "source": [
    "### 1.2- Mise en place de l'algorithme\n",
    "\n",
    "On souhaite créer une fonction **rendre_monnaie(cash, a_rendre)** pour laquelle :\n",
    " - le paramètre 'cash' est une liste des 'pièces' disponibles dans la caisse du commerçant\n",
    " - le paramètre 'a_rendre' est la somme que le commerçant doit rendre au client.\n",
    "\n",
    "Cette fonction renverra le dictionnaire 'monnaie' qui aura été créé et initialisé par compréhension **dans** la fonction."
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rendre_monnaie(cash, a_rendre):\n",
    "    \"\"\" fonction qui renvoie sous la forme d'un dictionnaire,\n",
    "    le nombre de 'pièces' de chaque valeur faciale à rendre\n",
    "    :param cash: (list) une liste des pièces disponibles\n",
    "    :param a_rendre: (int) la somme à rendre\n",
    "    :return: (dict) un dictionnaire donnant le nombre de pièces de chaque valeur faciale à rendre\n",
    "    \"\"\"    \n",
    "    \n",
    "    \n",
    "\n",
    "# test de la fonction :\n",
    "caisse = [50, 20, 10, 5, 2, 1]\n",
    "\n",
    "print(rendre_monnaie(caisse, 49))\n"
   ]
  },
  {
   "source": [
    "### 1.3- Améliorer la présentation du rendu de monnaie :\n",
    "\n",
    "Plutôt que d'afficher le rendu de monnaie sous la forme d'un dictionnaire, comme par exemple :\n",
    "\n",
    "{'50': 0, '20': 2, '10': 0, '5': 1, '2': 2, '1': 0} \n",
    "\n",
    "on souhaiterait avoir un affichage tel que :\n",
    "    \n",
    " Monnaie rendue :\n",
    "\n",
    " - 2  x  20  €\n",
    " - 1  x  5  €\n",
    " - 2  x  2  €\n",
    "\n",
    "Ecrire le code de la fonction **affiche_rendu()** conformément à la docstring présentée ci-dessous :\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def affiche_rendu(money):\n",
    "    \"\"\" procédure qui affiche de façon plus explicite le dictionnaire du rendu de monnaie\n",
    "    :param money: (dict) dictionnaire du rendu de monnaie\n",
    "    Exemple : pour {'50': 0, '20': 2, '10': 0, '5': 1, '2': 2, '1': 0} on affiche :\n",
    "    Monnaie rendue :\n",
    "    2  x  20  €\n",
    "    1  x  5  €\n",
    "    2  x  2  €\n",
    "    \"\"\"\n",
    "    print('Monnaie rendue :')\n",
    "    ???\n",
    "    ...\n",
    "    ???\n",
    "\n",
    "\n",
    "# Test de la fonction :\n",
    "???\n",
    "...\n",
    "???"
   ]
  },
  {
   "source": [
    "### 1.4- Le programme complet :\n",
    "\n",
    "Ecrire un programme complet de rendu de monnaie dans lequel :\n",
    " - le commerçant \"annonce\" le prix à payer\n",
    " - le client \"annonce\" la somme qu'il donne\n",
    " (pour ces deux entrées on utilisera des 'input')\n",
    "\n",
    "Le programme doit ensuite : \n",
    " - vérifier que la somme donnée par le client est suffisante\n",
    " - réaliser le calcul du rendu de monnaie\n",
    " - afficher la monnaie rendue avec la fonction **affiche_rendu()**"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# le programme complet :\n",
    "\n",
    "# la (les) fonction(s):\n",
    "\n",
    "\n",
    "# code :\n",
    "caisse = [50, 20, 10, 5, 2, 1]\n"
   ]
  }
 ]
}