{
 "nbformat_minor": 0, 
 "nbformat": 4, 
 "cells": [
  {
   "source": [
    "$$\n", 
    "\\def\\CC{\\bf C}\n", 
    "\\def\\QQ{\\bf Q}\n", 
    "\\def\\RR{\\bf R}\n", 
    "\\def\\ZZ{\\bf Z}\n", 
    "\\def\\NN{\\bf N}\n", 
    "$$\n", 
    "# Exemples (`def` + `while` + `for` + `if`)"
   ], 
   "cell_type": "markdown", 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "from __future__ import division, print_function   # Python 3"
   ], 
   "outputs": [], 
   "metadata": {}
  }, 
  {
   "source": [
    "On a vu dans les chapitres pr\u00e9c\u00e9dents comment d\u00e9finir des fonctions avec `def`, des boucles avec `while` et `for` et des tests avec `if` ainsi que quelques exemples sur chaque notion mais ind\u00e9pendants des autres. Tr\u00e8s souvent en programmation, on a besoin d'utiliser plus tous ces outils \u00e0 la fois. C'est leur utilisation simultan\u00e9e qui permet de r\u00e9soudre des probl\u00e8mes tr\u00e8s divers et de les exprimer en quelques lignes de code.\n", 
    "\n", 
    "Dans ce chapitre, nous allons voir quelques exemples qui utilisent les fonctions, les boucles et les conditions dans un m\u00eame programme.\n", 
    "\n", 
    "## Conjecture de Syracuse\n", 
    "\n", 
    "La *suite de Syracuse* une suite d'entiers naturels d\u00e9finie de la mani\u00e8re suivante. On part d'un nombre entier plus grand que z\u00e9ro ; s\u2019il est pair, on le divise par 2 ; s\u2019il est impair, on le multiplie par 3 et on ajoute 1. En r\u00e9p\u00e9tant l\u2019op\u00e9ration, on obtient une suite d'entiers positifs dont chacun ne d\u00e9pend que de son pr\u00e9d\u00e9cesseur. Par exemple, la suite de Syracuse du nombre 23 est:\n", 
    "\n", 
    "> 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...\n", 
    "\n", 
    "Apr\u00e8s que le nombre 1 a \u00e9t\u00e9 atteint, la suite des valeurs (1, 4, 2, 1, 4, 2, ...) se r\u00e9p\u00e8te ind\u00e9finiment en un cycle de longueur 3, appel\u00e9 cycle trivial.\n", 
    "\n", 
    "La [conjecture de Syracuse](https://fr.wikipedia.org/wiki/Conjecture_de_Syracuse) est l'hypoth\u00e8se selon laquelle la suite de Syracuse de n'importe quel entier strictement positif atteint 1. En d\u00e9pit de la simplicit\u00e9 de son \u00e9nonc\u00e9, cette conjecture d\u00e9fie depuis de nombreuses ann\u00e9es les math\u00e9maticiens. Paul Erdos a dit \u00e0 propos de la conjecture de Syracuse : \"les math\u00e9matiques ne sont pas encore pr\u00eates pour de tels probl\u00e8mes\"."
   ], 
   "cell_type": "markdown", 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "def syracuse(n):\n", 
    "    while n != 1:\n", 
    "        print(n, end=' ')\n", 
    "        if n % 2 == 0:\n", 
    "            n = n//2\n", 
    "        else:\n", 
    "            n = 3*n+1"
   ], 
   "outputs": [], 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "syracuse(23)"
   ], 
   "outputs": [
    {
     "execution_count": 1, 
     "output_type": "execute_result", 
     "data": {
      "text/plain": [
       "23 70 35 106 53 160 80 40 20 10 5 16 8 4 2"
      ]
     }, 
     "metadata": {}
    }
   ], 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "syracuse(245)"
   ], 
   "outputs": [
    {
     "execution_count": 1, 
     "output_type": "execute_result", 
     "data": {
      "text/plain": [
       "245 736 368 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2"
      ]
     }, 
     "metadata": {}
    }
   ], 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "syracuse(245154)"
   ], 
   "outputs": [
    {
     "execution_count": 1, 
     "output_type": "execute_result", 
     "data": {
      "text/plain": [
       "245154 122577 367732 183866 91933 275800 137900 68950 34475 103426 51713 \n", 
       "155140 77570 38785 116356 58178 29089 87268 43634 21817 65452 32726 16363\n", 
       "49090 24545 73636 36818 18409 55228 27614 13807 41422 20711 62134 31067 \n", 
       "93202 46601 139804 69902 34951 104854 52427 157282 78641 235924 117962 58981 \n", 
       "176944 88472 44236 22118 11059 33178 16589 49768 24884 12442 6221 18664 9332 \n", 
       "4666 2333 7000 3500 1750 875 2626 1313 3940 1970 985 2956 1478 739 2218 1109 \n", 
       "3328 1664 832 416 208 104 52 26 13 40 20 10 5 16 8 4 2"
      ]
     }, 
     "metadata": {}
    }
   ], 
   "metadata": {}
  }, 
  {
   "source": [
    "Pouvez-vous trouver un nombre `n` tel que la suite de Syracuse n'atteint pas le cycle 4-2-1?\n", 
    "\n", 
    "## \u00c9num\u00e9rer les diviseurs d'un nombre entier\n", 
    "\n", 
    "Une fonction qui retourne la liste des diviseurs d'un nombre entiers peut s'\u00e9crire comme ceci en utilisant une boucle `for` et un test `if` :"
   ], 
   "cell_type": "markdown", 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "def diviseurs(n):\n", 
    "    L = []\n", 
    "    for i in range(1, n+1):\n", 
    "        if n % i == 0:\n", 
    "            L.append(i)\n", 
    "    return L"
   ], 
   "outputs": [], 
   "metadata": {}
  }, 
  {
   "source": [
    "On v\u00e9rifie que la fonction marche bien:"
   ], 
   "cell_type": "markdown", 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "diviseurs(12)"
   ], 
   "outputs": [
    {
     "execution_count": 1, 
     "output_type": "execute_result", 
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 6, 12]"
      ]
     }, 
     "metadata": {}
    }
   ], 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "diviseurs(13)"
   ], 
   "outputs": [
    {
     "execution_count": 1, 
     "output_type": "execute_result", 
     "data": {
      "text/plain": [
       "[1, 13]"
      ]
     }, 
     "metadata": {}
    }
   ], 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "diviseurs(15)"
   ], 
   "outputs": [
    {
     "execution_count": 1, 
     "output_type": "execute_result", 
     "data": {
      "text/plain": [
       "[1, 3, 5, 15]"
      ]
     }, 
     "metadata": {}
    }
   ], 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "diviseurs(24)"
   ], 
   "outputs": [
    {
     "execution_count": 1, 
     "output_type": "execute_result", 
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 6, 8, 12, 24]"
      ]
     }, 
     "metadata": {}
    }
   ], 
   "metadata": {}
  }, 
  {
   "source": [
    "## Tester si un nombre est premier\n", 
    "\n", 
    "Une fonction peut en utiliser une autre. Par exemple, en utilisant la fonction `diviseur` que l'on a d\u00e9finit plus haut, on peut tester si un nombre est premier:"
   ], 
   "cell_type": "markdown", 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "def est_premier_1(n):\n", 
    "    L = diviseurs(n)\n", 
    "    return len(L) == 2"
   ], 
   "outputs": [], 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "est_premier_1(12)"
   ], 
   "outputs": [
    {
     "execution_count": 1, 
     "output_type": "execute_result", 
     "data": {
      "text/plain": [
       "False"
      ]
     }, 
     "metadata": {}
    }
   ], 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "est_premier_1(13)"
   ], 
   "outputs": [
    {
     "execution_count": 1, 
     "output_type": "execute_result", 
     "data": {
      "text/plain": [
       "True"
      ]
     }, 
     "metadata": {}
    }
   ], 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "[n for n in range(20) if est_premier_1(n)]"
   ], 
   "outputs": [
    {
     "execution_count": 1, 
     "output_type": "execute_result", 
     "data": {
      "text/plain": [
       "[2, 3, 5, 7, 11, 13, 17, 19]"
      ]
     }, 
     "metadata": {}
    }
   ], 
   "metadata": {}
  }, 
  {
   "source": [
    "On pourrait faire plus efficace, car il suffit de v\u00e9rifier la non-existence de diviseurs inf\u00e9rieurs \u00e0 la racine carr\u00e9e de `n`."
   ], 
   "cell_type": "markdown", 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "from math import sqrt\n", 
    "def est_premier(n):\n", 
    "    sq = int(sqrt(n))\n", 
    "    for i in range(2, sq):\n", 
    "        if n % i == 0:\n", 
    "            return False\n", 
    "    return True"
   ], 
   "outputs": [], 
   "metadata": {}
  }, 
  {
   "source": [
    "En utilisant cette fonciton, on trouve que la liste des premiers nombres premiers inf\u00e9rieurs \u00e0 20 est:"
   ], 
   "cell_type": "markdown", 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "[n for n in range(20) if est_premier(n)]"
   ], 
   "outputs": [
    {
     "execution_count": 1, 
     "output_type": "execute_result", 
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15, 17, 19]"
      ]
     }, 
     "metadata": {}
    }
   ], 
   "metadata": {}
  }, 
  {
   "source": [
    "Le r\u00e9sulat est erron\u00e9! Pourquoi?\n", 
    "\n", 
    "La fonction `est_premier(8)` retourne `True` en ce moment, car la racine carr\u00e9e de 8 vaut `2.828` et donc `sq=int(2.828)` est \u00e9gal \u00e0 `2` et la boucle ne teste pas la valeur `i=2`, car `range(2,2)` retourne une liste vide. On peut corriger de la fa\u00e7on suivante en ajoutant un `+1` au bon endroit:"
   ], 
   "cell_type": "markdown", 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "from math import sqrt\n", 
    "def est_premier(n):\n", 
    "    sq = int(sqrt(n))\n", 
    "    for i in range(2, sq+1):\n", 
    "        if n % i == 0:\n", 
    "            return False\n", 
    "    return True"
   ], 
   "outputs": [], 
   "metadata": {}
  }, 
  {
   "source": [
    "On v\u00e9rifie que la fonction retourne bien que 4 et 8 ne sont pas des nombres premiers:"
   ], 
   "cell_type": "markdown", 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "[n for n in range(20) if est_premier(n)]"
   ], 
   "outputs": [
    {
     "execution_count": 1, 
     "output_type": "execute_result", 
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 5, 7, 11, 13, 17, 19]"
      ]
     }, 
     "metadata": {}
    }
   ], 
   "metadata": {}
  }, 
  {
   "source": [
    "Mais il y a encore une erreur, car 0 et 1 ne devraient pas faire partie de la liste. Une solution est de traiter ces deux cas de base \u00e0 part:"
   ], 
   "cell_type": "markdown", 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "from math import sqrt\n", 
    "def est_premier(n):\n", 
    "    if n == 0 or n == 1:\n", 
    "        return False\n", 
    "    sq = int(sqrt(n))\n", 
    "    for i in range(2, sq+1):\n", 
    "        if n % i == 0:\n", 
    "            return False\n", 
    "    return True"
   ], 
   "outputs": [], 
   "metadata": {}
  }, 
  {
   "source": [
    "On v\u00e9rifie que tout marche bien maintenant:"
   ], 
   "cell_type": "markdown", 
   "metadata": {}
  }, 
  {
   "execution_count": null, 
   "cell_type": "code", 
   "source": [
    "[n for n in range(50) if est_premier(n)]"
   ], 
   "outputs": [
    {
     "execution_count": 1, 
     "output_type": "execute_result", 
     "data": {
      "text/plain": [
       "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]"
      ]
     }, 
     "metadata": {}
    }
   ], 
   "metadata": {}
  }
 ], 
 "metadata": {
  "kernelspec": {
   "display_name": "python2", 
   "name": "python2"
  }
 }
}