{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# L3 E - S5 2018-19 --- TD ordinateurs --- séance 2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Les listes "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les $\\texttt{listes}$ sont un autre type de $\\texttt{sequences}$. Elles sont notées entre crochets et leurs éléments ne sont pas forcément du même type :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "L=[\"a\",\"b\",'c',23,\"salut\",-56.34,12/29,1234]\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comme pour les $\\textit{chaînes}$, on a différentes façons d'en connaître des éléments ou des sous-séquences : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print (L[0])      \n",
    "print (L[2:])    \n",
    "print (L[-2])\n",
    "print (L[3:6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut également savoir si un élément est (ou n'est pas) dans une liste :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "1 in L, 0 in L, 'B' in L, \"b\" in L, 100 not in L"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il y a aussi diverses possibilités de concaténer :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "M=[-1,1,-1,1,0,1]\n",
    "print (L+M+L)\n",
    "print (len(L+M))\n",
    "print (L[0:24:3])\n",
    "print ((L+M)[0:24:3])\n",
    "print ((L+M+L)[0:24:3])\n",
    "print(L+['au revoir']+['s','t','o',\"p\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ATTENTION !! La syntaxe peut changer sur certains points, suivant qu'on utilise une version 2.x ou 3.x.; dans l'exemple précédent, la commande $\\texttt{print \"le nombre d'éléments de L est\", len(L)}$ ne fonctionne que sur les versions 2.x. Avec les versions3.x, c'est la syntaxe suivante qui donnera le même résultat (et qui fonctionnera aussi avec la version 2) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print(\"le nombre d'éléments de L est\", len(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'addition $L+L+...+L$ (où $L$ apparaît $n$ fois) se donne aussi $n*L$ ou $L*n$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "L+L+L==3*L, L*4==4*L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print (3*L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans une liste, on peut modifier la valeur d'une entrée :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print (\"L[2]=\",L[2])\n",
    "L[2]=\"je suis nouveau\"\n",
    "print (\"L[2]=\",L[2])\n",
    "print (L)\n",
    "L[4]=M\n",
    "print (L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il est parfois utile de créer une liste vide :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "liste=[]\n",
    "print(\"liste=\",liste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut aussi tester si un élément figure dans une liste, l'insérer en fin de liste ou à un endroit fixé ou encore suppprimer l'élément correspondant à un indice fixé :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A=[1,2,3,4,5,16,7]\n",
    "print (\"A=\",A)\n",
    "A.append(1.11)\n",
    "print (\"A=\",A)\n",
    "A.insert(5,-2)\n",
    "print (\"A=\",A)\n",
    "A.pop(6)\n",
    "print (\"A=\",A)\n",
    "A.remove(2)        ### cette fonction ne marchera pas si 2 n'est pas dans A...\n",
    "print (\"A=\",A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On note la syntaxe du type $\\texttt{x.fonction(...)}$ qui signifie qu'on applique la fonction (avec les arguments donnés entre parenthèses) à l'objet $\\texttt{x}$. Il existe aussi des fonctions prédéfinies pour les listes :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print (max(A), \"est le plus grand nombre de la liste A\")\n",
    "print (min(A), \"est le plus petit nombre de la liste A\")\n",
    "A = sorted(A) # la même liste en réordonnant les éléments\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Et des $\\texttt{listes}$ prédéfinies qui permettent de définir des suites très rapidement :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A=range(10)\n",
    "print(len(A))\n",
    "print(A[0],A[1],A[2],A[3],A[4],A[5],A[9])\n",
    "print(A[4])\n",
    "B=A[0:8:3]\n",
    "print(len(B))\n",
    "print(B[0],B[1],B[2])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# La boucle for"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La commande $\\texttt{for}$ permet d'itérer une instruction ; par exemple, on peut l'utiliser avec toute liste de nombres :  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for i in A:\n",
    "    print (i**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ou comme indice classique, éventuellement avec une incrémentation différente de 1 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for i in range(10):\n",
    "    print(i**3)             \n",
    "print (\"\\n\")\n",
    "    \n",
    "for i in range(1,10,2):\n",
    "    print (i**3),      ### A quoi sert la virgule ??\n",
    "print (\"\\n\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut ainsi se donner très rapidement les termes d'une suite (définie par une formule explicite) :  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print([i**3 for i in range(10)])\n",
    "print ([n+n**2 for n in range(1,10)])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut imbriquer des boucles :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "L=[]                           #### je vais ranger toutes mes valeurs dans une liste L\n",
    "for i in range (5):\n",
    "    for j in range (5):\n",
    "        L.append((i+j)**2)  \n",
    "print (L)        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Définir de nouvelles fonctions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Il est temps de définir nos propres $\\textit{fonctions}$ ; par exemple, la $\\textit{fonction}$ $f(x):=x^5+12x^3-6x+7$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def f(x):           # f est le nom de notre fonction\n",
    "                    # elle s'applique à une variable (qu'on appelle x)\n",
    "    return(x**5+12*x**3-6*x+7)  # ce que renverra f(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A présent, je peux chercher les valeurs des images que je veux :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print(f(1),f(-2),f(0),f(4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Attention, l'instruction $\\texttt{return}$ est importante ; c'est elle qui nous dit ce que vaut $f(x)$. Par exemple, la fonction $g$ suivante semble faire la même chose que $f$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def g(x):                   \n",
    "    print(x**5+12*x**3-6*x+7) \n",
    "g(1),g(-1),g(0),g(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mais c'est ne pas du tout le cas comme le petit calcul suivant peut nous en convaincre :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print(f(1)+f(-2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g(1)+g(-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici l'exemple de la fonction qu'on va appeler $\\texttt{facto}$ qui calcule la $factorielle$ en utisant l'instruction conditionnelle $\\texttt{while}$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def facto(x) :   # je donne un nom à la fonction\n",
    "    f=1          # une variable intermédiaire que je vais utiliser\n",
    "                 # pour faire le calcul\n",
    "    while(x>0) :\n",
    "        f=f*x \n",
    "        # je calcule x!... C'est clair ??\n",
    "        x=x-1\n",
    "    return f     # ma fonction va renvoyer x !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et maintenant, je peux utiliser ma fonction $\\texttt{facto}$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print (\"100!=\",facto(100))\n",
    "for i in range(8):\n",
    "    print (i,\"! =\",facto(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il peut bien entendu exister plusieurs façons de calculer une même fonction :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def facto2(x):             ##### méthode itérative\n",
    "    a=1\n",
    "    for i in range(2,x+1):\n",
    "        a *= i              ### noter le raccourci de a=a*i\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "facto2(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une fonction peut avoir plusieurs arguments ; par exemple, si on veut une fonction qui calcule le PGCD (cf. Exercice 7) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def PGCD(a,b):\n",
    "    A,B=a,b\n",
    "    while B!=0:\n",
    "        A,B=B,A%B\n",
    "    return(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print(PGCD(28,45))\n",
    "print(PGCD(48,45))\n",
    "print(PGCD(3**7*5**2*11*4,3*22*5**4*13))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# L'instruction if"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "L'instruction conditionnelle $\\texttt{if}$ permet de s'assurer qu'une condition est vérifiée. Par exemple, la fonction $\\texttt{facto2}$ que l'on vient de voir nécessite des entiers (est-ce aussi la cas de $\\texttt{facto}$ ?) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "facto2(3.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut donc intégrer une vérification que l'argument rentré est bien un entier :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def facto2(x):            ##### méthode ITERATIVE\n",
    "    if type(x) != int:                ## si la condition est vérifiée, on fait...            \n",
    "        return(\"hé, il faut donner un entier !!\")  \n",
    "    else:                   ## si la condition n'est pas vérifiée, on fait... \n",
    "        a=1                                        \n",
    "        for i in range(2,x+1):\n",
    "            a *= i              ### noter le raccourci de a=a*i\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "facto2(3.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'instruction $\\texttt{if}$ est très utile pour définir les fonctions ; voici une nouvelle version du calacul de la fonction $factorielle$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def facto3(x):        ###### méthode RECURSIVE\n",
    "    if x==0:\n",
    "        return(1)\n",
    "    else :\n",
    "        return(x*facto3(x-1))   ##### Une fonction récursive est une fonction qui fait\n",
    "                                ##### appel à elle-même"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "facto3(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans l'exemple suivant, on va calculer le nombre de solutions du trinôme $ax^2+bx+c$ avec $a\\neq 0$  et $a,b,c$ réels :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def nb_de_racines(a,b,c):\n",
    "    if a==0:\n",
    "        print(\"ce n'est pas une équation du second degré\")\n",
    "    else :\n",
    "        delta=b**2-4*c\n",
    "        if delta > 0:\n",
    "            print(\"L'équation a deux solutions réelles\")\n",
    "        else :\n",
    "            if delta == 0:\n",
    "                print(\"L'équation a une unique solution réelle (racine double)\")\n",
    "            else :\n",
    "                print(\"L'équation n'a pas de solution réelle\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nb_de_racines(1,0,-1)\n",
    "nb_de_racines(1,0,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans l'exemple précédent, on peut trouver déplaisante la cascade de $\\texttt{if}$. L'instruction $\\texttt{elif}$ est faite pour éviter ce genre de cascade :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def nb_de_rac(a,b,c):\n",
    "    delta=b**2-4*c\n",
    "    if a==0:\n",
    "        print(\"ce n'est pas une équation du second degré\")\n",
    "    elif delta >0 :\n",
    "        print(\"L'équation a deux solutions réelles\")\n",
    "    elif delta == 0 :\n",
    "        print(\"L'équation a une unique solution réelle (racine double)\")\n",
    "    elif delta < 0 :\n",
    "        print(\"L'équation n'a pas de solution réelle\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nb_de_rac(1,0,1)\n",
    "nb_de_rac(1,-2,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 8 : années bissextiles\n",
    "\n",
    "Ecrire une fonction booléenne $\\texttt{bissectile(n)}$ qui renvoie 1 si $n$ est une année bissectile et 0 sinon. On rappelle que les années bissextiles reviennent tous les 4 ans, sauf lorsqu'elles sont un multiple de cent qui n'est pas un multiple de 400. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Exercice 9 :  le crible d'Eratosthène\n",
    "\n",
    "Ecrire une liste qui contient les nombres premiers inférieurs à 100, obtenus en appliquant la méthode du crible d'Ertosthène."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 10 : somme de carrés\n",
    "\n",
    "Ecrire une fonction qui, pour tout $M$ réel postif, retourne le couple $(n,m)$ où $n$ est le plus petit entier tel que $m=1+2^2+3^2+...+n^2 >=M$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 11 : présent ou pas\n",
    "\n",
    "Ecrire une fonction $\\texttt{present(x,L)}$ qui retourne $\\texttt{True}$ si $x$ est dans $L$ et $\\texttt{False}$ sinon (et qui vérifie que le second argument est bien une liste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 12 : présence d'une lettre dans un mot\n",
    "\n",
    "Ecrire une fonction $\\texttt{presente(a,M)}$ qui retourne l'indice de la lettre $a$ dans la chaîne $M$ si $a$ est dans $M$, qui renvoie -1 sinon et qui vérifie que le second argument est bien une chaîne de caractères."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 13 : écriture en base 16\n",
    "\n",
    "Ecrire une fonction $\\texttt{H(n)}$ qui renvoie l'écriture en base 16 de l'entier n (les chiffres retenus pour l'écriture en base 16 sont $0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 14 : Test de primalité \n",
    "\n",
    "Ecrire une fonction $\\texttt{est_premier(N)}$ qui retourne $\\texttt{True}$ si l'entier $N>=2$ est premier et $\\texttt{False}$ sinon en testant si $N$ admet un diviseur parmi les entiers inférieurs ou égaux à sa racine carrée. On utilisera la fonction $\\texttt{sqrt}$ (qu'il faudra peut-être importer, par exemple en tapant $\\texttt{from math import *}$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 15 : décomposition en produit de facteurs premiers\n",
    "\n",
    "Ecrire une fonction $\\texttt{decomposition_en_facteurs_premiers(N)}$ qui retourne la décomposition en facteurs premiers de l'entier $\\texttt{N>=2}$\n",
    "(nota bene : le résultat est attendu sous la forme d'une chaîne de caractères)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}