Algorithmique et programmation

Un algorithme est une suite d'instructions pour résoudre un problème. En seconde, on les écrit en Python. Tous les programmes de cette page s'exécutent directement dans ton navigateur, et le mode « pas à pas » montre l'évolution des variables.

Manipuler variables et types
Écrire une instruction conditionnelle
Programmer des boucles for et while
Définir et appeler des fonctions

Le premier lancement charge Python dans la page (environ 10 Mo, connexion internet nécessaire) ; ensuite tout est instantané. Raccourci : Ctrl + Entrée pour exécuter.

Cours

1. Variables et affectation

Une variable est un nom associé à une valeur stockée en mémoire. L'affectation x = 5 range la valeur 5 dans la variable x. Attention : en Python, = n'est pas une égalité mathématique ; x = x + 1 signifie « la nouvelle valeur de x est l'ancienne plus 1 ».

Type	Nom Python	Exemples
entier	`int`	`7`, `-12`
flottant (nombre à virgule)	`float`	`3.14`, `2.0`, `1e-3`
booléen	`bool`	`True`, `False`
chaîne de caractères	`str`	`"bonjour"`, `'A'`

+ - * / ; puissance ** ; quotient entier // ; reste % ; comparaisons == != < <= > >= ; logique and or not.

Exemples : 17 // 5 vaut 3, 17 % 5 vaut 2, 2 ** 10 vaut 1024, 0.1 + 0.2 vaut 0.30000000000000004 (les flottants sont des valeurs approchées !).

