2de · Du modèle à l’autonomie

Algorithmique et Python : pas à pas

Observe un exemple expliqué, entraîne-toi avec des indices, puis résous une autre situation sur papier. Compare les étapes avant de faire le point.

Mon objectif

Retrouver mes révisions

Variables, types et affectations

1. Observer

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.

2. S’entraîner avec aide

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}$

Comparer avec 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.

3. Résoudre seul

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.

Comparer avec l’explication

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.

Comparer avec l’explication

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.

4. Aller plus loin

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$$ .

Comparer avec l’explication

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$$ .

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}}.

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

1. Observer

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$$ .

2. S’entraîner avec aide

Liste les valeurs de range(2, 9, 3), range(5, 2, -1) et range(3, 3). Pourquoi range(1, 5, 0) est-il refusé ?

Comparer avec l’explication

Les valeurs sont $$2,5,8$$ , puis $$5,4,3$$ , puis aucune. Le pas $$0$$ provoque une erreur. Dans une boucle sans tour, le corps ne s’exécute pas : une variable créée seulement dedans peut rester non définie. À réessayer : écris un range donnant $$8,6,4,2$$ .

3. Résoudre seul

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)

Comparer avec l’explication

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}.

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.

Comparer avec l’explication

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.

4. Aller plus loin

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$$ .

Comparer avec l’explication

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.

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

1. Observer

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$$ .

2. S’entraîner avec aide

Utilise premier_carre_superieur avec un seuil de $$25$$ . Pourquoi faut-il renvoyer $$6$$ et non $$5$$ ? Que renvoie la fonction pour le seuil $$0$$ ?

Comparer avec l’explication

La boucle doit encore passer de $$5$$ à $$6$$ ; alors $$36>25$$ . Pour le seuil $$0$$ , le premier test $0\leqslant0$ est vrai et l’on renvoie $$1$$ . À réessayer : écris la condition permettant de chercher le premier carré supérieur ou égal ; pour le seuil $$25$$ , le résultat devient $$5$$ .

3. Résoudre seul

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.

Comparer avec l’explication

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.

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.

Comparer avec l’explication

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}}.

4. Aller plus loin

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.

Comparer avec l’explication

Démonstration · Algorithme d'Euclide

É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.

La recherche et les corrigés restent accessibles ici. JavaScript permet de mémoriser ton autoévaluation.