{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b7d6ba73",
   "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": "62d2294f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c86193f6",
   "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": "ee077c84",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1aeb3ad1",
   "metadata": {},
   "source": [
    "**Question 3 :** En utilisant la liste `jours`, afficher le troisième jour de la semaine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "53f98efa",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5a0a544",
   "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": "bb3d25e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d5ba848",
   "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": "ecc83441",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1738e4e5",
   "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": "2a6db81b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5c2a21f",
   "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": "b87a9611",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "edcd8191",
   "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": "ec1b0e84",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af82f9d0",
   "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": "503d10a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d50e6946",
   "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": "0362558d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99906537",
   "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": "9512655a",
   "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": "b34e379f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8f530d2",
   "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": "369981e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52a756fe",
   "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": "c93cdb7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "531ba5ac",
   "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": "98be1947",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "571e509e",
   "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": "f2c70b5b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73c93eb9",
   "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": "d4739dbf",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d845ba7",
   "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": "8369fd04",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}