Algorithmique et Python · Première spécialité

Avant de commencer5 questions pour vérifier tes bases

1. Quelles valeurs parcourt range(3) en Python ?

1, 2, 30, 1, 20, 1, 2, 3

2. Après « x = 3 », puis « x = x + 2 », quelle valeur contient x ?

Une égalité impossible35

3. La condition Python « x < 5 » est-elle vraie pour x = 5 ?

Cela dépend de la valeur précédente de xOuiNon

4. Si u₀ = 2 et uₙ₊₁ = 3uₙ, combien vaut u₂ ?

61218

5. Si f(x) = x² − 1, quelle est l’image de 3 ?

852

Pourquoi programmer en maths ?

La machine fait le calcul, toi tu fais le raisonnement

Beaucoup de problèmes mathématiques demandent de répéter un calcul des centaines de fois, ou de tester une condition sur une longue liste de nombres. À la main, c'est interminable et source d'erreurs. La programmation confie cette exécution mécanique à la machine : tu décris une fois pour toutes la méthode (l'algorithme), et l'ordinateur exécute les instructions écrites ; une méthode incorrecte ou des arrondis peuvent produire un résultat inadapté. Ton travail reste le plus important : penser la méthode.

Algorithme ou programme ?

Un algorithme est une suite finie d'instructions non ambiguës qui résout un problème. On peut l'écrire en langage naturel (en français, avec le symbole $\aff$ pour « prend la valeur ») ou dans un langage de programmation comme Python. Le programme, c'est la traduction de l'algorithme dans un langage que la machine comprend.

L'idée directrice

L'idée avant le code

Une variable, c'est une boîte avec une étiquette

Choisir, répéter : les deux gestes de base

Découper pour ne pas se noyer : les fonctions

Le cours complet

Variables, types et affectation

Propriété · Les principaux types

Type	Description	Exemple Python
`int`	nombre entier	$\texttt{n = 7}$
`float`	approximation binaire d'un réel	$\texttt{x = 3.14}$
`str`	chaîne de caractères	$\texttt{nom = "Ada"}$
`bool`	booléen (vrai/faux)	$\texttt{test = True}$
`list`	liste de valeurs	$\texttt{L = [2, 4, 6]}$

Exemple · Échanger deux variables

Pour échanger les contenus de a et b, on passe par une variable temporaire (sinon on écrase une valeur) :

a = 3
b = 8
temp = a      # on met de cote l'ancien a
a = b         # a recoit b
b = temp       # b recoit l'ancien a
print(a, b)   # affiche 8 3

À toi d’essayer

Pourquoi l'ordre des lignes compte

Prédis les valeurs finales après a = 3, puis b = 8, puis a = b, puis b = a. Ce code échange-t-il les deux valeurs ? Répare-le sans utiliser l'affectation simultanée de Python.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Après a = b, l'ancienne valeur $$3$$ n'est plus dans a.

Indice 2 · Un pas de plus

Conserve cette ancienne valeur dans une troisième variable avant de remplacer a.

Voir l’explication

La trace donne successivement $$(a,b)=(3,8)$$ , puis $$(8,8)$$ , puis $$(8,8)$$ : l'échange n'a pas eu lieu. La réparation est temp = a, puis a = b, puis b = temp, ce qui donne $$(8,3)$$ . À chaque affectation, on évalue d'abord la droite avec les valeurs courantes, puis on remplace la valeur de gauche. Réessaie : trace x = 2, y = x + 3, x = y * 2 ; la valeur de y change-t-elle lors de la dernière ligne ?

Exemple · Lire les opérations avant de les utiliser

Code	Résultat	Question résolue
`7 / 2`	`3.5`	division
`7 // 2`	`3`	quotient entier
`7 % 2`	`1`	reste
`2 ** 3`	`8`	puissance
$\texttt{7 == 2}$	`False`	comparaison

Avec un diviseur positif, // arrondit vers le bas, même pour un résultat négatif : -7 // 2 vaut $$-4$$ et -7 % 2 vaut $$1$$ , puisque $-7=2\times(-4)+1$ . Une division par zéro n'est pas définie. Le point de 3.5 est la notation décimale de Python ; la virgule sert à séparer des objets.

Instructions conditionnelles : choisir

Définition · Conditionnelle if / elif / else

Une instruction conditionnelle exécute un bloc si une condition est vraie, un autre sinon. En Python, l'indentation (le décalage) délimite les blocs.

if note >= 10:
    print("Admis")
elif note >= 8:
    print("Rattrapage")
else:
    print("Refuse")

À toi d’essayer

Un test vrai peut empêcher de lire le suivant

Pour les valeurs $$7$$ , $$8$$ , $$9$$ et $$10$$ , prédis la sortie du programme précédent. Que se passe-t-il si on place le test note >= 8 avant celui de note >= 10, dans la même chaîne if / elif ?

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Teste les bornes exactes : $8\geqslant8$ et $10\geqslant10$ sont vrais.

Indice 2 · Un pas de plus

Dans une chaîne if / elif, un premier test vrai suffit à choisir la branche.

Voir l’explication

Dans l'ordre initial, on obtient Refusé, Rattrapage, Rattrapage, Admis. En inversant l'ordre des deux tests avec leurs actions, une note de $$10$$ satisfait déjà note >= 8 et reçoit Rattrapage ; le second test n'est plus évalué. Deux if séparés pourraient, eux, exécuter deux blocs. Réessaie : trace les deux variantes pour $$12$$ , puis explique pourquoi l'ordre initial traite d'abord le groupe le plus restrictif.

Boucles bornées : répéter un nombre connu de fois

Définition · Boucle for

La boucle for répète un bloc pour chaque valeur d'une plage. range(a, b) parcourt les entiers de a à b-1 (la borne de droite est exclue).

somme = 0
for k in range(1, 101):   # k va de 1 a 100
    somme = somme + k
print(somme)              # 5050

À toi d’essayer

Voir une somme se construire

On initialise s = 0, puis, pour k in range(1, 5), on exécute s = s + k*k. Prédis la valeur finale et construis une ligne de trace par tour. Que se passe-t-il avec range(1, 1) ?

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Les valeurs de k sont $$1,2,3,4$$ ; $$5$$ est exclu.

Indice 2 · Un pas de plus

La nouvelle somme est l'ancienne somme plus le carré courant, pas seulement le carré courant.

Voir l’explication

La trace est :

$$k$$	ancien $$s$$	$$k^2$$	nouveau $$s$$
1	0	1	1
2	1	4	5
3	5	9	14
4	14	16	30

La valeur finale est $$30$$ . Avec range(1, 1), aucun tour n'a lieu et s reste $$0$$ . Initialiser l'accumulateur avant la boucle permet de garder les apports précédents. Réessaie : calcule la somme des cubes de $$1$$ à $$3$$ en adaptant exactement deux endroits.

Boucles non bornées : répéter jusqu'à une condition

Définition · Boucle while

La boucle while répète un bloc tant que sa condition reste vraie. On l'utilise quand on ne sait pas d'avance combien de répétitions seront nécessaires (recherche de seuil, par exemple).

capital = 1000
annees = 0
while capital < 2000:     # tant qu'on n'a pas double
    capital = capital * 1.05   # +5% par an
    annees = annees + 1
print(annees)             # nombre d'annees pour doubler

À toi d’essayer

Lire le test avant chaque tour

On initialise u = 1, n = 0. Tant que u <= 8, on double u, puis on augmente n de $$1$$ . Quelle valeur finale de n obtient-on ? Pourquoi le résultat change-t-il avec u < 8 ?

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Le test est fait avant le tour, y compris lorsque u vaut exactement $$8$$ .

Indice 2 · Un pas de plus

Trace les couples $$(n,u)$$ depuis $$(0,1)$$ jusqu'au premier test faux.

Voir l’explication

Les couples sont $$(0,1),(1,2),(2,4),(3,8),(4,16)$$ . Avec <=, le programme s'arrête à $$n=4$$ , premier rang où $$u>8$$ . Avec <, il s'arrête à $$n=3$$ , premier rang où $u\geqslant8$ . Le choix du test vient du seuil strict ou large demandé. Réessaie : remplace le seuil par $$0$$ ; combien de tours sont effectués ?

Fonctions et programmation modulaire

Définition · Fonction

Une fonction regroupe un bloc d'instructions sous un nom. Elle reçoit des paramètres (entrées) et renvoie un résultat avec return.

def aire_disque(rayon):
    return 3.14159 * rayon**2

a = aire_disque(2)    # appel : rayon vaut 2
print(a)              # 12.56636

Exemple · Un appel, une valeur renvoyée

def carre(x):
    resultat = x*x
    return resultat

y = carre(3) + carre(4)

Le premier appel calcule $$9$$ , le second $$16$$ . Le programme additionne ces valeurs puis affecte $$25$$ à y. Les noms x et resultat sont locaux à chaque appel ; ils ne sont pas automatiquement disponibles après la fonction. La définition seule ne lance aucun calcul : il faut un appel.

À toi d’essayer

Un affichage peut cacher une absence de résultat

On remplace return resultat par print(resultat) dans la fonction précédente. Que voit-on, et l'affectation à y réussit-elle ? Comment conserver à la fois un résultat réutilisable et un affichage ?

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Afficher une valeur et la transmettre comme résultat d'un appel sont deux opérations différentes.

Indice 2 · Un pas de plus

Sans return explicite, l'appel renvoie None.

Voir l’explication

Le programme affiche $$9$$ puis $$16$$ , mais essaie ensuite d'additionner None et None : l'affectation à y échoue. Il faut conserver return resultat dans la fonction, puis écrire print(y) après l'affectation. Réessaie : écris une fonction qui renvoie $$2x+1$$ et utilise son résultat dans une multiplication.

Les listes : la grande nouveauté

Définition · Liste

Une liste range plusieurs valeurs dans un ordre précis, sous un seul nom. Chaque élément a un indice (sa position), qui commence à 0.

L = [5, 12, 8, 20]   # liste en extension
print(L[0])          # 5   (premier element, indice 0)
print(L[3])          # 20  (quatrieme element, indice 3)
print(len(L))        # 4   (nombre d'elements)

Propriété · Trois façons de créer une liste

# 1. En extension : on ecrit les elements
carres = [0, 1, 4, 9, 16]

# 2. Par ajouts successifs : on part du vide et on remplit
carres = []
for k in range(5):
    carres.append(k**2)     # ajoute k^2 a la fin

# 3. En comprehension : une formule + une plage (+ une condition)
carres = [k**2 for k in range(5)]
pairs  = [k for k in range(20) if k % 2 == 0]   # avec condition

À toi d’essayer

Indice, valeur et filtre

Avec L = [4, 1, 0, 1, 4], donne L[1], len(L), L[-1] et le résultat de [x for x in L if x > 0]. Le dernier résultat contient-il deux fois $$4$$ ?

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

L'indice $$1$$ désigne le deuxième élément, pas l'élément de valeur $$1$$ recherché.

Indice 2 · Un pas de plus

Le filtre examine chacune des cinq positions ; il retire seulement les valeurs qui ne satisfont pas le test.

Voir l’explication

On obtient $$1$$ , $$5$$ , $$4$$ , puis [4, 1, 1, 4]. Le zéro a été exclu ; les deux $$4$$ sont conservés. Pour une liste vide, aucun indice n'est valide, même -1. Réessaie : construis la liste des $$k^2$$ pour $$k$$ allant de $$-3$$ à $$3$$ inclus, puis garde uniquement les carrés strictement supérieurs à $$1$$ .

Méthode · Opérations courantes sur les listes

Opération	Code Python
Longueur	`len(L)`
Accéder à l'élément d'indice `i`	`L[i]`
Ajouter à la fin	`L.append(x)`
Supprimer l'élément d'indice `i`	`del L[i]`
Tester l'appartenance	`x in L`
Somme / maximum / minimum	`sum(L)`, `max(L)`, `min(L)`

Propriété · Deux façons de parcourir une liste

L = [5, 12, 8, 20]

# Parcourir par INDICES (utile si on a besoin de la position)
for i in range(len(L)):
    print(i, L[i])

# ITERER sur les ELEMENTS (plus simple si la position est inutile)
for valeur in L:
    print(valeur)

Exemple · Moyenne d'une liste de notes

def moyenne(notes):
    if len(notes) == 0:
        return None          # liste vide : pas de moyenne
    return sum(notes) / len(notes)

print(moyenne([12, 8, 15, 10]))   # 11.25

À toi d’essayer

Compter ou additionner : deux accumulateurs différents

Pour L = [-2, 5, 0, 5], calcule le nombre d'éléments strictement positifs et leur somme. Propose une boucle qui met à jour deux variables nombre et total. Que doivent-elles valoir pour une liste vide ?

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Le nombre augmente de $$1$$ ; la somme augmente de la valeur lue.

Indice 2 · Un pas de plus

Le zéro ne vérifie pas le test strict x > 0. Initialise les deux variables avant la boucle.

Voir l’explication

On obtient $$2$$ éléments et une somme de $$10$$ . Initialise nombre = 0 et total = 0, parcours les éléments, puis, si x > 0, ajoute $$1$$ à nombre et x à total. Pour une liste vide, aucun tour n'est exécuté et les deux résultats valent $$0$$ . Une moyenne des éléments positifs n'est définie que si leur nombre est non nul. Réessaie : applique ce raisonnement à [-3, 0, -1] avant toute division.

Un peu de logique et d'ensembles

Propriété · Négation des propositions quantifiées

Proposition	Sa négation
« Tous les $$x$$ vérifient $$P$$ »	« Il existe un $$x$$ qui ne vérifie pas $$P$$ »
« Il existe un $$x$$ tel que $$P$$ »	« Aucun $$x$$ ne vérifie $$P$$ »
« $$P$$ et $$Q$$ »	« (non $$P$$ ) ou (non $$Q$$ ) »
« $$P$$ ou $$Q$$ »	« (non $$P$$ ) et (non $$Q$$ ) »

À toi d’essayer

Nier une condition sans perdre les bornes

Pour un réel $$x$$ , nie « $$x>0$$ et $$x<2$$ ». Écris un test Python correspondant à cette négation. Puis nie « tous les éléments de la liste sont strictement positifs » et explique ce qui se passe pour une liste vide.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

La négation de « et » utilise « ou ». La négation de $$x>0$$ inclut $$0$$ .

Indice 2 · Un pas de plus

Une valeur strictement positive ne réfute pas « tous strictement positifs » ; il faut une valeur qui ne soit pas strictement positive.

Voir l’explication

La première négation est $x\leqslant0$ ou $x\geqslant2$ , soit x <= 0 or x >= 2. La seconde est « il existe au moins un élément inférieur ou égal à $$0$$ ». Une liste vide n'a aucun contre-exemple : « tous ses éléments sont strictement positifs » est vraie au sens logique, tandis que « elle contient un élément strictement positif » est fausse. Réessaie : nie « il existe un élément supérieur à $$10$$ » et écris un test qui cherche un contre-exemple à ta négation.

Couples et produit cartésien

Exemple · Construire un produit cartésien

Si $A=\{1,2\}$ et $B=\{a,b,c\}$ , alors

\begin{aligned}&A\times B\\[.35em]&= \{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)\}.\end{aligned}

