renduMonProf.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table style=\"border:1px solid black\">\n",
    "    <tbody>\n",
    "    <tr>\n",
    "        <td style=\"text-align: center; vertical-align: middle; border:1px solid black;\"><h1>TP<br></h1></td>\n",
    "        <td style=\"text-align: center; vertical-align: middle; border:1px solid black;\"><h2>3 h<br></h2></td>\n",
    "        <td style=\"text-align: center; vertical-align: middle; border:1px solid black;\"><h2>Langages et programmation <br> Algorithmique </h2></td>\n",
    "        <td style=\"text-align: center; vertical-align: middle; border:1px solid black;\"><h2>Terminale<br></h2></td>\n",
    "     </tr>\n",
    "     <tr>\n",
    "        <th colspan=\"2\" style=\"text-align: center; vertical-align: middle; border:1px solid black; background-color:white;\"><img alt=\"logoLLG\" src=\"logoLLG.jpg\"></th>\n",
    "        <td style=\"text-align: center; vertical-align: middle; border:1px solid black;\"><h2>Implémentation de l'algorithme du rendu de monnaie<br></h2></td>\n",
    "        <th style=\"text-align: center; vertical-align: middle; border:1px solid black; background-color:white;\"><img alt=\"logoNSI\" src=\"logoNSI.png\"></th> \n",
    "    </tr>\n",
    "    </tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<article style=\"display : flex;justify-content : space-evenly;align-items : center;\">\n",
    "    <div><br><br><p>Dans un distributeur de boissons, le monnayeur utilise des pièces de 0,01 €, 0,02 €, 0,05 €, 0,10 €, 0,20 €, 0,50 €, 1 € et 2 €.<br>On considère que la pièce de 2 € ne fait pas l'objet d'un rendu.<br>\n",
    "    On peut écrire ce système de pièces sous la forme d'un n-uplet (tuple) tp = (p0,p1,...,p6) constituant une suite de nombres entiers croissante avec p0 = 1 et p6 = 100 (en centimes).<br>\n",
    "        On cherche une liste d'entiers positifs <i>ln = [n0,n1,...,n6]</i> qui vérifie la contrainte <i>r = n0*p0+n1*p1+...+n6*p6.</i></p>\n",
    "    <h2>Algorithme naïf</h2>\n",
    "    <p>Afin de tester l'ensemble des solutions, nous vous proposons l'algorithme naïf suivant, qui prend en paramètres r(somme à rendre), tp, ln(liste constituée de k(nombre de pièces différentes) 0) :</p>\n",
    "    </div>\n",
    "    <img alt=\"distributeur boissons\" src=\"DistriBoissons.jpg\" />\n",
    "</article>\n",
    "<div style=\"background-color:aliceblue\">\n",
    "    AlgoNaif(r,tp,ln)\n",
    "    <blockquote>pour n0 de 0 à r//p0 faire\n",
    "    <blockquote>pour n1 de 0 à r//p1 faire\n",
    "    <blockquote>pour n2 de 0 à r//p2 faire\n",
    "    <blockquote>pour n3 de 0 à r//p3 faire\n",
    "    <blockquote>pour n4 de 0 à r//p4 faire\n",
    "    <blockquote>pour n5 de 0 à r//p5 faire\n",
    "    <blockquote>pour n6 de 0 à r//p6 faire\n",
    "    <blockquote>si r = n0\\*p0+n1\\*p1+...+n6\\*p6 alors\n",
    "    <blockquote>Enregistrer ln</blockquote></blockquote></blockquote></blockquote></blockquote></blockquote></blockquote></blockquote></blockquote>Fin<br></div>\n",
    "<p>On donne le programme suivant :\n",
    "<i style=\"color:red\">Attention, ce programme étant très long à executer, nous le testons pour r très petit (7)<i></p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def AlgoNaif(r,tp,ln):\n",
    "    global cpt\n",
    "    for ln[0] in range(r//tp[0]+1):\n",
    "        for ln[1] in range(r//tp[1]+1):\n",
    "            for ln[2] in range(r//tp[2]+1):\n",
    "                for ln[3] in range(r//tp[3]+1):\n",
    "                    for ln[4] in range(r//tp[4]+1):\n",
    "                        for ln[5] in range(r//tp[5]+1):\n",
    "                            for ln[6] in range(r//tp[6]+1):\n",
    "                                cpt += 1\n",
    "                                if r == ln[0]*tp[0]+ln[1]*tp[1]+ln[2]*tp[2]+ln[3]*tp[3]+ln[4]*tp[4]+ln[5]*tp[5]+ln[6]*tp[6]:\n",
    "                                    M.append(list(ln))\n",
    "\n",
    "tp = (1,2,5,10,20,50,100) #Valeurs du système monétaire\n",
    "r = 6 #Somme à rendre\n",
    "k = len(tp)\n",
    "ln = [0]*k #Nombre de pièces à rendre par valeur\n",
    "cpt = 0 #compteur d'itérations\n",
    "M = list() #enregistrement des combinaisons de pièces à rendre par valeur\n",
    "AlgoNaif(r,tp,ln)\n",
    "print(\"compteur itératif = \",cpt)\n",
    "print(\"M : \",M)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>La complexité temporelle de cet algorithme est </p>\n",
    "\\[\n",
    "   \\prod_{i = 0}^{k-1} (r//pi + 1)\n",
    "\\]\n",
    "<p>Soit en O(2<sup>n</sup>) !</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>Approche gloutonne</h2>\n",
    "<p>Le principe de l’algorithme <b>glouton</b> est le suivant : parmi les pièces de valeurs au plus r, on choisit autant de fois que possible la pièce de plus grande valeur. On poursuit avec cette même stratégie pour la quantité restante, jusqu’à ce que cette valeur restante soit nulle.</p>\n",
    "    <ol><li>Ecrire l’algorithme \"AlgoGlouton\" en pseudo-code. Il prend en paramètres r(somme à rendre), k(nombre de pièces possibles), tp, ln(liste de 0) et retourne ln.</li>\n",
    "        <li>Quelle est la complexité temporelle de cet algorithme dans le pire des cas ?</li></ol>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "AlgoGlouton(r,k,lp,ln)\n",
    "Pour i de k à 1 faire\n",
    "        ln[k] <-- valeur entière de r divisée par tp[k]\n",
    "        r <-- reste de la division de r divisée par tp[k] * ln[k]\n",
    "    Fin pour\n",
    "Fin\n",
    "\n",
    "Compléxité : O(n)\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<ol start=\"3\"><li>Implanter cet algorithme en langage Python. On donne :</li></ol>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def AlgoGlouton(r,k,tp,ln):\n",
    "    for i in range(k-1,-1,-1):\n",
    "        ln[i]=r//tp[i]\n",
    "        r=r%tp[i]\n",
    "    return ln\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour tester votre programme, on donne :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tp = (1,2,5,10,20,50,100)\n",
    "r = 231\n",
    "k = len(tp)\n",
    "ln = [0]*k\n",
    "print(AlgoGlouton(r,k,tp,ln))\n",
    "try:\n",
    "    assert(AlgoGlouton(r,k,tp,ln))==[1, 0, 0, 1, 1, 0, 2]\n",
    "except:\n",
    "    print(\"\\nC'est pas encore ça !\")\n",
    "else:\n",
    "    print(\"\\nbravo !\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1>Approche récursive</h1>\n",
    "<p>Revenons à la solution de départ, plus exaustive. <br>\n",
    "    On définit la suite a(r) :</p>\n",
    "    \\[ \n",
    "        a(r)=\\left\\{ \n",
    "            \\begin{split}\n",
    "                &0~si~r=0\\\\\n",
    "                &\\infty~si~r<0\\\\\n",
    "                &a(r-P(i))~pour~i~de~0~à~k~si~r>0\n",
    "            \\end{split}\n",
    "        \\right. \n",
    "    \\]\n",
    "<p>On donne le schéma sous forme d'arbre de toutes les combinaisons possibles, en choisissant de rendre r = 6 centimes avec k = 3 types de pièces, P0 = 1, P1 = 2 et P2 = 5 centimes.</p>\n",
    "<img src=\"arbreExhaustif.png\" alt=\"Arbre exhaustif\"/>\n",
    "<p>Ce graphe nous montre quinze possibilités mais seulement cinq sont différentes ! Nous voyons également que nous sommes dans une méthode \"diviser pour régner\".<br>\n",
    "    Votre programme devra afficher la solution (best) ne donnant qu'un minimum de pièces. L'ensemble des solutions sera stocké dans un tableau M. On donne les algorithmes suivants :<br><br></p>\n",
    "<article style=\"display : flex;justify-content : space-evenly;align-items : center;\">\n",
    "<div style=\"background-color:aliceblue\">\n",
    "    RenduExhaustif(k,tp,r,ln,i=0)\n",
    "    <blockquote>si r = 0 alors renvoyer 0<br>\n",
    "        sinon si r < 0 alors renvoyer &infin;<br>\n",
    "        sinon pour i de 0 à k faire\n",
    "    <blockquote>incrémenter ln(i)<br>\n",
    "        x &larr; RenduExhaustif(k,tp,r-tp[i],ln,i)<br>\n",
    "        si x = 0 alors\n",
    "    <blockquote>enregistre(ln)\n",
    "    </blockquote>décrémenter ln(i)</blockquote></blockquote>Fin<br></div>\n",
    "<div style=\"background-color:aliceblue\">\n",
    "    enregistre(ln)\n",
    "    <blockquote>si le contenu de ln n'est pas dans M alors\n",
    "    <blockquote>M &larr; contenu de ln</blockquote>\n",
    "        si somme(best) > somme(ln) alors\n",
    "    <blockquote>best &larr; contenu de ln</blockquote></blockquote>Fin<br></div>    \n",
    "</article>\n",
    "<ol start=\"4\"><li>Traduire les algorithmes en langage Python.</li></ol>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "compteur récursif =  849\n",
      "M :  [[9, 0, 0, 0, 0, 0, 0, 0], [7, 1, 0, 0, 0, 0, 0, 0], [5, 2, 0, 0, 0, 0, 0, 0], [4, 0, 1, 0, 0, 0, 0, 0], [3, 3, 0, 0, 0, 0, 0, 0], [2, 1, 1, 0, 0, 0, 0, 0], [1, 4, 0, 0, 0, 0, 0, 0], [0, 2, 1, 0, 0, 0, 0, 0]]\n",
      "nombre de solutions 8\n",
      "La meilleure solution est  [0, 2, 1, 0, 0, 0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "from math import inf\n",
    "\n",
    "def enregistre(ln):\n",
    "    global M,best\n",
    "    if ln not in M : #pour que chaque solution soit unique\n",
    "        M.append(list(ln)) #M <-- ln\n",
    "    if sum(best) > sum(ln): #si le nouveau rendu est meilleur que le précédent\n",
    "        best = [i for i in ln] #best <-- ln\n",
    "\n",
    "def RenduExhaustif(k,tp,r,ln,i=0):\n",
    "    global cpt #pour comptabiliser le nombre de récursions\n",
    "    cpt += 1\n",
    "    if r == 0 :\n",
    "        return 0\n",
    "    elif r < 0 :\n",
    "        return inf\n",
    "    else :\n",
    "        for i in range(k) :\n",
    "            ln[i] += 1\n",
    "            x = RenduExhaustif(k,tp,r-tp[i],ln,i)\n",
    "            if x == 0 :\n",
    "                enregistre(ln)\n",
    "            ln[i] -= 1\n",
    "\n",
    "tp = (1,2,5,10,20,50,100,200) #Valeurs du système monétaire\n",
    "r = 9\n",
    "k = len(tp)\n",
    "ln = [0]*k #Nombre de pièces à rendre par valeur\n",
    "cpt = 0 #compteur d’appels de boucle récursive\n",
    "M = list() #enregistrement des combinaisons de pièces à rendre par valeur\n",
    "best=[inf for i in range(k)] #Meilleure solution\n",
    "RenduExhaustif(k,tp,r,ln)\n",
    "print(\"compteur récursif = \",cpt)\n",
    "print(\"M : \",M)\n",
    "print(\"nombre de solutions\",len(M))\n",
    "print(\"La meilleure solution est \",best)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>Le programme précédent compte trop de récursions inutiles comme toutes les branches qui donnent une solution &infin;. \n",
    "    <ol start=\"5\"><li>Corriger-le afin de limiter l'étude aux valeurs de pièces inférieures ou égales à la somme r à rendre.</li></ol>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "durée du traitement =  0.5068769454956055 s\n",
      "compteur récursif =  331349\n",
      "M :  [[23, 0, 0, 0, 0, 0, 0, 0], [21, 1, 0, 0, 0, 0, 0, 0], [19, 2, 0, 0, 0, 0, 0, 0], [18, 0, 1, 0, 0, 0, 0, 0], [17, 3, 0, 0, 0, 0, 0, 0], [16, 1, 1, 0, 0, 0, 0, 0], [15, 4, 0, 0, 0, 0, 0, 0], [14, 2, 1, 0, 0, 0, 0, 0], [13, 5, 0, 0, 0, 0, 0, 0], [13, 0, 2, 0, 0, 0, 0, 0], [13, 0, 0, 1, 0, 0, 0, 0], [12, 3, 1, 0, 0, 0, 0, 0], [11, 6, 0, 0, 0, 0, 0, 0], [11, 1, 2, 0, 0, 0, 0, 0], [11, 1, 0, 1, 0, 0, 0, 0], [10, 4, 1, 0, 0, 0, 0, 0], [9, 7, 0, 0, 0, 0, 0, 0], [9, 2, 2, 0, 0, 0, 0, 0], [9, 2, 0, 1, 0, 0, 0, 0], [8, 5, 1, 0, 0, 0, 0, 0], [8, 0, 3, 0, 0, 0, 0, 0], [8, 0, 1, 1, 0, 0, 0, 0], [7, 8, 0, 0, 0, 0, 0, 0], [7, 3, 2, 0, 0, 0, 0, 0], [7, 3, 0, 1, 0, 0, 0, 0], [6, 6, 1, 0, 0, 0, 0, 0], [6, 1, 3, 0, 0, 0, 0, 0], [6, 1, 1, 1, 0, 0, 0, 0], [5, 9, 0, 0, 0, 0, 0, 0], [5, 4, 2, 0, 0, 0, 0, 0], [5, 4, 0, 1, 0, 0, 0, 0], [4, 7, 1, 0, 0, 0, 0, 0], [4, 2, 3, 0, 0, 0, 0, 0], [4, 2, 1, 1, 0, 0, 0, 0], [3, 10, 0, 0, 0, 0, 0, 0], [3, 5, 2, 0, 0, 0, 0, 0], [3, 5, 0, 1, 0, 0, 0, 0], [3, 0, 4, 0, 0, 0, 0, 0], [3, 0, 2, 1, 0, 0, 0, 0], [3, 0, 0, 2, 0, 0, 0, 0], [3, 0, 0, 0, 1, 0, 0, 0], [2, 8, 1, 0, 0, 0, 0, 0], [2, 3, 3, 0, 0, 0, 0, 0], [2, 3, 1, 1, 0, 0, 0, 0], [1, 11, 0, 0, 0, 0, 0, 0], [1, 6, 2, 0, 0, 0, 0, 0], [1, 6, 0, 1, 0, 0, 0, 0], [1, 1, 4, 0, 0, 0, 0, 0], [1, 1, 2, 1, 0, 0, 0, 0], [1, 1, 0, 2, 0, 0, 0, 0], [1, 1, 0, 0, 1, 0, 0, 0], [0, 9, 1, 0, 0, 0, 0, 0], [0, 4, 3, 0, 0, 0, 0, 0], [0, 4, 1, 1, 0, 0, 0, 0]]\n",
      "nombre de solutions 54\n",
      "La meilleure solution est  [1, 1, 0, 0, 1, 0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "from time import time\n",
    "\n",
    "def RenduExhaustif(k,tp,r,ln,i=0):\n",
    "    global cpt #pour comptabiliser le nombre de récursions\n",
    "    cpt += 1\n",
    "    if r == 0 :\n",
    "        return 0\n",
    "    elif r < 0 :\n",
    "        return inf\n",
    "    else :\n",
    "        for i in range(k) :\n",
    "            if tp[i] <= r :\n",
    "                ln[i] += 1\n",
    "                x = RenduExhaustif(k,tp,r-tp[i],ln,i)\n",
    "                if x == 0 :\n",
    "                    enregistre(ln)\n",
    "                ln[i] -= 1\n",
    "\n",
    "t1 = time() #temps de début du traitement \n",
    "tp = (1,2,5,10,20,50,100,200) #Valeurs du système monétaire\n",
    "r = 23\n",
    "k = len(tp)\n",
    "ln = [0]*k #Nombre de pièces à rendre par valeur\n",
    "cpt = 0 #compteur d’appels de boucle récursive\n",
    "M = list() #enregistrement des combinaisons de pièces à rendre par valeur\n",
    "best=[inf for i in range(k)] #Meilleure solution\n",
    "RenduExhaustif(k,tp,r,ln)\n",
    "print(\"durée du traitement = \",time()-t1,\"s\")\n",
    "print(\"compteur récursif = \",cpt)\n",
    "print(\"M : \",M)\n",
    "print(\"nombre de solutions\",len(M))\n",
    "print(\"La meilleure solution est \",best)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1>Programmation dynamique</h1>\n",
    "<p>La programmation dynamique (de type Top Down ici) permet l'optimisation du programme précédent en enregistrant dans un dictionnaire \"ajou\" les valeurs de r déjà étudiées. En fait, ce dictionnaire possède comme clés toutes les valeurs possibles de r et comme valeurs, une ou plusieurs listes d'éléments qui servent à corriger les valeurs de ln en cours. Ceci permet de ne pas refaire deux fois les mêmes calculs. Le schéma illustré précédement se simplifie. On en précise le fonctionnement :</p>\n",
    "<img src=\"arbreDynamique.png\" alt=\"Arbre dynamique\"/>\n",
    "<p>Dans ce cas, le dictionnaire \"ajou\" contient : <br>\n",
    "{1: [[1, 0, 0]], 2: [[0, 1, 0]], 3: [[1, 1, 0]], 4: [[0, 2, 0]], 5: [[1, 2, 0], [0, 0, 1]], 6: [[0, 3, 0], [1, 0, 1]]}<br>\n",
    "La suite a(r) devient :</p>\n",
    "    \\[ \n",
    "        a(r)=\\left\\{ \n",
    "            \\begin{split}\n",
    "                &0~si~r=0\\\\\n",
    "                &\\infty~si~r<0\\\\\n",
    "                &rien~si~ajou[r]~!=~[]\\\\\n",
    "                &a(r-P(i))~pour~i~de~0~à~k~si~r>0\n",
    "            \\end{split}\n",
    "        \\right. \n",
    "    \\]\n",
    "<p>Lorsque la fonction renvoie 0, vous devez enregistrer la liste ln et ajouter dans le dictionnaire, à la clé r, une nouvelle liste de valeurs. Lorsque la clé r du dictionnaire contient déjà au moins une liste, il faut corriger les valeurs de ln, les enregistrer et ajouter dans le dictionnaire, à la clé r+tp[i], une nouvelle liste de valeurs. Cette étape doit se répéter autant de fois qu'il y a de listes pour une clé.<br>\n",
    "On donne : \n",
    "<div style=\"background-color:aliceblue\">\n",
    "    RenduDynamique(k,tp,r,ln,ajou,i=0)\n",
    "    <blockquote>si r = 0 alors renvoyer 0<br>\n",
    "        sinon si r < 0 alors renvoyer &infin;<br>\n",
    "        sinon si liste ajou(r) différent de () alors\n",
    "        <blockquote>pour tous les éléments de ajou(r) faire\n",
    "            <blockquote>créer une liste \"solution\" de k valeurs<br>\n",
    "            pour a de 0 à k faire\n",
    "                <blockquote>solution(a) = ln(a)+élément(a)</blockquote>\n",
    "            enregistre(solution)<br>\n",
    "            copier la liste \"élément\" dans une liste \"Najou\"<br>\n",
    "            incrémenter Najou(i)<br>\n",
    "            ajouter Najou dans ajou(r+tp(i))</blockquote></blockquote>\n",
    "        sinon pour i de 0 à k faire\n",
    "            <blockquote>incrémenter ln(i)<br>\n",
    "            x &larr; RenduExhaustif(k,tp,r-tp[i],ln,i)<br>\n",
    "            si x = 0 alors\n",
    "                <blockquote>enregistre(ln)<br>\n",
    "                créer une liste \"Najou\" de k valeurs<br>\n",
    "                incrémenter Najou(i)<br>\n",
    "                ajouter Najou dans ajou(r)</blockquote>\n",
    "            décrémenter ln(i)</blockquote></blockquote>Fin<br></div>\n",
    "</p>\n",
    "<ol start=\"6\"><li>Compléter le programme suivant afin d'optimiser votre précédent traitement.</li></ol>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "durée du traitement =  0.004987955093383789 s\n",
      "compteur récursif =  185\n",
      "M :  [[23, 0, 0, 0, 0, 0, 0, 0], [21, 1, 0, 0, 0, 0, 0, 0], [19, 2, 0, 0, 0, 0, 0, 0], [18, 0, 1, 0, 0, 0, 0, 0], [17, 3, 0, 0, 0, 0, 0, 0], [16, 1, 1, 0, 0, 0, 0, 0], [15, 4, 0, 0, 0, 0, 0, 0], [14, 2, 1, 0, 0, 0, 0, 0], [13, 5, 0, 0, 0, 0, 0, 0], [13, 0, 2, 0, 0, 0, 0, 0], [13, 0, 0, 1, 0, 0, 0, 0], [12, 3, 1, 0, 0, 0, 0, 0], [11, 6, 0, 0, 0, 0, 0, 0], [11, 1, 2, 0, 0, 0, 0, 0], [11, 1, 0, 1, 0, 0, 0, 0], [10, 4, 1, 0, 0, 0, 0, 0], [9, 7, 0, 0, 0, 0, 0, 0], [9, 2, 2, 0, 0, 0, 0, 0], [9, 2, 0, 1, 0, 0, 0, 0], [8, 5, 1, 0, 0, 0, 0, 0], [8, 0, 3, 0, 0, 0, 0, 0], [8, 0, 1, 1, 0, 0, 0, 0], [7, 8, 0, 0, 0, 0, 0, 0], [7, 3, 2, 0, 0, 0, 0, 0], [7, 3, 0, 1, 0, 0, 0, 0], [6, 6, 1, 0, 0, 0, 0, 0], [6, 1, 3, 0, 0, 0, 0, 0], [6, 1, 1, 1, 0, 0, 0, 0], [5, 9, 0, 0, 0, 0, 0, 0], [5, 4, 2, 0, 0, 0, 0, 0], [5, 4, 0, 1, 0, 0, 0, 0], [4, 7, 1, 0, 0, 0, 0, 0], [4, 2, 3, 0, 0, 0, 0, 0], [4, 2, 1, 1, 0, 0, 0, 0], [3, 10, 0, 0, 0, 0, 0, 0], [3, 5, 2, 0, 0, 0, 0, 0], [3, 5, 0, 1, 0, 0, 0, 0], [3, 0, 4, 0, 0, 0, 0, 0], [3, 0, 2, 1, 0, 0, 0, 0], [3, 0, 0, 2, 0, 0, 0, 0], [3, 0, 0, 0, 1, 0, 0, 0], [2, 8, 1, 0, 0, 0, 0, 0], [2, 3, 3, 0, 0, 0, 0, 0], [2, 3, 1, 1, 0, 0, 0, 0], [1, 11, 0, 0, 0, 0, 0, 0], [1, 6, 2, 0, 0, 0, 0, 0], [1, 6, 0, 1, 0, 0, 0, 0], [1, 1, 4, 0, 0, 0, 0, 0], [1, 1, 2, 1, 0, 0, 0, 0], [1, 1, 0, 2, 0, 0, 0, 0], [1, 1, 0, 0, 1, 0, 0, 0], [0, 9, 1, 0, 0, 0, 0, 0], [0, 4, 3, 0, 0, 0, 0, 0], [0, 4, 1, 1, 0, 0, 0, 0]]\n",
      "nombre de solutions 54\n",
      "La meilleure solution est  [1, 1, 0, 0, 1, 0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "def RenduDynamique(k,tp,r,ln,ajou,i=0): \n",
    "    global cpt #pour comptabiliser le nombre de récursions\n",
    "    cpt += 1 \n",
    "    if r == 0 :\n",
    "        return 0\n",
    "    elif r < 0 :\n",
    "        return inf\n",
    "    elif ajou[r] != [] :\n",
    "        for elem in ajou[r]:\n",
    "            solu = [0]*k #création d'une solution à enregistrer\n",
    "            for a in range(k) :\n",
    "                solu[a] = ln[a] + elem[a]\n",
    "            enregistre(solu)\n",
    "            Najou = list(elem)\n",
    "            Najou[i] += 1\n",
    "            ajou[r+tp[i]].append(Najou)\n",
    "    else :\n",
    "        for i in range(k) :\n",
    "            ln[i] += 1\n",
    "            x = RenduDynamique(k,tp,r-tp[i],ln,ajou,i)\n",
    "            if x == 0 :\n",
    "                enregistre(ln)\n",
    "                Najou = [0]*k\n",
    "                Najou[i] += 1\n",
    "                ajou[r].append(Najou)\n",
    "            ln[i] -= 1\n",
    "\n",
    "t1 = time() #temps de début du traitement \n",
    "tp = (1,2,5,10,20,50,100,200) #Valeurs du système monétaire\n",
    "r = 23\n",
    "k = len(tp)\n",
    "ln = [0]*k #Nombre de pièces à rendre par valeur\n",
    "cpt = 0 #compteur d’appels de boucle récursive\n",
    "M = list() #enregistrement des combinaisons de pièces à rendre par valeur\n",
    "best=[inf for i in range(k)] #Meilleure solution\n",
    "ajou={1+d:[] for d in range(r)} #valeur à ajouter au nombre de pièce lors de la mémoïsation\n",
    "RenduDynamique(k,tp,r,ln,ajou)\n",
    "print(\"durée du traitement = \",time()-t1,\"s\")\n",
    "print(\"compteur récursif = \",cpt)\n",
    "print(\"M : \",M)\n",
    "print(\"nombre de solutions\",len(M))\n",
    "print(\"La meilleure solution est \",best)"
   ]
  },
  {
   "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}