{"id":2813,"date":"2025-11-09T09:38:00","date_gmt":"2025-11-09T08:38:00","guid":{"rendered":"https:\/\/labodemaths.fr\/WordPress3\/?p=2813"},"modified":"2025-11-10T07:09:16","modified_gmt":"2025-11-10T06:09:16","slug":"nsi-un-nouvel-algorithme","status":"publish","type":"post","link":"https:\/\/labodemaths.fr\/WordPress3\/nsi-un-nouvel-algorithme\/","title":{"rendered":"NSI, un nouvel algorithme"},"content":{"rendered":"\n<p>On d\u00e9sire mettre en place d&rsquo;un algorithme permettant de d\u00e9terminer si une valeur est pr\u00e9sente ou non dans une liste de nombres al\u00e9atoires rang\u00e9e par ordre croissant.<\/p>\n\n\n\n<h2>1. G\u00e9n\u00e9rer une liste al\u00e9atoire de n nombres entiers diff\u00e9rents d&rsquo;une valeur k<\/h2>\n\n\n\n<p>Ecrire une fonction r\u00e9pondant \u00e0 sa docstring :<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def liste_alea(n,k):\n    '''\n    g\u00e9n\u00e8re un tuple al\u00e9atoire de n entiers compris entre\n    0 et n diff\u00e9rents de k\n    '''\n<\/code><\/pre>\n\n\n\n<h2>2. Tester un premier algorithme<\/h2>\n\n\n\n<p>Compl\u00e9ter la fonction suivante<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def presence(liste,val):\n    '''\n    d\u00e9terminer si une valeur est pr\u00e9sente dans une liste\n    >>>presence((1,2,3),5)\n    False\n    >>>presence((1,2,3),2)\n    True\n    '''\n    for i in .......:\n        if .....==.....:\n            return .......\n    return ........\n    <\/code><\/pre>\n\n\n\n<h2>3. Mesurer le temps d&rsquo;ex\u00e9cution et d\u00e9terminer si il est lin\u00e9aire ou quadratique<\/h2>\n\n\n\n<p>Ajouter les lignes suivantes dans votre programme<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>import time\n<meta charset=\"utf-8\">l=liste_alea(100000,8)\nl=sorted(l)\nt0 = time.time()\n<meta charset=\"utf-8\">presence(l,8)\nt1 = time.time()\ntemps=t1-t0\nprint(temps)\n<\/code><\/pre>\n\n\n\n<p>D\u00e9terminer si le temps d&rsquo;ex\u00e9cution de la fonction presence() est lin\u00e9aire ou quadratique<\/p>\n\n\n\n<h2>4. Un algorithme plus performant : la dichotomie<\/h2>\n\n\n\n<figure class=\"wp-block-image size-full\"><a href=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2025\/05\/recherche_dichotomique.png\"><img loading=\"lazy\" width=\"382\" height=\"244\" src=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2025\/05\/recherche_dichotomique.png\" alt=\"\" class=\"wp-image-2814\" srcset=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2025\/05\/recherche_dichotomique.png 382w, https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2025\/05\/recherche_dichotomique-300x192.png 300w\" sizes=\"(max-width: 382px) 100vw, 382px\" \/><\/a><\/figure>\n\n\n\n<pre class=\"wp-block-code\"><code>def recherche_dichotomique(v, T):\n    \"\"\"\n    T : tuple d\u2019entiers tri\u00e9 dans l\u2019ordre croissant\n    v : nombre entier\n    La fonction renvoie True si T contient v et False sinon\n    \"\"\"\n    debut = ....\n    fin = .......\n    while debut &lt;= fin:\n        m = ...\n        if v == T&#91;m]:\n            return ...\n        elif v > T&#91;m]:\n            debut = m + 1\n        else:\n            fin = ...\n    return ...<\/code><\/pre>\n\n\n\n<p>Tester le temps d&rsquo;ex\u00e9cution de ce nouvel algorithme<\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>On d\u00e9sire mettre en place d&rsquo;un algorithme permettant de d\u00e9terminer si une valeur est pr\u00e9sente&#8230;<\/p>\n<div class=\"more-link-wrapper\"><a class=\"more-link\" href=\"https:\/\/labodemaths.fr\/WordPress3\/nsi-un-nouvel-algorithme\/\">Read the post<span class=\"screen-reader-text\">NSI, un nouvel algorithme<\/span><\/a><\/div>\n","protected":false},"author":2,"featured_media":2814,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[57],"tags":[],"_links":{"self":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/2813"}],"collection":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/comments?post=2813"}],"version-history":[{"count":3,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/2813\/revisions"}],"predecessor-version":[{"id":2937,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/2813\/revisions\/2937"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media\/2814"}],"wp:attachment":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media?parent=2813"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/categories?post=2813"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/tags?post=2813"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}