{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.e - Correction de l'interrogation \u00e9crite du 14 novembre 2014\n", "\n", "dictionnaires"]}, {"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\u00e9 1"]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Q1\n", "\n", "Le code suivant produit une erreur. Laquelle ?"]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": ["def make_squares(n):\n", "    squares = [i**2 for i in range(n)]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Comme il n'y a pas d'instruction return, la fonction retourne toujours ``None`` quelque chose le r\u00e9sultat de ce qu'elle calcule."]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["None\n"]}], "source": ["def make_squares(n):\n", "    squares = [i**2 for i in range(n)]\n", "print ( make_squares(2) )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Q2\n", "\n", "Que vaut ``a`` ?"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": ["s = 1\n", "a = 0\n", "for i in range(4):\n", "    a += s\n", "    s += 2"]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"data": {"text/plain": ["16"]}, "execution_count": 6, "metadata": {}, "output_type": "execute_result"}], "source": ["a"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Si on affiche les r\u00e9sultats interm\u00e9diaires :"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["0 1\n", "1 3\n", "4 5\n", "9 7\n"]}, {"data": {"text/plain": ["16"]}, "execution_count": 7, "metadata": {}, "output_type": "execute_result"}], "source": ["s = 1\n", "a = 0\n", "for i in range(4):\n", "    print(a,s)\n", "    a += s\n", "    s += 2\n", "    \n", "a"]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Q3\n", "\n", "On rappelle que ``ord('a')=97``. Que vaut ``x`` ?"]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": ["d = {i:chr(i+97) for i in range(10)}\n", "x = d[4]"]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"data": {"text/plain": ["'e'"]}, "execution_count": 9, "metadata": {}, "output_type": "execute_result"}], "source": ["x"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Il suffit de remplacer ``i`` par 4. ``x`` vaut ``chr(97+4)`` et on se d\u00e9place de 4 lettres dans l'alphabet, soit ``e``."]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Q4\n", "\n", "Que fait le programme suivant ?"]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["(['Alice', 'Claire', 'Bob'], 18)\n"]}], "source": ["notes = { \"Alice\": 17, \"Bob\": 18, \"Jean\u2212Ma\": 17 }\n", "notes['Claire'] = 18\n", "\n", "def mystere(d):\n", "    a = 0\n", "    b = []\n", "    for k,v in d.items():\n", "        if v >= a:\n", "            a = v\n", "            b.append(k)\n", "    return (b,a)\n", "\n", "print(mystere(notes))"]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [{"data": {"text/plain": ["{'Alice': 17, 'Claire': 18, 'Bob': 18, 'Jean\u2212Ma': 17}"]}, "execution_count": 11, "metadata": {}, "output_type": "execute_result"}], "source": ["notes"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le programme commence par ajouter la cl\u00e9 ``Claire`` au dictionnaire. La variable ``a`` m\u00e9morise la valeur num\u00e9rique la plus grande. En l'\u00e9tat, le r\u00e9sultat programme est assez impr\u00e9visible puisqu'il d\u00e9pend de l'ordre dans lequel on parcourt les \u00e9l\u00e9ments. Je pense que la fonction devrait r\u00e9cup\u00e9rer dans une liste l'ensemble des pr\u00e9noms correspondant \u00e0 cette valeur maximale s'il \u00e9tait \u00e9crit comme ceci :"]}, {"cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["(['Claire', 'Bob'], 18)\n"]}], "source": ["notes = { \"Alice\": 17, \"Bob\": 18, \"Jean\u2212Ma\": 17 }\n", "notes['Claire'] = 18\n", "\n", "def mystere(d):\n", "    a = 0\n", "    b = []\n", "    for k,v in d.items():\n", "        if v == a:\n", "            b.append(k)\n", "        elif v > a:\n", "            a = v\n", "            b = [ k ]\n", "    return (b,a)\n", "\n", "print(mystere(notes))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Q5\n", "\n", "Que renvoie la fonction suivante en fonction de ``n`` ?"]}, {"cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": ["def f(n):\n", "    while n != 1:\n", "        if n%2 == 0:\n", "            n = n/2\n", "        else:\n", "            n = 3*n + 1\n", "    return n"]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [{"data": {"text/plain": ["1.0"]}, "execution_count": 14, "metadata": {}, "output_type": "execute_result"}], "source": ["f(3)"]}, {"cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [{"data": {"text/plain": ["1.0"]}, "execution_count": 15, "metadata": {}, "output_type": "execute_result"}], "source": ["f(4)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["D'apr\u00e8s la condition indiqu\u00e9e dans la boucle ``while``, la fonction retourne 1. Reste \u00e0 savoir si cela est toujours possible quelque soit $n$. Cette question \u00e9tait un peu hors sujet. Il faudrait \u00e9tudier la convergence de la suite $u_{n+1}=f(u_n)$ o\u00f9 $f$ est la fonction :\n", "\n", "$f(n) = \\left\\{ \\begin{array}{ll} \\frac{n}{2} & si \\; n \\; pair \\\\ 3n+1 &sinon \\end{array}\\right.$\n", "\n", "Ce probl\u00e8me n'est pas \u00e9vident puisqu'il ressemble beaucoup \u00e0 la [conjecture de Syracuse](http://fr.wikipedia.org/wiki/Conjecture_de_Syracuse)."]}, {"cell_type": "code", "execution_count": 15, "metadata": {}, "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}