Branches conditionnelles et boucles

L'extrait ci-dessous implémente une fonction maximum.

def maximum(a,b):
    if a >= b:   # Si a≥ b
        return a # renvoyer a
    else:        # sinon
        return b # renvoyer b

\hspace{0.4cm} Règles de syntaxe pour l'utilisation if :

• Le if est suivi une expression (a>=b) qui s'évalue en un booléen, suivi de « : ».
• Les instructions qui sont à exécuter sous cette condition sont indentées.
• Le else:, optionnel, est au même niveau d'indentation que le if.
• Les instructions à exécuter sous le else sont indentées.

Le if signifie «si» et le else «sinon». On peut utiliser une branche if sans la compléter d'une branche else.

Ces opérateurs renvoient un booléen, c'est-à-dire True ou False. Pour chaque exemple plus haut, préciser à droite s'il renvoie True ou False.

In [1]: (7**8 > 8**7) or (7**8 < 8**7)
Out[1]: True # Rmq : les parenthèses sont inutiles

In [2]: (7**7) % 2 == 1 and not (7**7) % 3 == 0
Out[2]: True # Idem

Dans une fonction, l'instruction return interrompt l'exécution du corps de la fonction et peut simplifier la logique.

Les deux schémas suivants sont équivalents.

def fn(…):
    if C:
        return A
    else:
        return B

def fn(…):
    if C:
        return A
    return B

Le schéma de gauche suivant est à éviter, étant équivalent à celui de droite.

def fn(…):
    if C:
        return True
    else:
        return False

def fn(…):
    return C

def f(a):
    if a % 2 > 0:
        print("impair")
        return a
    print("pair")

f(5)

def g(a):
    if a % 2 > 0:
        return(a)
        print("impair")
    print("pair")

g(5)

def h(a):
    if a % 2 > 0:
        print("impair")
    print("pair")


h(5)

\vspace*{2\baselineskip}

La fonction positifs_non_nuls prend deux arguments et renvoie True si ses deux arguments sont positifs, et non tous les deux nuls. Les trois extraits suivants sont équivalents.

def positifs_non_nuls(a,b):
    if a > 0:
        if b >= 0:
            return True
        else:
            return False
    if a >= 0:
        if b > 0:
            return True
    return False

def positifs_non_nuls(a,b):
    if a > 0:
        return b >= 0
    if a == 0:
        return b > 0
    return False

def positifs_non_nuls(a,b):
    return (a >= 0 and b > 0) or (a > 0 and b >= 0)

Les assertions sont des instructions particulières qui prennent la forme assert(condition). Si condition s'évalue en True, cette instruction ne fait rien, et si condition est False, l'instruction interrompt l'exécution du programme et signale une erreur.

Dans le shell, essayer les commandes assert(1+1==2) et assert(1+1==3).

On utilisera les assertions

1. pour tester les valeurs renvoyées par une fonction sur des exemples,
2. éventuellement pour signaler des conditions qui doivent être vérifiées par les arguments d'une fonction.

La fonction suivante prend en argument trois entiers a,b,c, avec $a\neq 0$, et renvoie le nombre de solutions réelles de l'équation $ax^2 + bx + c = 0$ en calculant le discriminant du polynôme.

### Nombre de solutions d'un trinôme

def nb_sols(a,b,c):
    assert(a != 0)  # si a=0, ce n'est pas un trinôme
    d = b*b - 4*a*c # Δ = b² − 4ac
    if d > 0:
        return 2    # early return : le reste n'est pas évalué
    if d == 0:
        return 1
    return 0        # dans ce cas, c'est que Δ < 0
# Les assertions suivantes sont en dehors du corps de la fonction
# Elles testent le comportement de la fonction
assert(nb_sols(1,0,1) == 0)  # x² + 1 = 0 n'a pas de solutions
assert(nb_sols(1,2,1) == 1)  # x² + 2x + 1 = 0 a une unique solution : −1
assert(nb_sols(1,0,-1) == 2) # x² − 1 = 0 a deux solutions : ± 1

Un bon jeu de tests doit couvrir les différents cas généraux possibles, et d'éventuels cas critiques (arguments nuls, ou liste vide par exemple).

