{"id":767,"date":"2022-05-07T09:47:47","date_gmt":"2022-05-07T07:47:47","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/?p=767"},"modified":"2022-05-10T10:57:32","modified_gmt":"2022-05-10T08:57:32","slug":"algorithmes-gloutons","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/?p=767","title":{"rendered":"Algorithmes gloutons"},"content":{"rendered":"\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/wp-content\/uploads\/2022\/05\/image-6.png\" alt=\"\" class=\"wp-image-768\" width=\"723\" height=\"146\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/wp-content\/uploads\/2022\/05\/image-6.png 964w, http:\/\/yb-isn.fr\/2021\/nsi\/wp-content\/uploads\/2022\/05\/image-6-300x60.png 300w, http:\/\/yb-isn.fr\/2021\/nsi\/wp-content\/uploads\/2022\/05\/image-6-768x155.png 768w\" sizes=\"(max-width: 723px) 100vw, 723px\" \/><\/figure>\n\n\n\n<p>les algorithmes gloutons sont utilis\u00e9s dans des probl\u00e8mes d&rsquo;optimisation. Un probl\u00e8me d&rsquo;optimisation consiste \u00e0 d\u00e9terminer les valeurs des param\u00e8tres 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&rsquo;algorithme (\u00e0 chaque \u00e9tape, on fait le milleur choix possible).<\/p>\n\n\n\n<p>Il n&rsquo;y a pas de retour en arri\u00e8re : quand un choix est fait \u00e0 une \u00e9tape, il n&rsquo;est pas modifi\u00e9 ult\u00e9rieurement et il ne modifie pas les choix pr\u00e9c\u00e9dents.<\/p>\n\n\n\n<p>L&rsquo;autre caract\u00e9ristiques des algorithmes gloutons est que lorsqu&rsquo;un 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><strong>Exemple du rendu de monnaie<\/strong><\/p>\n\n\n\n<p>Le probl\u00e8me du rendu de monnaie est un probl\u00e8me d&rsquo;algorithmique qui s&rsquo;\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&rsquo;euros, 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<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container\">\n<p>donne une solution sans programmation<\/p>\n\n\n\n<p>\u00c9crire un algorithme en pseudo-code<\/p>\n\n\n\n<p>Impl\u00e9menter l&rsquo;algorithme en python<\/p>\n<\/div><\/div>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"482\" height=\"63\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/wp-content\/uploads\/2022\/05\/image-8.png\" alt=\"\" class=\"wp-image-810\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/wp-content\/uploads\/2022\/05\/image-8.png 482w, http:\/\/yb-isn.fr\/2021\/nsi\/wp-content\/uploads\/2022\/05\/image-8-300x39.png 300w\" sizes=\"(max-width: 482px) 100vw, 482px\" \/><\/figure>\n\n\n\n<p>On pourra \u00e9crire une fonction <code>rendu_monnaie(somme, systeme)<\/code> qui prend en entr\u00e9e la somme \u00e0 rendre et le syst\u00e8me de monnaie contenant les valeurs des pi\u00e8ces et billets et qui renvoie la liste des billets et pi\u00e8ces. <\/p>\n\n\n\n<p>Par exemple <code>rendu_monnaie(97, systeme_euro)<\/code> doit renvoyer la liste <code>[50, 20, 20, 5, 2]<\/code>).<\/p>\n\n\n\n<p>L&rsquo;id\u00e9e est la suivante : on rend la monnaie avec le plus grand billet, tant que l&rsquo;on peut, puis on essaye avec le suivante, puis la suivante&#8230; Il y a une boucle <code>for<\/code> et, dans celle-ci, une boucle <code>while<\/code>.<\/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]\n\ndef rendu_monnaie(somme,systeme):\n    liste_pieces=[]\n    for valeur in systeme:\n        while somme>=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&rsquo;optimisation. Un probl\u00e8me d&rsquo;optimisation 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 <a class=\"more-link\" href=\"http:\/\/yb-isn.fr\/2021\/nsi\/?p=767\">Lire plus &#8230;<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/index.php?rest_route=\/wp\/v2\/posts\/767"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=767"}],"version-history":[{"count":5,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/index.php?rest_route=\/wp\/v2\/posts\/767\/revisions"}],"predecessor-version":[{"id":816,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/index.php?rest_route=\/wp\/v2\/posts\/767\/revisions\/816"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=767"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=767"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=767"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}