Algorithmique et Python · Seconde générale

Avant de commencer5 questions pour vérifier tes bases

1. Que vaut 2t² + 3 pour t = −2 ?

−51911

2. Pour x = 2, quelle proposition est vraie ?

3x + 1 < 73x + 1 = 73x + 1 > 7

3. Pars de 4, ajoute 3, puis multiplie le résultat par 2. Quel nombre obtiens-tu ?

141110

4. Quel est le plus petit entier n tel que 3n > 10 ?

10/334

5. Dans un fichier, 7 personnes sont à la fois cyclistes et majeures. Quelle case du tableau croisé contient ce nombre ?

La somme des marges cyclistes et majeuresL’intersection de la ligne cyclistes et de la colonne majeuresLe total de toutes les personnes

Ton parcours dans ce chapitre

Tu peux comprendre un programme en suivant quelques valeurs sur papier. L'objectif est de relier chaque instruction à ce qu'elle change, puis d'expliquer pourquoi le résultat répond à la question.

Bases utiles : calculer une expression dans l'ordre des opérations, lire un intervalle et un pourcentage. Les définitions nécessaires sont rappelées. Une erreur de code indique une instruction à reprendre, pas une incapacité à programmer. Les indices et solutions restent consultables librement.

Programme 2026–2027 : variables, conditions, boucles, fonctions, simulation et lecture de calculs statistiques. La programmation se travaille aussi dans les autres chapitres ; cette fiche rassemble les outils pour y revenir. La syntaxe des listes n'est pas à mémoriser pour lire une moyenne. La preuve formelle par invariant, le module de fractions et les derniers problèmes sont des prolongements guidés.

Pourquoi étudier l'algorithmique ?

Un ordinateur calcule très vite, mais il ne devine rien. Pour lui faire résoudre un problème, il faut décrire une suite d'instructions sans ambiguïté. Cette description s'appelle un algorithme. Python est un langage qui permet de la rendre exécutable.

Du langage naturel à Python

Lire un programme de haut en bas

Sauf instruction particulière, Python exécute les lignes dans l'ordre. Les espaces au début d'une ligne, appelés indentation, indiquent les blocs appartenant à une condition, une boucle ou une fonction.

Exemple · Un premier programme

prix = 80
taux = 15
prix_reduit = prix * (1 - taux / 100)
print(prix_reduit)

La sortie est 68.0. Le point indique que Python manipule ici un nombre de type float.

Afficher n'est pas renvoyer

Exemple · Pourquoi la différence compte

def carre(x):
    return x ** 2

y = carre(5) + 1
print(y)

La fonction renvoie $$25$$ , puis le programme calcule $$25+1$$ et affiche $$26$$ .

Variables, types et affectations

Une variable informatique est une boite nommée

Exemple · Table de trace

x = 4
y = 3 * x
x = x + 2
y = y - x

Après la ligne	`x`	`y`
1	4	non définie
2	4	12
3	6	12
4	6	6

Une table de trace permet de suivre exactement l'état des variables.

À toi d’essayer

Une variable ne suit pas automatiquement les autres

Prévois les valeurs finales, puis explique pourquoi la première valeur de y ne change pas toute seule.

$\texttt{x = 2}$
$\texttt{y = x}$
$\texttt{x = x + 3}$
$\texttt{z = x + y}$

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

Indice 1 · Une piste

Après chaque ligne, recopie les variables qui n’ont pas été modifiées.

Indice 2 · Un pas de plus

La deuxième ligne mémorise le nombre $$2$$ , pas une relation permanente entre deux variables.

Voir l’explication

Les états sont $(x,y)=(2,\text{non définie})$ , puis $$(2,2)$$ , puis $$(5,2)$$ . Enfin

\begin{aligned}z &= 5+2\\[.35em]&= 7\end{aligned}.

À réessayer : déplace la ligne y = x après x = x + 3. Retrouve $$z=10$$ et explique le changement.

Suivre les variables, une instruction à la fois

Prévois z pour x = 2 au départ. Avance d’une ligne à la fois. Puis inverse l’ordre des deux lignes du milieu : y conserve-t-il le même nombre ?

La ligne bleue est la dernière instruction exécutée. Les cases montrent les valeurs mémorisées à cet instant. « Non définie » signifie qu’aucune valeur n’a encore été affectée à la variable.

Pour x = 2, copier y avant de modifier x donne successivement (x ; y) = (2 ; 2), puis (5 ; 2), et z = 7. Copier y après donne (5 ; 5), puis z = 10. L’affectation copie une valeur au moment où elle est exécutée.

Lire les valeurs et les coordonnées

Pour x = 2, copier y avant de modifier x donne successivement (x ; y) = (2 ; 2), puis (5 ; 2), et z = 7. Copier y après donne (5 ; 5), puis z = 10. L’affectation copie une valeur au moment où elle est exécutée.

Reviens à l’étape 2 et change l’ordre. Explique pourquoi modifier x ne met pas automatiquement y à jour. Puis prévois le résultat avec x = −1 au départ : 1 dans le premier ordre, 4 dans le second.

Les quatre types essentiels

Type Python	Nom	Exemple	Valeur
`int`	entier	$\texttt{n = 12}$	$$12$$
`float`	flottant	$\texttt{x = 2.5}$	approximation décimale
`str`	chaine de caractères	$\texttt{mot = "lycee"}$	texte
`bool`	booléen	$\texttt{ok = x > 0}$	`True` ou `False`

Calculs, comparaisons et booléens

Opérateurs numériques

Python	Mathématiques	Exemple
`+`, `-`, `*`, `/`	$+,-,\times,\div$	`7 / 2` donne `3.5`
`**`	puissance	`3 ** 2` donne `9`
`//`	quotient entier	`17 // 5` donne `3`
`%`	reste	`17 % 5` donne `2`

Comparaisons et connecteurs logiques

Python	Sens	Python	Sens
$\texttt{==}$	est égal à	$\texttt{!=}$	est différent de
$\texttt{<}, \texttt{<=}$	inférieur, inférieur ou égal	$\texttt{>}, \texttt{>=}$	supérieur, supérieur ou égal
`and`	et : deux conditions vraies	`or`	ou : au moins une vraie
`not`	négation

Exemple · Appartenance à un intervalle

La condition mathématique $2\leqslant x<7$ s'écrit directement

2 <= x < 7

La condition « $$n$$ est un multiple positif de $$3$$ inférieur à $$20$$ » s'écrit

n > 0 and n < 20 and n % 3 == 0

Choisir avec if, elif, else

Définition · Instruction conditionnelle

Une condition permet d'exécuter un bloc seulement lorsqu'une proposition est vraie.

if condition:
    instructions_si_vraie
else:
    instructions_si_fausse

Les deux-points et l'indentation sont obligatoires.

Exemple · Tarif selon l'âge

def tarif(age):
    if age < 0:
        return "age impossible"
    elif age < 12:
        return 5
    elif age < 18:
        return 8
    else:
        return 12

Pour age = 15, le premier test est faux, le deuxième est faux, le troisième est vrai : la fonction renvoie $$8$$ et Python ne lit pas le dernier else.

À toi d’essayer

Un second test utilise déjà la nouvelle valeur

Compare les deux programmes pour x = 4.

$\texttt{if x > 0:}$
$\quad \texttt{x = x - 5}$
$\texttt{if x < 0:}$
$\quad \texttt{x = 0}$

Le second programme remplace le deuxième if par elif.

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

Indice 1 · Une piste

Dans le premier programme, la valeur devient $$-1$$ après le premier bloc.

Indice 2 · Un pas de plus

Dans une chaine if/elif, un premier test vrai empêche de tester la branche suivante.

Voir l’explication

Le premier programme obtient $$x=-1$$ , puis teste cette nouvelle valeur et la remplace par $$0$$ . Le second conserve $$x=-1$$ : sa première branche a déjà été choisie. Les deux programmes répondent à des règles différentes. À réessayer : compare-les pour $$x=-2$$ et pour $$x=0$$ .

Répéter un nombre connu de fois : la boucle for

Comprendre `range`

Définition · Boucle bornée

for i in range(debut, fin, pas):
    instructions

La variable i prend les valeurs de debut à fin exclue, en avançant de pas. Si le début vaut $$0$$ et le pas vaut $$1$$ , on peut les omettre.

Instruction	Valeurs prises par `i`	Nombre de tours
`range(5)`	$$0,1,2,3,4$$	5
`range(2, 6)`	$$2,3,4,5$$	4
`range(1, 10, 2)`	$$1,3,5,7,9$$	5
`range(6, 1, -1)`	$$6,5,4,3,2$$	5

Accumuler une somme

Exemple · Somme des entiers de $1$ à $n$

def somme_entiers(n):
    s = 0
    for k in range(1, n + 1):
        s = s + k
    return s

Pour $$n$$ entier positif ou nul, la somme vide en $$n=0$$ vaut $$0$$ . Pour $$n=4$$ , la variable s prend successivement les valeurs $$0,1,3,6,10$$ .

Une preuve à construire

Pourquoi cet algorithme est correct

Explique pourquoi somme_entiers(n) renvoie la somme voulue pour chaque entier $n\geqslant0$ .

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

Indice 1 · Une piste

Commence par $$n=0$$ , puis décris ce que contient s après le tour $$k$$ .

Indice 2 · Un pas de plus

Avant le tour $$k$$ , la somme s’arrête à $$k-1$$ ; l’instruction ajoute le terme suivant.

Voir la preuve expliquée

Avant la boucle, $$s=0$$ . Après le tour correspondant à $$k$$ , la variable $$s$$ contient

1+2+\cdots+k.

En effet, si elle contient $1+\cdots+(k-1)$ avant le tour, l'affectation s = s + k lui ajoute précisément $$k$$ . Si $$n=0$$ , aucun tour n’a lieu et la fonction renvoie $$0$$ . Si $n\geqslant1$ , au dernier tour $$k=n$$ : la fonction renvoie donc $1+2+\cdots+n$ . Cette propriété conservée au fil des tours s'appelle un invariant de boucle.

Compter des valeurs qui vérifient une condition

Exemple · Nombre de multiples de $7$ entre $1$ et $n$

def compte_multiples_7(n):
    compteur = 0
    for k in range(1, n + 1):
        if k % 7 == 0:
            compteur = compteur + 1
    return compteur

L'accumulateur s additionne des valeurs ; le compteur ajoute seulement $$1$$ lorsqu'une condition est satisfaite.

Répéter jusqu'à un seuil : la boucle while

Définition · Boucle non bornée

while condition:
    instructions

Tant que la condition est vraie, le bloc est répété. Le nombre de tours n'est pas fixé à l'avance.

Exemple · Premier entier dont le carré dépasse un seuil

def premier_carre_superieur(seuil):
    n = 0
    while n ** 2 <= seuil:
        n = n + 1
    return n

Pour seuil = 30, la boucle s'arrête à $$n=6$$ , car $5^2\leqslant30$ mais $$6^2>30$$ .

Une preuve à construire

Correction et arrêt

Pour un seuil positif ou nul, pourquoi la recherche du premier carré strictement supérieur s’arrête-t-elle, et pourquoi le résultat est-il le premier ?

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

Indice 1 · Une piste

Les entiers testés partent de $$0$$ et augmentent de $$1$$ .

Indice 2 · Un pas de plus

À la sortie, le test est faux ; au tour précédent il était vrai. Comme le seuil est positif ou nul, il y a au moins un tour.

Voir la preuve expliquée

Pendant la boucle, $$n$$ augmente de $$1$$ : il finira donc par avoir un carré supérieur au seuil si celui-ci est positif. Au moment où la boucle s'arrête, la condition n ** 2 <= seuil est fausse, donc $$n^2>seuil$$ . Au tour précédent, on avait encore $(n-1)^2\leqslant seuil$ . Ainsi, $$n$$ est bien le premier entier qui convient.

Construire des fonctions réutilisables

Définition · Fonction Python

Une fonction possède un nom, zéro ou plusieurs paramètres, un bloc d'instructions et, le plus souvent, une valeur renvoyée par return.

def nom(parametre1, parametre2):
    instructions
    return resultat

Exemple · Distance entre deux nombres

def distance(a, b):
    return abs(a - b)

L'appel distance(3, 8) renvoie $$5$$ . Les nombres $$3$$ et $$8$$ sont les arguments transmis aux paramètres a et b.

Exemple · Une fonction qui appelle une autre fonction

def aire_disque(r):
    return 3.141592653589793 * r ** 2

def aire_couronne(r1, r2):
    return aire_disque(r2) - aire_disque(r1)

Pour $0\leqslant r_1\leqslant r_2$ , on soustrait l'aire du petit disque à celle du grand.

Simuler une expérience aléatoire

Une réalisation n'est pas une probabilité

Exemple · Simuler un succès de probabilité $p$

from random import random

def bernoulli(p):
    if random() < p:
        return 1
    return 0

