{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "054147e7",
   "metadata": {},
   "source": [
    "# Monter les marches\n",
    "\n",
    "Un enfant veut monter un escalier de `n` marches. À chaque pas, il peut monter soit 1, soit 2 marches.\n",
    "\n",
    "On veut déterminer de combien de façons différentes il peut monter tout l’escalier."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1853b7ad",
   "metadata": {},
   "source": [
    "## Étape 1 — Explorer le problème\n",
    "\n",
    "**Question 1.1** : Lister toutes les façons de monter 1, 2, puis 3 marches.\n",
    "\n",
    "**Question 1.2** : Donner explicitement les valeurs de f(1), f(2), f(3), f(4).\n",
    "\n",
    "**Question 1.3** : Quelle relation de récurrence obtient-on ? (Expliquez pourquoi.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "febb61a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ou code ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8b92b5c",
   "metadata": {},
   "source": [
    "## Étape 2 — Fonction récursive simple\n",
    "**Question 2** : Complétez la fonction récursive ci-dessous, puis testez-la avec différentes valeurs de n."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6cfac0c4",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def nb_facons(n):\n",
    "    if n == 0 or n == 1:\n",
    "        return 1\n",
    "    # Complétez la ligne suivante pour la récursion\n",
    "    return ... # à compléter\n",
    "\n",
    "# Exemple de test\n",
    "print(nb_facons(5))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf26253c",
   "metadata": {},
   "source": [
    "## Étape 3 — Visualisation des appels récursifs\n",
    "**Question 3** : Ajoutez un compteur global pour afficher le nombre d'appels récursifs pour n = 10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "42e014a0",
   "metadata": {},
   "outputs": [],
   "source": [
    "compteur = 0\n",
    "\n",
    "def nb_facons_compteur(n):\n",
    "    global compteur\n",
    "    compteur ...\n",
    "    if n == 0 or n == 1:\n",
    "        return 1\n",
    "    return ... # à compléter\n",
    "\n",
    "compteur = 0\n",
    "print(nb_facons_compteur(10))\n",
    "print('Nombre d\\'appels récursifs :', compteur)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6c54046",
   "metadata": {},
   "source": [
    "## Étape 4 — Optimisation par mémoïsation\n",
    "**Question 4** : Complétez la version mémoïsée ci-dessous."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "481bb2f9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nb_facons_memo(n, memo={}):\n",
    "    if n in memo:\n",
    "        return memo[n]\n",
    "    if n == 0 or n == 1:\n",
    "        memo[n] = 1\n",
    "    else:\n",
    "        memo[n] = ... # à compléter\n",
    "    return memo[n]\n",
    "\n",
    "# Test\n",
    "print(nb_facons_memo(30))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc1a3368",
   "metadata": {},
   "source": [
    "## Étape 5 — Programmation dynamique itérative\n",
    "**Question 5** : Complétez la version itérative (bottom-up) ci-dessous."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a7ddf0e9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nb_facons_dp(n):\n",
    "    dp = [0]*(n+1)\n",
    "    dp[0] = 1\n",
    "    if n > 0:\n",
    "        dp[1] = 1\n",
    "    for i in range(2, n+1):\n",
    "        dp[i] = ... # à compléter\n",
    "    return dp[n]\n",
    "\n",
    "print(nb_facons_dp(30))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c71927fe",
   "metadata": {},
   "source": [
    "## Étape 6 — Optimisation mémoire supplémentaire\n",
    "**Question 6** : Complétez la version qui utilise seulement deux variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "08b4b859",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nb_facons_optimise(n):\n",
    "    a, b = 1, 1\n",
    "    for _ in range(2, n+1):\n",
    "        a, b = b, ... # à compléter\n",
    "    return b\n",
    "\n",
    "print(nb_facons_optimise(30))\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}