Le développement piloté par les tests (test-driven development), est une pratique de développement qui consiste à concevoir un programme (une fonction, un logiciel) en écrivant les tests avant d'écrire le code source. En plus d'assurer la correction de la fonction finale (si les tests passent), cette pratique force à s'interroger sur le comportement que devra avoir la fonction dans les cas critiques.

Les boucles permettent de répéter un bloc d'instructions. La boucle for de Python permet de répéter des instructions un nombre prédéterminé $n$ de fois. On l'utilise avec l'instruction range(n) qui énumère les entiers de $\boxed{0 \text{ à }n-1}$ (il y en a $n$).

Dans les extraits suivants ( essayer), la variable i va prendre successivement les valeurs de l'énumération, et pour chaque valeur, les instructions à l'intérieur de la boucle seront exécutées.

for i in range(5):
    print("Coucou")

for i in range(5):
    print(i)

La fonction suivante calcule la somme $S = \sum_{i=1}^n i$ des entiers de $1$ à $n$.

def somme(n):
    s = 0                   # La somme sera stockée dans la variable s
    for i in range(1,n+1):  # i prend les valeurs entières de 1 à n
        s = s + i           # On incrémente la variable s
    return s                # Noter le retour à l'indentation précédente

Noter les « : » obligatoires dans la ligne du for, et l'indentation qui suit. Ce sont les instructions sous l'indentation qui seront répétées.

s = 0
for i in range(2,5):
    s = s + 1
s = s + 1

s = 0
for i in range(2,5):
    s = s + 1
    s = s + 1

Si $(u_n)_{n\in\N^*}$ est une suite, on note $\sum_{k=1}^n u_k$ la somme des termes d'indice $k$ de la suite, pour $k$ variant de $1$ à $n$. Autrement dit, $\displaystyle\sum_{k=1}^n u_k = u_1 + u_2 + \dots + u_n$, et par convention $\displaystyle\sum_{k=1}^0 u_k = 0$.

\enlargethispage{1.5cm}

Une boucle while (tant que) répète une série d'instruction tant qu'une condition est vérifiée.

1. Comprendre, puis exécuter () le premier extrait.

2. Quel résultat est-ce que l'exécution du deuxième extrait va produire ? Vérifier.

   Utiliser un des boutons en haut du shell pour interrompre l'exécution (l'éclair jaune).

i = 0
while i < 3: # tant que i< 3
    print(i)
    i = i+1  # ou i += 1

i = 0
while i < 5: # tant que i< 5
    print(i)
i = i+1      # ou i += 1

Dans l'extrait de gauche qui suit, la même boucle for i est exécutée deux fois. L'extrait de droite est donc équivalent.

s = 0
for i in range(3):
    s = s + i
for i in range(3):
    s = s + i

s = 0
for j in range(2):
    for i in range(3):
        s = s + i

s1 = 0
for i in range(3):     # i prend les valeurs 0,1,2
    for j in range(3): # j prend les valeurs 0,1,2
        s1 = s1 + j

s2 = 0
for i in range(3):
    for j in range(3):
        s2 = s2 + i + j

s3 = 0
for i in range(3):
    for j in range(i,3):
        s3 = s3 + i + j

Une itération avec deux boucles for imbriquée sur deux ensembles $I$, $J$ indépendant revient à itérer sur les couples du produit cartésien $I\times J$. En particulier, les instructions à l'intérieur sont exécutées $|I|\times |J|$ fois.

for i in range(n):
    for j in range(m):
        # Exécuté nm fois
        f(i, j)

for i in range(n):
    for j in range(n):
        # Exécuté n² fois
        f(i, j)

for i in range(n):
    for j in range(i, n):
        # Exécuté \frac{n(n+1)}{2} = O(n²) fois
        f(i, j)

def S1(n):
    s = 0
    for i in range(1,n+1):
        for j in range(1,n+1):
            s += 1/(ij)
    return s

def S2(n):
    s = 0
    for i in range(1,n+1):
        for j in range(j+1,n+1):
            s += 1/(ij)
    return s