Pour $0\leqslant p\leqslant1$ , on modélise les tirages comme uniformes et indépendants. Dans ce modèle idéal, la longueur de $$[0;p[$$ est $$p$$ . Le générateur informatique utilise des flottants discrets et approche ce modèle ; $$p=0$$ et $$p=1$$ donnent exactement les issues constantes attendues.

Répéter pour obtenir une fréquence

Exemple · Estimer une probabilité

def frequence_succes(p, n):
    succes = 0
    for k in range(n):
        succes = succes + bernoulli(p)
    return succes / n

On impose $$n$$ entier strictement positif et $0\leqslant p\leqslant1$ . Pour un grand $$n$$ , le résultat est généralement proche de $$p$$ , mais il varie d'une exécution à l'autre.

À toi d’essayer

Définir les entrées avant de simuler

Prévois frequence_succes(0, 20) et frequence_succes(1, 20). Pourquoi l’appel avec $$n=0$$ ne convient-il pas ? Pour $$p=0{,}4$$ , vingt essais doivent-ils donner exactement huit succès ?

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

Indice 1 · Une piste

random() est toujours supérieur ou égal à $$0$$ et strictement inférieur à $$1$$ .

Indice 2 · Un pas de plus

La fréquence est un nombre de succès divisé par un nombre d’essais.

Voir l’explication

Les résultats sont $$0$$ et $$1$$ . Avec $$n=0$$ , la dernière division serait impossible ; le contrat demande $n\geqslant1$ . Pour $$p=0{,}4$$ , huit succès sont possibles, mais non imposés : un autre nombre peut apparaître. À réessayer : donne deux fréquences possibles pour dix essais et explique pourquoi elles ne modifient pas le paramètre $$p$$ .

Lire une fonction statistique

Les séries utilisées ici sont finies, non vides et constituées de nombres réels finis. Le programme demande de savoir lire une fonction renvoyant une moyenne ou un écart type, sans exiger la connaissance des listes. Il faut donc comprendre le rôle des étapes, même si certaines écritures seront fournies.

Exemple · Moyenne d'une série

def moyenne(valeurs):
    somme = 0
    for x in valeurs:
        somme = somme + x
    return somme / len(valeurs)

len(valeurs) est le nombre de données. Si valeurs = [8, 11, 15, 10], la fonction renvoie $$(8+11+15+10)/4=11$$ .

Exemple · Écart type : comprendre sans mémoriser le code

from math import sqrt

def ecart_type(valeurs):
    m = moyenne(valeurs)
    somme = 0
    for x in valeurs:
        somme = somme + (x - m) ** 2
    return sqrt(somme / len(valeurs))

Le programme calcule la moyenne, les écarts à la moyenne, leurs carrés, leur moyenne, puis la racine carrée.

Tester, expliquer et corriger un programme

Exemple · Une erreur de logique

On veut tester si $$n$$ est pair.

def est_pair(n):
    return n % 2 == 1

Le code s'exécute, mais renvoie True pour les impairs. Il faut remplacer == 1 par == 0.

À toi d’essayer

Construire un programme à partir de sa question

Écris une fonction qui compte les entiers de $$1$$ à $$10$$ dont le cube est strictement inférieur à $$100$$ . Prévois son résultat et explique pourquoi chaque entier est examiné exactement une fois.

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

Indice 1 · Une piste

Utilise une boucle for ; sa borne finale doit permettre d’examiner $$10$$ .

Indice 2 · Un pas de plus

Le compteur augmente seulement si k ** 3 < 100.

Voir l’explication

On peut écrire :

`def compter_cubes():`
$\quad \texttt{compteur = 0}$
`for k in range(1, 11):`
$\quad \quad \texttt{if k ** 3 < 100:}$
$\quad \quad \quad \texttt{compteur = compteur + 1}$
`return compteur`

Les valeurs retenues sont $$1,2,3,4$$ , car $$4^3=64<100$$ et $$5^3=125>100$$ ; le résultat est $$4$$ . Le range parcourt chacun des dix entiers une fois. À réessayer sans modèle : compte les cubes inférieurs ou égaux à $$125$$ , puis additionne les entiers retenus. Les deux sorties attendues sont $$5$$ et $$15$$ .

Pour aller plus loin : raisonner sur les algorithmes

L'invariant : une preuve qui accompagne la boucle

Exemple · Produit des entiers de $1$ à $n$

def produit_entiers(n):
    p = 1
    for k in range(1, n + 1):
        p = p * k
    return p

Après le tour d'indice $$k$$ , l'invariant est $p=1\times2\times\cdots\times k$ . L'initialisation à $$1$$ est indispensable : partir de $$0$$ rendrait tous les produits nuls.

Pour la suite : on peut garder des fractions exactes en important Fraction depuis fractions. Fraction(1, 1000) représente exactement $$1/1000$$ . Les opérations conservent des fractions : cela permet de distinguer une approximation mathématique contrôlée des arrondis d'un flottant. Ce module est fourni ici comme outil de prolongement, pas comme syntaxe à mémoriser.

La dichotomie : éliminer la moitié à chaque étape

On cherche une valeur approchée de $\sqrt{2}$ , donc un nombre $$x$$ tel que $$x^2=2$$ . On sait que $$1^2<2<2^2$$ .

from fractions import Fraction

def racine2(epsilon):
    if epsilon <= 0:
        raise ValueError("precision positive attendue")
    a = Fraction(1)
    b = Fraction(2)
    while b - a > epsilon:
        m = (a + b) / 2
        if m ** 2 < 2:
            a = m
        else:
            b = m
    return (a + b) / 2

Par exemple, racine2(Fraction(1, 1000)) renvoie une fraction proche de $\sqrt2$ . La preuve ci-dessous concerne cette fraction ; la convertir avec float introduit un arrondi supplémentaire.

Une preuve à construire

Pourquoi l'erreur est contrôlée

Pour une précision strictement positive, explique pourquoi conserver un encadrement et prendre son milieu contrôle l’erreur. Pourquoi la boucle finit-elle ?

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

Indice 1 · Une piste

Les comparaisons des fractions sont exactes et la fonction carré est croissante sur les nombres positifs.

Indice 2 · Un pas de plus

Après $$k$$ tours, la largeur est $$1/2^k$$ . À la sortie, le milieu est à au plus une demi-largeur de la racine.

Voir la preuve expliquée

Après $$k$$ tours, la largeur vaut $$1/2^k$$ et finit par être inférieure à toute précision strictement positive. La boucle s’arrête donc. L’invariant $a\leqslant\sqrt2\leqslant b$ est conservé par le choix de la moitié qui contient $\sqrt2$ . À la sortie, $b-a\leqslant\varepsilon$ . Le milieu est à une distance d'au plus $(b-a)/2\leqslant\varepsilon/2$ de tout point de $$[a;b]$$ , donc en particulier de $\sqrt2$ .

Les entrées de pgcd sont des entiers positifs ou nuls, non tous deux nuls. La sortie attendue est le PGCD positif. L’affectation simultanée évalue les deux expressions à droite avant de remplacer les deux valeurs à gauche.

Euclide : un algorithme vieux de plus de deux mille ans

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Une preuve à construire

L'idée mathématique

Pour $$a=bq+r$$ avec $$b>0$$ , montre que les diviseurs communs de $$a,b$$ et de $$b,r$$ sont les mêmes. Explique ensuite l’arrêt pour des entiers positifs ou nuls non tous deux nuls.

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

Indice 1 · Une piste

Un diviseur commun de $$a$$ et $$b$$ divise aussi $$a-bq$$ .

Indice 2 · Un pas de plus

Réciproquement, un diviseur de $$b$$ et $$r$$ divise $$bq+r$$ . Le nouveau second entier est strictement plus petit.

Voir la preuve expliquée

Si $$a=bq+r$$ , les diviseurs communs de $$a$$ et $$b$$ sont exactement les diviseurs communs de $$b$$ et $$r$$ :

\begin{aligned}&d\mid a\ \text{et}\ d\mid b\\[.35em]&\ssi d\mid b\ \text{et}\ d\mid(a-bq) = r.\end{aligned}

Remplacer $$(a,b)$$ par $$(b,r)$$ ne change donc pas le PGCD. Les restes diminuent jusqu'à $$0$$ ; le dernier reste non nul est le PGCD.

Boite à outils Python de Seconde

Exemple · Patron accumulateur

s = 0
for k in range(n):
    s = s + valeur(k)

Exemple · Patron compteur

c = 0
for k in range(n):
    if condition(k):
        c = c + 1

Exemple · Patron seuil

n = 0
valeur = valeur_initiale
while valeur < seuil:
    valeur = mise_a_jour(valeur)
    n = n + 1

Exercices progressifs

Pour chaque programme, commence par prévoir le résultat sans ordinateur. Une table de trace est toujours autorisée et souvent recommandée.

On travaille avec des nombres réels finis et, pour les comptages, des entiers. Les moyennes et fréquences demandent un effectif strictement positif ; les rayons sont positifs ou nuls. Les exercices 14 et 15 et le problème du coffre sont des prolongements guidés.

Exercice 1 ★☆☆ : Types et affectations

On exécute :

a = 7
b = 2.5
nom = "Ada"
test = a > 5
a = a + 3
b = a / 4

Donne le type initial de chacune des variables a, b, nom et test.
Donne les valeurs finales de a, b, nom et test.
Explique pourquoi la dernière valeur de b est un flottant.

Exercice 2 ★☆☆ : Construire une table de trace

x = 5
y = 2
x = x + y
y = 2 * x - y
x = y - x
print(x, y)

Construis une table donnant les valeurs de x et y après chaque affectation, puis indique l'affichage final.

Exercice 3 ★☆☆ : Traduire une formule

Écris une fonction prix_ttc(prix_ht, taux) qui renvoie le prix TTC pour un taux exprimé en pourcentage.
Calcule à la main puis avec ta fonction le prix TTC d'un objet à $$60$$ euros soumis à un taux de $20\,\%$ .
Écris une fonction distance(vitesse, duree) qui renvoie la distance parcourue à vitesse constante.

Exercice 4 ★☆☆ : Trois cas

On considère la fonction :

def signe(x):
    if x > 0:
        return 1
    elif x == 0:
        return 0
    else:
        return -1

Que renvoient signe(-4), signe(0) et signe(2.7) ?
Pourquoi le dernier else correspond-il nécessairement à $$x<0$$ ?
Écris une fonction minimum(a, b) qui renvoie le plus petit des deux nombres.

Exercice 5 ★★☆ : Traduire un ensemble par une condition

On veut tester si un réel $$x$$ appartient à

E=[-3;2[\ \cup\ ]5;+\infty[.

Écris une expression booléenne Python qui vaut True exactement lorsque $x\in E$ .
Teste mentalement $$x=-3$$ , $$x=2$$ , $$x=5$$ et $$x=5{,}1$$ .
Écris une expression équivalente à not(x in E), sans utiliser not.

Exercice 6 ★☆☆ : Maitriser `range`

Donne, sans ordinateur, toutes les valeurs successives de k et le nombre de tours pour :

range(4) ;
range(3, 8) ;
range(2, 13, 3) ;
range(10, 3, -2).

Puis indique ce qu'affiche :

for k in range(1, 6):
    print(2 * k)

Exercice 7 ★★☆ : La somme des nombres impairs

def somme_impairs(n):
    s = 0
    for k in range(n):
        s = s + (2 * k + 1)
    return s

Fais une table de trace pour $$n=4$$ .
Conjecture une formule simple pour le résultat en fonction de $$n$$ .
Montre que $$(k+1)^2-k^2=2k+1$$ .
Explique pourquoi cette égalité prouve ta conjecture.

Exercice 8 ★★☆ : Compter les diviseurs

Complète la fonction suivante afin qu'elle renvoie le nombre de diviseurs positifs de $$n$$ :

def nombre_diviseurs(n):
    compteur = ...
    for d in range(..., ...):
        if ...:
            compteur = ...
    return compteur

Utilise-la ensuite pour écrire est_premier(n), qui renvoie True exactement lorsque $$n$$ est premier. Pense au cas $$n<2$$ .

Exercice 9 ★★☆ : Une épargne atteint un seuil

Un capital de $$500$$ euros augmente de $1{,}5\,\%$ par mois. On exécute :

capital = 500
mois = 0
while capital < 600:
    capital = capital * 1.015
    mois = mois + 1
print(mois, capital)

Explique le rôle de chaque variable et la condition de la boucle.
Pourquoi la boucle finit-elle par s'arrêter ?
Montre qu'après $$n$$ mois, le capital vaut $500\times1{,}015^n$ .
Détermine la valeur affichée pour mois et encadre le capital final au centime.

Exercice 10 ★★☆ : Composer des fonctions

Écris les fonctions suivantes :

carre(x), qui renvoie $$x^2$$ ;
distance_origine(x, y), qui renvoie $\sqrt{x^2+y^2}$ en appelant carre ;
dans_disque(x, y, r), qui renvoie un booléen indiquant si le point $$(x;y)$$ appartient au disque de centre l'origine et de rayon $$r$$ .

Teste les points $$(3;4)$$ avec $$r=5$$ puis $$(4;4)$$ avec $$r=5$$ .

Exercice 11 ★★☆ : Deux méthodes, un même résultat

Pour $$n$$ entier strictement positif, la fonction suivante renvoie la moyenne des entiers de $$1$$ à $$n$$ par une méthode inhabituelle :

def moyenne_entiers(n):
    somme = 0
    for k in range(1, n):
        somme = somme + k
    return somme / n + 1

Calcule le résultat pour $$n=3$$ puis $$n=4$$ et compare aux moyennes attendues.
Explique pourquoi ne pas ajouter $$n$$ dans la boucle, puis ajouter $$1$$ après la division, conserve le résultat.
Propose une autre version qui additionne tous les entiers avant de diviser.
Démontre que le résultat renvoyé vaut $$(n+1)/2$$ .

Exercice 12 ★★☆ : Deux dés simulés

On lance deux dés équilibrés et on s'intéresse à l'évènement « la somme est au moins $$10$$ ».

Complète la fonction de simulation.

from random import randint

def frequence_somme_10(n):
    succes = 0
    for k in range(n):
        d1 = randint(..., ...)
        d2 = randint(..., ...)
        if ...:
            succes = ...
    return ...

Calcule exactement la probabilité recherchée en dénombrant les $$36$$ couples équiprobables.
Quelle valeur attends-tu approximativement pour $$n=100000$$ ? Pourquoi ne peut-elle pas être exactement $$1/6$$ pour ce nombre d’essais ?

Exercice 13 ★★☆ : Lire une fonction d'écart type

On reprend la fonction du cours.

def ecart_type(valeurs):
    m = moyenne(valeurs)
    somme = 0
    for x in valeurs:
        somme = somme + (x - m) ** 2
    return sqrt(somme / len(valeurs))

Explique chaque ligne en français.
Calcule à la main le résultat pour valeurs = [2, 2, 6, 6].
Que renvoie la fonction si toutes les valeurs sont égales ? Justifie sans exécuter le code.

Exercice 14 ★★★ : Approcher $\sqrt3$ par dichotomie

Complète les quatre zones :

from fractions import Fraction

def racine3(epsilon):
    if epsilon <= 0:
        raise ValueError("precision positive attendue")
    a = Fraction(1)
    b = Fraction(2)
    while ...:
        m = ...
        if ...:
            a = m
        else:
            ...
    return (a + b) / 2

Effectue deux tours à la main à partir de $$[1;2]$$ .
Montre que $a\leqslant\sqrt3\leqslant b$ reste vrai après chaque tour.
Si la fonction s'arrête lorsque $b-a\leqslant10^{-3}$ , majore l'erreur sur la valeur renvoyée.

Exercice 15 ★★★ : Comprendre l'algorithme d'Euclide

On considère :

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Construis la table de trace pour pgcd(252, 105).
Vérifie que la fonction renvoie $$21$$ et que $$21$$ divise les deux entiers initiaux.
Si $$a=bq+r$$ , montre qu'un entier divise $$a$$ et $$b$$ si et seulement s'il divise $$b$$ et $$r$$ .
Explique pourquoi le deuxième nombre diminue strictement tant qu'il n'est pas nul. Déduis-en que la boucle s'arrête.
Conclus que la valeur renvoyée est bien le PGCD.

Problème défi : le coffre à code

Un coffre choisit secrètement un entier $$s$$ entre $$1$$ et $$100$$ . À chaque question, on propose un entier $$m$$ et le coffre répond si $s\leqslant m$ . On veut retrouver le secret en posant le moins de questions possible. Toutes les parties sont guidées ; les résultats précédents peuvent être réutilisés.

Partie A : découvrir la stratégie

On part de $$[a;b]=[1;100]$$ et on choisit à chaque étape $$m=(a+b)//2$$ .

Si $$m=50$$ et si la réponse est « non », quel nouvel intervalle contient $$s$$ ?
Si la réponse est « oui », quel nouvel intervalle contient $$s$$ ?
Explique pourquoi le nombre de candidats est approximativement divisé par $$2$$ à chaque question.
Retrouve $$s=73$$ en indiquant successivement les intervalles et les milieux.

Partie B : lire et justifier le programme

def nombre_questions(secret, maximum):
    a = 1
    b = maximum
    questions = 0
    while a < b:
        m = (a + b) // 2
        if secret <= m:
            b = m
        else:
            a = m + 1
        questions = questions + 1
    return questions

Pourquoi la condition est-elle a < b et non a <= b ?
Montre que l'invariant $a\leqslant s\leqslant b$ est vrai au départ et conservé par les deux branches.
Montre que la longueur $$b-a+1$$ de l'intervalle diminue strictement si $$a<b$$ .
Déduis des deux questions précédentes qu'à la sortie on a
$\begin{aligned}a &= b\\[.35em]&= s\end{aligned}.$
Vérifie que nombre_questions(73, 100) renvoie $$7$$ .

Partie C : garantir un nombre maximal de questions

Après $$k$$ questions, le nombre de candidats est au plus

\left\lceil\frac{100}{2^k}\right\rceil.

Explique cette formule à partir du partage en deux moitiés.
Compare $$2^6$$ , $$2^7$$ et $$100$$ . Prouve que sept questions suffisent toujours, alors que six ne peuvent pas suffire dans tous les cas.

Complète le programme qui vérifie les cent secrets et renvoie le pire nombre de questions.

def pire_cas(maximum):
    pire = 0
    for secret in range(..., ...):
        q = ...
        if ...:
            pire = ...
    return pire

Partie D : secret aléatoire et nombre moyen de questions

Complète la simulation suivante.

from random import randint

def moyenne_questions(n):
    total = 0
    for k in range(n):
        secret = randint(..., ...)
        total = total + ...
    return ...

Une exécution avec un grand $$n$$ donne environ $$6{,}72$$ . Explique pourquoi ce résultat varie légèrement et pourquoi il ne dépasse pas $$7$$ .

Partie E : quand une réponse peut être fausse

Chaque réponse du coffre a une probabilité $$0{,}05$$ d'être erronée. Pour sécuriser une question, on la pose trois fois et on garde la réponse majoritaire. On suppose les trois réponses indépendantes.

La majorité est fausse s'il y a exactement deux ou exactement trois erreurs. Montre que cette probabilité vaut
$3\times0{,}05^2\times0{,}95+0{,}05^3=0{,}00725.$

Complète la fonction qui renvoie True lorsque la majorité des trois réponses est correcte.

from random import random

def reponse_majoritaire_correcte():
    correctes = 0
    for k in range(3):
        if random() >= ...:
            correctes = correctes + 1
    return correctes >= ...

Compare $$0{,}00725$$ à $$0{,}05$$ et explique l'intérêt, mais aussi le cout, de la répétition.
Une erreur au début peut-elle être réparée par la suite par l'algorithme de dichotomie ? Explique pourquoi il faut sécuriser chaque réponse.

Corrigés détaillés des exercices

Corrigé 1

Corrigé 2

Démonstration · Table de trace

On utilise toujours les valeurs disponibles avant l'affectation de la ligne.

Ligne	`x`	`y`	Calcul
1	5	non définie	initialisation de $$x$$
2	5	2	initialisation de $$y$$
3	7	2	$x\leftarrow5+2$
4	7	12	$y\leftarrow2\times7-2$
5	5	12	$x\leftarrow12-7$

Le programme affiche donc 5 12.

Corrigé 3

Démonstration · Traduire une formule

1. Augmenter le prix HT du taux $$t$$ revient à multiplier par $$1+t/100$$ .

def prix_ttc(prix_ht, taux):
    return prix_ht * (1 + taux / 100)

2. À la main,

\begin{aligned}60\left(1+\frac{20}{100}\right) &= 60\times1{,}2\\[.35em]&= \boxed{72\text{ euros}}.\end{aligned}

L'appel prix_ttc(60, 20) renvoie 72.0.

3. À vitesse constante, $d=v\times t$ :

def distance(vitesse, duree):
    return vitesse * duree

Les unités doivent être compatibles : par exemple km/h et h donnent des km.

Corrigé 4

Démonstration · Trois cas

1. On obtient

\begin{aligned}&\boxed{\texttt{signe(-4) = -1}},\\[.35em]&\boxed{\texttt{signe(0) = 0}},\\[.35em]&\boxed{\texttt{signe(2.7) = 1}}.\end{aligned}

2. Lorsque Python atteint else, il sait que x > 0 est faux et que x == 0 est faux. Le nombre n'est ni positif ni nul ; il est donc strictement négatif.

3.

def minimum(a, b):
    if a <= b:
        return a
    else:
        return b

Le cas $$a=b$$ renvoie $$a$$ , qui est bien le minimum commun.

Corrigé 5

Démonstration · Ensemble et booléen

1. La première partie impose $-3\leqslant x<2$ et la seconde $$x>5$$ :

(-3 <= x < 2) or (x > 5)

2.

$$-3$$ appartient à $$E$$ : la borne est incluse ;
$$2$$ n'appartient pas à $$E$$ : la borne est exclue ;
$$5$$ n'appartient pas à $$E$$ ;
$$5{,}1$$ appartient à $$E$$ .

3. Le complémentaire de $$E$$ est

]-\infty;-3[\ \cup\ [2;5].

Une expression sans not est donc

(x < -3) or (2 <= x <= 5)

On retrouve bien le changement de statut de toutes les frontières.

Corrigé 6

Démonstration · Les bornes de range

La borne finale n'est jamais prise.

Instruction	Valeurs	Tours
`range(4)`	$$0,1,2,3$$	4
`range(3, 8)`	$$3,4,5,6,7$$	5
`range(2, 13, 3)`	$$2,5,8,11$$	4
`range(10, 3, -2)`	$$10,8,6,4$$	4

Dans la dernière boucle, $$k$$ prend les valeurs $$1,2,3,4,5$$ . Le programme affiche, sur cinq lignes,

\boxed{2,\ 4,\ 6,\ 8,\ 10}.

Corrigé 7

Démonstration · Somme des impairs

1. Pour $$n=4$$ :

$$k$$	nombre ajouté $$2k+1$$	$$s$$ après le tour
avant la boucle	aucun	0
0	1	1
1	3	4
2	5	9
3	7	16

2. On conjecture somme_impairs(n)=n^2.

3. En développant,

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

4. Le programme additionne

1+3+\cdots+(2n-1)=\sum_{k=0}^{n-1}(2k+1).

Or $$2k+1=(k+1)^2-k^2$$ . Les termes intermédiaires s'annulent :

(1^2-0^2)+(2^2-1^2)+\cdots+(n^2-(n-1)^2)=n^2.

La conjecture est donc démontrée.

Corrigé 8

Démonstration · Compter les diviseurs

On teste tous les entiers $$d$$ de $$1$$ à $$n$$ inclus et on incrémente le compteur lorsque le reste est nul.

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

Un entier est premier s'il est au moins égal à $$2$$ et possède exactement deux diviseurs positifs.

def est_premier(n):
    if n < 2:
        return False
    return nombre_diviseurs(n) == 2

Par exemple, $$1$$ possède un seul diviseur mais n'est pas premier ; le test $$n<2$$ est donc indispensable.

Corrigé 9

Démonstration · Capital et seuil

1. capital contient la somme disponible et mois compte les augmentations déjà appliquées. La boucle continue tant que le capital reste strictement inférieur à $$600$$ euros.

2. À chaque tour, le capital positif est multiplié par $$1{,}015>1$$ : il augmente. Les puissances de $$1{,}015$$ finissent par dépasser $$600/500=1{,}2$$ , donc la boucle s'arrête.

3. Au départ, pour $$n=0$$ , le capital vaut $500=500\times1{,}015^0$ . S'il vaut $500\times1{,}015^n$ , le tour suivant le multiplie par $$1{,}015$$ et donne $500\times1{,}015^{n+1}$ . La formule est donc vraie à chaque mois.

4. On trouve

\begin{aligned}500\times1{,}015^{12} &\approx597{,}81<600,\\[.35em]500\times1{,}015^{13} &\approx606{,}78\geqslant600.\end{aligned}

Le programme affiche donc 13 mois. Le capital final est encadré par

606{,}77<500\times1{,}015^{13}<606{,}78.

Son arrondi au centime est $$606{,}78$$ euros. Le programme conserve les décimales à chaque mois ; un arrondi bancaire mensuel définirait un autre modèle.

Corrigé 10

Démonstration · Composer des fonctions

from math import sqrt

def carre(x):
    return x ** 2

def distance_origine(x, y):
    return sqrt(carre(x) + carre(y))

def dans_disque(x, y, r):
    return distance_origine(x, y) <= r

Pour $$(3;4)$$ , la distance vaut $\sqrt{9+16}=5$ : le point appartient au disque fermé de rayon $$5$$ . Pour $$(4;4)$$ , elle vaut $\sqrt{32}=4\sqrt2\approx5{,}66>5$ : le point n'y appartient pas. Ainsi,

\begin{aligned}&\boxed{\texttt{dans\_disque(3, 4, 5) = True}},\\[.35em]&\boxed{\texttt{dans\_disque(4, 4, 5) = False}}.\end{aligned}

Corrigé 11

Démonstration · Deux calculs équivalents

1. Pour $$n=3$$ , la boucle utilise seulement $$k=1,2$$ , donc somme vaut $$3$$ . La dernière ligne renvoie $$3/3+1=2$$ , alors que la moyenne de $$1,2,3$$ est également $$2$$ . Ce cas donne donc le bon résultat : il est compatible avec le résultat attendu. Pour $$n=4$$ , le programme renvoie

\frac{1+2+3}{4}+1=2{,}5,

alors que la vraie moyenne vaut $$(1+2+3+4)/4=2{,}5$$ : l’égalité persiste pour tout entier $n\geqslant1$ .

Le programme est donc une autre méthode valide. Pour le justifier pour tout $$n$$ , il faut expliquer son calcul.

2. range(1, n) additionne seulement les termes jusqu’à $$n-1$$ . Ajouter $$1=n/n$$ après la division revient exactement à inclure le terme manquant $$n$$ avant de diviser la somme complète par $$n$$ .

3.

def moyenne_entiers(n):
    somme = 0
    for k in range(1, n + 1):
        somme = somme + k
    return somme / n

4. Pour $n\geqslant1$ ,

1+2+\cdots+n=\frac{n(n+1)}2.

La fonction renvoie donc

\frac{n(n+1)/2}{n}=\boxed{\frac{n+1}{2}}.

Corrigé 12

Démonstration · Deux dés

1.

from random import randint

def frequence_somme_10(n):
    succes = 0
    for k in range(n):
        d1 = randint(1, 6)
        d2 = randint(1, 6)
        if d1 + d2 >= 10:
            succes = succes + 1
    return succes / n

2. Les couples favorables sont

\[(4,6),(5,5),(5,6),(6,4),(6,5),(6,6).\]

Il y en a $$6$$ parmi $$36$$ couples équiprobables, donc

\begin{aligned}P(\text{somme}\geqslant10) &= \frac6{36}\\[.35em]&= \boxed{\frac16}.\end{aligned}

3. Pour $$n=100000$$ , on attend une fréquence proche de $1/6\approx0{,}1667$ . Le nombre de succès fluctue. Ici, $$100000$$ n’est pas divisible par $$6$$ : une fréquence égale exactement à $$1/6$$ est impossible. Avec un nombre d’essais multiple de $$6$$ , elle serait possible, sans être garantie.

Corrigé 13

Corrigé 14

Démonstration · Dichotomie pour $\sqrt3$

Le programme complété est :

from fractions import Fraction

def racine3(epsilon):
    if epsilon <= 0:
        raise ValueError("precision positive attendue")
    a = Fraction(1)
    b = Fraction(2)
    while b - a > epsilon:
        m = (a + b) / 2
        if m ** 2 < 3:
            a = m
        else:
            b = m
    return (a + b) / 2

1. Premier milieu : $$m=1{,}5$$ et $m^2=2{,}25<3$ , donc le nouvel intervalle est $$[1{,}5;2]$$ . Deuxième milieu : $$m=1{,}75$$ et $m^2=3{,}0625>3$ , donc le nouvel intervalle est $$[1{,}5;1{,}75]$$ .

2. Supposons $a\leqslant\sqrt3\leqslant b$ . Si $$m^2<3$$ , alors $m<\sqrt3$ et remplacer $$a$$ par $$m$$ conserve l'encadrement. Sinon $m^2\geqslant3$ , donc $m\geqslant\sqrt3$ et remplacer $$b$$ par $$m$$ conserve encore l'encadrement.

3. À la sortie, $b-a\leqslant10^{-3}$ . Le milieu est à une distance d'au plus $$(b-a)/2$$ de $\sqrt3$ , donc

\boxed{\left|\frac{a+b}{2}-\sqrt3\right|\leqslant5\times10^{-4}}.

Corrigé 15

Démonstration · Algorithme d'Euclide

1.

Étape	$$a$$	$$b$$
départ	252	105
1	105	$252\mathbin{\%}105=42$
2	42	$105\mathbin{\%}42=21$
3	21	$42\mathbin{\%}21=0$

2. La fonction renvoie 21. On vérifie $252=21\times12$ et $105=21\times5$ .

3. Si $$d$$ divise $$a$$ et $$b$$ , alors il divise toute combinaison $$a-bq=r$$ . Réciproquement, s'il divise $$b$$ et $$r$$ , il divise $$bq+r=a$$ . Ainsi

\begin{aligned}&d\mid a\ \text{et}\ d\mid b\\[.35em]&\ssi d\mid b\ \text{et}\ d\mid r.\end{aligned}

4. Le reste $r=a\mathbin{\%}b$ vérifie $0\leqslant r<b$ . Tant que $b\neq0$ , le nouveau deuxième nombre est donc un entier positif ou nul strictement plus petit que l'ancien. Une suite strictement décroissante d'entiers naturels ne peut pas continuer indéfiniment : la boucle s'arrête.

5. Chaque remplacement conserve exactement les diviseurs communs, donc conserve le PGCD. À la fin, le couple est $$(a,0)$$ ; ses diviseurs communs sont les diviseurs de $$a$$ , et le plus grand est $$a$$ . La valeur renvoyée est bien le PGCD initial.

Corrigé détaillé du problème

Partie A : découvrir la stratégie

Démonstration · Questions 1 à 4

1. Si la réponse à $s\leqslant50$ est « non », alors $$s>50$$ et le nouvel intervalle est [51;100].

2. Si la réponse est « oui », on conserve [1;50].

3. Le milieu sépare l'intervalle en deux parties dont les effectifs diffèrent d'au plus $$1$$ . Une réponse permet donc d'éliminer environ la moitié des candidats.

4. Pour $$s=73$$ :

Question	Intervalle avant	Milieu $$m$$	Intervalle après
1	$$[1;100]$$	50	$$[51;100]$$
2	$$[51;100]$$	75	$$[51;75]$$
3	$$[51;75]$$	63	$$[64;75]$$
4	$$[64;75]$$	69	$$[70;75]$$
5	$$[70;75]$$	72	$$[73;75]$$
6	$$[73;75]$$	74	$$[73;74]$$
7	$$[73;74]$$	73	$$[73;73]$$

Le secret est isolé après sept questions.

Partie B : lire et justifier le programme

Démonstration · Questions 5 à 9

5. Lorsque $$a=b$$ , l'intervalle ne contient plus qu'un entier : le secret est trouvé. Avec a <= b, la boucle ferait un tour inutile et pourrait ne plus réduire correctement un intervalle déjà réduit à un point.

6. Au départ, l'entrée garantit $1\leqslant s\leqslant maximum$ , donc l'invariant est vrai. Supposons $a\leqslant s\leqslant b$ .

Si $s\leqslant m$ , on remplace $$b$$ par $$m$$ : alors $a\leqslant s\leqslant m$ .
Sinon $$s>m$$ ; comme $$s$$ est entier, $s\geqslant m+1$ . On remplace $$a$$ par $$m+1$$ et $m+1\leqslant s\leqslant b$ .

L'invariant est donc conservé.

7. Si $$a<b$$ , le milieu $$m=(a+b)//2$$ vérifie $a\leqslant m<b$ . Dans la branche gauche, la nouvelle longueur est $$m-a+1<b-a+1$$ . Dans la branche droite, elle vaut $$b-m<b-a+1$$ . Elle diminue donc strictement.

8. La longueur est un entier positif qui diminue : elle finit par valoir $$1$$ , donc $$a=b$$ . L'invariant donne alors $a\leqslant s\leqslant a$ , d'où a=b=s.

9. La trace de la partie A compte sept réductions, donc

\boxed{\texttt{nombre\_questions(73, 100) = 7}}.

Partie C : garantir le pire cas

Démonstration · Questions 10 à 12

10. Une question remplace un ensemble de $$N$$ candidats par une moitié contenant au plus $\lceil N/2\rceil$ candidats. Après deux questions, il en reste au plus $\lceil100/2^2\rceil$ , et après $$k$$ questions au plus $\lceil100/2^k\rceil$ .

11. On a

2^6=64<100\leqslant128=2^7.

La réduction démontrée donne après sept questions au plus $\lceil100/128\rceil=1$ candidat : sept questions suffisent. Six réponses ne produisent que $$64$$ suites possibles de réponses : elles ne peuvent pas identifier à coup sûr l'un des $$100$$ secrets.

12.

def pire_cas(maximum):
    pire = 0
    for secret in range(1, maximum + 1):
        q = nombre_questions(secret, maximum)
        if q > pire:
            pire = q
    return pire

L'appel pire_cas(100) renvoie 7, ce qui confirme la garantie démontrée.

Partie D : moyenne pour un secret aléatoire

Démonstration · Questions 13 et 14

13.

from random import randint

def moyenne_questions(n):
    total = 0
    for k in range(n):
        secret = randint(1, 100)
        total = total + nombre_questions(secret, 100)
    return total / n

14. Les secrets sont tirés aléatoirement, donc leurs effectifs varient légèrement d'une exécution à l'autre. La moyenne fluctue autour de la valeur théorique. Pour un grand échantillon, elle est généralement proche de $$6{,}72$$ et ne dépasse pas $$7$$ , car chaque recherche demande soit six, soit sept questions. Un échantillon ne contenant que des recherches en sept questions donnerait exactement $$7$$ . Plus précisément, $$28$$ secrets demandent six questions et $$72$$ en demandent sept, donc

\frac{28\times6+72\times7}{100}=\boxed{6{,}72}.

Partie E : réponses imparfaites

Démonstration · Questions 15 à 18

15. Pour exactement deux erreurs, il y a trois choix pour la seule réponse correcte. Par indépendance, chaque ordre a une probabilité $0{,}05^2\times0{,}95$ . Pour trois erreurs, la probabilité est $0{,}05^3$ . Ainsi

\begin{aligned}P(\text{majorité fausse}) &= 3\times0{,}05^2\times0{,}95+0{,}05^3\\[.35em]&= \boxed{0{,}00725}.\end{aligned}

16.

from random import random

def reponse_majoritaire_correcte():
    correctes = 0
    for k in range(3):
        if random() >= 0.05:
            correctes = correctes + 1
    return correctes >= 2

Une réponse est modélisée correcte lorsque le nombre tiré appartient à $$[0{,}05;1[$$ , de longueur $$0{,}95$$ .

17. Le risque passe de $5\,\%$ à $0{,}725\,\%$ , soit environ sept fois moins. En contrepartie, chaque étape demande trois réponses au lieu d'une : le temps et le nombre total de questions sont triplés.

18. Une mauvaise réponse choisit la moitié qui ne contient pas le secret. Le secret sort alors définitivement de l'intervalle $$[a;b]$$ ; les étapes suivantes ne cherchent que dans le mauvais intervalle et ne peuvent pas le récupérer. Il faut donc sécuriser chaque décision, surtout les premières.

Fiche-mémoire

Méthode · Choisir

if condition:
    action_A
else:
    action_B

Méthode · Répéter $n$ fois

for k in range(n):
    action

Méthode · Répéter jusqu'au seuil

while valeur < seuil:
    valeur = mise_a_jour(valeur)

Définition · 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.

Question	Intervalle avant	Milieu $\(m\)$	Intervalle après
1	$\([1;100]\)$	50	$\([51;100]\)$
2	$\([51;100]\)$	75	$\([51;75]\)$
3	$\([51;75]\)$	63	$\([64;75]\)$
4	$\([64;75]\)$	69	$\([70;75]\)$
5	$\([70;75]\)$	72	$\([73;75]\)$
6	$\([73;75]\)$	74	$\([73;74]\)$
7	$\([73;74]\)$	73	$\([73;73]\)$

Instruction	Valeurs prises par `i`	Nombre de tours
`range(5)`	$\(0,1,2,3,4\)$	5
`range(2, 6)`	$\(2,3,4,5\)$	4
`range(1, 10, 2)`	$\(1,3,5,7,9\)$	5
`range(6, 1, -1)`	$\(6,5,4,3,2\)$	5

Ligne	`x`	`y`	Calcul
1	5	non définie	initialisation de $\(x\)$
2	5	2	initialisation de $\(y\)$
3	7	2	$x\leftarrow5+2$
4	7	12	$y\leftarrow2\times7-2$
5	5	12	$x\leftarrow12-7$

Instruction	Valeurs	Tours
`range(4)`	$\(0,1,2,3\)$	4
`range(3, 8)`	$\(3,4,5,6,7\)$	5
`range(2, 13, 3)`	$\(2,5,8,11\)$	4
`range(10, 3, -2)`	$\(10,8,6,4\)$	4

Avant le cours, vérifie tes bases

Ton parcours dans ce chapitre

Pourquoi étudier l'algorithmique ?

Du langage naturel à Python

Lire un programme de haut en bas

Afficher n'est pas renvoyer

Variables, types et affectations

Une variable informatique est une boite nommée

Les quatre types essentiels

Calculs, comparaisons et booléens

Opérateurs numériques

Comparaisons et connecteurs logiques

Choisir avec if, elif, else

Répéter un nombre connu de fois : la boucle for

Comprendre range

Accumuler une somme

Compter des valeurs qui vérifient une condition

Répéter jusqu'à un seuil : la boucle while

Construire des fonctions réutilisables

Simuler une expérience aléatoire

Une réalisation n'est pas une probabilité

Répéter pour obtenir une fréquence

Lire une fonction statistique

Tester, expliquer et corriger un programme

Pour aller plus loin : raisonner sur les algorithmes

L'invariant : une preuve qui accompagne la boucle

La dichotomie : éliminer la moitié à chaque étape

Euclide : un algorithme vieux de plus de deux mille ans

Boite à outils Python de Seconde

Exercices progressifs

Exercice 1 ★☆☆ : Types et affectations

Exercice 2 ★☆☆ : Construire une table de trace

Exercice 3 ★☆☆ : Traduire une formule

Exercice 4 ★☆☆ : Trois cas

Exercice 5 ★★☆ : Traduire un ensemble par une condition

Exercice 6 ★☆☆ : Maitriser range

Exercice 7 ★★☆ : La somme des nombres impairs

Exercice 8 ★★☆ : Compter les diviseurs

Exercice 9 ★★☆ : Une épargne atteint un seuil

Exercice 10 ★★☆ : Composer des fonctions

Exercice 11 ★★☆ : Deux méthodes, un même résultat

Exercice 12 ★★☆ : Deux dés simulés

Exercice 13 ★★☆ : Lire une fonction d'écart type

Exercice 14 ★★★ : Approcher \(\sqrt3\) par dichotomie

Exercice 15 ★★★ : Comprendre l'algorithme d'Euclide

Problème défi : le coffre à code

Partie A : découvrir la stratégie

Partie B : lire et justifier le programme

Partie C : garantir un nombre maximal de questions

Partie D : secret aléatoire et nombre moyen de questions

Partie E : quand une réponse peut être fausse

Corrigés détaillés des exercices

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é détaillé du problème

Partie A : découvrir la stratégie

Partie B : lire et justifier le programme

Partie C : garantir le pire cas

Partie D : moyenne pour un secret aléatoire

Partie E : réponses imparfaites

Fiche-mémoire

Maîtrise du chapitre

Pour relier les notions

Comprendre `range`

Exercice 6 ★☆☆ : Maitriser `range`

Exercice 14 ★★★ : Approcher $\sqrt3$ par dichotomie