Introduction à la Programmation Python

1. Manipulation des objets élémentaires

1.1. Entiers

((567*34 -(222 + 103*(890-888))*5*3**(3127-5**5))**4 + 17471268) // 1454586
((567*34 -(222 + 103*(890-888))*5*3**(3127-5**5))**4 + 17471268) % 1454586

1.2. Opération Booléennes

Pour 1, 2, et 3 on obtient dans l’ordre : True, False et True. On remarque que l’expression 1 donne le même résultat que l’expression 3. Le and est donc prioritaire sur le or.

Pour la 4, on obtient True puis False, le not est donc prioritaire sur le and et le or.

1.3. Flottants

(530.4709375 * 42) ** (1/6) / 3.5

150 // 12 donne un résultat entier, le quotient de la division euclienne, alors que 150 / 12 calcule le résultat de la division flottante. 

2 ** 0.5
(2 ** 0.5) ** 2

On remarque que l’utilisation des flottant implique une approximation des résultats mathématiques attendus, et que cette approximation induit une erreur sur le calcul de \(\sqrt{2}^{2}\).

1.4. Néant

On remarque que la console n’affiche aucun résultat. En effet, lorsque le résultat est None, cela signifie qu’il n’y a pas de résultat.

1.5. Comparaisons

On remarque que les comparaisons sur les flottants ne correspondent pas aux attendus mathématiques. C’est du à la précision finie que nous permet d’avoir un flottant.

On peut observer aussi que B == True renvoie toujours B. Il est donc inutile d’écrire B == True, mieux vaut écrire B directement. De même B == False peut être simplifié en not B.

2. Nommage

2.3. Fonction, Définition

def racine(x,n) :
    return x ** (1/n)
 
def ordonnees(a,b,c,d) :
    return a < b and b < c and c < d
 
def quasiegal(x,y,e) :
    return -e < x-y and x-y < e

2.4. Fonctions, Environnement

Lien vers une simulation Python Tutor

Il y a au plus 2 environnements locaux simultanés, en plus de l’environnement global.

3. Flot d’exécution

3.1. Appels

1, 4, 7, 10, 1, 2, 7, 8, 7, 8, 4, 5, 7, 8, 5, 2, 10

Lien vers une simulation Python Tutor

3.2. Conditionnelles

Lien vers une simulation Python Tutor 

f(10,20) : 1, 2, 3, 4, 11,
f(5,6) : 1, 2, 3, 5, 6, 8, 11,
f(3,4) : 1, 2, 3, 4, 11,
f(7,10) : 1, 2, 3, 5, 10, 11,
f(-3,2) : 1, 2, 3, 5, 6, 7, 8, 11,

3.3. Bissextile

def bissextile(annee) :
    if annee % 400 == 0 :
        return True
    elif annee % 4 == 0 and annee % 100 != 0 :
        return True
    else :
        return False

On peu aussi écrire… 

def bissextile(annee) :
    return annee % 400 == 0 or (annee % 4 == 0 and annee % 100 != 0)

3.4. Boucles

f(12) : 1, 2, 3,
4, 5, 6, 7,
4, 5, 7, ~ x4
4, 5, 6, 7,
4, 5, 7, ~ x4
4, 5, 6, 7,
4, 5, 7,
4, 8,
9, 10, 11, ~ x3
9, 12,

f(21) :
1, 2, 3,
4, 5, 6, 7,
4, 5, 7, ~ x4
4, 5, 6, 7,
4, 5, 7, ~ x4
4, 5, 6, 7,
4, 5, 7, ~ x4
4, 5, 6, 7,
4, 5, 7, ~ x4
4, 5, 6, 7,
4, 8,
9, 10, 11, ~ x5
9, 12,

f(0) : 1, 2, 3, 4, 8, 9, 12,

f(-5) : 1, 2, 3, 4, 8, 9, 12,

