Algorithmique & programmation (Python)

Algorithmique & programmation (Python) — socle

Idée. Un algorithme est une suite finie d'instructions précises qui transforme des données en un résultat ; un programme l'écrit dans un langage qu'une machine exécute. Programmer sert à calculer ce qu'on ne ferait pas à la main, et surtout à penser juste : une machine n'interprète rien, il faut savoir à chaque instant ce que vaut chaque variable et combien de fois tourne chaque boucle — l'exigence d'une démonstration. Le programme du CAPES externe de mathématiques (bac+3) en fait une rubrique : « Variables, expressions, instructions conditionnelles, boucles, tableaux unidimensionnels. Expression dans un langage de programmation textuel. » On la suit ici en Python 3, le langage du lycée : variables et expressions (A), conditionnelles et boucles (B), tableaux et fonctions (E).

Note (périmètre de vérification). Chaque programme de cette leçon a été exécuté par le banc du chapitre (_verif_algorithmique.py) ; chaque sortie montrée est sa sortie réelle sous Python 3, comparée à l'octet près, messages d'erreur compris. La syntaxe s'en tient à Python 3.8. Avant de lire une sortie, essaie de la prédire.

A. Variables et expressions

Affectation. L'instruction x = 5 se lit « x reçoit 5 ». Python calcule d'abord la droite, avec les valeurs du moment, puis range le résultat sous le nom de gauche en écrasant l'ancienne valeur : x = x + 1 n'est pas une équation absurde, c'est un ordre. Pour prédire une sortie, on dresse la trace du programme : une ligne par instruction, une colonne par variable.

x = 3
y = x * x
x = x + 1
y = y - x
print(x, y)

4 5

La dernière ligne utilise le nouveau x.

= affecte, == compare. En mathématiques, $a=b$ est une affirmation symétrique ; en Python, a = b est un ordre, qui ne crée aucun lien durable entre les deux noms. Pour tester une égalité, on écrit ==, qui renvoie True ou False.

a = 3
b = a
print(a == b)
a = 4
print(a == b, b)

True
False 3

Échanger deux variables. Le piège : deux affectations croisées.

a = 2
b = 5
a = b
b = a
print(a, b)

5 5

Dès a = b, la valeur 2 est perdue. Deux remèdes : une variable temporaire t, ou l'affectation simultanée a, b = b, a, qui calcule tout le côté droit avant de ranger (ici elle ré-échange : retour à 2 5).

a = 2
b = 5
t = a
a = b
b = t
print(a, b)
a, b = b, a
print(a, b)

5 2
2 5