Il contient $2\times3=6$ couples. En Python :

A = [1, 2]
B = ["a", "b", "c"]
produit = [(x, y) for x in A for y in B]

Les deux boucles correspondent aux deux choix successifs : un élément de $$A$$ , puis un élément de $$B$$ .

À toi d’essayer

Deux boucles, quel ordre de résultats ?

Avec A = [1, 2] et B = ["a", "b", "c"], prédis l'ordre des couples de [(x, y) for x in A for y in B]. Que donne la même expression si B est vide ?

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

La boucle sur $$x$$ est extérieure : pour une valeur fixée de $$x$$ , la boucle sur $$y$$ est parcourue entièrement.

Indice 2 · Un pas de plus

Chaque élément de $$A$$ est associé successivement aux trois éléments de $$B$$ .

Voir l’explication

L'ordre est $$(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)$$ . Il y a $2\times3=6$ couples. Si $$B$$ est vide, aucun couple n'est créé et le résultat est une liste vide. Les listes doivent être sans doublons si l'on veut que chaque couple du produit cartésien apparaisse exactement une fois. Réessaie : inverse l'ordre des boucles en conservant l'expression (x, y) et prédis le nouvel ordre.

Identité, équation et statut des lettres

Trois structures de raisonnement

Une preuve à construire

Une implication à prouver en changeant de sens

Pour un entier $$n$$ , prouve : si $$n^2$$ est pair, alors $$n$$ est pair. Formule d'abord sa contraposée, en la distinguant de sa réciproque.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

La contraposée de « $$P$$ implique $$Q$$ » est « non $$Q$$ implique non $$P$$ ».

Indice 2 · Un pas de plus

Écris un entier impair sous la forme $$2k+1$$ , puis calcule son carré.

Voir la preuve expliquée

La contraposée est : « si $$n$$ est impair, alors $$n^2$$ est impair ». Pour $$n=2k+1$$ ,

\begin{aligned}n^2&=(2k+1)^2\\[.35em]&=4k^2+4k+1\\[.35em]&=2(2k^2+2k)+1.\end{aligned}

Le nombre entre parenthèses est entier : le carré est impair. La contraposée, logiquement équivalente à l'implication initiale, est démontrée. La réciproque serait « si $$n$$ est pair, alors $$n^2$$ est pair » : elle est aussi vraie ici, mais n'est pas l'énoncé que nous venons d'utiliser.

Une preuve à construire

Faire apparaître une contradiction

Démontre qu'aucun entier n'est à la fois pair et impair. Écris explicitement ce que suppose un raisonnement par l'absurde.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Suppose qu'il existe un entier possédant les deux propriétés.

