Mathématiques.club

Ecrire un algorithme de seuil

Neige — 2017-03-26T20:48:32Z

Méthode

Ecrire un algorithme n'est pas toujours facile.
On présente ici le cas particulier de l'écriture d'un algorithme "de seuil".

Un algorithme "de seuil" permet de déterminer une valeur pour laquelle une condition est respectée pour la première fois.
Ce type d'algorithme peut être utilisé pour répondre, par exemple, à ce genre de question : « déterminer la plus petite valeur de $n$ pour laquelle $u_n \gt 4,99$ ».

Concrètement, on considère une suite $(u_n)$ et on cherche à écrire un algorithme "de seuil" sur cette suite.
Le modèle à utiliser est le suivant (où les termes de la suite sont représentés par la lettre U et les rangs par la lettre N) :

N prend sa valeur initiale (souvent 0 ou 1)
U prend sa valeur initiale
TANT QUE ... (la condition dépend de l'exercice) N prend la valeur N+1 U prend la valeur .... (le terme suivant qui dépend de l'exercice)
FIN TANT QUE
Afficher ... (selon la question)

Remarque : à l'intérieur de la boucle TANT QUE, l'ordre de l'actualisation de N et U peut être inversé (d'abord U puis N). Même remarque pour l'initialisation de N et U en début d'algorithme.

On s'aperçoit que l'algorithme calcule les termes successifs de $(u_n)$ et que la boucle TANT QUE va tourner tant que la condition sera vraie. Dès que la condition deviendra fausse, on va sortir de cette boucle et afficher un résultat.

Il est important de connaître ce modèle et de suivre les recommandations suivantes :

écrire le squelette du modèle.
écrire la condition. En fait, cette condition doit devenir fausse dès qu'on veut arrêter l'algorithme (il faut donc écrire le contraire de la condition qui apparaît dans la question posée) .
écrire le passage d'un terme U au suivant et du rang N au suivant à l'intérieur de la boucle TANT QUE.
écrire l'affichage final (en vérifiant qu'on répond bien à la question).
tester l'algorithme écrit en l'exécutant pas à pas (on pourra pour cela consulter la méthode : Faire "tourner" un algorithme).

Un exemple en vidéo

D'autres exemples pour comprendre

Niveau facile
On considère la suite $(u_n)$ définie par $u_0=26$ et pour tout $n \in \mathbb{N}$ par $u_{n+1}=1,2u_n-5$.
On admet que cette suite est croissante et tend vers $+\infty$.
Dans ce contexte, à quoi sert l'algorithme suivant ?

N prend la valeur 0
U prend la valeur 26
TANT QUE U≤100 FAIRE N prend la valeur N+1 U prend la valeur 1,2U-5
FIN TANT QUE
Afficher N

Voir la réponse

Cet algorithme affiche la plus petite valeur de $n$ telle que $u_n \gt 100$.
Explications : on commence à exécuter l'algorithme pas à pas.

N=0
U=26
(U≤100 : on entre dans la boucle)
N=1
U=26,2
(U≤100 : on entre dans la boucle)
N=2
U=26,44
...
...
(U>100 : on sort de la boucle)
On affiche N

On s'aperçoit que cet algorithme calcule les termes successifs de $(u_n)$. On entre dans la boucle tant que U≤100 et on en sortira dès que U deviendra strictement supérieur à 100.
Une fois sorti de la boucle TANT QUE, on affiche N, le plus petit entier pour lequel U est strictement supérieur à 100.

Niveau facile
On appelle $v_n$ le nombre de voitures détenues par les habitants d'un village en juillet de l'année $2010+n$. On sait que la suite $(v_n)$ est définie par $v_0=100$ (c'est à dire qu'on compte 100 voitures en juillet 2010) et pour tout $n \in \mathbb{N}$ par $v_{n+1}=1,5v_n+1$.
On admet que cette suite est croissante et tend vers $+\infty$.
Compléter l'algorithme suivant pour qu'il affiche l'année à partir de laquelle le nombre de voitures dépassera 10 000 unités.

