{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "55ffc681",
   "metadata": {},
   "source": [
    "# Feuille d'exercices 2\n",
    "\n",
    "\n",
    "```{admonition} Objectifs\n",
    "* Listes\n",
    "* Boucles\n",
    "* Compléments sur les fonctions\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Exercice 1 : manipulation élémentaire de liste\n",
    "\n",
    "\n",
    "**Question 1 :** Effectuer successivement les étapes suivantes :\n",
    "1. Affecter à une variable nommée `L` une liste vide.\n",
    "2. Ajouter l'entier $3$ à la fin de la liste `L`.\n",
    "3. Insérer l'entier $-2$ au début de la liste `L`.\n",
    "4. Afficher la liste `L`.\n",
    "5. Si le second élément de la liste `L` est strictement positif, alors afficher \"Positif\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6c56b2ee",
   "metadata": {},
   "outputs": [],
   "source": [
    "L = []\n",
    "L.append(3)\n",
    "L.insert(0, -2)\n",
    "print(L)\n",
    "if L[1] > 0:\n",
    "    print(\"Positif\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e0b7a69",
   "metadata": {},
   "source": [
    "**Question 2 :** Créer une liste `jours` contenant les noms des $7$ jours de la semaine (chacun exprimé sous la forme d'une chaîne de caractères)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3708e6f4",
   "metadata": {},
   "outputs": [],
   "source": [
    "jours = [\"lundi\", \"mardi\", \"mercredi\", \"jeudi\", \"vendredi\", \"samedi\", \"dimanche\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6da6244c",
   "metadata": {},
   "source": [
    "**Question 3 :** En utilisant la liste `jours`, afficher le troisième jour de la semaine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f30abb77",
   "metadata": {},
   "outputs": [],
   "source": [
    "jours[2]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7eb8bd23",
   "metadata": {},
   "source": [
    "Rappelons que pour connaître la longueur d'une chaîne de caractère, on utilise la fonction `len`. Par exemple, `len(\"bonjour\")` vaut $7$.\n",
    "\n",
    "**Question 4 :** En parcourant la liste `jours` avec une boucle `for`, et en effectuant un test à chaque tour de boucle, afficher les jours de la semaine qui sont formés de $5$ lettres exactement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d580356f",
   "metadata": {},
   "outputs": [],
   "source": [
    "for j in jours:\n",
    "    if (len(j) == 5):\n",
    "        print(j)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36732672",
   "metadata": {},
   "source": [
    "## Exercice 2 : boucle `for` et itérateur `range`\n",
    "\n",
    "\n",
    "\n",
    "**Question 1 :** À l'aide d'une boucle `for` et du mot-clef `range`, afficher successivement les nombres entiers allant de $-3$ à $8$ (inclus)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "22bc4537",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(-3, 9):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5017a684",
   "metadata": {},
   "source": [
    "**Question 2 :** À l'aide d'une boucle `for` et du mot-clef `range`, afficher, **dans l'ordre décroissant,** l'ensemble des nombres divisibles par $5$ qui sont compris entre $400$ et $500$ (bornes incluses)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "20cbf157",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(500, 399, -5):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4784a15b",
   "metadata": {},
   "source": [
    "**Question 3 :** À l'aide d'une boucle `for` et du mot-clef `range`, calculer la somme des entiers naturels naturels **impairs** inférieurs à $200$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9aeb3297",
   "metadata": {},
   "outputs": [],
   "source": [
    "somme = 0\n",
    "for n in range(1, 200, 2):\n",
    "    somme += n\n",
    "somme"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb3115d3",
   "metadata": {},
   "source": [
    "**Question 4 (plus difficile) :** À l'aide d'une boucle `for`, du mot-clef `range` et l'opérateur `*` qui permet de copier plusieurs fois le même caractère, reproduire la figure suivante, mais avec un triangle de **taille 20x20** :\n",
    "```\n",
    "**********\n",
    "*********\n",
    "********\n",
    "*******\n",
    "******\n",
    "*****\n",
    "****\n",
    "***\n",
    "**\n",
    "*\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dd5d009d",
   "metadata": {},
   "outputs": [],
   "source": [
    "for j in range(20, 0, -1):\n",
    "    s = \"*\" * j\n",
    "    print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ab60ce3",
   "metadata": {},
   "source": [
    "## Exercice 3 : boucle `while`\n",
    "\n",
    "\n",
    "**Question 1 :** À l'aide d'une boucle `while` (donc, sans boucle `for` ni mot-clef `range`), afficher les entiers pairs compris entre $16$ (inclus) et $26$ (exclus)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d7d5d9a7",
   "metadata": {},
   "outputs": [],
   "source": [
    "i = 16\n",
    "while (i < 26):\n",
    "    print(i)\n",
    "    i += 2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70f8c482",
   "metadata": {},
   "source": [
    "**Question 2 :** À l'aide d'une boucle `while`, afficher les puissances de $2$ inférieures à $1.000.000$ (en partant de $2^0 = 1$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bca68b05",
   "metadata": {},
   "outputs": [],
   "source": [
    "i = 1\n",
    "while i <= 1000000:\n",
    "    print(i)\n",
    "    i *= 2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b98c1b28",
   "metadata": {},
   "source": [
    "**Question 3 :** Dans la cellule suivante, une fonction `ma_fonction` est écrite pour calculer le maximum d'une liste `L`. Décommentez la dernière ligne, exécutez la cellule, puis observez ce qui est affiché. Essayez ensuite de corriger l'erreur pour obtenir le bon résultat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "543a1f61",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ma_fonction(L):\n",
    "    m = 0\n",
    "    i = 0\n",
    "    n = len(L)\n",
    "    while i <= n:\n",
    "        if L[i] > m:\n",
    "            m = L[i]\n",
    "        i += 1\n",
    "    return m\n",
    "\n",
    "# ma_fonction([13, 12, 42, -37])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a1e5393a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ma_fonction(L):\n",
    "    m = 0\n",
    "    i = 0\n",
    "    n = len(L)\n",
    "    while i <= n:\n",
    "        if L[i] > m:\n",
    "            m = L[i]\n",
    "        i += 1\n",
    "    return m\n",
    "\n",
    "ma_fonction([13, 12, 42, -37])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5050f776",
   "metadata": {},
   "source": [
    "On obtient une erreur de dépassement d'indice de liste. Le problème vient du fait que lorsque la variable `i` atteint  `n = len(L)`, on souhaite accéder à l'élément `L[i]` de la liste, qui n'existe pas. En effet, la liste `L` contient les `n` éléments suivants : `L[0]`, `L[1]`, `L[2]`, ..., `L[n-1]`.\n",
    "\n",
    "Pour corriger la fonction, il suffit de parcourir la liste une fois de moins :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1dea0fa6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ma_fonction_corrigee(L):\n",
    "    m = 0\n",
    "    i = 0\n",
    "    n = len(L)\n",
    "    while i < n:\n",
    "        if L[i] > m:\n",
    "            m = L[i]\n",
    "        i += 1\n",
    "    return m\n",
    "\n",
    "ma_fonction_corrigee([13, 12, 42, -37])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "230044ec",
   "metadata": {},
   "source": [
    "## Exercice 4 : fonction factorielle\n",
    "\n",
    "Rappelons qu'une fonction est dite **récursive** si elle s'appelle elle-même, et **itérative** sinon.\n",
    "\n",
    "**Question 1 :** Écrire une fonction **itérative** ``factorielle(n)`` qui calcule la factorielle d'un entier ``n`` passé en paramètre. Tester ensuite la fonction avec les valeurs de $n \\in \\{ 0, 1, 5, 10 \\}$ pour lesquelles on a $0! = 1$, $1! = 1$, $5! = 120$ et $10! = 3628800$.\n",
    "\n",
    "Ensuite, que vaut $100!$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "71dc38a5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorielle(n):\n",
    "    res = 1\n",
    "    for i in range(1, n+1):\n",
    "        res *= i\n",
    "    return res\n",
    "\n",
    "print(\"0! =\", factorielle(0))\n",
    "print(\"1! =\", factorielle(1))\n",
    "print(\"5! =\", factorielle(5))\n",
    "print(\"10! =\", factorielle(10))\n",
    "print(\"100! =\", factorielle(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58b38c30",
   "metadata": {},
   "source": [
    "**Question 2 :** Écrire une version **récursive** de la fonction factorielle, qui sera nommée ``factorielle_rec(n)``. Tester ensuite la fonction avec les mêmes valeurs que précédemment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "838257a0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorielle_rec(n):\n",
    "    if (n == 0):\n",
    "        return 1\n",
    "    return n * factorielle_rec(n-1)\n",
    "\n",
    "print(\"0! =\", factorielle_rec(0))\n",
    "print(\"1! =\", factorielle_rec(1))\n",
    "print(\"5! =\", factorielle_rec(5))\n",
    "print(\"10! =\", factorielle_rec(10))\n",
    "print(\"100! =\", factorielle_rec(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "518c9d6f",
   "metadata": {},
   "source": [
    "## Exercice 5 : suite récurrente d'ordre 1\n",
    "\n",
    "On considère la suite récurrente d'ordre $1$ définie par\n",
    "\n",
    "$$\n",
    "u_0 = 1 \\quad \\text{ et } \\quad u_{n+1} = \\left\\lfloor \\frac{u_n^2}{3} \\right\\rfloor + n, \\; \\forall n \\ge 0\\,.\n",
    "$$\n",
    "\n",
    "**Question 1.** Écrire une fonction itérative `calcule_u_iter(n)` qui calcule la valeur de $u_n$ par une fonction **itérative** (c'est-à-dire, sans que la fonction s'appelle elle-même).\n",
    "\n",
    "On vérifiera notamment que $u_2 = 1$, $u_4 = 4$ et $u_{10} = 96177957631162369$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0591ed4c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calcule_u_iter(n):\n",
    "    u = 1\n",
    "    for i in range(n):\n",
    "        u = u**2 // 3 + i\n",
    "    return u\n",
    "\n",
    "print(\"u(0) =\", calcule_u_iter(0))\n",
    "print(\"u(2) =\", calcule_u_iter(2))\n",
    "print(\"u(4) =\", calcule_u_iter(4))\n",
    "print(\"u(10) =\", calcule_u_iter(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cdf24409",
   "metadata": {},
   "source": [
    "**Question 2.** Écrire une fonction récursive `calcule_u_rec(n)` qui calcule la valeur de $u_n$ par une fonction récursive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "df071fdd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calcule_u_rec(n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        u = calcule_u_rec(n-1)\n",
    "        return u**2 // 3 + (n-1)\n",
    "\n",
    "print(\"u(0) =\", calcule_u_rec(0))\n",
    "print(\"u(10) =\", calcule_u_rec(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fad8e131",
   "metadata": {},
   "source": [
    "## Exercice 6 : test de croissance de liste\n",
    "\n",
    "\n",
    "**Question 1 :**  Écrire une fonction **itérative** ``est_croissante_iter(L)``, qui prend en entrée une liste ``L``, et qui teste si cette liste est triée dans l'ordre croissant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67f372e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_croissante_iter(L):\n",
    "    n = len(L)\n",
    "    i = 0 \n",
    "    while (i < n-1):\n",
    "        if L[i] > L[i+1]:\n",
    "            return False\n",
    "        i += 1\n",
    "    return True\n",
    "\n",
    "print(est_croissante_iter([]))\n",
    "print(not(est_croissante_iter([1, 2, 5, 2, 3])))\n",
    "print(est_croissante_iter([1, 2, 2, 3, 7]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93d681b1",
   "metadata": {},
   "source": [
    "Observons maintenant qu'une liste `L` de longueur $n$ est triée dans l'ordre croissant si les deux propriétés suivantes sont vérifiées :\n",
    "* ses deux derniers éléments sont triés dans l'ordre croissant\n",
    "* la sous-liste de ses $n-1$ premiers éléments est également triée dans l'ordre croissant. \n",
    "\n",
    "Par ailleurs, une liste de longueur $1$ est toujours triée dans l'ordre croissant. On obtient donc une manière **récursive** de vérifier si une liste est triée dans l'ordre croissant.\n",
    "\n",
    "**Question 2 :** En utilisant la caractérisation donnée plus haut, écrire une fonction **récursive** ``est_croissante_rec(L)``, qui prend en entrée une liste ``L``, et qui teste si cette liste est triée dans l'ordre croissant. Votre fonction **devra** être récursive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c1c724ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_croissante_rec(L):\n",
    "    n = len(L)\n",
    "    if (n <= 1):\n",
    "        return True\n",
    "    elif L[n-2] > L[n-1]:\n",
    "        return False\n",
    "    else:\n",
    "        L.pop()\n",
    "        return est_croissante_rec(L)\n",
    "        \n",
    "print(not(est_croissante_rec([1, 2, 5, 2, 3])))\n",
    "print(est_croissante_rec([1, 2, 2, 3, 7]))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}