# Affichage des nbs triangulaires qui sont des carrés
import math
for i in range(math.floor(math.sqrt(1000)) + 1):
    n = i ** 2
    j = 0
    while (j * (j+1)) // 2 < n:
        j += 1
    if (j * (j+1)) // 2 == n:
        print n

Quand un algorithme utilise une boucle while, il faut vérifier que celle-ci termine, c'est-à-dire que la condition d'arrêt finit (ici m < b) par être vérifiée.

Pour cela, on utilise un variant de boucle. Dans la majorité des cas, c'est une variable prenant des valeurs entières positives dont la valeur décroît strictement à chaque itération de la boucle. Comme il n'existe pas de suite d'entiers naturels strictement décroissante, cela justifie que la boucle ne tourne qu'un nombre fini de fois, donc que la condition d'arrêt est atteinte.

Dans la fonction mystere, la variable m prend des valeurs entières positives (car la boucle s'arrête si $m\lt 0$) et strictement décroissantes (car $b\gt 0$). Cela justifie la terminaison de l'algorithme. On a également identifié l'hypothèse importante ($b\gt 0$).

La fonction mystere détermine le reste de la division euclidienne de n par b.

Pour justifier qu'elle fait bien cela, on utilise un invariant de boucle. On identifie une quantité qui ne change pas de valeur, ou une assertion mathématique qui reste vraie à chaque itération de la boucle.

On appelle complexité d'un algorithme le nombre d'opérations élémentaires exécutées en fonction de la taille des paramètres d'entrée.

Comme le quotient de la division euclidienne de $n$ par $b$ est $\lfloor \frac{n}{b}\rfloor$, d'après le second invariant de boucle, la boucle de la fonction mystere sera exécutée $\lfloor \frac{n}{b}\rfloor$ fois.

À l'intérieur de la boucle, on exécute une soustraction et une affectation. La fonction réalise donc au total $\lfloor \frac{n}{b}\rfloor$ soustractions et affectations et $\lfloor \frac{n}{b}\rfloor + 1$ comparaisons.

On dira que la complexité est en $O(\frac{n}{b})$ opérations élémentaires, c'est-à-dire que le nombre d'opérations élémentaires est majoré par $K \frac{n}{b}$, pour une certaine constante $K$.

Dans le calcul du pgcd de $a,b$ par l'algorithme d'Euclide, notons $a_n, b_n$ les entiers considérés à l'issue de la $n$-ième itération de la boucle, définis par $$\begin{cases}a_0 = a \\ b_0 = b \end{cases}\quad \et \quad \forall n\in\N,\,\begin{cases}a_{n+1} = b_n \\ b_{n+1} = r_n \end{cases}, \text{ où } a_n = b_n q_n + r_n \text{ est la division euclidienne.}$$

On se convainc aisément que pour tout $n\in\N$, $a_n$ et $b_n$ sont des combinaisons linéaires entières des entiers $a,b$ d'origine, c'est-à-dire qu'il existe $u_n,v_n\in\Z$ tels que $b_n = u_n a + v_n b$. En particulier, à la dernière étape, $\op{pgcd}(a,b)$ est lui-même une combinaison linéaire de $a,b$ :

def eucl_etendu(a0,b0):
    # Inutile d'échanger a et b si b> a, l'algorithme fonctionne
    # quand même, avec une étape qui ne fait justement qu'échanger a
    # et b.

    a, b = a0, b0 # On utilise d'autres variables, pour clarifier
    ua, va = 1, 0 # a = uₐ a₀ + vₐ b₀, invariant qui sera maintenu par la suite
    ub, vb = 0, 1 # b = u_b a₀ + v_b b₀, invariant

    while b != 0:
        r, q = a % b, a // b
        # On a r = a − bq = (uₐ a₀ + vₐ b₀) − q (u_b a₀ + v_b b₀)
        # Donc r = a₀ (uₐ − q u_b) + b₀ (vₐ − q v_b)
        a, b = b, r
        ur, vr = ua - q * ub, va - q * vb
        ua, va = ub, vb
        ub, vb = ur, vr
    # À l'issue de la boucle, le a est égal au pgcd
    return (ua, va)