Types. Chaque valeur a un type : int (entier), float (nombre à virgule, écrit avec un point), bool (True ou False), str (chaîne, entre apostrophes ou guillemets : '7' et "7" sont la même chaîne). + additionne deux nombres mais colle deux chaînes ; int et str convertissent. Les entiers sont exacts et sans limite de taille (seule la mémoire les borne ; par défaut, les versions récentes de Python refusent d'afficher un entier de plus de 4 300 chiffres), les flottants gardent environ seize chiffres (e+30 se lit $\times10^{30}$).

print(type(7), type(7.0))
print(type(7 > 2), type('7'))
print('12' + '1', int('12') + 1)
print(2 ** 100)
print(2.0 ** 100)

<class 'int'> <class 'float'>
<class 'bool'> <class 'str'>
121 13
1267650600228229401496703205376
1.2676506002282294e+30

Diviser : /, // et %. / rend toujours un flottant ; // et % donnent le quotient et le reste euclidiens, liés par a == b * (a // b) + a % b. Pour b positif, Python arrondit le quotient vers le bas : le reste est entre 0 et b - 1, même pour un dividende négatif ($-7=2\times(-4)+1$).

print(7 / 2, 6 / 2)
print(7 // 2, 7 % 2)
print(-7 // 2, -7 % 2)
a = -7
b = 2
print(a == b * (a // b) + a % b)

3.5 3.0
3 1
-4 1
True

⚠️ int(-7 / 2) vaut −3 : int tronque vers 0. Usages constants : n % 2 == 0 teste la parité (pour tout entier, même négatif) ; pour n naturel, n % 10 donne le chiffre des unités et n // 10 l'efface.

Les flottants ne sont pas des réels. Un flottant est rangé en binaire, sur 53 chiffres binaires significatifs. Or $0{,}1=\frac1{10}$ n'a pas d'écriture binaire finie (il faudrait que le dénominateur de la fraction irréductible soit une puissance de 2, et $10=2\times5$) : 0,1 est stocké arrondi, comme 0,2 et 0,3, et ici leurs erreurs ne se compensent pas (elles le font parfois : exercice A4).

print(0.1 + 0.2)
print(0.1 + 0.2 == 0.3)
print(0.1 + 0.2 - 0.3)
print(0.5 + 0.25 == 0.75)
x = 0.1 + 0.2
print(abs(x - 0.3) < 1e-9)

0.30000000000000004
False
5.551115123125783e-17
True
True

$0{,}5=\frac12$ et $0{,}25=\frac14$ s'écrivent exactement en binaire : ce calcul-là est juste. Règle : jamais de == entre flottants calculés, mais une tolérance, ici $10^{-9}$, écrite 1e-9.

Priorités. Comme en mathématiques : parenthèses, puissance **, puis *, /, //, %, enfin + et - ; à priorité égale, de gauche à droite — sauf la puissance.

print(2 + 3 * 4)
print(-2 ** 2, (-2) ** 2)
print(2 ** 3 ** 2)
print(7 - 3 - 2)
a = 4
b = 10
print((a + b) / 2, a + b / 2)

14
-4 4
512
2
7.0 9.0

-2 ** 2 vaut −4, comme $-2^2$ au tableau ; 2 ** 3 ** 2 se groupe par la droite, $2^{(3^2)}=512$ ; une moyenne exige ses parenthèses.

Booléens. Les comparaisons <, <=, >, >=, ==, != (« différent de ») renvoient un booléen, que l'on combine avec les connecteurs not, and, or (chapitre de raisonnement), prioritaires dans cet ordre en Python. Elles s'enchaînent : 0 < x < 1 signifie 0 < x and x < 1.

x = 0.3
print(0 < x < 1, not x > 0.5)
print(True or True and False)

True True
True

La dernière ligne se lit True or (True and False). L'évaluation est paresseuse : A and B s'arrête dès que A est faux, A or B dès que A est vrai, sans évaluer B. D'où la garde placée devant un calcul dangereux :

x = 0
print(x != 0 and 1 / x > 2)

False

Dans l'ordre inverse, le calcul part en premier :

x = 0
print(1 / x > 2 and x != 0)

ZeroDivisionError: division by zero

À retenir.

• = affecte, == compare ; une affectation copie une valeur, sans créer de lien.
• On échange avec une variable temporaire, ou a, b = b, a.
• // et % : quotient et reste euclidiens ; entre flottants, une tolérance, jamais ==.
• -2 ** 2 vaut −4 ; la garde d'un and se place en premier.

B. Conditionnelles et boucles

Instruction conditionnelle. if condition: exécute le bloc qui suit si la condition est vraie ; elif (« sinon si ») ajoute un test, else traite les cas restants. C'est l'indentation (quatre espaces) qui délimite un bloc. Seule la première branche dont la condition est vraie s'exécute.

note = 15.5
if note >= 16:
    m = 'très bien'
elif note >= 14:
    m = 'bien'
elif note >= 12:
    m = 'assez bien'
else:
    m = 'sans mention'
print(m)

bien

15,5 vérifie aussi note >= 12, mais la branche « bien » est prise avant : l'ordre des tests fait partie de l'algorithme. On l'éprouve sur chaque branche et sur les frontières 16, 14, 12.

Boucle for. for i in range(n): répète le bloc pour i valant 0, 1, …, n − 1 : n tours, et n n'est pas atteint. range(a, b) va de a à b − 1, range(a, b, p) avance de p en p. Les valeurs, mises en liste (partie E) :

print(list(range(5)))
print(list(range(2, 7)))
print(list(range(1, 10, 3)))

[0, 1, 2, 3, 4]
[2, 3, 4, 5, 6]
[1, 4, 7]

Accumulateur. Pour calculer $1+2+\dots+n$, on initialise une variable à 0 avant la boucle, et chaque tour y ajoute un terme ; pour aller jusqu'à n inclus, il faut range(1, n + 1). On recoupe avec $\frac{n(n+1)}2$ :

n = 100
s = 0
for k in range(1, n + 1):
    s = s + k
print(s, n * (n + 1) // 2)

5050 5050

Avec range(1, n), le dernier terme manque, sans que rien le signale :

n = 100
s = 0
for k in range(1, n):
    s = s + k
print(s)

4950

L'écart vaut 100 : le terme oublié. Pour un produit, l'accumulateur part de 1. Voici $5!$ et sa trace, une ligne « avant » puis une ligne par tour :

n = 5
p = 1
for k in range(2, n + 1):
    p = p * k
print(p)

120

range(2, 6) fait 4 tours ; avec n = 10, le même programme affiche 3628800, soit $10!$.

Compteur. Un compteur ajoute 1 chaque fois qu'une condition est vérifiée. Combien d'entiers de 1 à 100 sont multiples de 3 ou de 5 ?

c = 0
for n in range(1, 101):
    if n % 3 == 0 or n % 5 == 0:
        c = c + 1
print(c)

47

Recoupement par le crible (chapitre de raisonnement) : 33 multiples de 3, 20 de 5, 6 de 15, et $33+20-6=47$.

Boucle while et seuil. while condition: répète son bloc tant que la condition est vraie : on l'emploie quand on ignore le nombre de tours. Un capital de 1 000 € placé à 5 % par an vérifie $u_{n+1}=1{,}05\,u_n$, $u_0=1000$ ; en combien d'années double-t-il ?

u = 1000
n = 0
while u < 2000:
    u = u * 1.05
    n = n + 1
print(n, round(u, 2))

15 2078.93

u et n avancent ensemble : u vaut toujours $u_n$. À la sortie, la condition est fausse : $u_n\geq2000$, pour la première fois. Recoupement : $1{,}05^n\geq2$ équivaut à $n\geq\frac{\ln2}{\ln1{,}05}\approx14{,}2$ (chapitre sur les suites). ⚠️ Parti de n = 1, le programme afficherait 16 : le décalage d'une unité guette.

Un while doit faire évoluer sa condition vers la sortie. Celui-ci ne termine jamais : n prend les valeurs impaires et passe par-dessus 10.

n = 1
while n != 10:
    n = n + 2

Avec while n < 10:, il s'arrête sur n égal à 11. Une condition en != n'est sûre que si l'on est certain de tomber pile sur la valeur.

L'algorithme d'Euclide. C'est le while le plus célèbre. Si r est le reste de la division de a par b non nul, alors $\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r)$ (chapitre d'arithmétique). On remplace donc (a, b) par (b, a % b) jusqu'à un reste nul ; le pgcd est la dernière valeur non nulle, restée dans a.

a = 21
b = 15
while b != 0:
    a, b = b, a % b
print(a)

3

Dans la suite 21, 15, 6, 3, 0, chaque terme à partir du troisième est le reste de la division des deux précédents. Ici b != 0 est sûr : b est un entier naturel qui diminue strictement (a % b est plus petit que b), et une suite strictement décroissante d'entiers naturels est finie — un variant, repris dans l'approfondissement.

La figure en donne le sens géométrique. Dans le rectangle $21\times15$, on découpe le plus grand carré possible, de côté 15, qui tient une fois ; dans le rectangle $15\times6$ restant, deux carrés de côté 6 ; le rectangle $6\times3$ restant est rempli exactement par deux carrés de côté 3. Chaque tour découpe : a // b compte les carrés, a % b est le petit côté du reste.

a = 21
b = 15
while b != 0:
    print(a // b, 'carré(s) de', b)
    a, b = b, a % b

1 carré(s) de 15
2 carré(s) de 6
2 carré(s) de 3

Les aires se recoupent : $15^2+2\times6^2+2\times3^2=315=21\times15$. Et le plus petit carré, de côté 3, pave à lui seul le rectangle ($7\times5=35$ carrés), car 3 divise 6, donc divise $15=2\times6+3$, donc divise $21=15+6$ : des carrés de côté entier c pavent le rectangle quand c divise 21 et 15, et le pgcd est le plus grand de ces côtés.

Boucles imbriquées. Le corps de la boucle intérieure s'exécute, à chaque tour extérieur, autant de fois que tourne la boucle intérieure. Comptons les couples $(i,j)$ tels que $1\leq i<j\leq5$ :

c = 0
for i in range(1, 6):
    for j in range(i + 1, 6):
        c = c + 1
print(c)

10

Pour i valant 1, 2, 3, 4, 5, la boucle intérieure tourne 4, 3, 2, 1, 0 fois : $4+3+2+1=10=\binom52$.

À retenir.

• Dans une chaîne if, elif, else, seule la première branche vraie s'exécute : l'ordre des tests compte.
• range(a, b) s'arrête à b − 1 ; jusqu'à n inclus, range(1, n + 1).
• Un accumulateur s'initialise avant la boucle : 0 pour une somme, 1 pour un produit.
• À la sortie d'un while, sa condition est fausse ; chaque tour doit rapprocher la boucle de cette sortie.

E. Tableaux et fonctions

Listes. Le « tableau unidimensionnel » du programme est, en Python, une liste : des valeurs entre crochets, repérées par un indice qui commence à 0. Les indices vont de 0 à len(t) - 1, et le dernier élément s'écrit aussi t[-1]. t[i] = … modifie un élément, t.append(v) ajoute v à la fin : on construit ainsi une liste à partir de [].

t = [7, 3, 9, 4]
print(len(t))
print(t[0], t[3], t[-1])
t[1] = 10
t.append(5)
print(t, len(t))

4
7 4 4
[7, 10, 9, 4, 5] 5

L'indice len(t) n'existe pas : le demander arrête le programme, après ce qu'il a déjà affiché.

t = [7, 3, 9, 4]
print(t[1])
print(t[4])

3
IndexError: list index out of range

Parcourir une liste. Par valeur, for x in t:, ou par indice, for i in range(len(t)):. Seul le second donne la position où écrire : x n'est qu'un nom posé sur une valeur, et lui en affecter une autre ne change rien à t.

t = [1, 2, 3]
for x in t:
    x = 10 * x
print(t)
for i in range(len(t)):
    t[i] = 10 * t[i]
print(t)

[1, 2, 3]
[10, 20, 30]

Maximum et sa position. On garde le plus grand élément vu, m, et son indice, p, en initialisant avec t[0] — jamais avec 0, qui serait un « maximum » absent d'une liste de négatifs.

t = [-5, -2, -9, -2]
m = t[0]
p = 0
for i in range(1, len(t)):
    if t[i] > m:
        m = t[i]
        p = i
print(m, p)

-2 1

Avec > strict, on garde la première position du maximum ; avec >=, ce serait la dernière, 3.

Sommer et compter. Les accumulateurs de la partie B marchent sur une liste : moyenne d'une série de notes (chapitre de statistique descriptive) et nombre de notes au moins égales à 10.

notes = [12, 8, 15, 9, 12]
s = 0
c = 0
for x in notes:
    s = s + x
    if x >= 10:
        c = c + 1
print(s / len(notes), c)

11.2 3

Fonctions. def nom(paramètres): définit une fonction au corps indenté. return v renvoie v à qui l'appelle et termine la fonction ; print ne fait qu'afficher. Une fonction sans return renvoie None.

def carre(x):
    return x * x

def carre_aff(x):
    print(x * x)

y = carre(3) + 1
print(y)
z = carre_aff(3)
print(z)

10
9
None

carre_aff(3) affiche 9, et z reçoit None : carre_aff(3) + 1 serait une erreur. Une fonction qui calcule renvoie son résultat ; l'affichage se fait à part. Enfin, une variable affectée dans une fonction est locale : elle ne touche pas une variable du même nom définie au dehors.

def f(x):
    n = 2 * x
    return n + 1

n = 10
print(f(3), n)

7 10

Recherche séquentielle. On parcourt les indices et l'on sort dès qu'on a trouvé : un return dans la boucle arrête toute la fonction, et le return -1 final n'est atteint que si rien ne convenait.

def indice(t, v):
    for i in range(len(t)):
        if t[i] == v:
            return i
    return -1

t = [4, 8, 15, 16, 23, 42]
print(indice(t, 16), indice(t, 5))

3 -1

⚠️ Un else renvoyant −1 dans la boucle abandonnerait dès le premier élément différent de v.

Aliasing : b = a ne copie pas une liste. Après b = a, les deux noms désignent la même liste : la modifier par l'un, c'est la modifier pour l'autre. Pour une copie, on écrit list(a) : une nouvelle liste, qu'on modifie sans toucher à a (tant qu'elle contient des nombres : une liste de listes garderait ses sous-listes partagées). (Un entier, lui, ne se modifie pas sur place : une fonction peut modifier une liste reçue en paramètre, jamais un entier.)

a = [1, 2, 3]
b = a
b[0] = 99
print(a)
c = list(a)
c[1] = 0
print(a, c)

[99, 2, 3]
[99, 2, 3] [99, 0, 3]

À retenir.

• Indices de 0 à len(t) - 1 ; t[len(t)] lève IndexError.
• Parcourir par indice pour modifier, par valeur pour lire ; un maximum part de t[0].
• return renvoie et termine, print affiche ; sans return, une fonction renvoie None. Ses variables sont locales.
• b = a donne un second nom à la même liste ; list(a) la copie.

L'approfondissement prouve qu'un programme calcule ce qu'on attend (invariant) et s'arrête (variant), compte ce qu'il coûte, puis programme Euclide étendu, Horner, la dichotomie, les tris, le crible, les rectangles et les trapèzes.