{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ee6956f6",
   "metadata": {},
   "source": [
    "# Feuille d'exercices 2 -- avancé\n",
    "\n",
    "\n",
    "```{warning} \n",
    "Ces exercices sont prévus pour les étudiant·e·s ayant déjà réussi la feuille d'exercices \"classiques\".\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Exercice 7 : suite récurrente d'ordre 2\n",
    "\n",
    "\n",
    "On considère la suite récurrente d'ordre $2$, dite de **Fibonacci**, définie par\n",
    "\n",
    "$$\n",
    "F_0 = 0, \\; F_1 = 1 \\quad \\text{ et } \\quad F_{n+2} = F_{n+1} + F_n, \\; \\forall n \\ge 0\n",
    "$$\n",
    "\n",
    "**Question 1.** Écrire une fonction `fibonacci_iter(n)` qui calcule la valeur de $F_n$ de manière itérative (c'est-à-dire, sans que la fonction s'appelle elle-même).\n",
    "\n",
    "On vérifiera entre autres que $F_{10} = 55$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c8322a42",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci_iter(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    elif n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        Fn = 0\n",
    "        Fn1 = 1\n",
    "        for j in range(2, n+1):\n",
    "            Fn2 = Fn1 + Fn\n",
    "            Fn = Fn1\n",
    "            Fn1 = Fn2\n",
    "        return Fn2\n",
    "        \n",
    "print(fibonacci_iter(0))\n",
    "print(fibonacci_iter(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d9e724c",
   "metadata": {},
   "source": [
    "**Question 2.** Écrire une fonction `fibonacci_rec(n)` qui calcule la valeur de $F_n$ de manière récursive (attention, ne tester cette fonction qu'avec de petites valeurs, typiquement inférieures à $25$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7a6e1851",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci_rec(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    elif n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return fibonacci_rec(n-1) + fibonacci_rec(n-2)\n",
    "        \n",
    "print(fibonacci_rec(0))\n",
    "print(fibonacci_rec(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e11df37",
   "metadata": {},
   "source": [
    "**Question 3 (plus difficile).** Pour $n = 32$, la fonction `fibonacci_rec(n)` devrait prendre quelques secondes à être évaluée. Ce n'est pas du tout le cas de `fibonacci_iter`, qui calcule même $F_{10000}$ instantanément. Avez-vous une explication pour ce phénomène ?\n",
    "\n",
    "**Réponse.** L'explication est la suivante : pour calculer de manière récursive $F_n$, la fonction `fibonacci_rec` s'appelle elle-même sur l'entrée $n-1$ et l'entrée $n-2$. Or pour calculer $F_{n-1}$, on a également besoin de $F_{n-2}$ et de $F_{n-3}$. Par conséquent, la fonction `fibonacci_rec` est appelée deux fois sur l'entrée $n-2$, alors qu'une seule suffirait.\n",
    "\n",
    "Puis, ce \"gâchis\" est répété (et s'empire) pur calculer $F_{n-3}$, $F_{n-4}$, etc. Au bout du compte, le nombre d'appels à `fibonacci_rec` est immense : de l'ordre de $7$ millions d'appels pour calculer $F_{32}$...\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Exercice 8 : triangle de Pascal\n",
    "\n",
    "Le **triangle de Pascal** est la donnée de tous les coefficients binomiaux $\\binom{n}{k}$, pour $0 \\le k \\le n \\le N$ où l'entier $N$ est appelé l'ordre du triangle. Usuellement, on dispose l'ensemble des coefficients binomiaux sous la forme d'un triangle, d'où le nom. Le coefficient binomial $\\binom{0}{0} = 1$ est placé en haut à gauche. Puis, sur la ligne suivante on dispose $\\binom{1}{0} = 1$ et $\\binom{1}{1} = 1$. À la troisième ligne $\\binom{2}{0} = 1$, $\\binom{2}{1} = 2$, $\\binom{2}{2} = 1$, etc.\n",
    "\n",
    "$$\n",
    "\\begin{array}{cccc}\n",
    "\\binom{0}{0} & & & \\\\\n",
    "\\binom{1}{0} & \\binom{1}{1} & & \\\\\n",
    "\\binom{2}{0} & \\binom{2}{1} & \\binom{2}{2} & \\\\\n",
    "\\binom{3}{0} & \\binom{3}{1} & \\binom{3}{2} & \\binom{3}{3}\\\\\n",
    "\\end{array}~\\;~=~\\;~\n",
    "\\begin{array}{cccc}\n",
    "1 & & & \\\\\n",
    "1 & 1 & & \\\\\n",
    "1 & 2 & 1&  \\\\\n",
    "1 & 3 & 3& 1 \\\\\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "Pour calculer le triangle, l'idée de commencer à calculer le coefficient binomial pour $n = 0$, puis d'utiliser la **formule de Pascal** (une nouvelle fois, d'où le nom), valable pour tout $n \\ge 0$ et tout $k \\ge 1$ en admettant que $\\binom{i}{j} = 0$ si $j > i$ :\n",
    "\n",
    "$$\n",
    "\\binom{n+1}{k} = \\binom{n}{k-1} + \\binom{n}{k}\\,.\n",
    "$$\n",
    "\n",
    "Pour calculer $\\binom{n+1}{k}$, on peut donc sommer $\\binom{n}{k-1}$ et $\\binom{n}{k}$, qui sont deux valeurs précédemment calculées. Cela permet d'économiser un grand nombre de calculs de factorielles.\n",
    "\n",
    "\n",
    "\n",
    "**Question 1 :** Implanter une fonction `triangle_pascal(N)` qui retourne le triangle de Pascal d'ordre ``N``, sous la forme d'une liste `L` comportant `N+1` sous-listes, telle que la $j$-ème liste contient l'ensemble des binomiaux de la forme $\\binom{j}{i}$ pour $0 \\le i \\le j$.\n",
    "\n",
    "Par exemple, pour ``N = 6``, la fonction `triangle_pascal(N)` doit retourner :\n",
    "```\n",
    "[[1],\n",
    " [1, 1],\n",
    " [1, 2, 1],\n",
    " [1, 3, 3, 1],\n",
    " [1, 4, 6, 4, 1],\n",
    " [1, 5, 10, 10, 5, 1],\n",
    " [1, 6, 15, 20, 15, 6, 1]]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8959174e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def triangle_pascal(N):\n",
    "    L = [[1]]\n",
    "    for n in range(1, N+1):\n",
    "        ligne = [1]\n",
    "        for k in range(1, n):\n",
    "            ligne.append(L[n-1][k-1] + L[n-1][k])\n",
    "        ligne.append(1)\n",
    "        L.append(ligne)\n",
    "    return L\n",
    "\n",
    "triangle_pascal(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49428347",
   "metadata": {},
   "source": [
    "## Exercice 9 : Fusion de listes ordonnées\n",
    "\n",
    "\n",
    "On appelle **fusion ordonnée** de deux listes ordonnées $A = [a_1, \\dots, a_n]$ et $B = [b_1, \\dots, b_m]$ la liste des éléments de $A$ et $B$ ordonnée selon l'ordre de $A$ et $B$. Par exemple, si les listes $A$ et $B$ sont \n",
    "\n",
    "$$\n",
    "    A = [ 1, 7, 7, 13 ] \\quad \\text{ et } \\quad B = [ 0, 3, 6, 13, 15 ]\n",
    "$$\n",
    "\n",
    "alors (en observant que $A$ et $B$ sont croissantes), la fusion ordonnée de $A$ et $B$ est \n",
    "\n",
    "$$\n",
    "    [0, 1, 3, 6, 7, 7, 13, 13, 15 ]\n",
    "$$\n",
    "\n",
    "**Question 1 :** Écrire une fonction **itérative** `fusionne_iter(liste1, liste2)` qui retourne la fusion ordonnée de deux listes croissantes `liste1` et `liste2`. On **supposera** que les deux listes en entrée sont croissantes (on ne le vérifiera pas)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3e4b61bc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fusionne_iter(liste1, liste2):\n",
    "    i = 0\n",
    "    j = 0\n",
    "    n = len(liste1)\n",
    "    m = len(liste2)\n",
    "    \n",
    "    L = []\n",
    "    while (i < n) and (j < m):\n",
    "        if liste1[i] < liste2[j]:\n",
    "            L.append(liste1[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            L.append(liste2[j])\n",
    "            j += 1\n",
    "    \n",
    "    if i == n:\n",
    "        for k in range(j, m):\n",
    "            L.append(liste2[k])\n",
    "    elif j == m:\n",
    "        for k in range(i, n):\n",
    "            L.append(liste1[k])\n",
    "        \n",
    "    return L\n",
    "       \n",
    "    \n",
    "\n",
    "print(fusionne_iter([1, 4, 5], [2, 4, 8]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fed443ad",
   "metadata": {},
   "source": [
    "**Question 2 :** Écrire une fonction **récursive** `fusionne_rec(liste1, liste2)` qui retourne la fusion ordonnée de deux listes croissantes `liste1` et `liste2`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fbafaa37",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fusionne_rec(liste1, liste2):\n",
    "    if liste1 == []:\n",
    "        return liste2\n",
    "    elif liste2 == []:\n",
    "        return liste1\n",
    "    else:\n",
    "        x1 = liste1[0]\n",
    "        x2 = liste2[0]\n",
    "        if x1 <= x2:\n",
    "            liste1.pop(0)\n",
    "            return [x1] + fusionne_rec(liste1, liste2)\n",
    "        else:\n",
    "            liste2.pop(0)\n",
    "            return [x2] + fusionne_rec(liste1, liste2)\n",
    "            \n",
    "    \n",
    "print(fusionne_rec([1, 4, 5], [2, 4, 8]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c58dfc80",
   "metadata": {},
   "source": [
    "**Question 3 :** On suppose que `L` est une liste de listes. Écrire une fonction `fusionne_tout(L)` qui retourne la fusion ordonnée de toutes les listes présentes dans `L` (qui sont supposées toutes croissantes).\n",
    "\n",
    "Par exemple, avec les listes suivantes :\n",
    "\n",
    "```\n",
    "[1, 4, 5]\n",
    "[]\n",
    "[7, 11, 11]\n",
    "[1, 2, 4, 7]\n",
    "[2, 4, 8]\n",
    "```\n",
    "on doit obtenir la liste fusionnée\n",
    "```\n",
    "[1, 1, 2, 2, 4, 4, 4, 5, 7, 7, 8, 11, 11]\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "**Solution en récursif :**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7db12796",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fusionne_tout(L):\n",
    "    if len(L) == 0:\n",
    "        return []\n",
    "    if len(L) == 1:\n",
    "        return L[0]\n",
    "    if len(L) == 2:\n",
    "        return fusionne_rec(L[0], L[1])\n",
    "    liste = L.pop()\n",
    "    return fusionne_rec(liste, fusionne_tout(L))\n",
    "            \n",
    "    \n",
    "print(fusionne_tout([[1, 4, 5], [], [7, 11, 11], [1, 2, 4, 7], [2, 4, 8]]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4de17bad",
   "metadata": {},
   "source": [
    "**En itératif :**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4f21964a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fusionne_tout(L):\n",
    "    resultat = []\n",
    "    for liste in L:\n",
    "        resultat = fusionne_iter(resultat, liste)\n",
    "    return resultat\n",
    "            \n",
    "    \n",
    "print(fusionne_tout([[1, 4, 5], [], [7, 11, 11], [1, 2, 4, 7], [2, 4, 8]]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba8e2493",
   "metadata": {},
   "source": [
    "## Exercice 10 : maximum d'une liste par fonction récursive\n",
    "\n",
    "Soit $v = (v_1, \\dots, v_n) \\in \\mathbb{R}^n$. Alors, la valeur maximale des coordonnées de $v$ vérifie\n",
    "\n",
    "$$\n",
    "\\mathrm{max}(v) = \\mathrm{max}(v_1, \\dots, v_n) = \\mathrm{max}(\\mathrm{max}(v_1, \\dots, v_{n-1}), v_n)\n",
    "$$\n",
    "\n",
    "Ainsi, on obtient une relation de récurrence pour calculer le maximum d'une liste.\n",
    "\n",
    "**Question 1 :** Utiliser la relation ci-dessus pour écrire une fonction **récursive** ``maximum_rec(L)``, qui prend en entrée une liste ``L``, et qui retourne le maximum de la liste `L`. Votre fonction **devra** être récursive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0f97ca6a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maximum_rec(L):\n",
    "    if len(L) == 1:\n",
    "        return L[0]\n",
    "    else:\n",
    "        x = L.pop()\n",
    "        y = max(L)\n",
    "        if x > y:\n",
    "            return x\n",
    "        else:\n",
    "            return y\n",
    "\n",
    "print(maximum_rec([1, 2, 5, 2, 3]))\n",
    "print(maximum_rec([12]))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}