{"id":6297,"date":"2021-06-22T15:29:16","date_gmt":"2021-06-22T13:29:16","guid":{"rendered":"https:\/\/www.mathweb.fr\/euclide\/?p=6297"},"modified":"2021-06-22T15:29:17","modified_gmt":"2021-06-22T13:29:17","slug":"le-codage-de-fibonacci-et-python","status":"publish","type":"post","link":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/","title":{"rendered":"Le codage de Fibonacci et Python"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Le codage de Fibonacci et Python : mais c&rsquo;est quoi ce codage ?<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Nous allons avant tout parler math\u00e9matiques, puis nous allons impl\u00e9menter tout \u00e7a en Python.<\/p>\n\n\n\n<!--more-->\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_85 counter-hierarchy ez-toc-counter ez-toc-white ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Au menu sur cette page...<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#Le_codage_de_Fibonacci_et_Python_approche_mathematique\" >Le codage de Fibonacci et Python: approche math\u00e9matique<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#Codage_de_Fibonacci_dun_caractere\" >Codage de Fibonacci d&rsquo;un caract\u00e8re<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#Du_decimal_au_binaire\" >Du d\u00e9cimal au binaire<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#Du_decimal_au_%C2%AB_fibonaire_%C2%BB\" >Du d\u00e9cimal au \u00ab\u00a0fibonaire\u00a0\u00bb<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#Suite_de_Fibonacci\" >Suite de Fibonacci<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#Theoreme_de_Zeckendorf\" >Th\u00e9or\u00e8me de Zeckendorf<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#Codage_et_decodage_de_Fibonacci\" >Codage et d\u00e9codage de Fibonacci<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#Le_codage_de_Fibonacci_en_Python\" >Le codage de Fibonacci en Python<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#Construction_dune_table_contenant_les_termes_de_la_suite_de_Fibonacci\" >Construction d&rsquo;une table contenant les termes de la suite de Fibonacci<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#La_fonction_de_codage\" >La fonction de codage<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#La_fonction_de_decodage\" >La fonction de d\u00e9codage<\/a><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Le_codage_de_Fibonacci_et_Python_approche_mathematique\"><\/span>Le codage de Fibonacci et Python: approche math\u00e9matique<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Codage_de_Fibonacci_dun_caractere\"><\/span>Codage de Fibonacci d&rsquo;un caract\u00e8re<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Un caract\u00e8re est repr\u00e9sent\u00e9 en ASCII par un nombre. Par exemple, le caract\u00e8re \u00ab\u00a0A\u00a0\u00bb est repr\u00e9sent\u00e9 par le nombre \u00ab\u00a065\u00a0\u00bb. Bien s\u00fbr, \u00ab\u00a065\u00a0\u00bb peut \u00eatre repr\u00e9sent\u00e9 en binaire&#8230;<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Du_decimal_au_binaire\"><\/span>Du d\u00e9cimal au binaire<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Pour convertir un nombre d\u00e9cimal au binaire, il suffit de d\u00e9composer le nombre d\u00e9cimal en somme de puissances de 2.$$\\begin{align}65&amp;=64+1\\\\&amp;=2^6+1\\\\&amp;=\\small 0 \\times 2^7 + 1 \\times 2^6 + 0 \\times 2^5 + 0 \\times 2^4 + 0 \\times 2^3 + 0 \\times 2^2 + 0 \\times 2^1 + 1 \\times 2^0\\end{align}$$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">On peut repr\u00e9senter cette d\u00e9composition \u00e0 l&rsquo;aide du tableau suivant:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">\\(2^7\\)<\/td><td class=\"has-text-align-center\" data-align=\"center\">\\(2^6\\)<\/td><td class=\"has-text-align-center\" data-align=\"center\">\\(2^5\\)<\/td><td class=\"has-text-align-center\" data-align=\"center\">\\(2^4\\)<\/td><td class=\"has-text-align-center\" data-align=\"center\">\\(2^3\\)<\/td><td class=\"has-text-align-center\" data-align=\"center\">\\(2^2\\)<\/td><td class=\"has-text-align-center\" data-align=\"center\">\\(2^1\\)<\/td><td class=\"has-text-align-center\" data-align=\"center\">\\(2^0\\)<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Ainsi, le nombre d\u00e9cimal 65 peut \u00eatre cod\u00e9 en binaire sur un <em>octet<\/em> (8 bits) par 01000001.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Du_decimal_au_%C2%AB_fibonaire_%C2%BB\"><\/span>Du d\u00e9cimal au \u00ab\u00a0fibonaire\u00a0\u00bb<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Ne cherchez pas la d\u00e9finition du \u00ab\u00a0fibonaire\u00a0\u00bb, c&rsquo;est un mot que j&rsquo;ai invent\u00e9 \ud83d\ude42<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Nous allons suivre le m\u00eame principe que pr\u00e9c\u00e9demment, mais au lieu de d\u00e9composer en somme de puissances de 2, nous allons le faire en somme de termes de la suite de Fibonacci.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Suite_de_Fibonacci\"><\/span>Suite de Fibonacci<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Cette suite, souvent not\u00e9e \\( (F_n) \\) est d\u00e9finie par ses deux premiers termes \\(F_0=F_1=1\\) et par la relation de r\u00e9currence:$$\\forall\\ n\\in\\mathbb{N},\\quad F_{n+2} = F_{n+1} + F_n.$$ Ses premiers termes sont donc :<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\\(F_2 = F_0+F_1=1+1=2\\)<\/li><li>\\(F_3=F_1+F_2=1+2=3\\)<\/li><li>\\(F_4=F_2+F_3=2+3=5\\)<\/li><li>\\(F_5=F_3+F_4=3+5=8\\)<\/li><li>&#8230;<\/li><\/ul>\n\n\n\n<h4 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Theoreme_de_Zeckendorf\"><\/span>Th\u00e9or\u00e8me de Zeckendorf<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Le th\u00e9or\u00e8me de <a href=\"https:\/\/www.dcode.fr\/representation-zeckendorf\">Zeckendorf<\/a> stipule que tout entier naturel <em>n<\/em> peut s&rsquo;\u00e9crire sous la forme:$$n = \\sum_{i=1}^k\\alpha_i F_i$$o\u00f9:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\\(\\alpha_i \\in \\{0;1\\}\\)<\/li><li>\\(\\alpha_i \\times \\alpha_{i+1} = 0\\)<\/li><li>\\(F_i\\) est le <em>i<\/em>-\u00e8me terme de la suite de Fibonacci.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Par exemple, $$65 = 2+8+55$, que l&rsquo;on peut repr\u00e9senter sous forme de tableau:<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-regular\"><table><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><td class=\"has-text-align-center\" data-align=\"center\">2<\/td><td class=\"has-text-align-center\" data-align=\"center\">3<\/td><td class=\"has-text-align-center\" data-align=\"center\">5<\/td><td class=\"has-text-align-center\" data-align=\"center\">8<\/td><td class=\"has-text-align-center\" data-align=\"center\">13<\/td><td class=\"has-text-align-center\" data-align=\"center\">21<\/td><td class=\"has-text-align-center\" data-align=\"center\">34<\/td><td class=\"has-text-align-center\" data-align=\"center\">55<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Codage_et_decodage_de_Fibonacci\"><\/span>Codage et d\u00e9codage de Fibonacci<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Pour coder le caract\u00e8re \u00ab\u00a0A\u00a0\u00bb, il suffit d&rsquo;ajouter un \u00ab\u00a01\u00a0\u00bb \u00e0 droite de la d\u00e9composition. On obtient alors :<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\">\u00ab\u00a0A\u00a0\u00bb devient 0100100011<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Le th\u00e9or\u00e8me de Zeckendorf nous assure que le codage ne peut pas comporter deux \u00ab\u00a01\u00a0\u00bb c\u00f4te-\u00e0-c\u00f4te sauf \u00e0 la fin, ce qui s&rsquo;av\u00e8re utile pour coder un message.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">En effet, si l&rsquo;on doit d\u00e9coder le message :<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">1010100011000100011101010000110001001001110010010011001010110100010001100001000011100101000111001010001101010010011010010000110010010001100000010011000010000110000001001110010010011001010110100100001110101000011001010110010001001101010010011101010000110010101110010100011000100011100000100110000001001100101011010000100111010100001101010010011100100100110010101100000100011000010000110010010001110100010011101010000110010101110101011<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">il suffit de rep\u00e9rer les deux \u00ab\u00a01\u00a0\u00bb pour savoir o\u00f9 d\u00e9couper. Ici, on aura donc:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>1010100011, <\/li><li>puis 000100011 (quand il y a 3 \u00ab\u00a01\u00a0\u00bb, il faut ne prendre que les deux premiers &#8211; qui indiquent la fin du codage d&rsquo;un caract\u00e8re &#8211; car l&rsquo;autre 1 correspond au premier chiffre du codage du caract\u00e8re suivant),<\/li><li>puis 10101000011,<\/li><li>etc.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Une fois la d\u00e9coupe faite, il suffit, pour chaque paquet, de supprimer le \u00ab\u00a01\u00a0\u00bb final et de faire le chemin inverse du codage. Par exemple, ici, le premier paquet est 1010100011; on enl\u00e8ve le \u00ab\u00a01\u00a0\u00bb final et on met le r\u00e9sultat dans le tableau:<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-regular\"><table><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><td class=\"has-text-align-center\" data-align=\"center\">2<\/td><td class=\"has-text-align-center\" data-align=\"center\">3<\/td><td class=\"has-text-align-center\" data-align=\"center\">5<\/td><td class=\"has-text-align-center\" data-align=\"center\">8<\/td><td class=\"has-text-align-center\" data-align=\"center\">13<\/td><td class=\"has-text-align-center\" data-align=\"center\">21<\/td><td class=\"has-text-align-center\" data-align=\"center\">34<\/td><td class=\"has-text-align-center\" data-align=\"center\">55<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">$$1+3+8+55=67$$donc le premier paquet est le codage de 67, qui correspond au caract\u00e8re \u00ab\u00a0C\u00a0\u00bb.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Le_codage_de_Fibonacci_en_Python\"><\/span>Le codage de Fibonacci en Python<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Regardons pas \u00e0 pas comment impl\u00e9menter un codage de Fibonacci en Python.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Construction_dune_table_contenant_les_termes_de_la_suite_de_Fibonacci\"><\/span>Construction d&rsquo;une table contenant les termes de la suite de Fibonacci<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"dracula\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"false\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def suite(n):\n    table = [1,1]\n    k = 1\n    while max(table) &lt;= n:\n        table.append( table[k-1] + table[k] )\n        k += 1\n    table.pop()\n    \n    return table[1:]<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">L&rsquo;id\u00e9e est ici d&rsquo;\u00e9crire une fonction <em>suite(n)<\/em> qui retourne tous les termes de \\(F_1\\) \u00e0 \\(F_k\\), o\u00f9 \\(F_k\\leqslant n\\).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"La_fonction_de_codage\"><\/span>La fonction de codage<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">On va d&rsquo;abord commencer par coder un caract\u00e8re:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"dracula\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"false\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def codage_car(c): # codage d'un caract\u00e8re\n    s = 0\n    coef = []\n    F = suite( ord(c) )\n    for i in range( 1 , len(F)+1 ):\n        if s + F[-i] &lt;= ord(c):\n            coef.append(1)\n            s += F[-i]\n        else:\n            coef.append(0)\n    coef.reverse()\n            \n    return ''.join([str(_) for _ in coef]) + '1'<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Ensuite, on impl\u00e9mente une fonction qui code tout un message:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"dracula\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"false\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def codage(message):\n    r = ''\n    for l in message:\n        r += codage_car(l)\n        \n    return r<\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>>>> codage(\"C'est g\u00e9nial!\")\n1010100011000100011101010000110001001001110010010011001010111000010001100000000000110000001001100100100011000010000111001010001110101011<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"La_fonction_de_decodage\"><\/span>La fonction de d\u00e9codage<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">On commence par la fonction qui d\u00e9code un paquet:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"dracula\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"false\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def decodage_car(c):\n    C = list(c[:-1])\n    F = [1,1]\n    for i in range( len(C)-1 ):\n        F.append( F[i] + F[i+1] )\n    \n    G = F[1:]\n    s = 0\n    \n    for i in range( len(C) ):\n        s += G[i]*int(C[i])\n        \n    return chr(s)<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">puis celle qui d\u00e9code le message entier:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"dracula\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"false\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def decode(message):\n    r = ''\n    while len(message) !=0 :\n        p = message.find('11')\n        r += decodage_car(message[:(p+2)])\n        message = message[(p+2):]\n        \n    return r<\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>>>> decodage('1010100011000100011101010000110001001001110010010011001010111000010001100000000000110000001001100100100011000010000111001010001110101011')\nC'est g\u00e9nial!<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Le codage de Fibonacci et Python : mais c&rsquo;est quoi ce codage ? Nous allons avant tout parler math\u00e9matiques, puis nous allons impl\u00e9menter tout \u00e7a en Python.<\/p>\n","protected":false},"author":1,"featured_media":6302,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,5],"tags":[19,292,96],"class_list":["post-6297","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-mathematiques","category-python","tag-chiffrement","tag-codage","tag-fibonacci"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v28.1 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Le codage de Fibonacci et Python - Mathweb.fr - Compression de donn\u00e9es<\/title>\n<meta name=\"description\" content=\"Le codage de Fibonacci peut-\u00eatre impl\u00e9ment\u00e9 en Python, bien \u00e9videmment. Il a une utilit\u00e9 en informatique dans la compression. Voyons cela.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/\" \/>\n<meta property=\"og:locale\" content=\"fr_FR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Le codage de Fibonacci et Python - Mathweb.fr - Compression de donn\u00e9es\" \/>\n<meta property=\"og:description\" content=\"Le codage de Fibonacci peut-\u00eatre impl\u00e9ment\u00e9 en Python, bien \u00e9videmment. Il a une utilit\u00e9 en informatique dans la compression. Voyons cela.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/\" \/>\n<meta property=\"og:site_name\" content=\"Mathweb.fr\" \/>\n<meta property=\"article:published_time\" content=\"2021-06-22T13:29:16+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2021-06-22T13:29:17+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2021\/06\/codage-fibonacci-python.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"740\" \/>\n\t<meta property=\"og:image:height\" content=\"198\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"St\u00e9phane Pasquet\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u00c9crit par\" \/>\n\t<meta name=\"twitter:data1\" content=\"St\u00e9phane Pasquet\" \/>\n\t<meta name=\"twitter:label2\" content=\"Dur\u00e9e de lecture estim\u00e9e\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2021\\\/06\\\/22\\\/le-codage-de-fibonacci-et-python\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2021\\\/06\\\/22\\\/le-codage-de-fibonacci-et-python\\\/\"},\"author\":{\"name\":\"St\u00e9phane Pasquet\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#\\\/schema\\\/person\\\/e4d3bb07968238378f0d5052a70dcd69\"},\"headline\":\"Le codage de Fibonacci et Python\",\"datePublished\":\"2021-06-22T13:29:16+00:00\",\"dateModified\":\"2021-06-22T13:29:17+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2021\\\/06\\\/22\\\/le-codage-de-fibonacci-et-python\\\/\"},\"wordCount\":616,\"commentCount\":2,\"publisher\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#\\\/schema\\\/person\\\/e4d3bb07968238378f0d5052a70dcd69\"},\"image\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2021\\\/06\\\/22\\\/le-codage-de-fibonacci-et-python\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2021\\\/06\\\/codage-fibonacci-python.jpg\",\"keywords\":[\"chiffrement\",\"codage\",\"fibonacci\"],\"articleSection\":[\"Math\u00e9matiques\",\"Python\"],\"inLanguage\":\"fr-FR\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2021\\\/06\\\/22\\\/le-codage-de-fibonacci-et-python\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2021\\\/06\\\/22\\\/le-codage-de-fibonacci-et-python\\\/\",\"url\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2021\\\/06\\\/22\\\/le-codage-de-fibonacci-et-python\\\/\",\"name\":\"Le codage de Fibonacci et Python - Mathweb.fr - Compression de donn\u00e9es\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2021\\\/06\\\/22\\\/le-codage-de-fibonacci-et-python\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2021\\\/06\\\/22\\\/le-codage-de-fibonacci-et-python\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2021\\\/06\\\/codage-fibonacci-python.jpg\",\"datePublished\":\"2021-06-22T13:29:16+00:00\",\"dateModified\":\"2021-06-22T13:29:17+00:00\",\"description\":\"Le codage de Fibonacci peut-\u00eatre impl\u00e9ment\u00e9 en Python, bien \u00e9videmment. Il a une utilit\u00e9 en informatique dans la compression. Voyons cela.\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2021\\\/06\\\/22\\\/le-codage-de-fibonacci-et-python\\\/#breadcrumb\"},\"inLanguage\":\"fr-FR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2021\\\/06\\\/22\\\/le-codage-de-fibonacci-et-python\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2021\\\/06\\\/22\\\/le-codage-de-fibonacci-et-python\\\/#primaryimage\",\"url\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2021\\\/06\\\/codage-fibonacci-python.jpg\",\"contentUrl\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2021\\\/06\\\/codage-fibonacci-python.jpg\",\"width\":740,\"height\":198,\"caption\":\"codage fibonacci python\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2021\\\/06\\\/22\\\/le-codage-de-fibonacci-et-python\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Accueil\",\"item\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Le codage de Fibonacci et Python\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#website\",\"url\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/\",\"name\":\"Mathweb.fr\",\"description\":\"Math\u00e9matiques, LaTeX et Python\",\"publisher\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#\\\/schema\\\/person\\\/e4d3bb07968238378f0d5052a70dcd69\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"fr-FR\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#\\\/schema\\\/person\\\/e4d3bb07968238378f0d5052a70dcd69\",\"name\":\"St\u00e9phane Pasquet\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2025\\\/06\\\/cropped-logo-mathweb.webp\",\"url\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2025\\\/06\\\/cropped-logo-mathweb.webp\",\"contentUrl\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2025\\\/06\\\/cropped-logo-mathweb.webp\",\"width\":74,\"height\":77,\"caption\":\"St\u00e9phane Pasquet\"},\"logo\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2025\\\/06\\\/cropped-logo-mathweb.webp\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Le codage de Fibonacci et Python - Mathweb.fr - Compression de donn\u00e9es","description":"Le codage de Fibonacci peut-\u00eatre impl\u00e9ment\u00e9 en Python, bien \u00e9videmment. Il a une utilit\u00e9 en informatique dans la compression. Voyons cela.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/","og_locale":"fr_FR","og_type":"article","og_title":"Le codage de Fibonacci et Python - Mathweb.fr - Compression de donn\u00e9es","og_description":"Le codage de Fibonacci peut-\u00eatre impl\u00e9ment\u00e9 en Python, bien \u00e9videmment. Il a une utilit\u00e9 en informatique dans la compression. Voyons cela.","og_url":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/","og_site_name":"Mathweb.fr","article_published_time":"2021-06-22T13:29:16+00:00","article_modified_time":"2021-06-22T13:29:17+00:00","og_image":[{"width":740,"height":198,"url":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2021\/06\/codage-fibonacci-python.jpg","type":"image\/jpeg"}],"author":"St\u00e9phane Pasquet","twitter_card":"summary_large_image","twitter_misc":{"\u00c9crit par":"St\u00e9phane Pasquet","Dur\u00e9e de lecture estim\u00e9e":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#article","isPartOf":{"@id":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/"},"author":{"name":"St\u00e9phane Pasquet","@id":"https:\/\/www.mathweb.fr\/euclide\/#\/schema\/person\/e4d3bb07968238378f0d5052a70dcd69"},"headline":"Le codage de Fibonacci et Python","datePublished":"2021-06-22T13:29:16+00:00","dateModified":"2021-06-22T13:29:17+00:00","mainEntityOfPage":{"@id":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/"},"wordCount":616,"commentCount":2,"publisher":{"@id":"https:\/\/www.mathweb.fr\/euclide\/#\/schema\/person\/e4d3bb07968238378f0d5052a70dcd69"},"image":{"@id":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#primaryimage"},"thumbnailUrl":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2021\/06\/codage-fibonacci-python.jpg","keywords":["chiffrement","codage","fibonacci"],"articleSection":["Math\u00e9matiques","Python"],"inLanguage":"fr-FR","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/","url":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/","name":"Le codage de Fibonacci et Python - Mathweb.fr - Compression de donn\u00e9es","isPartOf":{"@id":"https:\/\/www.mathweb.fr\/euclide\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#primaryimage"},"image":{"@id":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#primaryimage"},"thumbnailUrl":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2021\/06\/codage-fibonacci-python.jpg","datePublished":"2021-06-22T13:29:16+00:00","dateModified":"2021-06-22T13:29:17+00:00","description":"Le codage de Fibonacci peut-\u00eatre impl\u00e9ment\u00e9 en Python, bien \u00e9videmment. Il a une utilit\u00e9 en informatique dans la compression. Voyons cela.","breadcrumb":{"@id":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#breadcrumb"},"inLanguage":"fr-FR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/"]}]},{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#primaryimage","url":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2021\/06\/codage-fibonacci-python.jpg","contentUrl":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2021\/06\/codage-fibonacci-python.jpg","width":740,"height":198,"caption":"codage fibonacci python"},{"@type":"BreadcrumbList","@id":"https:\/\/www.mathweb.fr\/euclide\/2021\/06\/22\/le-codage-de-fibonacci-et-python\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Accueil","item":"https:\/\/www.mathweb.fr\/euclide\/"},{"@type":"ListItem","position":2,"name":"Le codage de Fibonacci et Python"}]},{"@type":"WebSite","@id":"https:\/\/www.mathweb.fr\/euclide\/#website","url":"https:\/\/www.mathweb.fr\/euclide\/","name":"Mathweb.fr","description":"Math\u00e9matiques, LaTeX et Python","publisher":{"@id":"https:\/\/www.mathweb.fr\/euclide\/#\/schema\/person\/e4d3bb07968238378f0d5052a70dcd69"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.mathweb.fr\/euclide\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"fr-FR"},{"@type":["Person","Organization"],"@id":"https:\/\/www.mathweb.fr\/euclide\/#\/schema\/person\/e4d3bb07968238378f0d5052a70dcd69","name":"St\u00e9phane Pasquet","image":{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2025\/06\/cropped-logo-mathweb.webp","url":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2025\/06\/cropped-logo-mathweb.webp","contentUrl":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2025\/06\/cropped-logo-mathweb.webp","width":74,"height":77,"caption":"St\u00e9phane Pasquet"},"logo":{"@id":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2025\/06\/cropped-logo-mathweb.webp"}}]}},"_links":{"self":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/posts\/6297","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/comments?post=6297"}],"version-history":[{"count":0,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/posts\/6297\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/media\/6302"}],"wp:attachment":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/media?parent=6297"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/categories?post=6297"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/tags?post=6297"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}