{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2fb131ad",
   "metadata": {},
   "source": [
    "# Monter les marches\n",
    "## Corrigé"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1a9af15",
   "metadata": {},
   "source": [
    "## Étape 2 — Fonction récursive simple\n",
    "\n",
    "La récurrence vient du fait qu'on arrive à la marche n soit depuis n-1 (saut de 1), soit depuis n-2 (saut de 2)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "05671177",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n"
     ]
    }
   ],
   "source": [
    "def nb_facons(n):\n",
    "    if n == 0 or n == 1:\n",
    "        return 1\n",
    "    # On additionne les façons d'arriver à n-1 et à n-2\n",
    "    return nb_facons(n-1) + nb_facons(n-2)\n",
    "\n",
    "print(nb_facons(5))  # 8"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "37714a0b",
   "metadata": {},
   "source": [
    "## Étape 3 — Visualisation des appels récursifs\n",
    "\n",
    "On incrémente le compteur à chaque appel pour voir l'explosion du nombre d'appels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "6b727457",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "89\n",
      "Appels : 177\n"
     ]
    }
   ],
   "source": [
    "compteur = 0\n",
    "\n",
    "def nb_facons_compteur(n):\n",
    "    global compteur\n",
    "    compteur += 1\n",
    "    if n == 0 or n == 1:\n",
    "        return 1\n",
    "    return nb_facons_compteur(n-1) + nb_facons_compteur(n-2)\n",
    "\n",
    "compteur = 0\n",
    "print(nb_facons_compteur(10))\n",
    "print('Appels :', compteur)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78a3bb54",
   "metadata": {},
   "source": [
    "## Étape 4 — Mémoïsation\n",
    "\n",
    "On stocke les résultats déjà calculés pour éviter les recalculs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "72fdf9e6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1346269\n"
     ]
    }
   ],
   "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] = nb_facons_memo(n-1, memo) + nb_facons_memo(n-2, memo)\n",
    "    return memo[n]\n",
    "\n",
    "print(nb_facons_memo(30))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce25b2fe",
   "metadata": {},
   "source": [
    "## Étape 5 — Programmation dynamique\n",
    "\n",
    "On construit un tableau de bas en haut avec les solutions déjà connues."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "4fc3a7c7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1346269\n"
     ]
    }
   ],
   "source": [
    "def nb_facons_dp(n):\n",
    "    dp = [0] * (n+1)\n",
    "    dp[0], dp[1] = 1, 1\n",
    "    for i in range(2, n+1):\n",
    "        dp[i] = dp[i-1] + dp[i-2]\n",
    "    return dp[n]\n",
    "\n",
    "print(nb_facons_dp(30))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d034b38",
   "metadata": {},
   "source": [
    "## Étape 6 — Optimisation mémoire\n",
    "\n",
    "On garde seulement les deux dernières valeurs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "0967c0db",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1346269\n"
     ]
    }
   ],
   "source": [
    "def nb_facons_optimise(n):\n",
    "    a, b = 1, 1\n",
    "    for _ in range(2, n+1):\n",
    "        a, b = b, a + b\n",
    "    return b\n",
    "\n",
    "print(nb_facons_optimise(30))"
   ]
  }
 ],
 "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
}