Indice 2 · Un pas de plus

Il s'écrirait à la fois $$2p$$ et $$2q+1$$ , avec $$p,q$$ entiers.

Voir la preuve expliquée

Supposons qu'un tel entier $$n$$ existe. Alors $$2p=2q+1$$ , donc $$p-q=1/2$$ . Or la différence de deux entiers est entière, tandis que $$1/2$$ ne l'est pas. Cette contradiction interdit l'existence supposée ; aucun entier n'a donc les deux propriétés. La contradiction doit venir des hypothèses et de propriétés connues, pas seulement d'un résultat inattendu.

Pour aller plus loin : prouver qu'un algorithme est correct

Exemple · Le programme à expliquer : une liste non vide de nombres

def maximum(L):
    if len(L) == 0:
        raise ValueError('liste vide : maximum non defini')
    m = L[0]
    for x in L[1:]:
        if x > m:
            m = x
    return m

L[1:] désigne la liste à partir de son deuxième élément. On suppose des nombres réels finis ; la liste vide est refusée explicitement.

Une preuve à construire

Pourquoi ce maximum est-il correct ?

Justifie l'arrêt et la correction du programme précédent. Quelle propriété de m conserve-t-on après chaque élément lu ?

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Au départ, seul le premier élément a été pris en compte.

Indice 2 · Un pas de plus

À la lecture de $$x$$ , traite les deux cas $$x>m$$ et $x\leqslant m$ .

Voir la preuve expliquée

Au départ, $$m=L[0]$$ est le maximum des éléments déjà pris en compte. Supposons cette propriété vraie avant de lire $$x$$ . Si $$x>m$$ , le nouveau maximum est $$x$$ ; sinon, il reste $$m$$ . La propriété est donc conservée. La boucle lit les $$n-1$$ éléments restants et s'arrête, car la liste est finie. À la sortie, tous ont été pris en compte : $$m$$ est bien le maximum de la liste. Pour une liste d'un seul élément, aucun tour n'a lieu et l'initialisation suffit.

À toi d’essayer

Un test qui révèle une initialisation inadaptée

Un programme de maximum commence par m = 0. Teste mentalement [-4, -2, -7]. Pourquoi une liste positive aurait-elle pu masquer le défaut ? Quelle initialisation répare le raisonnement ?

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Compare chacun des trois nombres avec $$0$$ .

Indice 2 · Un pas de plus

Le maximum doit être une valeur de la liste ; ici $$0$$ n'en fait pas partie.

Voir l’explication

Aucun élément n'est supérieur à $$0$$ , donc le programme erroné renvoie $$0$$ au lieu de $$-2$$ . Sur une liste positive, une valeur aurait remplacé $$0$$ , masquant le défaut. Initialiser à $$L[0]$$ donne une valeur réellement présente et un invariant vrai dès le début. Réessaie : trace le programme corrigé sur $$[-4]$$ , puis sur $$[-4,-2,-2]$$ , en indiquant les comparaisons.

