{"id":273,"date":"2022-05-10T11:18:33","date_gmt":"2022-05-10T09:18:33","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/kelya\/?p=273"},"modified":"2022-05-10T11:22:57","modified_gmt":"2022-05-10T09:22:57","slug":"algorithmes-gloutons","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/kelya\/2022\/05\/10\/algorithmes-gloutons\/","title":{"rendered":"Algorithmes gloutons"},"content":{"rendered":"\n

Un algorithme glouton (parfois appel\u00e9 aussi algorithmes gourmand, ou goulu) est un algorithme qui suit le principe de faire, \u00e9tape par \u00e9tape, un choix optimum local, dans l’espoir d’obtenir un r\u00e9sultat optimum global.<\/p>\n\n\n\n

exercice consigne:<\/p>\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 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

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

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

Tentative:<\/p>\n\n\n\n

system_euro = [500,200,100,50,20,10,5,2,1]\nsystem = system_euro\n\ndef rendu(somme , system):\n  liste_piece=[]\n  for val in system:\n    if somme >= system[0]:\n      liste_piece = system [0]\n    else liste_piece \n  return liste_piece<\/pre>\n\n\n\n
rendu(600,system)<\/pre>\n\n\n\n
Correction:<\/p>\n\n\n\n
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\n\n\n
rendu_monnaie(888,system)<\/pre>\n\n\n\n
Lien collab pour voir les essaies:<\/p>\n\n\n\n
https:\/\/colab.research.google.com\/drive\/1X0dvaCywrAgfUuBO00yNntzQkRd5encs?usp=sharing<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Un algorithme glouton (parfois appel\u00e9 aussi algorithmes gourmand, ou goulu) est un algorithme qui suit le principe de faire, \u00e9tape par \u00e9tape, un choix optimum local, dans l’espoir d’obtenir un r\u00e9sultat optimum global. exercice consigne: 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, […]<\/p>\n","protected":false},"author":17,"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\/kelya\/wp-json\/wp\/v2\/posts\/273"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/kelya\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/kelya\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/kelya\/wp-json\/wp\/v2\/users\/17"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/kelya\/wp-json\/wp\/v2\/comments?post=273"}],"version-history":[{"count":2,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/kelya\/wp-json\/wp\/v2\/posts\/273\/revisions"}],"predecessor-version":[{"id":276,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/kelya\/wp-json\/wp\/v2\/posts\/273\/revisions\/276"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/kelya\/wp-json\/wp\/v2\/media?parent=273"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/kelya\/wp-json\/wp\/v2\/categories?post=273"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/kelya\/wp-json\/wp\/v2\/tags?post=273"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}