{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.algo - Calculer le nombre de fa\u00e7ons de monter une \u00e9chelle.\n", "\n", "Une grenouille monte une \u00e9chelle. Elle peut faire des bonds de un ou deux barreaux. Combien a-t-elle de fa\u00e7ons de monter une \u00e9chelle de treize barreaux ? Notion abord\u00e9e : fonction r\u00e9cursive."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["<div id=\"my_id_menu_nb\">run previous cell, wait for 2 seconds</div>\n", "<script>\n", "function repeat_indent_string(n){\n", "    var a = \"\" ;\n", "    for ( ; n > 0 ; --n)\n", "        a += \"    \";\n", "    return a;\n", "}\n", "var update_menu_string = function(begin, lfirst, llast, sformat, send, keep_item, begin_format, end_format) {\n", "    var anchors = document.getElementsByClassName(\"section\");\n", "    if (anchors.length == 0) {\n", "        anchors = document.getElementsByClassName(\"text_cell_render rendered_html\");\n", "    }\n", "    var i,t;\n", "    var text_menu = begin;\n", "    var text_memo = \"<pre>\\nlength:\" + anchors.length + \"\\n\";\n", "    var ind = \"\";\n", "    var memo_level = 1;\n", "    var href;\n", "    var tags = [];\n", "    var main_item = 0;\n", "    var format_open = 0;\n", "    for (i = 0; i <= llast; i++)\n", "        tags.push(\"h\" + i);\n", "\n", "    for (i = 0; i < anchors.length; i++) {\n", "        text_memo += \"**\" + anchors[i].id + \"--\\n\";\n", "\n", "        var child = null;\n", "        for(t = 0; t < tags.length; t++) {\n", "            var r = anchors[i].getElementsByTagName(tags[t]);\n", "            if (r.length > 0) {\n", "child = r[0];\n", "break;\n", "            }\n", "        }\n", "        if (child == null) {\n", "            text_memo += \"null\\n\";\n", "            continue;\n", "        }\n", "        if (anchors[i].hasAttribute(\"id\")) {\n", "            // when converted in RST\n", "            href = anchors[i].id;\n", "            text_memo += \"#1-\" + href;\n", "            // passer \u00e0 child suivant (le chercher)\n", "        }\n", "        else if (child.hasAttribute(\"id\")) {\n", "            // in a notebook\n", "            href = child.id;\n", "            text_memo += \"#2-\" + href;\n", "        }\n", "        else {\n", "            text_memo += \"#3-\" + \"*\" + \"\\n\";\n", "            continue;\n", "        }\n", "        var title = child.textContent;\n", "        var level = parseInt(child.tagName.substring(1,2));\n", "\n", "        text_memo += \"--\" + level + \"?\" + lfirst + \"--\" + title + \"\\n\";\n", "\n", "        if ((level < lfirst) || (level > llast)) {\n", "            continue ;\n", "        }\n", "        if (title.endsWith('\u00b6')) {\n", "            title = title.substring(0,title.length-1).replace(\"<\", \"&lt;\")\n", "         .replace(\">\", \"&gt;\").replace(\"&\", \"&amp;\");\n", "        }\n", "        if (title.length == 0) {\n", "            continue;\n", "        }\n", "\n", "        while (level < memo_level) {\n", "            text_menu += end_format + \"</ul>\\n\";\n", "            format_open -= 1;\n", "            memo_level -= 1;\n", "        }\n", "        if (level == lfirst) {\n", "            main_item += 1;\n", "        }\n", "        if (keep_item != -1 && main_item != keep_item + 1) {\n", "            // alert(main_item + \" - \" + level + \" - \" + keep_item);\n", "            continue;\n", "        }\n", "        while (level > memo_level) {\n", "            text_menu += \"<ul>\\n\";\n", "            memo_level += 1;\n", "        }\n", "        text_menu += repeat_indent_string(level-2);\n", "        text_menu += begin_format + sformat.replace(\"__HREF__\", href).replace(\"__TITLE__\", title);\n", "        format_open += 1;\n", "    }\n", "    while (1 < memo_level) {\n", "        text_menu += end_format + \"</ul>\\n\";\n", "        memo_level -= 1;\n", "        format_open -= 1;\n", "    }\n", "    text_menu += send;\n", "    //text_menu += \"\\n\" + text_memo;\n", "\n", "    while (format_open > 0) {\n", "        text_menu += end_format;\n", "        format_open -= 1;\n", "    }\n", "    return text_menu;\n", "};\n", "var update_menu = function() {\n", "    var sbegin = \"\";\n", "    var sformat = '<a href=\"#__HREF__\">__TITLE__</a>';\n", "    var send = \"\";\n", "    var begin_format = '<li>';\n", "    var end_format = '</li>';\n", "    var keep_item = -1;\n", "    var text_menu = update_menu_string(sbegin, 2, 4, sformat, send, keep_item,\n", "       begin_format, end_format);\n", "    var menu = document.getElementById(\"my_id_menu_nb\");\n", "    menu.innerHTML=text_menu;\n", "};\n", "window.setTimeout(update_menu,2000);\n", "            </script>"], "text/plain": ["<IPython.core.display.HTML object>"]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Enonc\u00e9s"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Enonc\u00e9 1\n", "\n", "On suppose qu'une grenouille peut montrer une \u00e9chelle de 13 barreaux avec des sauts de 1 ou 2 barreaux. Combien a-t-elle de fa\u00e7ons de monter les 13 premiers barreaux ?"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Enonc\u00e9 2\n", "\n", "Le probl\u00e8me est presque le m\u00eame except\u00e9 que l'\u00e9paisseur des barreaux est plus ou moins grande. L'\u00e9paisseur du barreau $i$ est un entier $e_i > 0$. Arriv\u00e9e au barreau $i$, la grenouille peut faire un bond de $k$ barreaux avec $k \\leqslant e_i$. La grenouille commence toujours au barreau."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Enonc\u00e9 3\n", "\n", "On consid\u00e8re la grenouille de l'\u00e9nonc\u00e9 2 mais on souhaite conna\u00eetre le chemin pour lequel la grenouille a fait le moins de bonds possible."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Solutions"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Solution au probl\u00e8me 1\n", "\n", "L'id\u00e9e de d\u00e9part consiste \u00e0 consid\u00e9rer le probl\u00e8me par r\u00e9currence. D'o\u00f9 la grenouille peut-elle venir si elle est au barreau $n$ ? La r\u00e9ponse est assez simple :\n", "- elle a pu venir du barreau $n-1$ avec un saut de un barreau,\n", "- elle a pu venir du barreau $n-2$ avec un saut de deux barreaux\n", "\n", "On obtient la formule de r\u00e9currence suivante : $f(n) = f(n-1) + f(n-2)$. C'est une [suite de Fibonacci](http://fr.wikipedia.org/wiki/Suite_de_Fibonacci)."]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["barreau 0 : 1 fa\u00e7ons de monter\n", "barreau 1 : 1 fa\u00e7ons de monter\n", "barreau 2 : 2 fa\u00e7ons de monter\n", "barreau 3 : 3 fa\u00e7ons de monter\n", "barreau 4 : 5 fa\u00e7ons de monter\n", "barreau 5 : 8 fa\u00e7ons de monter\n", "barreau 6 : 13 fa\u00e7ons de monter\n", "barreau 7 : 21 fa\u00e7ons de monter\n", "barreau 8 : 34 fa\u00e7ons de monter\n", "barreau 9 : 55 fa\u00e7ons de monter\n", "barreau 10 : 89 fa\u00e7ons de monter\n", "barreau 11 : 144 fa\u00e7ons de monter\n", "barreau 12 : 233 fa\u00e7ons de monter\n", "barreau 13 : 377 fa\u00e7ons de monter\n"]}], "source": ["def grenouille(n):\n", "    a = 1  # 1 fa\u00e7on d'arriver au barreau 0\n", "    b = 1  # 1 fa\u00e7on d'arriver au barreau 1\n", "    i = 1\n", "    while i < n :\n", "        a,b = b, a + b\n", "        i += 1\n", "    return b\n", "\n", "for i in range(0,14) :\n", "    print ( \"barreau {0} : {1} fa\u00e7ons de monter\".format( i, grenouille(i) ) )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Solution au probl\u00e8me 2\n", "\n", "La solution au second probl\u00e8me est presque la m\u00eame. L'id\u00e9e de d\u00e9part consiste toujours \u00e0 consid\u00e9rer le probl\u00e8me par r\u00e9currence. D'o\u00f9 la grenouille peut-elle venir si elle est au barreau $n$ ? La r\u00e9ponse est assez simple :\n", "- elle a pu venir du barreau $n-1$ avec un saut de un barreau si $e_{n-1} \\geqslant 1$\n", "- elle a pu venir du barreau $n-2$ avec un saut de deux barreaux si $e_{n-2} \\geqslant 2$\n", "- elle a pu venir du barreau $n-k$ avec un saut de deux barreaux si $e_{n-k} \\geqslant k$"]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["barreau 0 : 1 = 1 fa\u00e7ons de monter\n", "barreau 1 : 1 = 1 fa\u00e7ons de monter\n", "barreau 2 : 2 = 1 fa\u00e7ons de monter\n", "barreau 3 : 3 = 2 fa\u00e7ons de monter\n", "barreau 4 : 5 = 3 fa\u00e7ons de monter\n", "barreau 5 : 8 = 5 fa\u00e7ons de monter\n", "barreau 6 : 13 = 8 fa\u00e7ons de monter\n", "barreau 7 : 21 = 13 fa\u00e7ons de monter\n", "barreau 8 : 34 = 21 fa\u00e7ons de monter\n", "barreau 9 : 55 = 34 fa\u00e7ons de monter\n", "barreau 10 : 89 = 55 fa\u00e7ons de monter\n", "barreau 11 : 144 = 89 fa\u00e7ons de monter\n", "barreau 12 : 233 = 144 fa\u00e7ons de monter\n", "barreau 13 : 377 = 233 fa\u00e7ons de monter\n"]}], "source": ["def grenouille2(n, barreaux):\n", "    nb = [ 1,1] # 1 fa\u00e7on d'arriver au barreau 0 ou 1\n", "    while len(nb) < n:\n", "        s = 0\n", "        i = len(nb)\n", "        for k in range(0, i):\n", "            if barreaux[i-k-1] >= k+1:\n", "                s += nb[i-k-1]\n", "        nb.append(s)\n", "        i += 1\n", "    return nb[-1]\n", "\n", "# on regarde si on obtient le m\u00eame r\u00e9sultat que pr\u00e9c\u00e9demment\n", "g1 = [ 2 for i in range(0,14) ]\n", "for i in range(0,14) :\n", "    print ( \"barreau {0} : {1} = {2} fa\u00e7ons de monter\".format( i, grenouille(i), grenouille2(i,g1) ) )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La solution est l\u00e9g\u00e8rement diff\u00e9rente car contrairement au premier \u00e9nonc\u00e9, la grenouille ne peut aller directement au barreau 2. On essaye avec un autre example trivial mais qui permet de s'assurer que la fonction retourne bien le r\u00e9sultat voulu."]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["barreau 0 : 1 fa\u00e7ons de monter\n", "barreau 1 : 1 fa\u00e7ons de monter\n", "barreau 2 : 1 fa\u00e7ons de monter\n", "barreau 3 : 1 fa\u00e7ons de monter\n", "barreau 4 : 1 fa\u00e7ons de monter\n", "barreau 5 : 1 fa\u00e7ons de monter\n", "barreau 6 : 1 fa\u00e7ons de monter\n", "barreau 7 : 2 fa\u00e7ons de monter\n", "barreau 8 : 3 fa\u00e7ons de monter\n", "barreau 9 : 3 fa\u00e7ons de monter\n", "barreau 10 : 3 fa\u00e7ons de monter\n", "barreau 11 : 3 fa\u00e7ons de monter\n", "barreau 12 : 3 fa\u00e7ons de monter\n", "barreau 13 : 3 fa\u00e7ons de monter\n"]}], "source": ["g2 = [ 1 for i in range(0,14) ]\n", "g2[4] = 3\n", "for i in range(0,14) :\n", "    print ( \"barreau {0} : {1} fa\u00e7ons de monter\".format( i, grenouille2(i,g2) ) )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Solution au probl\u00e8me 3\n", "\n", "Pour ce probl\u00e8me, la solution est quasi identique except\u00e9 qu'au lieu de sommer les nombres de chemins, on souhaite garder le nombre de bonds du chemin qui en contient le moins."]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["barreau 0 : 1 bonds pour le chemin qui en contient le moins\n", "barreau 1 : 1 bonds pour le chemin qui en contient le moins\n", "barreau 2 : 1 bonds pour le chemin qui en contient le moins\n", "barreau 3 : 2 bonds pour le chemin qui en contient le moins\n", "barreau 4 : 2 bonds pour le chemin qui en contient le moins\n", "barreau 5 : 3 bonds pour le chemin qui en contient le moins\n", "barreau 6 : 3 bonds pour le chemin qui en contient le moins\n", "barreau 7 : 4 bonds pour le chemin qui en contient le moins\n", "barreau 8 : 4 bonds pour le chemin qui en contient le moins\n", "barreau 9 : 5 bonds pour le chemin qui en contient le moins\n", "barreau 10 : 5 bonds pour le chemin qui en contient le moins\n", "barreau 11 : 6 bonds pour le chemin qui en contient le moins\n", "barreau 12 : 6 bonds pour le chemin qui en contient le moins\n", "barreau 13 : 7 bonds pour le chemin qui en contient le moins\n"]}], "source": ["def grenouille3(n, barreaux):\n", "    nb = [ 1,1] # 1 fa\u00e7on d'arriver au barreau 0 ou 1\n", "    while len(nb) < n:\n", "        s = 0\n", "        i = len(nb)\n", "        for k in range(0, i):\n", "            if barreaux[i-k-1] >= k+1 and (s == 0 or nb[i-k-1] < s) :\n", "                # on prend le miminum\n", "                s = nb[i-k-1]\n", "        nb.append(s+1)\n", "        i += 1\n", "    return nb[-1]\n", "\n", "g1 = [ 2 for i in range(0,14) ]\n", "for i in range(0,14) :\n", "    print ( \"barreau {0} : {1} bonds pour le chemin qui en contient le moins\".format( i, grenouille3(i,g1) ) )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Si on veut conserver le chemin pr\u00e9cis qui contient le moins de bonds possibles, il suffit de m\u00e9moriser le barreau pr\u00e9c\u00e9dent $i$ que la grenouille a emprunt\u00e9 pour aller en un minimum de bonds au barreau $n$ : on conserve en m\u00e9moire le **pr\u00e9d\u00e9cesseur**. Pour construire le meilleur chemin, on remonte de pr\u00e9d\u00e9cesseur en pr\u00e9d\u00e9cesseur."]}, {"cell_type": "code", "execution_count": 6, "metadata": {"collapsed": true}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}, "language_info": {"codemirror_mode": {"name": "ipython", "version": 3}, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.1"}}, "nbformat": 4, "nbformat_minor": 2}