Boîte à outils : réflexes pour le bac

Méthode · Mémo syntaxe Python

x = 5                  # affectation
if cond:               # condition (: puis indentation)
    ...
elif autre_cond:
    ...
else:
    ...
for k in range(a, b):  # boucle bornee (b exclu)
    ...
while cond:            # boucle non bornee
    ...
def f(parametres):     # fonction
    return resultat
L = [1, 2, 3]          # liste ; L[0] premier ; len(L) longueur
L.append(x)            # ajoute a la fin
[expr for k in range(n) if cond]   # liste en comprehension

Propriété · Quel outil pour quel besoin ?

Besoin	Outil
Choisir entre plusieurs cas	`if / elif / else`
Répéter un nombre connu de fois	`for ... in range(...)`
Répéter jusqu'à une condition	`while ...`
Réutiliser un calcul	`def ...: return ...`
Stocker plusieurs valeurs	une `list`
Construire une liste « en sélectionnant »	liste en compréhension avec `if`

Méthode · Trois algorithmes à reconstruire et expliquer

Pour moyenne et maximum, on exige une liste non vide de nombres. Pour le seuil, $$S$$ est un réel fini ; la suite $$2^n$$ dépasse tout seuil fixé. Les tests d'entrée peuvent être ajoutés comme dans l'exemple précédent.

# 1. Somme / moyenne d'une liste
def moyenne(L):
    return sum(L) / len(L)

# 2. Recherche du maximum (sans max())
def maximum(L):
    m = L[0]
    for x in L:
        if x > m:
            m = x
    return m

# 3. Recherche de seuil (premier n tel que u_n depasse S)
def seuil(S):
    u = 1
    n = 0
    while u <= S:
        u = u * 2      # exemple : u_n = 2^n
        n = n + 1
    return n

Exercices

Exercice 1 ★☆☆ : Lire une affectation

On exécute : a = 4 ; b = 7 ; a = a + b ; b = a - b. Quelles sont les valeurs finales de a et b ?

Exercice 2 ★☆☆ : Trace d'une boucle

Que vaut s après ce code ? Détailler les valeurs successives.

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

Exercice 3 ★☆☆ : Lire une liste

Soit L = [3, 9, 1, 7, 4]. Donner L[0], L[2], len(L), L[len(L)-1], et la valeur de sum(L).

Exercice 4 ★☆☆ : Pair ou impair

Écrire une fonction parite(n) qui renvoie la chaîne "pair" si n est pair, "impair" sinon. (Indice : n % 2 vaut $$0$$ si n est pair.)

Exercice 5 ★☆☆ : Compter

Écrire une fonction compte_pairs(L) qui renvoie le nombre d'éléments pairs d'une liste L.

Exercice 6 ★☆☆ : Liste en compréhension

Écrire, en une seule ligne (compréhension), la liste des cubes $$k^3$$ pour $$k$$ de $$1$$ à $$10$$ . Puis la liste des multiples de $$3$$ entre $$0$$ et $$30$$ inclus.

Exercice 7 ★★☆ : Somme conditionnelle

Écrire une fonction somme_positifs(L) qui renvoie la somme des éléments strictement positifs d'une liste L.

Exercice 8 ★★☆ : Table de multiplication

Écrire une fonction table(n) qui renvoie la liste [n, 2n, 3n, ..., 10n].

Exercice 9 ★★☆ : Maximum et sa position

Pour une liste non vide de nombres, écrire une fonction indice_max(L) qui renvoie l'indice du plus grand élément (le premier en cas d'égalité).

Exercice 10 ★★☆ : Suite et seuil

On définit $$u_0=2$$ et $u_{n+1}=1{,}5\,u_n$ . Écrire une fonction seuil(S) qui renvoie le plus petit $$n$$ tel que $$u_n>S$$ .

Exercice 11 ★★☆ : Recherche dans une liste

Écrire une fonction est_present(x, L) qui renvoie True si x apparaît dans L, False sinon, sans le test d'appartenance x in L. Une boucle de parcours for ... in L est autorisée.

Exercice 12 ★★★ : Logique et méthodes de preuve

1. Pour chaque implication, dire si elle est vraie, puis donner sa réciproque et dire si elle est vraie.

« $$n$$ multiple de $$4$$ $\Rightarrow$ $$n$$ pair » ;
« $x>3 \Rightarrow x>1$ » ;
«
$x^2=9\Rightarrow x=3$
».

2. Nier correctement : « tous les élèves ont réussi » ; « il existe un entier pair supérieur à $$100$$ » ; « $$x>0$$ et $$x<2$$ ».

3. Démontrer par disjonction des cas que $$n(n+1)$$ est pair pour tout entier $$n$$ .

4. Démontrer par contraposée : si $$n^2$$ est pair, alors $$n$$ est pair.

5. Démontrer par l'absurde qu'aucun entier ne peut être à la fois pair et impair.

Exercice 13 ★★★ : Tester et lister les nombres premiers

Écrire une fonction est_premier(n) qui renvoie True si n est premier ( $n\geqslant 2$ ), puis une fonction premiers_jusqua(N) qui renvoie la liste des nombres premiers inférieurs ou égaux à N.