N prend la valeur 0
V prend la valeur 100
TANT QUE V≤10 000 FAIRE N prend la valeur N+1 V prend la valeur 1,5V+1
FIN TANT QUE
Afficher ...

Voir la réponse

On cherche à afficher la plus petite année pour laquelle le nombre de voitures dépassera 10 000 unités. Or, cet algorithme sort de la boucle TANT QUE dès que le nombre de voitures V dépasse 10 000. Il suffit donc de récupérer la valeur de N en fin d'algorithme et de faire afficher 2010+N :

N prend la valeur 0
V prend la valeur 100
TANT QUE V≤10 000 FAIRE N prend la valeur N+1 V prend la valeur 1,5V+1
FIN TANT QUE
Afficher 2010+N

Niveau moyen
On considère la suite $(u_n)$ définie par $u_0=25$ et pour tout entier naturel $n$ par $u_{n+1}=0,8\times u_n+10$.
On admet que cette suite est croissante et a pour limite 50.
Compléter l'algorithme suivant pour qu'il calcule la plus petite valeur de $n$ telle que $u_n \geq 49$.

N prend la valeur 0
U prend la valeur 25
TANT QUE ... FAIRE N prend la valeur ... U prend la valeur ...
FIN TANT QUE
Afficher N

Voir la réponse

Cet algorithme va calculer les termes successifs de la suite $(u_n)$ et va boucler dans le TANT QUE tant que U sera inférieur à 49. Il en sortira dès que U sera supérieur ou égal à 49. La condition à écrire est donc TANT QUE U<49 FAIRE.
A l'intérieur de la boucle TANT QUE, il suffit d'actualiser les valeurs de N et U, ce qui donne :

N prend la valeur 0
U prend la valeur 25
TANT QUE U<49 FAIRE N prend la valeur N+1 U prend la valeur 0,8U+10
FIN TANT QUE
Afficher N

Niveau moyen
On appelle $a_n$ la valeur d'une action côtée en bourse le 1er janvier de l'année $2017+n$. Des spécialistes ont affirmé que la suite $(a_n)$ était définie pour tout entier naturel $n$ par $u_n=60\times 0,9^n+40$.
On admet que cette suite est décroissante et a pour limite 40.
Compléter l'algorithme suivant afin de déterminer à partir de quelle année le cours de l'action descendra en dessous de 50 € (selon les spécialiste).

N prend la valeur 0
A prend la valeur ...
TANT QUE ... FAIRE N prend la valeur ... A prend la valeur ...
FIN TANT QUE
Afficher ...

Voir la réponse

Comme dans les cas précédents, cet algorithme calcule les termes successifs de $(a_n)$ et sort de la boucle TANT QUE dès que $a_n<50$. On obtient donc :

N prend la valeur 0
A prend la valeur 100
TANT QUE A≥50 FAIRE N prend la valeur N+1 A prend la valeur 60×0,9^N+40
FIN TANT QUE
Afficher N+2017

Remarque : ^N signifie "à la puissance N".

Niveau difficile
On considère la suite $(u_n)$ définie par $u_1=10$ et pour tout entier naturel non nul $n$ par $u_{n+1}=0,9\times u_n+25-4\times n$.
On admet que cette suite admet des valeurs négatives.
Ecrire un algorithme qui permette de déterminer la plus petite valeur de $n$ telle que $u_n<0$.

Voir la réponse

Comme dans les cas précédents, cet algorithme calcule les termes successifs de $(u_n)$ et sort de la boucle TANT QUE dès que $u_n<0$. On obtient donc :

N prend la valeur 1
U prend la valeur 10
TANT QUE U≥0 FAIRE U prend la valeur 0,9U+25-4×N N prend la valeur N+1
FIN TANT QUE
Afficher N

Remarque : la valeur de N est actualisée après celle de U car, pour calculer $u_{n+1}$, c'est l'ancienne valeur de $n$ qui intervient. Pour s'en rendre compte, on peut exécuter cet algorithme pas à pas.

