{"id":308,"date":"2022-05-10T11:33:16","date_gmt":"2022-05-10T09:33:16","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/?p=308"},"modified":"2022-05-10T22:47:14","modified_gmt":"2022-05-10T20:47:14","slug":"algorithmes-gloutons","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/2022\/05\/10\/algorithmes-gloutons\/","title":{"rendered":"Algorithmes gloutons"},"content":{"rendered":"\n<figure class=\"wp-block-image\"><img src=\"http:\/\/yb-isn.fr\/2021\/nsi\/wp-content\/uploads\/2022\/05\/image-6.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"has-vivid-red-color has-pale-cyan-blue-background-color has-text-color has-background\">Les <strong>algorithmes<\/strong> <strong>gloutons<\/strong> sont utilis\u00e9s dans des <strong>probl\u00e8mes d\u2019optimisation<\/strong>. Un probl\u00e8me d\u2019optimisation consiste \u00e0 d\u00e9terminer<strong> les valeurs des param\u00e8tres<\/strong> permettant de :<\/p>\n\n\n\n<ul><li>minimiser ou maximiser une fonction objectif ;<\/li><li>satisfaire une ou des fonctions contraintes (il existe des probl\u00e8mes avec ou sans contrainte).<\/li><\/ul>\n\n\n\n<p>Ils correspondent \u00e0 une solution optimale obtenue en effectuant une suite de meilleurs choix pour chaque \u00e9tape de l\u2019algorithme (\u00e0 chaque \u00e9tape, on fait le milleur choix possible).<\/p>\n\n\n\n<p>Il n\u2019y a pas de retour en arri\u00e8re : quand un choix est fait \u00e0 une \u00e9tape, il n\u2019est pas modifi\u00e9 ult\u00e9rieurement et il ne modifie pas les choix pr\u00e9c\u00e9dents.<\/p>\n\n\n\n<p>L\u2019autre caract\u00e9ristiques des algorithmes gloutons est que lorsqu\u2019un choix est fait, on tente de r\u00e9soudre un probl\u00e8me plus petit. On appelle cela la progression descendante.<\/p>\n\n\n\n<p class=\"has-vivid-red-color has-pale-cyan-blue-background-color has-text-color has-background\">Prenons l&rsquo;exemple <strong>du rendu de monnaie<\/strong> : <\/p>\n\n\n\n<p>Le probl\u00e8me du rendu de monnaie est un probl\u00e8me d\u2019algorithmique qui s\u2019\u00e9nonce de la fa\u00e7on suivante : \u00e9tant donn\u00e9 un syst\u00e8me de monnaie, comment rendre une somme donn\u00e9e de fa\u00e7on optimale, c\u2019est-\u00e0-dire avec le nombre minimal de pi\u00e8ces et billets ?<\/p>\n\n\n\n<p>Dans la zone euro, le syst\u00e8me en vigueur, en mettant de c\u00f4t\u00e9 les centimes d\u2019euros, met \u00e0 disposition des pi\u00e8ces ou billets de : 1\u20ac, 2\u20ac, 5\u20ac, 10\u20ac, 20\u20ac, 50\u20ac, 100\u20ac, 200\u20ac, 500\u20ac.<\/p>\n\n\n\n<p>On suppose que nous avons \u00e0 notre disposition un nombre illimit\u00e9 de ces pi\u00e8ces ou billets.<\/p>\n\n\n\n<p>Vous devez rendre 423\u20ac<\/p>\n\n\n\n<p>Donne une solution sans programmation . <\/p>\n\n\n\n<p>Puis implanter en code python .<\/p>\n\n\n\n<p>Pour 423<\/p>\n\n\n\n<p>Cliquez sur le lien pour tout comprendre ! <\/p>\n\n\n\n<p><a href=\"https:\/\/pythontutor.com\/visualize.html#code=system_euro%3D%5B500,200,100,50,20,10,5,2,1%5D%0Adef%20rendu_monnaie%28somme,systeme%29%3A%0A%20%20%20%20liste_pieces%3D%5B%5D%0A%20%20%20%20for%20valeur%20in%20systeme%3A%0A%20%20%20%20%20%20%20%20while%20somme%3E%3Dvaleur%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20liste_pieces.append%28valeur%29%0A%20%20%20%20%20%20%20%20%20%20%20%20somme%3Dsomme-valeur%0A%20%20%20%20return%20liste_pieces%0A%0Arendu_monnaie%28423,system_euro%29&amp;cumulative=false&amp;curInstr=0&amp;heapPrimitives=nevernest&amp;mode=display&amp;origin=opt-frontend.js&amp;py=3&amp;rawInputLstJSON=%5B%5D&amp;textReferences=false\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/pythontutor.com\/visualize.html#code=system_euro%3D%5B500,200,100,50,20,10,5,2,1%5D%0Adef%20rendu_monnaie%28somme,systeme%29%3A%0A%20%20%20%20liste_pieces%3D%5B%5D%0A%20%20%20%20for%20valeur%20in%20systeme%3A%0A%20%20%20%20%20%20%20%20while%20somme%3E%3Dvaleur%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20liste_pieces.append%28valeur%29%0A%20%20%20%20%20%20%20%20%20%20%20%20somme%3Dsomme-valeur%0A%20%20%20%20return%20liste_pieces%0A%0Arendu_monnaie%28423,system_euro%29&amp;cumulative=false&amp;curInstr=0&amp;heapPrimitives=nevernest&amp;mode=display&amp;origin=opt-frontend.js&amp;py=3&amp;rawInputLstJSON=%5B%5D&amp;textReferences=false<\/a><\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">system_euro=[500,200,100,50,20,10,5,2,1]\ndef rendu_monnaie(somme,systeme):\n    liste_pieces=[]\n    for valeur in systeme:\n        while somme&gt;=valeur:\n            liste_pieces.append(valeur)\n            somme=somme-valeur\n    return liste_pieces<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Les algorithmes gloutons sont utilis\u00e9s dans des probl\u00e8mes d\u2019optimisation. Un probl\u00e8me d\u2019optimisation consiste \u00e0 d\u00e9terminer les valeurs des param\u00e8tres permettant de : minimiser ou maximiser une fonction objectif ; satisfaire une ou des fonctions contraintes (il existe des probl\u00e8mes avec ou sans contrainte). Ils correspondent \u00e0 une solution optimale obtenue en effectuant une suite de [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":313,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/posts\/308"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/comments?post=308"}],"version-history":[{"count":7,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/posts\/308\/revisions"}],"predecessor-version":[{"id":331,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/posts\/308\/revisions\/331"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/media\/313"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/media?parent=308"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/categories?post=308"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/tags?post=308"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}