Exercice 14 ★★★ : Simulation et espérance

On lance indépendamment deux dés équilibrés et on s'intéresse à la somme $$S$$ . Écrire une fonction moyenne_somme(n) qui simule n lancers de deux dés et renvoie la moyenne des sommes obtenues, pour un entier $$n>0$$ . Autour de quelle valeur les moyennes de grands échantillons se concentrent-elles dans ce modèle ? (Lien fiche 10.)

Exercice 15 ★★★ : Inverser une liste

Écrire une fonction renverse(L) qui renvoie une nouvelle liste contenant les éléments de L dans l'ordre inverse, sans utiliser L.reverse() ni L[::-1].

Exercice 16 ★★★ : Ensembles et produit cartésien via les listes

1. Écrire une fonction intersection(A, B) qui renvoie la liste des éléments présents à la fois dans A et dans B (sans doublon). Relier au symbole mathématique correspondant.

2. Écrire une fonction produit_cartesien(A, B) qui renvoie la liste de tous les couples $$(x,y)$$ avec $x\in A$ et $y\in B$ . Combien de couples obtient-on si $$A$$ contient $$p$$ éléments et $$B$$ en contient $$q$$ ?

Problème guidé d'approfondissement

Partie A : les briques de base\\[2pt] On dispose d'une liste de notes, par exemple notes = [12, 8, 15, 10, 6, 18, 9].

Écrire moyenne(L) qui renvoie la moyenne d'une liste non vide.
Écrire maximum(L) et minimum(L) sans utiliser max ni min.
Écrire nb_admis(L) qui renvoie le nombre de notes supérieures ou égales à $$10$$ .

Partie B : compréhensions et sélection\\[2pt]

En une ligne (compréhension), construire la liste des notes >= 10.
Écrire ajuste(L) qui renvoie une nouvelle liste où chaque note est augmentée de $$1$$ point, sans dépasser $$20$$ .

Partie C : assemblage modulaire\\[2pt]