Au Bac

On peut utilser cette méthode pour résoudre :

la question 4 de Asie, Juin 2016 - Exercice 3 (non spé).
la question 3a de Centres étrangers, Juin 2018 - Exercice 2.

Faire "tourner" un algorithme

Neige — 2016-12-24T23:34:44Z

Méthode

Un algorithme est une liste d'instruction basiques qui se succèdent.
En général, on conçoit un algorithme pour le faire fonctionner sur une machine (calculatrice, ordinateur, ...).
Faire "tourner" un algorithme, consiste à se mettre à la place de la machine et effectuer les instructions, ligne après ligne.

On passe ainsi d'une ligne à une autre dans le sens de la lecture à trois exceptions près :

1. La structure SI... ALORS... SINON... FIN SI
Elle s'utilise souvent ainsi :

ligne 1 : SI conditions ALORS
ligne 2 : instructions A
ligne 3 : SINON
ligne 4 : instructions B
ligne 5 : FIN SI
ligne 6 : (suite de l'algorithme)

On commence à la ligne 1.

Si les conditions sont VRAIES alors on passe à la ligne 2 et on effectue les instructions A.
On passe ensuite à la ligne 6 pour poursuivre l'exécution de l'algorithme.
Si les conditions sont FAUSSES alors on passe à la ligne 4 et on effectue les instructions B.
On passe ensuite à la ligne 6 pour poursuivre l'exécution de l'algorithme.

2. La structure POUR i entre a et b FAIRE... FIN POUR
Elle s'utilise souvent ainsi (avec a et b des nombres entiers) :

ligne 1 : POUR i entre a et b FAIRE
ligne 2 : instructions A
ligne 3 : FIN POUR
ligne 4 : (suite de l'algorithme)

On commence à la ligne 1.

i prend la valeur a.
On passe à la ligne 2 et on effectue les instructions A.
On remonte à la ligne 1 en ajoutant 1 à la valeur de i.
i prend la valeur a+1.
On passe à la ligne 2 et on effectue les instructions A.
On remonte à la ligne 1 en ajoutant 1 à la valeur de i.
i prend la valeur a+2.
On passe à la ligne 2 et on effectue les instructions A.
etc...
i prend la valeur b, c'est le dernier "passage".
On passe à la ligne 2 et on effectue les instructions A.
Cette fois, on passe à la ligne 4 et on poursuit l'exécution de l'algorithme.

3. La structure TANT QUE conditions FAIRE... FIN TANT QUE
Elle s'utilise souvent ainsi :

ligne 1 : TANT QUE conditions FAIRE
ligne 2 : instructions A
ligne 3 : FIN TANT QUE
ligne 4 : (suite de l'algorithme)

On commence à la ligne 1.

Si les conditions sont FAUSSES, on saute directement à la ligne 4 (sans effectuer les instructions A) et on poursuit l'exécution de l'algorithme.
Si les conditions sont VRAIES alors on passe à la ligne 2 et on effectue les instructions A.
On remonte à la ligne 1 et on teste à nouveau les conditions.

Si les conditions sont FAUSSES, on saute directement à la ligne 4 et on poursuit l'exécution de l'algorithme.
Si les conditions sont VRAIES alors on passe à la ligne 2 et on effectue les instructions A.
On remonte à la ligne 1 et on teste à nouveau les conditions.

etc...

Si les conditions sont toujours VRAIES, l'algorithme ne termine jamais, il réalise une boucle infinie, c'est un bug.
Normalement, au bout d'un certain nombre de "passages", les conditions deviennent FAUSSES et on peut poursuivre l'algorithme.

Un exemple en vidéo

D'autres exemples pour comprendre

Niveau facile
Faire "tourner" l'algorithme suivant :

ligne 1 : a prend la valeur 2
ligne 2 : b prend la valeur -3
ligne 3 : SI a+b>0 ALORS
ligne 4 : c prend la valeur 10
ligne 5 : SINON
ligne 6 : c prend la valeur 20
ligne 7 : FIN SI
ligne 8 : Afficher c

Voir la réponse

Dans ce qui suit, on a indiqué les numéros des lignes mais ce n'est pas nécessaire.

a=2 (ligne 1)
b=-3 (ligne 2)
a+b=-1<0 (ligne 3)
c=20 (ligne 6)
On affiche 20 (ligne 8)

Niveau moyen
Faire "tourner" l'algorithme suivant :

ligne 1 : u prend la valeur -1
ligne 2 : n prend la valeur 0
ligne 3 : TANT QUE n<5
ligne 4 : n prend la valeur n+1
ligne 5 : u prend la valeur 2u-3
ligne 6 : FIN TANT QUE
ligne 7 : Afficher n
ligne 8 : Afficher u

Voir la réponse

Dans ce qui suit, on a indiqué les numéros des lignes mais ce n'est pas nécessaire.

u=-1 (ligne 1)
n=0 (ligne 2)
n=0<5 (ligne 3)
n=0+1=1 (ligne 4)
u=2×(-1)-3=-5 (ligne 5)
n=1<5 (ligne 3)
n=1+1=2 (ligne 4)
u=2×(-5)-3=-13 (ligne 5)
n=2<5 (ligne 3)
n=2+1=3 (ligne 4)
u=2×(-13)-3=-29 (ligne 5)
n=3<5 (ligne 3)
n=3+1=4 (ligne 4)
u=2×(-29)-3=-61 (ligne 5)
n=4<5 (ligne 3)
n=4+1=5 (ligne 4)
u=2×(-61)-3=-125 (ligne 5)
n=5, cela rend la condition de la ligne 3 FAUSSE
On affiche n=5 (ligne 7)
On affiche u=-125 (ligne 8)

Remarque : cet algorithme pourrait servir à calculer $u_{5}$ pour la suite définie par $u_{0}=-1$ et pour tout entier naturel $n, u_{n+1}=2\times u_{n}-3$.

Niveau difficile
Faire "tourner" l'algorithme suivant :

ligne 1 : a prend la valeur 3
ligne 2 : b prend la valeur 1
ligne 3 : POUR i entre 1 et 2 FAIRE
ligne 4 : b prend la valeur b+i
ligne 5 : POUR j entre 5 et 7 FAIRE
ligne 6 : a prend la valeur a+i+j
ligne 7 : Afficher a×b
ligne 8 : FIN POUR
ligne 9 : FIN POUR

Voir la réponse

Dans ce qui suit, on a indiqué les numéros des lignes mais ce n'est pas nécessaire.

a=3 (ligne 1)
b=1 (ligne 2)
i=1 (ligne 3)
b=1+1=2 (ligne 4)
j=5 (ligne 5)
a=3+1+5=9 (ligne 6)
On affiche 9×2=18 (ligne 7)
j=6 (ligne 5)
a=9+1+6=16 (ligne 6)
On affiche 16×2=32 (ligne 7)
j=7 (ligne 5)
a=16+1+7=24 (ligne 6)
On affiche 24×2=48 (ligne 7)
i=2 (ligne 3)
b=2+2=4 (ligne 4)
j=5 (ligne 5)
a=24+2+5=31
On affiche 31×4=124 (ligne 7)
j=6 (ligne 5)
a=31+2+6=39 (ligne 6)
On affiche 39×4=156 (ligne 7)
j=7 (ligne 5)
a=39+2+7=48 (ligne 6)
On affiche 48×4=192 (ligne 7)

Au Bac

On peut utilser cette méthode pour résoudre :

la question 3 de Amérique du Sud, Novembre 2016 - Exercice 3 (non spé).
la question B.3a de Nouvelle Calédonie, Novembre 2016 - Exercice 2 (non spé).
la question 1a de Antilles-Guyane, Septembre 2016 - Exercice 4.
la question 3b de Centres étrangers, Juin 2018 - Exercice 2.