f(30) :
1, 2, 3,
4, 5, 6, 7,    | ~ x6
4, 5, 7, ~ x4  |
4, 8,
9, 10, 11, ~ x6
9, 12

4. Etude d’un algorithme

4.1. Simulation Papier

  1. Il y a 5 tours de boucles

  2. Voici les différentes valeurs :

    i 0 1 2 3 4 5
    f 1 1 2 6 24 120
  3. On a f = i!

4.2. Spécification de \(\cal F\)

L’algorithme \(\symcal{F}\) renvoie \(n!\).

4.4. Somme des entiers

On change simplement la multiplication par une addition et la valeur initiale de f par 0. On va renommer f en s pour la clareté. 

def somme(n) :
    i = 0
    s = 0
    while i < n :
        i = i + 1
        s = s + i
    return s

On peut construire ce code par analogie du code, ou par analogie sur la formule de récurrence.

Si on voit le code de l’algorithme F comme le calcul du terme n de la suite récurrente :

\[ \begin{cases} F_{0} & = 1 \\ F_{i+1} & = F_{i} * (i+1) \end{cases} \]

La somme des entiers se définie aussi pas une suite récurrente dont la définition est

\[ \begin{cases} S_{0} & = 0 \\ S_{i+1} & = S_{i} + (i+1) \end{cases} \]

Il suffit donc de garder le squelette de l’algorithme et de changer uniquement le terme initial de la suite et la formule qui permet de calculer le terme suivant à partir du précédent.

5. Diviser ou ne pas Diviser ?

5.1. Divisibilité

def est_diviseur(a,b) :
    return b % a == 0

5.2. Premier

def P(n) :
    p = True
    d = 2
    while d * d <= n :
        if est_diviseur(d,p) :
            p = False
        d = d + 1
    return p

Lien vers une simulation Python Tutor

Il y a un environnement local pour l’appel P(11), puis un environnement local pour chaque appel de est_diviseur, i.e. 2 environnements. Donc 3 environnements locaux au total et 2 qui existent simultanément au plus.

5.3. Euclide

def euclide(a, b) :
    while a != b :
        if a > b :
            a = a - b
        else :
            b = b - a
    return a

6. Suites récurrentes

6.1. Méthode de Halley pour le calcul de \(\sqrt 2\)

def halley(n) :
    i = 0
    h = 1.0 # H0
    while i < n : # Invariant : h est le terme de rang i de la suite.
        h_suiv = h * (h*h + 6.0) / (3.0 * h*h + 2.0)
        i = i + 1 # Rang suivant
        h = h_suiv # h contient le terme suivant.
    return H

6.2. Suite de Fibonacci

def fibonacci(n) :
    rang = 0
    f = 0
    f_suivant = 1
    while rang < n :
        f_suivant2 = f + f_suivant
        rang = rang + 1
        f = f_suivant
        f_suivant = f_suivant2
    return f

6.3. Syracuse

def syracuse(s0) :
    # Rang 0
    rang = 0
    s = s0
    # Calcul du rang suivant, jusqu'à ce que le terme courant soit 1
    while s != 1 :
        if s % 2 == 0 :
            s_suiv = s // 2
        else :
            s_suiv = 3 * s + 1
        rang = rang + 1
        s = s_suiv
    return rang

