Dans cette vidéo, on va voir comment trouver grâce à un algorithme, le plus petit entier n tel qu’une suite Un définie par récurrence soit plus petite ou plus grande qu’une certaine valeur.
Un, suite définie par récurrence.
Donc là, ce qu’on va prendre c’est une suite Un définie par récurrence. On va avoir U(n+1) égale à quelque chose. Alors ici, je vais prendre un exemple, on s’en moque un peu, c’est pas hyper important, ça pourrait aussi être f(Un).
Ici prenons par exemple, Un+1 = 3Un + 3 et U0 = 2. On a donc une suite définie par récurrence. Et la question c’est quel est le plus petit entier n tel que, bon on se moque un peu de… c’est la même chose ici, t’auras régulièrement ce genre d’exercice, ici par exemple je vais dire, tel que Un soit plus grand que 327.
L’important ici n’est pas cette chose là, mais c’est d’écrire un algorithme pour trouver le plus petit entier n tel que la suite Un définie par récurrence soit plus petite ou plus grande que…
Voilà, en gros, on a une suite et on va chercher le plus petit indice, le rang le plus petit de la suite tel que le terme de cette suite soit plus grand que 327.
Trouver le plus petit entier n tel que la suite Un définie par récurrence soit plus grande que… Quel algorithme ?
Alors, naturellement qu’est ce qu’on va faire ? Eh bien, on a U0 et on sait calculer de proche en proche. C’est-à-dire d’un terme à l’autre grâce à la formule de récurrence.
Ici U0 qui vaut deux, et U1 va valoir 3*2 + 3, donc ça fait 9. Ensuite, U2 va valoir 3*U1 + 3, etc, etc. Tu vois que là, si tu fais ça, eh bien tu vas avoir une valeur. Donc U0=2, U1=9, et puis ça va continuer, puis au bout d’un moment, nécessairement, enfin dans ce cas là en tout cas, on va arriver à une valeur qui est plus grande que 327.
Pourquoi faire un algorithme ?
Sauf que calculer tous les termes ici à la main c’est évidemment compliqué et long. Donc ce qu’on va vouloir faire c’est faire ce calcul là, c’est à dire le calcul de tous les termes, grâce à un algorithme.
En gros, U0 on le connaît, il va falloir qu’il calcule U1, U2, U3, etc. et qu’il vérifie pour chacun de ces termes si ce terme est plus grand que 327 ou non. Dès qu’on va passer au dessus de 327, eh bien on va dire : c’est parfait on s’arrête là et on connaît le plus petit entier n tel que Un soit plus grand que 327.
Donc pour faire ça avec un algorithme, on a besoin d’une variable qui nous retient la valeur du terme précédent et du terme courant, mais comme c’est la même chose ici, on ne va pas utiliser la même variable.
Initialisation.
Et on va avoir besoin d’une deuxième variable qui est n essentiellement, on va avoir n=0, ça c’est l’initialisation de notre variable n, et celle qui va retenir le rang, d’accord ?
Et on va appeler U, la variable dans laquelle on va mettre Un. Alors pour n=0, U c’est U0, donc il vaut 2. On ne va pas avoir une variable U0 et une variable U1, et une variable U2 puisqu’on s’en sortirait plus, il y en aurait une infinité. Le but c’est d’avoir U, et à chaque fois, on va l’écraser.
Donc on va mettre U0 d’abord, et puis après, on mettra U1 dedans, après on mettra U2, après on mettre U3. Donc ça c’est notre initialisation ici.
La récurrence.
Maintenant, ce qu’on va vouloir faire c’est calculer les termes suivants jusqu’à ce qu’on dépasse 327, d’accord ? Donc là, il va nous falloir une boucle tant que, puisqu’on ne sait pas combien d’itération on va faire, il nous faut une condition qui va faire intervenir eh bien ce qu’on cherche ici, donc ici 327 nécessairement. Alors, et qu’est ce qu’on veut ?
On veut comparer 327 avec le terme de la suite. Et le terme de la suite, on a dit, on le stock dans U. Donc tant que U, et c’est là où il faut réfléchir un peu… Ce qu’on veut trouver, c’est le plus petit n tel que Un soit plus grand de 327.
En fait, on va devoir continuer à calculer les termes suivants tant que Un est plus petit que 327, d’accord ? Donc ici, tant que U est plus petit que 327, on rentre dedans, et là qu’est ce qu’on veut faire ? Eh bien, on veut calculer le terme suivant.
Calcul et Mise à jour.
On connaît une formule de récurrence ici pour la suite et on veut aussi mettre à jour le rang de la suite. Donc le rang était 0, au terme suivant qu’est ce qu’on va avoir ?
On va avoir le rang qui va être le rang d’avant +1. Donc sur la première itération, on va avoir n qui devient 0 +1, donc ça devient 1. Donc pour calculer le terme de rang 1.
Et ici on fait U = 3U +3, tu vois que U ici c’est bien le terme U0 au départ, donc on va avoir 3*U0 + 3 qu’on va venir affecter à la variable U. Autrement dit, cette variable U, elle va devenir 3U0 + 3, soit U1.
On a deux étapes dans cette boucle, on met à jour l’indice, ici le rang de la suite et on met à jour le terme de la suite. Tout ça, en utilisant la formule de récurrence. Attention ici !
Tu vois qu’ici j’ai mis des signes « = » on aurait pu mettre ici simplement la flèche comme ça qui dit : on affecte n+1 à la variable n. Quand on rentre dans la boucle, n vaut 0, donc n+1 vaut 1, et on va l’affecter à n.
Donc c’est un petit peu subtil ici puisque tu viens écraser la valeur en l’utilisant, mais ça les ordinateurs savent très bien faire. Idem ici, on va avoir 3*U qui vaut 2 ici, plus 3, donc ça va faire 3*2, 6, plus 3, 9 qui vont être mis dans U, et donc U1 vaudra 9.
Résultat ?
Fin de la boucle tant que. Fin de la boucle, bon peu importe comment tu l’écris. Donc ici, fin de la boucle. Qu’est ce que ça veut dire ? Ça veut dire qu’on va revenir au début et on va regarder la valeur de U, d’accord ?
U maintenant c’est U1, U1 vaut 9, il est toujours plus petit que 327, eh bien on va rentrer dans la boucle. On va remplacer, n vaut 1, on va faire n+1, ça vaut 2, donc n va devenir 2, le rang de notre terme. Et ici on va faire 3*U1 + 3, ça va nous donner U2…
Et puis on va continuer comme ça, tu vois qu’ici l’ordinateur va le faire pour toi. Il va calculer le terme suivant jusqu’à temps qu’on ait un terme U qui soit plus grand que 327.
Puisque là, on rentrera plus dans la boucle puisque la condition de la boucle c’est U plus petit que 327. A partir du moment où U est plus grande que 327, eh bien qu’est ce qu’on va faire ?
Afficher le résultat.
On va afficher n puisque c’est n qui nous intéresse ici. On aura trouver le plus petit entier naturel n tel que Un soit plus grand que 327 grâce à notre algorithme.
Voilà, l’algorithme il est tout simple c’est initialisation ici comme toujours. Ici c’est affichage du résultat qui nous intéresse. Et ici, c’est tout le calcul, c’est la boucle de calcul, calcul des termes de la suite.
Tout ça, c’est très classique, il y a des chances que tu aies besoin d’utiliser ce genre de choses. Donc essaye de bien comprendre, on initialise ici le rang et le terme, on fait une boucle qui dans la condition dépend de ce qu’on veut chercher, c’est toujours le sens inverse du signe qu’on avait ici, on met à jour l’indice, on met à jour le terme et on continue.
A la fin, on affiche le rang de la suite qui est donc, l’entier le plus petit tel que ici Un plus grand que 327. Tu vois que si tu avais été dans l’autre sens, eh bien si ça avait été Un plus petit que 128, il aurait fallu regarder U plus grand que 128.
Voilà comment tu peux trouver le plus petit entier n tel qu’une suite définie pas récurrence soit plus petite ou plus grande qu’un certain nombre grâce à un algorithme.
Clique ici pour voir plus de vidéos sur ce thème, et abonne-toi à la chaine Youtube.
