{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b46f5b28",
   "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": "ca73d59e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12b2f8d5",
   "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": "64b5298a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "956c21e9",
   "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",
    "\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": "446b22eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f372ecb8",
   "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": "e956b212",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "576df351",
   "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": "5672e4d8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f72a73d0",
   "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",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cd343ede",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cd550f6b",
   "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": "3ef8f091",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}