{"id":160,"date":"2022-05-12T12:33:05","date_gmt":"2022-05-12T10:33:05","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/romain\/?p=160"},"modified":"2022-05-12T12:33:05","modified_gmt":"2022-05-12T10:33:05","slug":"algorithme-glouton","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/romain\/2022\/05\/12\/algorithme-glouton\/","title":{"rendered":"Algorithme Glouton"},"content":{"rendered":"\n
\"\"<\/figure>\n\n\n\n

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 :<\/span><\/strong><\/h3>\n\n\n\n
  • minimiser ou maximiser une fonction objectif ;<\/span><\/strong><\/li>
  • satisfaire une ou des fonctions contraintes (il existe des probl\u00e8mes avec ou sans contrainte).<\/span><\/strong><\/li><\/ul>\n\n\n\n

    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 meilleur choix possible).<\/span><\/strong><\/h3>\n\n\n\n

    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.<\/span><\/strong><\/h3>\n\n\n\n

    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.<\/span><\/strong><\/h3>\n\n\n\n

    Exem<\/span><\/strong>ple du rendu de monnaie<\/strong> :<\/span><\/h2>\n\n\n\n

    Le probl\u00e8me du rendu de monnaie est un probl\u00e8me d\u2019algorithmique qui s\u2019\u00e9nonce de la fa\u00e7on s<\/span><\/strong>uivante : \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 ?<\/strong><\/span><\/h3>\n\n\n\n

    Dans la zone euro, le syst\u00e8me en vigueur, en mettant de c\u00f4t\u00e9 les centimes d\u2019euros,<\/span><\/strong> 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.<\/strong><\/span><\/h3>\n\n\n\n

    On suppose que nous avons \u00e0 notre disposition un nombre illimit\u00e9 de ces pi\u00e8ces ou billets.<\/span><\/strong><\/h3>\n\n\n\n

    Vous devez rendre 423\u20ac<\/span><\/strong><\/h3>\n\n\n\n

    On pourra \u00e9crire une fonction\u00a0<\/span>rendu_monnaie(somme, systeme)<\/span><\/code>\u00a0qui prend en<\/span> 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.<\/span><\/strong><\/h3>\n\n\n\n

    Par exemple\u00a0<\/span><\/strong>rendu_monnaie<\/code><\/span>(97, systeme_<\/span><\/code>euro)<\/code>\u00a0<\/span>doit renvoyer la liste<\/span>\u00a0<\/strong>[50, 20, 20, 5, 2]<\/code><\/span>.<\/h3>\n\n\n\n

    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\u00a0for<\/code>\u00a0et, dans celle-ci, une boucle\u00a0<\/span>while<\/span><\/code>.<\/span><\/strong><\/h3>\n\n\n\n

    programme python :<\/span><\/h2>\n\n\n\n
    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>=valeur:\n            liste_pieces.append(valeur)\n            somme=somme-valeur\n    return liste_pieces<\/pre>\n\n\n\n
    <\/p>\n","protected":false},"excerpt":{"rendered":"
    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 […]<\/p>\n","protected":false},"author":11,"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\/romain\/wp-json\/wp\/v2\/posts\/160"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/romain\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/romain\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/romain\/wp-json\/wp\/v2\/users\/11"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/romain\/wp-json\/wp\/v2\/comments?post=160"}],"version-history":[{"count":2,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/romain\/wp-json\/wp\/v2\/posts\/160\/revisions"}],"predecessor-version":[{"id":163,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/romain\/wp-json\/wp\/v2\/posts\/160\/revisions\/163"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/romain\/wp-json\/wp\/v2\/media?parent=160"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/romain\/wp-json\/wp\/v2\/categories?post=160"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/romain\/wp-json\/wp\/v2\/tags?post=160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}