Mathématiques.club

Accueil > Terminale ES > Algorithmes > Méthodes > Ecrire un algorithme de seuil

Ecrire un algorithme de seuil

dimanche 26 mars 2017, par Neige

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 :

Un message, un commentaire ?

modération a priori

Ce forum est modéré a priori : votre contribution n’apparaîtra qu’après avoir été validée par un administrateur du site.

Qui êtes-vous ?
Votre message

Pour créer des paragraphes, laissez simplement des lignes vides.