7. Interlude – \textsc{Pour s'entraîner}

7.1. Suite géométrique

def u(a, q, n) :
    rang = 0
    u = a
    while rang < n :
        u = q * u
        rang = rang + 1
    return u

7.2. Suites adjacentes

def adjacentes(epsilon) :
    a = 1
    b = 2
    i = 0
    while -epsilon > a - b or a - b > epsilon :
        a = 2 / b
        b = (a + b) / 2
        i = i + 1
    return i

7.3. Méthode de Héron

def heron(a,n) :
    x = a
    i = 0
    while i < n :
        x = (x + a / x) / 2
        i = i + 1
    return x

7.4. Nombre parfait

def parfait(n) :
    if n < 2 :
        return False
    somme_diviseurs = 0
    diviseur = 1
    while diviseur < n :
        if n % diviseur == 0 :
            somme_diviseurs = somme_diviseurs + diviseur
        diviseur = diviseur + 1
    return somme_diviseur == n

On peut diminuer le nombre de diviseurs potentiels à vérifier en remarquant que si d divise n alors n // d divise n et que les diviseurs vont donc par pairs avec un diviseur plus petit que \(\sqrt n\) et un autre strictement plus grand. Il faut exclure les cas de \(1\) allant de pair avec \(n\) et de \(\sqrt n\) si il est entier qui va de pair avec lui même et ne doit pas être ajouté deux fois. 

def parfait_opt(n) :
    if n < 2 :
        return False
    somme_diviseurs = 1
    diviseur = 2
    while diviseur * diviseur < n :
        if n % diviseur == 0 :
            somme_diviseurs = somme_diviseurs + diviseur + ( n // diviseur)
        diviseur = diviseur + 1
    if diviseur * diviseur == n :
        somme_diviseurs = somme_diviseurs + diviseur
    return somme_diviseur == n

8. Interlude – \textsc{Pour aller plus loin}

8.1. Logarithme entier

Plusieurs visions sont possible.

  1. Partir de \(0\) et essayer tous les entiers \(l\) jusqu’à trouver le premier tel que \(b^l > n\).
  2. Transformer l’inégalité comme ceci : \[ 1 \leq \frac{n}{b^l} < b \] En conclure qu’il faut diviser \(n\) par \(b\) jusqu’à obtenir un nombre entre 1 et \(b\). \(l\) est le nombre de division effectuée
def log_entier(n, b) :
    l = 0
    q = n
    while 1 > q or q > b :
        q = q // b
        l = l + 1
    return l

8.2. Nombres Chanceux d’Euler

def premier(n) :
    """
    Entrées : n un entier >= 2
    Sortie : True ssi n est premier
    """
    diviseur = 2
    while diviseur * diviseur <= n :
        if n % diviseur == 0 :
            return False
        diviseur = diviseur + 1
    return True
 
def chanceux_euler(n) :
    i = 0
    while i <= n - 2 :
        if not premier(i * i + i + n) :
            return False
        i = i + 1
    return True

8.3. Fonction 91 de McCarthy

Cette fonction fait parti d’un groupe de fonction qui ont peu d’intérêt en soit, mais qui sont utilisées pour tester la performance des compilateurs.

La fonction est naturellement recursive… Mais on ne sait pas encore ce que ça veut dire…

Pour la coder de manière itérative, il faut se tordre un peu l’esprit…

On peut voir la fonction sous cet angle :

\[ \forall k \in \symbb{N^{*}, f^{k}(n) = \begin{cases} f^{k-1}(n-10) & \text{si} n>100 \\ f^{k+2}(n+11) & \text{sinon.} \end{cases} \]

Gardons un compteur profondeur qui compte le nombre de fois que la fonction doit être appliquée sur n. Au départ ce compteur sera égal à 1 vu qu’on cherche à calculer \(f(n)\).

On applique la fonction tant que le compteur n’est pas nul, cas de base de la définition.

  • si l’entrée > 100 alors on applique la fonction on enlève 10 à l’entrée. On diminue le compteur de 1, et le résultat sera l’entrée de la prochaine application de fonction.
  • si l’entrée <= 100 alors on ajoute 11 à l’entrée, et on augmente le compteur de 1. Le resultat sera l’entrée de la prochaine application de fonction.
def mccarthy91(n) :
    k = 1
    e = n
    # Invariant : f(n) = f^k(e)
    while k != 0 :
        if e > 100 :
            e = e - 10
            k = k - 1
        else :
            e = e + 11
            k = k + 1
    # Ici k vaut 0 dans f(n) = f^0(e) = e
    return e

9. Manipulation des listes

9.1. Création

l0 = [1,3,6]
l0[3] # IndexError
x = l0[len(l0)-1]
l1 = [12] * 144
l2 = l0 + l1 # Attention, ce n'est pas pareil que l1 + l0
l0 = []
l1 = l2[1:5]

9.2. Modification

l1[0] = 1
l1[1] = l1[2] // l1[1]
x = l1.pop()
l1[2] = len(l1)
l1.append(40 % x)

10. Etude d’un algorithme

10.1. Simulation Papier

  1. Il y a 10 tours de boucle.

  2. Les valeurs de i et m sont :

    i 1 2 3 4 5 6 7 8 9 10
    m 3 3 4 4 4 5 5 10 10 10
  3. m = max(l[:i])

10.2. Spécification de nadine

Comme à la fin i est égal à la longueur de la liste l, m = max(l). nadine renvoie le maximum de la liste donnée en entrée, ou None si celle-ci est vide.

10.3. Vérification

def nadine(l) :
    n = len(l)
    if n == 0 :
        return None
    m = l[0]
    i = 1
    while i < n :
        if m < l[i] :
            m = l[i]
        i = i + 1
    return m

Lien vers une simulation Python Tutor

11. Algorithmique des listes

11.1. Minimum de liste

11.2. Somme des éléments d’une liste

def somme(l) :
    n = len(l)
    i = 0
    somme = 0
    while i < n :
        somme = somme + l[i]
        i = i + 1
    return somme

11.3. Maximum, minimum, moyenne, variance

def imax(l) :
    n = len(l)
    if n == 0 :
        return None
    i_max = 0
    i = 1
    while i < n :
        if l[i] > l[i_max] :
            i_max = i
        i = i + 1
    return i_max

def imin(l) :
    n = len(l)
    if n == 0 :
        return None
    i_min = 0
    i = 1
    while i < n :
        if l[i] < l[i_min] :
            i_min = i
        i = i + 1
    return i_min

def moyenne(l) :
    n = len(l)
    i = 0
    somme = 0
    while i < n :
        somme = somme + l[i]
        i = i + 1
    return somme / n
# ou en utilisant la question précédente
def moyenne(l) :
    return somme(l) / len(l)

def variance(l) :
    n = len(l)
    i = 0
    moy = moyenne(l)
    somme = 0.0
    while i < n :
        somme = somme + (l[i] - moy) ** 2
        i = i + 1
    return somme / n

11.4. Recherche Linéaire

def recherche(l, x) :
    n = len(l)
    i_x = -1
    i = 0
    while i < n and i_x == -1 :
        if l[i] == x :
            i_x = i
        i = i + 1
    return i_x

11.5. Addition de deux listes

def somme(l1 : list[int], l2 : list[int]) -> list[int] :
    i = 0
    n = len(l1)
    l = [0] * n
    while i < n :
        l[i] = l1[i] + l2[i]
        i = i + 1
    return l

def addition(l1, l2) :
    n = len(l1)
    i = 0
    l = []
    while i < n :
        l.append(l1[i] + l2[i])
        i = i + 1
    return l

11.6. Liste des diviseurs

def diviseurs(n) :
    n = len(l1)
    d = 1
    l = []
    while d <= n :
        if n % d == 0 :
            l.append(d)
        d = d + 1
    return l

12. \textsc{Pour s'entraîner}

12.1. Moyenne pondérée

def moyenne_ponderee(l, c) :
    n = len(l)
    somme_pond = 0
    somme_coeff = 0
    i = 0
    while i < n :
        somme_pond = somme_pond + l[i] * c[i]
        somme_coeff = somme_coeff + c[i]
        i = i + 1
    return somme_coeff / somme_pond

12.2. Éléments impairs

def impairs(l) :
    n = len(l)
    i = 0
    impairs = []
    while i < n :
        if l[i] % 2 == 1 :
            impairs.append(l[i])
        i = i + 1
    return impairs

12.3. Liste des multiples

def multiples(n,m) :
    multiple = 0
    l = []
    while multiple <= n :
        l.append(multiple)
        multiple = multiple + m
    return multiple

12.4. Encadrement

On utilise deux astuces pour initialiser a et b ici.

On sait que les entiers de la liste sont positifs. En initialisant b à -1, on sait qu’il est plus petits que tous les éléments de la liste. Ainsi, le premier élément de la liste plus grand que x que l’on trouve sera plus grand que b. b deviendra cet élément, et b sera bien le plus petit élément de la liste plus grand que x trouvé à ce moment là. Si on ne trouve aucun élément de la liste plus grand que x, b ne change pas et on renvoie bien -1.

Pour ce qui est de a, on remarque que -a est le plus petit élément plus grand que -x dans la liste -l, où chaque entier est remplacé par son opposé. On peut donc le même algorithme de calcul que pour b mais en opposant chaque valeur. Ainsi b = -1 devient a = 1, l[i] > x and l[i] > b devient -l[i] > -x and -l[i] > a, donc l[i] < x and -a < l[i]. Il suffit de renvoyer -a à la fin. 

def encadrement(l,x) :
    n = len(l)
    a = 1
    b = -1
    i = 0
    while i < n :
        if l[i] == x :
            return [x,x]
        elif l[i] < x and -a < l[i] :
            a = -l[i]
        elif l[i] > x and l[i] < b :
            b = l[i]
        i = i + 1
    return [-a,b]

13. \textsc{Pour aller plus loin}

13.1. Crible d’Eratosthène

La grille d’entiers sera une liste crible.

Pour barrer les éléments il n’est pas efficace de les supprimer les éléments de la liste. Mieux vaut créer une nouvelle liste sans les éléments à barrer. 

def eratosthene(n) :
    premiers = []
    crible = []
    k = 2
    while k <= n :
        crible.append(k)
        k = k + 1
    while len(crible) != 0 :
        premiers.append(crible[0])
        nouveau_crible = []
        i = 0
        while i < len(crible) :
            if crible[i] % crible[0] != 0 :
                nouveau_crible.append(crible[i])
            i = i + 1
        # On associe crible à la nouvelle liste.
        crible = nouveau_crible # Ce n'est pas une copie !
    return premiers

13.2. Tri de liste

Le tri sélection est peut-être le plus intuitif.

  1. Trouver l’indice i du minimum de la liste l et échanger l’élément d’incide i avec celui d’indice 0.
  2. Trouver l’indice i du minimum de la liste l[1:] et échanger l’élément d’incide i avec celui d’indice 1.
  3. … Répéter jusqu’à l’avant dernier indice.

Par exemple sur la liste [5,3,6,3,1,2] :

  1. Echange de 1 et 5 : [1,3,6,3,5,2]
  2. Echange de 2 et 3 : [1,2,6,3,5,3]
  3. Echange de 6 et 3 : [1,2,3,6,5,3]
  4. Echange de 6 et 3 : [1,2,3,3,5,6]
  5. Echange de 5 et 5 : [1,2,3,3,5,6]
  6. Fin de l’algorithme
def tri_selection(l) :
    n = len(l)
    debut = 0
    while debut < n - 1 :
        m = debut
        i = debut+1
        while i < n :
            if l[i] < l[m] :
                m = i
            i = i + 1
        temp = l[m]
        l[m] = l[debut]
        l[debut] = temp
        debut = debut + 1
    return None

13.3. Calcul de la Médiane

def mediane(l) :
    k = l.copy()
    tri_selection(k)
    if len(k) % 2 == 1 :
        return k[len(k) // 2]
    return (k[len(k) // 2] + k[len(k) // 2 + 1]) / 2

Une autre méthode, sans trier, mais moins efficace (surtout si on trie de manière plus efficace), consiste chercher les éléments du milieu en comptant pour chaque élément combien il y en a de plus petits.

14. Chaînes et séquences

14.1. Recherche linéaire

def recherche_lineaire(s,c):
    for i in range(len(s)):
        if s[i] == c:
            return i
    return -1

14.2. Comptage chaîne

def compter_chaine(s,c):
    n = 0
    for car in s:
        if car == c:
            n = n + 1
    return n

14.3. Addition de liste

def addition_liste(l1,l2):
    l = []
    for i in range(len(l1)):
        l.append(l1[i] + l2[i])
    return l
 
# ou

def addition_liste(l1,l2):
    return [ l1[i] + l2[i] for i in range(len(l1)) ]

14.4. Addition de tuple

def addition_tuple(t1,t2):
    t = ()
    for i in range(len(t1)):
        t = t + (t1[i] + t[2],)
    return t

14.5. Deuxième minimum

def deuxieme_minimum(l):
    m = float("inf")
    m2 = float("inf")
    for x in l:
        if x < m:
            m = x
            m2 = m
        elif x < m2:
            m2 = x
    return m2

14.6. Voyelles

def voyelles(s):
    v = ""
    for c in s:
        if recherche_lineaire("aeiouyAEIOUY",c) != -1:
            v = v + c
    return v

15. Passage en deux dimensions

15.1. Pyramide

Pour produire la pyramide, on va produire chaque étage qu’on va concatener les un avec les autres, séparés par un retour à la ligne.

Pour produire le ième étage, on doit connaître :

  1. le nombre d’allumettes de l’étage
  2. la taille de la base de la pyramide pour pouvoir compléter avec des espaces

Le nombre d’allumettes à l’étage \(i\), \(0 \leq i < n\) , est \(2i + 1\). La base d’une pyramide de n étage est donc \(2n + 1\) allumettes. À chaque étage il reste \(2n + 1 − 2i + 1 = 2(n − i + 1)\) espaces. On les répartis, \((n − i + 1)\) espaces de chaque cotés pour équilibrer.

Le ième étage sera donc produit au ième tour de boucle du programme. 

def pyramide(n):
    str_pyramide = ""
    etage = 0
    for etage in range(n) :
        str_etage = (" " * (n - etage + 1)
                     + "|" * (2 * etage + 1)
                     + " " * ( n - etage + 1))
        str_pyramide = str_pyramide + str_etage + "\n"
    return str_pyramide

15.2. Table ASCII

def table_ascii():
    table = ""
    ligne_initiale = " "  # Ligne initiale
    for col in range(10) :
        ligne_initiale = ligne_initiale + " " + str(col) + " "
    # Barre
    barre = "-" * len(ligne_initiale)
    # Tableau 
    table = ligne_initiale + barre + "\n"
    # Ecriture de chaque ligne
    for ligne in range(0,130,10) : 
        ligne_courante = str(ligne) # Première colonne
        # Ecriture de chaque colonne 
        for col in range(10) :
            ligne_courante = ligne_courante + " " + chr(ligne + colonne) + " " 
        table = table + ligne_courante + "\n"
    return table

15.3. Table de multiplication

def table_multiplication(n : int) -> str : 
    table = ""
    colonne = 0
    # Ligne initiale
    ligne_initiale = ""
    ligne_initiale = ligne_initiale + " " # Première colonne
    while colonne <= n :
        # Affichage du chiffre de la colonne
        ligne_initiale = ligne_initiale + " " + str(colonne) + " " 
        colonne = colonne + 1
    table = ligne_initiale + "\n"
    # Barre
    barre = "-" * (1 + 3 * (n + 1))
    table = table + barre + "\n"
    # Tableau 
    ligne = 0
    # Ecriture de chaque ligne
    while ligne <= n : 
        colonne = 0
        ligne_courante = ""
        ligne_courante = ligne_courante + str(ligne) # Première colonne
        # Ecriture de chaque colonne 
        while colonne <= n :
            ligne_courante = ligne_courante + " " + str(ligne * colonne) + " " 
            colonne = colonne + 1
        table = table + ligne_courante + "\n"
        ligne = ligne + 1 # On passe à la dizaine suivante
    return table