Écrire bilan(L) qui réutilise les fonctions précédentes et renvoie un texte du type : « Moyenne : 11.1 ; Min : 6 ; Max : 18 ; Admis : 4/7 ».
Expliquer en deux phrases pourquoi découper en petites fonctions (plutôt qu'un seul long bloc) rend le programme plus sûr et plus réutilisable.

Corrigés détaillés

Corrigé 1

Corrigé 2

Corrigé 3

Corrigé 4

Démonstration

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

Le test n % 2 == 0 vérifie que le reste de la division par $$2$$ est nul. Noter le double égal == (test) et le : suivi de l'indentation.

Corrigé 5

Démonstration

On parcourt la liste et on compte :

def compte_pairs(L):
    c = 0
    for x in L:
        if x % 2 == 0:
            c = c + 1
    return c

On itère directement sur les éléments (for x in L) car la position ne sert pas. c compte les nombres pairs rencontrés.

Corrigé 6

Démonstration

cubes = [k**3 for k in range(1, 11)]        # 1 a 10 inclus
mult3 = [k for k in range(0, 31) if k % 3 == 0]

Pour aller jusqu'à $$10$$ inclus, on écrit range(1, 11). La condition if k%3==0 ne garde que les multiples de $$3$$ . Résultats : [1, 8, 27, ..., 1000] et [0, 3, 6, ..., 30].

Corrigé 7

Démonstration

def somme_positifs(L):
    s = 0
    for x in L:
        if x > 0:
            s = s + x
    return s

On n'ajoute x à la somme que s'il est strictement positif. Par exemple sur [3, -2, 5, -7] on obtient $$3+5=8$$ .

Corrigé 8

Démonstration

def table(n):
    return [n * k for k in range(1, 11)]

La compréhension construit [n*1, n*2, ..., n*10]. On pouvait aussi partir d'une liste vide et faire append dans une boucle : les deux méthodes sont équivalentes.

Corrigé 9

Démonstration

On retient à la fois la valeur du maximum et son indice :

def indice_max(L):
    imax = 0
    for i in range(len(L)):
        if L[i] > L[imax]:
            imax = i
    return imax

On compare chaque élément L[i] au meilleur trouvé L[imax]. L'inégalité stricte > garantit qu'en cas d'égalité on garde le premier indice. Ici on parcourt par indices car c'est la position qu'on veut renvoyer.

Corrigé 10

Démonstration

def seuil(S):
    u = 2          # u_0
    n = 0
    while u <= S:
        u = 1.5 * u    # u_{n+1} = 1.5 u_n
        n = n + 1
    return n

La suite est géométrique de raison $$1{,}5>1$$ , donc elle croît sans limite : le while finit toujours par s'arrêter. On compte dans n le nombre d'étapes jusqu'à dépasser S. Par exemple seuil(10) renvoie $$4$$ (car $u_0=2,\,u_1=3,\,u_2=4{,}5,\,u_3=6{,}75,\,u_4=10{,}125>10$ ).

Corrigé 11

Démonstration

def est_present(x, L):
    for valeur in L:
        if valeur == x:
            return True   # trouve : on sort tout de suite
    return False          # parcours fini sans trouver

Dès qu'on trouve x, le return True arrête la fonction (inutile de continuer). Si la boucle se termine sans rien trouver, on renvoie False.

Corrigé 12

Démonstration

1(a). « $$n$$ multiple de $4\Rightarrow n$ pair » : vraie (tout multiple de $$4$$ est multiple de $$2$$ ). Réciproque : « $$n$$ pair $\Rightarrow n$ multiple de $$4$$ » : fausse ( $$n=2$$ est pair mais pas multiple de $$4$$ ).

1(b). « $x>3\Rightarrow x>1$ » : vraie. Réciproque : « $x>1\Rightarrow x>3$ » : fausse ( $$x=2$$ ).

1(c). « $x^2=9\Rightarrow x=3$ » : fausse (contre-exemple $$x=-3$$ ). Réciproque : « $x=3\Rightarrow x^2=9$ » : vraie.

2. Les négations sont :

« il existe au moins un élève qui n'a pas réussi » ;
« aucun entier pair n'est supérieur à $$100$$ » ;
« $x\leqslant0$ ou $x\geqslant2$ ».

3. Soit $$n$$ un entier. S'il est pair, alors $$n(n+1)$$ contient le facteur pair $$n$$ . S'il est impair, alors $$n+1$$ est pair et le produit contient le facteur pair $$n+1$$ . Les deux cas couvrent tous les entiers ; donc $$n(n+1)$$ est toujours pair.

4. Prouvons la contraposée. Si $$n$$ est impair, il existe $k\in\Z$ tel que $$n=2k+1$$ . Alors

\begin{aligned}n^2 &= (2k+1)^2\\[.35em]&= 4k^2+4k+1\\[.35em]&= 2(2k^2+2k)+1,\end{aligned}

donc $$n^2$$ est impair. La contraposée est vraie ; ainsi $$n^2$$ pair implique $$n$$ pair.

5. Supposons qu'un entier $$n$$ soit pair et impair. Il existe alors $p,q\in\Z$ tels que $$n=2p$$ et $$n=2q+1$$ . Donc $$2p=2q+1$$ , soit $$2(p-q)=1$$ . Le membre de gauche est pair, celui de droite impair : contradiction. Un tel entier n'existe pas.

Leçon : une implication et sa réciproque ne se déduisent pas l'une de l'autre en général ; la contraposée est en revanche équivalente à l'implication initiale.

Corrigé 13

Démonstration

def est_premier(n):
    if n < 2:
        return False
    for d in range(2, n):       # diviseurs possibles
        if n % d == 0:
            return False        # un diviseur trouve : pas premier
    return True

def premiers_jusqua(N):
    return [n for n in range(2, N + 1) if est_premier(n)]

est_premier cherche un diviseur entre $$2$$ et $$n-1$$ : s'il en trouve un, $$n$$ n'est pas premier. premiers_jusqua réutilise cette fonction dans une compréhension (programmation modulaire). Par exemple premiers_jusqua(20) renvoie [2, 3, 5, 7, 11, 13, 17, 19].

Corrigé 14

Démonstration

from random import randint

def moyenne_somme(n):
    total = 0
    for _ in range(n):
        total += randint(1, 6) + randint(1, 6)   # somme de 2 des
    return total / n

D'après la fiche 10, l'espérance de la somme de deux dés vaut $$7$$ . Par la loi des grands nombres, moyenne_somme(n) se rapproche de $\boxed{7}$ quand n devient grand.

Corrigé 15

Démonstration

On parcourt L de la fin vers le début en ajoutant dans une nouvelle liste :

def renverse(L):
    R = []
    for i in range(len(L) - 1, -1, -1):   # de len-1 jusqu'a 0
        R.append(L[i])
    return R

range(len(L)-1, -1, -1) compte à rebours : indice de départ len(L)-1, on s'arrête avant $$-1$$ (donc à $$0$$ ), pas de $$-1$$ . Par exemple renverse([1,2,3]) renvoie [3, 2, 1].

Corrigé 16

Démonstration

1.

def intersection(A, B):
    R = []
    for x in A:
        if x in B and x not in R:   # dans B, et pas deja pris
            R.append(x)
    return R

On garde un élément de A s'il est aussi dans B (condition x in B) et pas déjà ajouté (évite les doublons). Cela réalise l'intersection d'ensembles, notée $A\cap B$ en mathématiques. Par exemple intersection([1,2,3,2], [2,3,5]) renvoie [2, 3].

Démonstration · Exercice 16 : produit cartésien

2.

def produit_cartesien(A, B):
    couples = []
    for x in A:
        for y in B:
            couples.append((x, y))
    return couples

Pour chacun des $$p$$ choix de $$x$$ , il existe $$q$$ choix possibles de $$y$$ . Le principe multiplicatif donne donc $p\times q$ couples. On peut aussi écrire en compréhension :

def produit_cartesien(A, B):
    return [(x, y) for x in A for y in B]

Corrigé du problème guidé

Démonstration · Partie A : les briques de base

def moyenne(L):
    return sum(L) / len(L)

def maximum(L):
    m = L[0]
    for x in L:
        if x > m:
            m = x
    return m

def minimum(L):
    m = L[0]
    for x in L:
        if x < m:
            m = x
    return m

def nb_admis(L):
    c = 0
    for note in L:
        if note >= 10:
            c = c + 1
    return c

Chaque fonction fait une seule chose et la renvoie. On peut les tester isolément, par exemple maximum([12, 8, 15]) doit donner $$15$$ .

Démonstration · Partie B : compréhensions et sélection

# 4. notes >= 10 en une ligne
def admis(L):
    return [note for note in L if note >= 10]

# 5. +1 point, plafonne a 20
def ajuste(L):
    return [min(note + 1, 20) for note in L]

La compréhension de la question 4 se lit « les notes telles que note $\geqslant 10$ ». Pour la question 5, min(note + 1, 20) garantit qu'on ne dépasse jamais $$20$$ : un $$20$$ reste $$20$$ , un $$19$$ devient $$20$$ , un $$12$$ devient $$13$$ .

Démonstration · Partie C : assemblage modulaire

def bilan(L):
    moy = round(moyenne(L), 1)
    mini = minimum(L)
    maxi = maximum(L)
    adm = nb_admis(L)
    total = len(L)
    return ("Moyenne : " + str(moy) +
            " ; Min : " + str(mini) +
            " ; Max : " + str(maxi) +
            " ; Admis : " + str(adm) + "/" + str(total))

notes = [12, 8, 15, 10, 6, 18, 9]
print(bilan(notes))
# Moyenne : 11.1 ; Min : 6 ; Max : 18 ; Admis : 4/7

7. Pourquoi découper ? Chaque petite fonction peut être testée et corrigée séparément, ce qui rend les erreurs faciles à localiser ; et une fois sûre, chaque fonction se réutilise dans d'autres programmes sans tout réécrire. Un seul long bloc serait illisible et chaque modification risquerait de tout casser.

Fiche-mémoire

Méthode · Choisir et répéter

if condition:
    action
for k in range(n):
    action
while condition:
    mise_a_jour

Méthode · Fonction

def calcul(x):
    resultat = ...
    return resultat

Maîtrise du chapitre

Validation contrôlée

Réponds aux QCM, sélectionne les bonnes propositions ou remets les étapes dans l'ordre. Le site vérifie chaque réponse avant d'ouvrir la balise suivante.

Proposition	Sa négation
« Tous les $\(x\)$ vérifient $\(P\)$ »	« Il existe un $\(x\)$ qui ne vérifie pas $\(P\)$ »
« Il existe un $\(x\)$ tel que $\(P\)$ »	« Aucun $\(x\)$ ne vérifie $\(P\)$ »
« $\(P\)$ et $\(Q\)$ »	« (non $\(P\)$ ) ou (non $\(Q\)$ ) »
« $\(P\)$ ou $\(Q\)$ »	« (non $\(P\)$ ) et (non $\(Q\)$ ) »

$\(k\)$	ancien $\(s\)$	$\(k^2\)$	nouveau $\(s\)$
1	0	1	1
2	1	4	5
3	5	9	14
4	14	16	30

Avant le cours, vérifie tes bases

Apprendre étape par étape

Pourquoi programmer en maths ?

La machine fait le calcul, toi tu fais le raisonnement

Algorithme ou programme ?

L'idée directrice

L'idée avant le code

Une variable, c'est une boîte avec une étiquette

Choisir, répéter : les deux gestes de base

Découper pour ne pas se noyer : les fonctions

Le cours complet

Variables, types et affectation

Instructions conditionnelles : choisir

Boucles bornées : répéter un nombre connu de fois

Boucles non bornées : répéter jusqu'à une condition

Fonctions et programmation modulaire

Les listes : la grande nouveauté

Un peu de logique et d'ensembles

Couples et produit cartésien

Identité, équation et statut des lettres

Trois structures de raisonnement

Pour aller plus loin : prouver qu'un algorithme est correct

Boîte à outils : réflexes pour le bac

Exercices

Exercice 1 ★☆☆ : Lire une affectation

Exercice 2 ★☆☆ : Trace d'une boucle

Exercice 3 ★☆☆ : Lire une liste

Exercice 4 ★☆☆ : Pair ou impair

Exercice 5 ★☆☆ : Compter

Exercice 6 ★☆☆ : Liste en compréhension

Exercice 7 ★★☆ : Somme conditionnelle

Exercice 8 ★★☆ : Table de multiplication

Exercice 9 ★★☆ : Maximum et sa position

Exercice 10 ★★☆ : Suite et seuil

Exercice 11 ★★☆ : Recherche dans une liste

Exercice 12 ★★★ : Logique et méthodes de preuve

Exercice 13 ★★★ : Tester et lister les nombres premiers

Exercice 14 ★★★ : Simulation et espérance

Exercice 15 ★★★ : Inverser une liste

Exercice 16 ★★★ : Ensembles et produit cartésien via les listes

Problème guidé d'approfondissement

Corrigés détaillés

Corrigé 1

Corrigé 2

Corrigé 3

Corrigé 4

Corrigé 5

Corrigé 6

Corrigé 7

Corrigé 8

Corrigé 9

Corrigé 10

Corrigé 11

Corrigé 12

Corrigé 13

Corrigé 14

Corrigé 15

Corrigé 16

Corrigé du problème guidé

Fiche-mémoire

Maîtrise du chapitre

Parcours validé

Pour relier les notions