{"id":1709,"date":"2022-05-10T11:13:08","date_gmt":"2022-05-10T09:13:08","guid":{"rendered":"https:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/?p=1709"},"modified":"2022-05-10T11:36:34","modified_gmt":"2022-05-10T09:36:34","slug":"algorithmes-glouton","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/2022\/05\/10\/algorithmes-glouton\/","title":{"rendered":"Algorithmes glouton"},"content":{"rendered":"\n<p><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"768\" height=\"155\" src=\"https:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/05\/image-6-768x155-1.png\" alt=\"\" class=\"wp-image-1711\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/05\/image-6-768x155-1.png 768w, http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/05\/image-6-768x155-1-300x61.png 300w\" sizes=\"(max-width: 768px) 100vw, 768px\" \/><\/figure>\n\n\n\n<p class=\"has-text-color has-background\" style=\"background-color:#daf1ff;color:#0b90e2\">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 :<\/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>Autre caract\u00e9ristique des algorithmes gloutons : lorsqu\u2019un choix est fait, on tente de r\u00e9soudre un probl\u00e8me plus petit. On appelle cela la <strong>progression descendante<\/strong>.<\/p>\n\n\n\n<p class=\"has-text-color has-background\" style=\"background-color:#d4e3ec;color:#1f7aaf\"><strong>Exemple du rendu de monnaie<\/strong> <strong>:<\/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 <strong>423<\/strong>\u20ac<\/p>\n\n\n\n<p>donne une solution sans programmation :<\/p>\n\n\n\n<ul><li>on prend une valeur<\/li><li>tant que la somme est sup\u00e9rieure \u00e0 la valeur, on ajoute la valeur \u00e0 la liste liste_pieces<\/li><li>la somme est alors \u00e9gale \u00e0 la somme moins la valeur<\/li><li>etc, jusqu&rsquo;\u00e0 obtenir la liste_pieces que l&rsquo;on renvoie<\/li><\/ul>\n\n\n\n<p>\u00c9crire un algorithme en pseudo-code<\/p>\n\n\n\n<p>Impl\u00e9menter l\u2019algorithme en python<\/p>\n\n\n\n<p><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"482\" height=\"63\" src=\"https:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/05\/image-8-1.png\" alt=\"\" class=\"wp-image-1714\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/05\/image-8-1.png 482w, http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/05\/image-8-1-300x39.png 300w\" sizes=\"(max-width: 482px) 100vw, 482px\" \/><\/figure>\n\n\n\n<p>On pourra \u00e9crire une fonction&nbsp;<code>rendu_monnaie(somme, systeme)<\/code>&nbsp;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&nbsp;<code>rendu_monnaie(97, systeme_euro)<\/code>&nbsp;doit renvoyer la liste&nbsp;<code>[50, 20, 20, 5, 2]<\/code>).<\/p>\n\n\n\n<p>L\u2019id\u00e9e est la suivante : on rend la monnaie avec le plus grand billet, tant que l\u2019on peut, puis on essaye avec le suivante, puis la suivante\u2026 Il y a une boucle\u00a0<code>for<\/code>\u00a0et, dans celle-ci, une boucle\u00a0<code>while<\/code>.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"godzilla\" 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\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"218\" height=\"76\" src=\"https:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/05\/image-18.png\" alt=\"\" class=\"wp-image-1734\" \/><figcaption>pour 97<\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"366\" height=\"256\" src=\"https:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/05\/image-16.png\" alt=\"\" class=\"wp-image-1720\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/05\/image-16.png 366w, http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/05\/image-16-300x210.png 300w\" sizes=\"(max-width: 366px) 100vw, 366px\" \/><figcaption>avec 423<\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"271\" height=\"387\" src=\"https:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/05\/image-17.png\" alt=\"\" class=\"wp-image-1722\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/05\/image-17.png 271w, http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/05\/image-17-210x300.png 210w\" sizes=\"(max-width: 271px) 100vw, 271px\" \/><figcaption>autre exemple avec 7341<\/figcaption><\/figure>\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":4,"featured_media":1729,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts\/1709"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/comments?post=1709"}],"version-history":[{"count":20,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts\/1709\/revisions"}],"predecessor-version":[{"id":1741,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts\/1709\/revisions\/1741"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/media\/1729"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/media?parent=1709"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/categories?post=1709"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/tags?post=1709"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}