{"id":233,"date":"2022-05-02T17:30:08","date_gmt":"2022-05-02T15:30:08","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/?p=233"},"modified":"2022-05-03T11:56:31","modified_gmt":"2022-05-03T09:56:31","slug":"dichotomie","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/?p=233","title":{"rendered":"Dichotomie"},"content":{"rendered":"\n

INTRODUCTION:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

JEU:<\/p>\n\n\n\n

Je choisis un nombre entre 1 et 100. L’objectif est de trouver quel est ce nombre.<\/p>\n\n\n\n

La meilleure strat\u00e9gie pour r\u00e9soudre ce probl\u00e8me est de \u00ab\u00a0couper en deux\u00a0\u00bb \u00e0 chaque fois l’intervalle d’\u00e9tude. On commence \u00e0 50, puis 75 ou 25 etc.<\/p>\n\n\n\n

Cependant, si je propose un nombre de d\u00e9part comme 90, la probabilit\u00e9 que le nombre choisi se trouve entre 90 et 100 est r\u00e9duite, en revanche s’il l’est, cela repr\u00e9sente un gros avantage car le nouvel intervalle est tr\u00e8s r\u00e9duit.<\/p>\n\n\n\n

Pour conclure, la strat\u00e9gie optimale est de diviser en deux \u00e0 chaque \u00e9tape l’intervalle d’\u00e9tude. On appelle cela une m\u00e9thode par dichotomie<\/strong>, du grec ancien \u03b4\u03b9\u03c7\u03bf\u03c4\u03bf\u03bc\u03af\u03b1, dikhotomia (\u00ab division en deux parties \u00bb).<\/p>\n\n\n\n

La m\u00e9thode de dichotomie fait partie des m\u00e9thodes dites \u00ab\u00a0diviser pour mieux r\u00e9gner<\/em>\u00ab\u00a0.<\/p>\n\n\n\n

\"\"
Source : Wikip\u00e9dia<\/figcaption><\/figure>\n\n\n\n
  1. Recherche s\u00e9quentielle<\/li><\/ol>\n\n\n\n
    def rechercher(tab,val):\n    for nombre in tab:\n        if nombre==val:\n            return True\n    return False   <\/pre>\n\n\n\n
     Dans cette fonction, l’ordinateur va regarder chaque valeur du tableau une \u00e0 une afin de trouver la valeur correspondante. Si la valeur ne se trouve pas dans le tableau, la fonction affichera False.<\/p>\n\n\n\n
    <\/p>\n\n\n\n
    2.Recherche dichotomique<\/p>\n\n\n\n
    def dichotomie(tab,val):\n    debut = 0\n    fin = len(tab) - 1\n    while debut <= 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
    Dans cette fonction, il est n\u00e9cessaire que la tableau soit un tableau tri\u00e9.<\/p>\n\n\n\n
    On prend l’indice de d\u00e9part ainsi que l’indice de fin. On introduit une boucle : tant que l’indice de d\u00e9part est inf\u00e9rieur ou \u00e9gal par rapport \u00e0 l’indice de fin, alors l’indice du centre est \u00e9gal \u00e0 la somme de l’indice du d\u00e9but diviser par deux. Si la valeur demand\u00e9e est \u00e9gale \u00e0 la valeur se trouvant \u00e0 l’indice du centre de ton tableau, la fonction affichera True. En revanche si la valeur…. <\/p>\n","protected":false},"excerpt":{"rendered":"
    INTRODUCTION: JEU: Je choisis un nombre entre 1 et 100. L’objectif est de trouver quel est ce nombre. La meilleure strat\u00e9gie pour r\u00e9soudre ce probl\u00e8me est de \u00ab\u00a0couper en deux\u00a0\u00bb \u00e0 chaque fois l’intervalle d’\u00e9tude. On commence \u00e0 50, puis 75 ou 25 etc. Cependant, si je propose un nombre de d\u00e9part comme 90, la […]<\/p>\n","protected":false},"author":16,"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\/lukas\/index.php?rest_route=\/wp\/v2\/posts\/233"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/users\/16"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=233"}],"version-history":[{"count":4,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/posts\/233\/revisions"}],"predecessor-version":[{"id":246,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/posts\/233\/revisions\/246"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=233"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=233"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=233"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}