{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "912d6cbe",
   "metadata": {},
   "source": [
    "# Feuille d'exercices 4 -- 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",
    "\n",
    "\n",
    "## Exercice 5 : décomposition en binaire\n",
    "\n",
    "**Question 1 :** Exécuter les instructions `bin(2)` et `bin(11)`. Quel type d'objet obtient-on ? Que contient-il ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9b3ed7a3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a23ad71f",
   "metadata": {},
   "source": [
    "**Question 2 :** Stocker dans une variable `x` la valeur de `bin(11)`, puis entrer la commande `int(x, 2)`. Qu'obtient-on ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a54b9e25",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ebc2e679",
   "metadata": {},
   "source": [
    "**Question 3 :** Écrire une fonction `decomposition(n)` qui prend en entrée un entier `n` positif ou nul, et qui retourne une liste formée des coefficients de la décomposition de `n` en base $2$. \n",
    "\n",
    "Par exemple, pour l'entier $n = 13$ qui s'écrit $n = 1 \\times 2^3 + 1 \\times 2^2 + 0 \\times 2^1 + 1 \\times 2^0$, la fonction retournera la liste `[1, 1, 0, 1]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0476775d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3f70de9",
   "metadata": {},
   "source": [
    "**Question 4 :** Écrire une fonction `my_bin(n)` qui copie le fonctionnement de `bin`. Puis, vérifiez qu'elle est correcte en testant si `my_bin(n)` égale `bin(n)` pour les $1000$  premiers entiers naturels `n`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d26b5dcd",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6696dbf6",
   "metadata": {},
   "source": [
    "## Exercice 6 : flocon de Koch \n",
    "\n",
    "Le but de cet exercice est de programmer une fonction qui dessine le flocon de Koch, comme sur l'image ci-dessous.\n",
    "\n",
    "```{image} ../../images/koch-rouge.png\n",
    ":alt: koch\n",
    ":width: 60%\n",
    ":align: center\n",
    "```\n",
    "\n",
    "Le flocon de Koch est une **fractale**, c'est-à-dire une figure similaire à elle-même à n'importe quelle échelle. On peut le construire de manière itérative, comme l'illustre par la série d'images suivantes :\n",
    "\n",
    "\n",
    "```{image} ../../images/koch0123.png\n",
    ":alt: koch0123\n",
    ":width: 70%\n",
    ":align: center\n",
    "```\n",
    "\n",
    "Les images précédentes représentent des parties d'un flocon de Koch **d'ordre** $0$, $1$, $2$ et $3$. L'ordre correspond au nombre d'itérations dans la construction de la figure.\n",
    "\n",
    "Pour obtenir le flocon d'ordre $n$ à partir du flocon d'ordre $n-1$, l'idée est d'opérer une **floraison** sur chacun des segments du flocon d'ordre $n-1$. On fait **fleurir** un segment par le procédé suivant :\n",
    "1. on partage le segment en 3 parties de longueur égale ;\n",
    "2. on préserve à l'identique les deux sous-segments extérieurs ;\n",
    "3. on supprime le sous-segment central, que l'on remplace par deux segments qui auraient formé un triangle équilatéral avec le sous-segment supprimé.\n",
    "\n",
    "\n",
    "```{image} ../../images/floraison.png\n",
    ":alt: koch0123\n",
    ":width: 80%\n",
    ":align: center\n",
    "```\n",
    "\n",
    "Mathématiquement, si le segment de base a pour extrémités $A$ et $B$, alors la forme obtenue après floraison est définie par les $5$ points suivants :\n",
    "\n",
    "- $A$\n",
    "- $M_1 = A + \\frac{1}{3} \\overrightarrow{AB}$\n",
    "- $M_2 = A + \\frac{1}{2} \\overrightarrow{AB} + \\frac{\\sqrt{3}}{6} {\\rm rot}(\\overrightarrow{AB})$\n",
    "- $M_3 = A + \\frac{2}{3} \\overrightarrow{AB}$\n",
    "- $B$\n",
    "\n",
    "où ${\\rm rot}(\\overrightarrow{AB})$ est la rotation de $+ 90°$ du vecteur $\\overrightarrow{AB}$.\n",
    "\n",
    "\n",
    "L'objectif des premières questions de cet exercice est d'écrire les fonctions auxiliaires qui permettront ensuite de construire le flocon. Dans tout l'exercice, on représentera les points du plan par leurs **coordonnées cartésiennes**. Un **point** du plan sera donc un couple $[x, y]$ de nombres.\n",
    "\n",
    "\n",
    "**Question 1 :**  Écrire une fonction `vecteur(A, B)` qui prend en entrée deux points du plan `A` et `B` et qui retourne les coordonnées du vecteur $\\overrightarrow{AB}$.\n",
    "\n",
    "*Par exemple, `vecteur([1, 0], [3, -1])` doit retourner la liste `[2, -1]`.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d9b2012a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb05517b",
   "metadata": {},
   "source": [
    "**Question 2 :** Écrire une fonction `rotation(u)` qui prend en entrée un vecteur `u` et qui retourne le vecteur obtenu par la rotation de $+90$ degrés de `u` autour de l'origine.\n",
    "\n",
    "*Par exemple, `rotation([2, 3])` doit retourner la liste `[-3, 2]`.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ef1f84aa",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4bd0ded8",
   "metadata": {},
   "source": [
    "**Question 3 :** Écrire une fonction `translation(A, u, x)` qui prend en entrée un point `A`, un vecteur directeur `u` et un nombre flottant `x` et qui retourne les coordonnées du point $A + x u$.\n",
    "\n",
    "*Par exemple, `translation([2, 3], [-1,1], 2)` doit retourner la liste `[0, 5]`.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5db007e1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "450054be",
   "metadata": {},
   "source": [
    "**Question 4 :** Écrire une fonction `etape_floraison(A, B)` qui prend en entrée deux points du plan `A` et `B`, et qui calcule la liste des $5$ points correspondant à une étape de floraison du flocon de Koch entre les points `A` et `B`.\n",
    "\n",
    "*Par exemple, pour $A = (0, 0)$ et $B = (1, 1)$, on doit obtenir une liste avec des valeurs approchées suivantes :*\n",
    "```\n",
    "[ [0,0], [0.3333, 0.3333], [0.2113, 0.7886], [0.6666, 0.6666], [1,1] ]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2de08df1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "685c8621",
   "metadata": {},
   "source": [
    "**Question 5 :** Écrire une fonction `flocon_koch(N, L)` qui prend en entrée un ordre `N` et une liste de points initiaux `L`, et qui retourne la liste des coordonnées des points du flocon de Koch à l'ordre $N$. Dans l'exemple donné au début de l'exercice, la liste $L$ correspond aux points du premier segment (typiquement, $[ (0,0), (1,0) ]$). \n",
    "\n",
    "*Par exemple, pour $N = 2$ et $L = [ (0,0), (1,0) ]$, on doit obtenir la liste avec les valeurs approchées suivantes :*\n",
    "```\n",
    "[\n",
    " [0,0], [0.1111, 0.0], [0.1666, 0.0962], [0.3333, 0.0], [0.3333, 0.0],\n",
    " [0.3888, 0.0962], [0.3333, 0.1925], [0.4444, 0.1925], [0.5, 0.2886],\n",
    " [0.5555, 0.1925], [0.6666, 0.1925], [0.6111, 0.0962], [0.6666, 0.0],\n",
    " [0.7777, 0.0], [0.8333, 0.0962], [0.8888, 0.0], [1.0, 0.0]\n",
    "]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "85690477",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dd26afc",
   "metadata": {},
   "source": [
    "**Question 6 :** Afficher le flocon de Koch d'ordre $6$, dans un graphe sans axe (grâce à la commande `plt.axis('off')`) et sans dilatation des axes (grâce à la commande `plt.axis('equal')`).\n",
    "\n",
    "Pour afficher le flocon on pourra :\n",
    "1. ou bien partir du segment `L = [ [0,0], [1,0] ]` comme dans la question précédente\n",
    "2. ou bien construire le flocon complet, en choisissant comme points initiaux la liste\n",
    "```\n",
    "triangle = [ [0,0], [1,0], [0.5, -sqrt(3)/2], [0,0] ]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d937fa1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ee3ed2c",
   "metadata": {},
   "source": [
    "<!-- ## Exercice 8 : tri par insertion -->\n",
    "\n",
    "\n",
    "\n",
    "<!-- **Question 1 :** ... -->\n",
    "\n",
    "<!-- <only student> -->\n",
    "<!-- ```{code-cell} -->\n",
    "<!-- # Votre réponse ici -->\n",
    "<!-- ``` -->\n",
    "<!-- <endonly> -->\n",
    "\n",
    "<!-- <only teacher> -->\n",
    "<!-- ```{code-cell} -->\n",
    "<!-- # aaa -->\n",
    "<!-- ``` -->\n",
    "<!-- <endonly> -->\n",
    "\n",
    "\n",
    "<!-- ## Exercice 9 : moyenne et écart-type -->\n",
    "\n",
    "<!-- **Question 1 :** ... -->\n",
    "\n",
    "<!-- <only student> -->\n",
    "<!-- ```{code-cell} -->\n",
    "<!-- # Votre réponse ici -->\n",
    "<!-- ``` -->\n",
    "<!-- <endonly> -->\n",
    "\n",
    "<!-- <only teacher> -->\n",
    "<!-- ```{code-cell} -->\n",
    "<!-- # aaa -->\n",
    "<!-- ``` -->\n",
    "<!-- <endonly> -->"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}