{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3ae124ef",
   "metadata": {},
   "source": [
    "# Feuille d'exercices 4\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "```{admonition} Objectifs\n",
    "* Fonctions natives\n",
    "* Bibliothèques python : math, random, matplotlib\n",
    "```\n",
    "\n",
    "\n",
    "## Exercice 1 : manipulations élémentaires\n",
    "\n",
    "\n",
    "**Question 1 :** En important (ou non) les bibliothèques appropriées, réaliser les instructions suivantes :\n",
    "- calculer la partie entière inférieure de $\\sqrt{1000}$\n",
    "- calculer l'arrondi de $\\tan(\\frac{101\\pi}{200})$\n",
    "- tirer aléatoirement un nombre décimal parmi $\\{ 0, 0.01, 0.02, 0.03, \\dots, 0.98, 0.99 \\}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "237d4c6e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import random\n",
    "\n",
    "print(math.floor(math.sqrt(1000)))\n",
    "print(round(math.tan(101*math.pi/200)))\n",
    "print(random.randint(0, 99)/100)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97f66fb6",
   "metadata": {},
   "source": [
    "**Question 2 :** Observer et expliquer les erreurs dans les calculs suivants."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0cd53a32",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "math.sqrt(-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e392ecb",
   "metadata": {},
   "source": [
    "**Réponse :** python indique que l'on donne une mauvaise valeur en entrée de la fonction `sqrt` : en effet, on ne peut pas prendre la racine carrée d'un nombre négatif."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "529138f8",
   "metadata": {},
   "outputs": [],
   "source": [
    "math.log(exp(-10), 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be49d0ac",
   "metadata": {},
   "source": [
    "**Réponse :** python indique que la fonction `exp` que l'on souhaite utiliser n'existe pas : il ne faut pas oublier le `math.` !\n",
    "\n",
    "\n",
    "**Question 3 :** Essayer de calculer $\\tan(\\pi/2)$ grâce à la fonction `tan` et au nombre `pi` de la bibliothèque `math`. Obtient-on une erreur ? Pourquoi ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "21f2e3d6",
   "metadata": {},
   "outputs": [],
   "source": [
    "math.tan(math.pi/2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cbc7ea34",
   "metadata": {},
   "source": [
    "On devrait avoir une erreur, car $\\tan(\\pi/2)$ n'est pas définie, mais on n'en a pas. La raison vient de l'approximation qui est faite sur $\\pi$ : l'erreur d'approximation fait que l'entrée (disons, $\\pi/2 + \\epsilon$ avec $\\epsilon \\ne 0$) est une valeur sur laquelle la fonction $\\tan$ est bien définie.\n",
    "\n",
    "\n",
    "\n",
    "**Question 4 (optionnelle) :** Écrire une fonction `maxabs(L)` qui retourne la plus grande valeur absolue de la liste `L`. Si possible, votre fonction utilisera un parcours de liste **par compréhension**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6adc2546",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxabs(L):\n",
    "    return max([abs(x) for x in L])\n",
    "\n",
    "maxabs([ -7, 2, 5, 0, -1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eeaabba8",
   "metadata": {},
   "source": [
    "## Exercice 2 : affichage graphique\n",
    "\n",
    "**Question 1 :** En utilisant `matplotlib.pyplot`, tracez le graphe de la fonction $\\sin(x)$ pour $x$ entre $0$ et $4 \\pi$. Pour tracer la fonction, on utilisera un pas de $0.01$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2727468a",
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "pas = 0.01\n",
    "X = [pas * i for i in range(math.floor(4*math.pi/pas))]\n",
    "Y = [math.sin(x) for x in X]\n",
    "plt.plot(X, Y)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa3af651",
   "metadata": {},
   "source": [
    "**Question 2 :** On rappelle que dans le plan, un cercle de centre $(x, y)$ et de rayon $r$ a pour équation paramétrique :\n",
    "\n",
    "$$\n",
    "    \\Big\\{ \\begin{pmatrix} x + r \\cos(t) \\\\ y + r \\sin(t)  \\end{pmatrix} ,\\; t \\in [0, 2\\pi] \\Big\\}\n",
    "$$\n",
    "\n",
    "Écrire une fonction `cercle(x, y, r)` qui trace un cercle dont le centre est le point de coordonnées $(x,y)$ et dont le rayon est $r$. Votre fonction n'aura pas de valeur de retour : elle tracera simplement le cercle.\n",
    "\n",
    "*Indication : pour que les axes de la figure soient à la même échelle (et ne pas observer une ellipse lors de l'affichage), il faut utiliser l'instruction `plt.axis('equal')` avant d'afficher le graphique.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a6e110e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cercle(x, y, r):\n",
    "    pas = 0.01\n",
    "    X = [x + r * math.cos(pas * i) for i in range(math.floor(2*math.pi/pas))]\n",
    "    Y = [x + r * math.sin(pas * i) for i in range(math.floor(2*math.pi/pas))]\n",
    "    plt.plot(X, Y)\n",
    "    plt.axis('equal')\n",
    "    plt.show()\n",
    "\n",
    "cercle(0, 0, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba102ea5",
   "metadata": {},
   "source": [
    "## Exercice 3 : pgcd\n",
    "\n",
    "\n",
    "**Question 1 :** Écrire une fonction `pgcd(a, b)` qui retourne le pgcd de deux entiers `a` et `b`. Pour cela, rappelons l'algorithme d'Euclide :\n",
    "\n",
    "- **Tant que** $b \\ne 0$:\n",
    "  - Calculer $q$ et $r$ le quotient et le reste de la division euclidienne de $a$ par $b$\n",
    "  - Remplacer $a$ par $b$ et $b$ par $r$\n",
    "- **Retourner** $a$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "363b5fcb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pgcd(a, b):\n",
    "    while b != 0:\n",
    "        q = a//b\n",
    "        r = a%b\n",
    "        a = b\n",
    "        b = r\n",
    "    return a"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3db84a40",
   "metadata": {},
   "source": [
    "**Question 2 :** En utilisant la fonction `gcd` de la bibliothèque `math`, vérifier que votre fonction est correctement implémentée. Pour cela, on pourra tirer des entiers $a$ et $b$ aléatoirement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "af5a0e1d",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = random.randint(1000, 10000)\n",
    "b = random.randint(1000, 10000)\n",
    "math.gcd(a, b) == pgcd(a, b)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6fe934bc",
   "metadata": {},
   "source": [
    "## Exercice 4 : La suite de Syracuse\n",
    "\n",
    "La **suite de Syracuse** est une suite récursive de nombres naturels définie par un premier terme $s_0 \\ge 1$, et par la relation de récurrence suivante (pour $n \\ge 0$) :\n",
    "- si $s_n$ est pair, alors $s_{n+1} = s_n/2$,\n",
    "- si $s_n$ est impair, alors $s_{n+1} = 3 s_n + 1$.\n",
    "\n",
    "Par exemple, les $15$ premiers termes de la suite de terme initial $s_0 = 6$ sont :\n",
    "\n",
    "$$\n",
    "    (6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1).\n",
    "$$\n",
    "\n",
    "On observe alors que, lorsque la suite atteint le nombre $1$, la suite devient périodique : le motif $(4, 2, 1)$ se répète indéfiniment. On appelle **prépériode** les termes $(s_0, s_1, \\dots, s_m)$ de la suite de Syracuse, où $s_m$ est la première occurence de la valeur $1$ dans la suite.\n",
    "\n",
    "**Question 1 :** Implanter une fonction `syracuse(s)` qui prend en entrée un entier $s \\ge 1$, et qui retourne la liste des termes de prépériode de la suite de Syracuse de terme initial $s$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a7391007",
   "metadata": {},
   "outputs": [],
   "source": [
    "def syracuse(s):\n",
    "    L = [s]\n",
    "    a = s\n",
    "    while a != 1:\n",
    "        if a % 2 == 0:\n",
    "            a //= 2\n",
    "        else:\n",
    "            a = 3*a + 1\n",
    "        L.append(a)\n",
    "    return L\n",
    "\n",
    "print(syracuse(6))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc2c7f75",
   "metadata": {},
   "source": [
    "**Question 2 :** Parmi les termes initiaux $s_0$ compris entre $1$ et $1000$, lequel produit une suite de Syracuse de plus grande prépériode ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d0133288",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trouve_max_syracuse(N):\n",
    "    longueur_max = 0\n",
    "    s = 0\n",
    "    for i in range(1, N+1):\n",
    "        n = len(syracuse(i))\n",
    "        if n > longueur_max:\n",
    "            longueur_max = n\n",
    "            s = i\n",
    "    return s\n",
    "\n",
    "trouve_max_syracuse(1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8efdacb",
   "metadata": {},
   "source": [
    "**Question 3 :** À l'aide de la bibliothèque ``matplotlib``, tracer le graphe de la prépériode de la suite de Syracuse (c'est-à-dire, $s_n$ en fonction de $n$) pour $s_0 = 7$. Si on le souhaite, on pourra afficher seulement des points (et non la ligne continue les reliant) avec les arguments optionnels `linestyle='', marker='o'` de `plot()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e2d1c7ef",
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "S = syracuse(7)\n",
    "plt.plot(S, linestyle='', marker='o')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01fafcba",
   "metadata": {},
   "source": [
    "**Question 4 :** Tracer sur un même graphe les prépériodes des suites de Syracuse de termes initiaux $s_0 = 8192$ et $s_0 = 1234$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "66cb9c3b",
   "metadata": {},
   "outputs": [],
   "source": [
    "S = syracuse(1234)\n",
    "plt.plot(S, linestyle='None', marker='+')\n",
    "\n",
    "T = syracuse(8192)\n",
    "plt.plot(T, linestyle='None', marker='o')\n",
    "\n",
    "plt.show()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}