{"cells":[{"metadata":{"hide_input":true,"hide_output":true,"init_cell":true,"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"# Permet de tout executer au lancement du notebook + conserver le notebook actif pendant 2h\nfrom IPython.display import Javascript\nfrom masquer import *\nJavascript(\"\"\"\nfunction repeter(){\nIPython.notebook.kernel.execute(\"a=1\");\n}\n// execute a = 1 en python toutes les 8 minutes pendant 2h\nlet timerId = setInterval(() => repeter(), 4800);\nsetTimeout(() => { clearInterval(timerId); alert('fin de cession'); }, 7200000);\n\n// Supprimer la taille limite pour la sortie d'une cellule\nIPython.OutputArea.prototype._should_scroll = function(lines) {\n    return false;\n};\nIPython.notebook.kernel.execute(\"url = '\" + window.location + \"'\");\n\n// Exécuter toutes les cellule du notebook\n    require(\n        ['base/js/namespace', 'jquery'], \n        function(jupyter, $) {\n            \n                \n                jupyter.actions.call('jupyter-notebook:run-all-cells-below');\n                jupyter.actions.call('jupyter-notebook:save-notebook');\n                Jupyter.actions.call('jupyter-notebook:hide-header')\n\n        }\n    );\"\"\")","execution_count":1,"outputs":[{"output_type":"execute_result","execution_count":1,"data":{"text/plain":"<IPython.core.display.Javascript object>","application/javascript":"\nfunction repeter(){\nIPython.notebook.kernel.execute(\"a=1\");\n}\n// execute a = 1 en python toutes les 8 minutes pendant 2h\nlet timerId = setInterval(() => repeter(), 4800);\nsetTimeout(() => { clearInterval(timerId); alert('fin de cession'); }, 7200000);\n\n// Supprimer la taille limite pour la sortie d'une cellule\nIPython.OutputArea.prototype._should_scroll = function(lines) {\n    return false;\n};\nIPython.notebook.kernel.execute(\"url = '\" + window.location + \"'\");\n\n// Exécuter toutes les cellule du notebook\n    require(\n        ['base/js/namespace', 'jquery'], \n        function(jupyter, $) {\n            \n                \n                jupyter.actions.call('jupyter-notebook:run-all-cells-below');\n                jupyter.actions.call('jupyter-notebook:save-notebook');\n                Jupyter.actions.call('jupyter-notebook:hide-header')\n\n        }\n    );"},"metadata":{}}]},{"metadata":{"hide_input":true,"hide_output":true,"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"from IPython.core.interactiveshell import InteractiveShell\nInteractiveShell.ast_node_interactivity = \"all\"\nHTML(\"\"\"<style>\nh1 {\n  font-family: 'Permanent Marker', cursive;\n  text-align: center;\n  color: red;\n  \n}\nol {\n  list-style-position: inside;\n  margin-left: 1em;\n  list-style-position: outside;\n}\nh2 {\n  font-family: 'Permanent Marker', cursive;\n  color: blue;\n}\nh3 {\n  font-family: 'Permanent Marker', cursive;\n\n}\n</style>\"\"\")","execution_count":3,"outputs":[{"output_type":"execute_result","execution_count":3,"data":{"text/plain":"<IPython.core.display.HTML object>","text/html":"<style>\nh1 {\n  font-family: 'Permanent Marker', cursive;\n  text-align: center;\n  color: red;\n  \n}\nol {\n  list-style-position: inside;\n  margin-left: 1em;\n  list-style-position: outside;\n}\nh2 {\n  font-family: 'Permanent Marker', cursive;\n  color: blue;\n}\nh3 {\n  font-family: 'Permanent Marker', cursive;\n\n}\n</style>"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"# <span style=\"color:red;\"><center>TD_02_2 - S'entrainer à écrire des fonctions récursives</center></span>"},{"metadata":{},"cell_type":"markdown","source":"## Exercice 1. Compter les arbres binaires"},{"metadata":{},"cell_type":"markdown","source":"Un arbre binaire est un arbre pour lequel chaque sommet possède 0 ou 2 fils. Un **noeud** est un sommet possédent deuxfils et une **feuille** est un sommet sans fils. La figure ci-dessous donne trois exemples d'abres binaires pour 0, 1 et 4 noeuds.\n![arbres](img/arbres_binaires.png)\n\n1. Ecrire une fonction tree qui prend comme argument un entier **n** représentant le nombre de noeuds et qui renvoie un entier correspondant au nombre d'arbres binaires possibles à n noeuds.\n2. Dessinez au brouillon tous les arbres possibles pour 3 et 4 noeuds et vérifiez que votre fonction renvoie bien le bon résultat.\n3. Déterminez tree(100) -il faudra peut être améliorer la fonction écrite dans un premier temps-\n"},{"metadata":{"trusted":true},"cell_type":"code","source":"# question 1.\n","execution_count":7,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# question 3.\n","execution_count":8,"outputs":[]},{"metadata":{"run_control":{"marked":false},"trusted":true},"cell_type":"markdown","source":"## Exercice 2. La fonction puissance"},{"metadata":{},"cell_type":"markdown","source":"1. Ecrire une fonction **puissance** récursive qui prend en argument un float **x** et un entier positif ou nul **n** et qui renvoie la valeur de $x^n$ calculée par $x^0 = 1$ et $x^n = x \\times x^{n-1}$\n\n2. Ecrire une fonction **puissance_rapide** récursive qui prend en argument un float **x** et un entier positif ou nul **n** et qui renvoie la valeur de $x^n$ calculée par $x^0 = 1$ et $x^n = x^{n//2} \\times x^{n//2}$ si n est pair et $x^n = x \\times x^{n//2} \\times x^{n//2}$ si n est impair.\n\n3. Expliquer ce qu'apporte la deuxième fonction par rapport à la première."},{"metadata":{"trusted":true},"cell_type":"code","source":"# Question 1.\n","execution_count":5,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Question 2.\n","execution_count":6,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"*Question 3* ***Répondre ici***"},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"## Exercice 3. Recherche de caractère"},{"metadata":{},"cell_type":"markdown","source":"1. Ecrire une fonction récursive **cherche** qui prend comme argument une chaine de caractères **ligne** et un caractère **cara** et qui renvoie le nombre d'occurences de la lettre dans la ligne.\n2. Ecrire une fonction récursive **indice** qui prend comme argument une chaine de caractères **ligne** et un caractère **cara** et qui renvoie l'indice de la première occurence du caractère dans la ligne et None s'il n'y est pas."},{"metadata":{"trusted":true},"cell_type":"code","source":"# question 1\n","execution_count":9,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# question 2\n","execution_count":10,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Exercice 4. Recherche Vs Recherche dichotomique"},{"metadata":{},"cell_type":"markdown","source":"1. Ecrire une fonction **recherche** qui prend en argument une liste de mots triée, et un mot à rechercher à l'intérieur et qui doit renvoyer l'indice correspondant par balayage d ela liste.\n2. Même question dans le cas d'une recherche dichotomique.\n3. Expliquer l'intérêt de la recherche dichotomique dans ce cas.\n4. Serait-il efficace de lancer un algorithme de tri sur une longue liste puis effectuer une recherche dichotomique ou de lancer directement une recherche par balayage ? Justifier"},{"metadata":{"trusted":true},"cell_type":"code","source":"# question 1.\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# question 2.\n","execution_count":11,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"*question 3.* ***Repondre ici***"},{"metadata":{},"cell_type":"markdown","source":"*question 4* ***Répondre ici***"}],"metadata":{"celltoolbar":"none","kernelspec":{"name":"python3","display_name":"Python 3","language":"python"},"language_info":{"name":"python","version":"3.7.8","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"},"varInspector":{"cols":{"lenName":16,"lenType":16,"lenVar":40},"kernels_config":{"python":{"delete_cmd_postfix":"","delete_cmd_prefix":"del ","library":"var_list.py","varRefreshCmd":"print(var_dic_list())"},"r":{"delete_cmd_postfix":") ","delete_cmd_prefix":"rm(","library":"var_list.r","varRefreshCmd":"cat(var_dic_list()) "}},"types_to_exclude":["module","function","builtin_function_or_method","instance","_Feature"],"window_display":false}},"nbformat":4,"nbformat_minor":4}