{"id":338,"date":"2026-03-29T12:31:01","date_gmt":"2026-03-29T10:31:01","guid":{"rendered":"https:\/\/yb-isn.fr\/2025\/nsi\/?p=338"},"modified":"2026-03-30T08:10:59","modified_gmt":"2026-03-30T06:10:59","slug":"30-recherche-dichotomique-et-algorithme-glouton","status":"publish","type":"post","link":"https:\/\/yb-isn.fr\/2025\/nsi\/2026\/03\/29\/30-recherche-dichotomique-et-algorithme-glouton\/","title":{"rendered":"32-Recherche dichotomique et algorithme glouton"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\"><a href=\"https:\/\/capytale2.ac-paris.fr\/web\/c\/43a5-6356951\/mlc\">https:\/\/capytale2.ac-paris.fr\/web\/c\/43a5-6356951\/mlc<\/a><\/p>\n\n\n\n<p class=\"has-white-color has-header-gradient-background-color has-text-color has-background wp-block-paragraph\">1)<strong>Recherche dichotomique dans un tableau tri\u00e9<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Recherche s\u00e9quentielle<\/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=\"\">def rechercher(tab,val):\n    for nombre in tab:\n        if nombre==val:\n            return True\n    return False   <\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Recherche dichotomique<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Tester la fonction ci-dessous<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">ex\u00e9cuter pas \u00e0 pas \u00ab\u00a0\u00e0 la main\u00a0\u00bb ou sur python tutor pour bien comprendre l&rsquo;algorithme<\/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=\"\">def dichotomie(tab,val):\n    debut = 0\n    fin = len(tab) - 1\n    while debut &lt;= fin:\n        m = (debut + fin) \/\/ 2\n        if val== tab[m]:\n            return True\n        if val > tab[m]:\n            debut = m + 1\n        else:\n            fin = m - 1\n    return False<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">comparaison<\/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=\"\">import time\n\ntab=[i for i in range(100000000)]\n\ndebut1=time.time()\nrechercher(tab,10000000)\nduree1=time.time()-debut1\nprint(duree1)\n\ndebut2=time.time()\ndichotomie(tab,10000000)\nduree2=time.time()-debut2\nprint(duree2)<\/pre>\n\n\n\n<p class=\"has-white-color has-header-gradient-background-color has-text-color has-background wp-block-paragraph\">2) <strong>Algorithmes gloutons<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">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 class=\"wp-block-list\">\n<li>minimiser ou maximiser une fonction objectif ;<\/li>\n\n\n\n<li>satisfaire une ou des fonctions contraintes (il existe des probl\u00e8mes avec ou sans contrainte).<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">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 class=\"wp-block-paragraph\">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 class=\"wp-block-paragraph\">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 class=\"wp-block-paragraph\"><strong>Exemple du rendu de monnaie<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">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 class=\"wp-block-paragraph\">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 class=\"wp-block-paragraph\">On suppose que nous avons \u00e0 notre disposition un nombre illimit\u00e9 de ces pi\u00e8ces ou billets.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Vous devez rendre 423\u20ac<\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<p class=\"wp-block-paragraph\">donne une solution sans programmation<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u00c9crire un algorithme en pseudo-code<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Impl\u00e9menter l&rsquo;algorithme en python<\/p>\n<\/div><\/div>\n\n\n\n<figure class=\"wp-block-image size-full\"><img decoding=\"async\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/wp-content\/uploads\/2022\/05\/image-8.png\" alt=\"\" class=\"wp-image-810\"\/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">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 class=\"wp-block-paragraph\">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 class=\"wp-block-paragraph\">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\n\n\n<p class=\"wp-block-paragraph\"><strong>Exercices \u00e0 chercher<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><a href=\"https:\/\/capytale2.ac-paris.fr\/web\/c\/b85e-6495848\/mlc\">https:\/\/capytale2.ac-paris.fr\/web\/c\/b85e-6495848\/mlc<\/a><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img decoding=\"async\" src=\"https:\/\/yb-isn.fr\/2024\/nsi\/wp-content\/uploads\/2025\/04\/image-1.png\" alt=\"\" class=\"wp-image-521\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" src=\"https:\/\/yb-isn.fr\/2024\/nsi\/wp-content\/uploads\/2025\/04\/image-1024x455.png\" alt=\"\" class=\"wp-image-520\"\/><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/capytale2.ac-paris.fr\/web\/c\/43a5-6356951\/mlc 1)Recherche dichotomique dans un tableau tri\u00e9 Recherche s\u00e9quentielle Recherche dichotomique Tester la fonction ci-dessous ex\u00e9cuter pas \u00e0 pas \u00ab\u00a0\u00e0 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_crdt_document":"","footnotes":""},"categories":[1],"tags":[],"class_list":["post-338","post","type-post","status-publish","format-standard","hentry","category-non-classe"],"_links":{"self":[{"href":"https:\/\/yb-isn.fr\/2025\/nsi\/wp-json\/wp\/v2\/posts\/338","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/yb-isn.fr\/2025\/nsi\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/yb-isn.fr\/2025\/nsi\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/yb-isn.fr\/2025\/nsi\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/yb-isn.fr\/2025\/nsi\/wp-json\/wp\/v2\/comments?post=338"}],"version-history":[{"count":2,"href":"https:\/\/yb-isn.fr\/2025\/nsi\/wp-json\/wp\/v2\/posts\/338\/revisions"}],"predecessor-version":[{"id":351,"href":"https:\/\/yb-isn.fr\/2025\/nsi\/wp-json\/wp\/v2\/posts\/338\/revisions\/351"}],"wp:attachment":[{"href":"https:\/\/yb-isn.fr\/2025\/nsi\/wp-json\/wp\/v2\/media?parent=338"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/yb-isn.fr\/2025\/nsi\/wp-json\/wp\/v2\/categories?post=338"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/yb-isn.fr\/2025\/nsi\/wp-json\/wp\/v2\/tags?post=338"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}