a = 7
b = 3
a = a + b
b = a - b
a = a - b
print("a =", a, "et b =", b)
print(17 // 5, 17 % 5, 2 ** 10)
print(type(3), type(3.0), type(3 > 2), type("3"))

Question : que font les trois lignes a = a + b, b = a - b, a = a - b ? Vérifie avec le mode pas à pas.

2. Instruction conditionnelle

if condition:
    instructions si la condition est vraie
elif autre_condition:
    instructions sinon, si l'autre condition est vraie
else:
    instructions dans tous les autres cas

Les deux-points : et l'indentation (4 espaces) délimitent les blocs : ils sont obligatoires.

x = -7
if x >= 0:
    absx = x
else:
    absx = -x
print("|x| =", absx)

note = 14.5
if note >= 16:
    mention = "Très bien"
elif note >= 14:
    mention = "Bien"
elif note >= 12:
    mention = "Assez bien"
else:
    mention = "Pas de mention"
print(mention)

3. Boucle bornée : for

On l'utilise quand on connaît à l'avance le nombre de répétitions.

for i in range(n): : $i$ prend les valeurs $0, 1, \dots, n - 1$ ($n$ valeurs).
for i in range(a, b): : de $a$ à $b - 1$.
for i in range(a, b, p): : de $a$ à $b - 1$ avec un pas de $p$.

# somme 1 + 2 + ... + 100
s = 0
for k in range(1, 101):
    s = s + k
print("Somme :", s)

# table de valeurs de f(x) = x² - 3x pour x de -2 à 5
for x in range(-2, 6):
    print(x, x**2 - 3*x)

4. Boucle non bornée : while

On l'utilise quand on ne connaît pas le nombre de répétitions : la boucle continue tant que la condition est vraie. Typiquement pour un algorithme de seuil.

Si la condition reste toujours vraie, la boucle ne s'arrête jamais (boucle infinie). Il faut que les instructions de la boucle finissent par rendre la condition fausse.

# Une population de 1000 bactéries augmente de 15 % par heure.
# Au bout de combien d'heures dépasse-t-elle 10 000 ?
p = 1000
h = 0
while p <= 10000:
    p = p * 1.15
    h = h + 1
print(h, "heures ; population :", round(p))

5. Fonctions

def nom_de_la_fonction(argument1, argument2):
    instructions
    return résultat

Une fonction peut avoir un ou plusieurs arguments. return renvoie le résultat (et termine la fonction). On l'appelle ensuite : nom_de_la_fonction(3, 5).

Ne pas confondre print (affiche à l'écran) et return (renvoie une valeur réutilisable dans un calcul). Une fonction mathématique $f(x) = 3x^2 - 1$ se traduit naturellement en fonction Python.

def f(x):
    return 3 * x**2 - 1

def distance(xA, yA, xB, yB):
    return ((xB - xA)**2 + (yB - yA)**2) ** 0.5

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

print(f(2), f(-1))
print(distance(1, 2, 4, 6))
print(est_multiple(91, 7), est_multiple(91, 5))

6. Listes (pour aller plus loin)

Une liste regroupe plusieurs valeurs : notes = [12, 15, 9]. notes[0] est le premier élément, len(notes) la longueur, notes.append(18) ajoute un élément. On parcourt une liste avec for x in notes:. Très utile en statistiques !

notes = [12, 15, 9, 18, 11, 14, 7, 16]

def moyenne(L):
    s = 0
    for x in L:
        s = s + x
    return s / len(L)

def au_dessus(L, seuil):
    R = []
    for x in L:
        if x >= seuil:
            R.append(x)
    return R

print("Moyenne :", moyenne(notes))
print("Notes >= 12 :", au_dessus(notes, 12))

Méthodes à connaître

Nombre de répétitions connu : for i in range(n):.
Répétition jusqu'à une condition : while condition: (la condition est celle pour continuer).
Initialise les variables avant la boucle, mets à jour dans la boucle, affiche ou renvoie après.

Exemple. Somme des carrés de 1 à 10 : s = 0 puis for k in range(1, 11): s = s + k**2.

Fais un tableau avec une colonne par variable.
Exécute les instructions une par une, en notant chaque nouvelle valeur sur une nouvelle ligne.
Pour une boucle while, teste la condition avant chaque passage.

def nom(paramètres): puis le corps indenté de 4 espaces.
Utilise return pour renvoyer le résultat (différent de print, qui affiche).
Teste la fonction sur des valeurs dont tu connais le résultat.

Exemple. def aire_disque(r): return 3.14159 * r**2.

Mini-jeux

Exercices

Utilise le bac à sable ci-dessous pour écrire et tester tes programmes.

# Écris ton programme ici

Qu'affiche ce programme ?

x = 4
y = x * 3
x = y - x
print(x, y)

8 12 : $y = 12$, puis $x = 12 - 4 = 8$.

Écrire une fonction parite(n) qui renvoie "pair" ou "impair".

def parite(n):
    if n % 2 == 0:
        return "pair"
    else:
        return "impair"

Écrire une fonction image(m, p, x) qui renvoie l'image de $x$ par la fonction affine $x \mapsto mx + p$, puis une fonction pente(xA, yA, xB, yB) qui renvoie le coefficient directeur de la droite $(AB)$ (on suppose $x_A \neq x_B$).

def image(m, p, x):
    return m * x + p

def pente(xA, yA, xB, yB):
    return (yB - yA) / (xB - xA)

Écrire une fonction colineaires(x1, y1, x2, y2) qui renvoie True si les vecteurs $(x_1\,;\,y_1)$ et $(x_2\,;\,y_2)$ sont colinéaires. L'utiliser pour écrire alignes(xA, yA, xB, yB, xC, yC).

def colineaires(x1, y1, x2, y2):
    return x1 * y2 - x2 * y1 == 0

def alignes(xA, yA, xB, yB, xC, yC):
    return colineaires(xB - xA, yB - yA, xC - xA, yC - yA)

Avec des flottants, on préfère tester abs(x1*y2 - x2*y1) < 1e-9 à cause des arrondis.

Écrire une fonction nb_diviseurs(n). Quel est le plus petit entier ayant exactement 10 diviseurs ? (Écrire une boucle while.)

def nb_diviseurs(n):
    c = 0
    for d in range(1, n + 1):
        if n % d == 0:
            c = c + 1
    return c

n = 1
while nb_diviseurs(n) != 10:
    n = n + 1
print(n)   # 48

On place 2 000 € à 2,5 % d'intérêts par an. Écrire un programme qui détermine le nombre d'années nécessaires pour que le capital dépasse 3 000 €.

c = 2000
n = 0
while c <= 3000:
    c = c * 1.025
    n = n + 1
print(n)   # 17

Écrire une fonction maximum(a, b, pas) qui cherche par balayage une valeur approchée du maximum de $f(x) = -x^2 + 4x + 1$ sur $[a\,;\,b]$, en renvoyant le couple $(x, f(x))$ correspondant. Tester avec maximum(0, 5, 0.01).

def f(x):
    return -x**2 + 4*x + 1

def maximum(a, b, pas):
    xm = a
    x = a
    while x <= b:
        if f(x) > f(xm):
            xm = x
        x = x + pas
    return xm, f(xm)

On obtient $x \approx 2$ et $f(x) \approx 5$ (en effet $f(x) = 5 - (x - 2)^2$).

Écrire une fonction simulation(n) qui lance $n$ fois deux dés et renvoie la fréquence de l'événement « obtenir un double ». Comparer avec la probabilité théorique. (Utiliser from random import randint.)

from random import randint

def simulation(n):
    c = 0
    for i in range(n):
        if randint(1, 6) == randint(1, 6):
            c = c + 1
    return c / n

La probabilité est $\frac{6}{36} = \frac16 \approx 0{,}167$ ; pour $n = 10\,000$, la fréquence en est proche (loi des grands nombres).