Dans cette vidéo, le présentateur explique le problème de calcul du plus grand commun diviseur (PGCD) de deux entiers positifs fournis par l'utilisateur. Il décrit trois méthodes classiques – énumération des diviseurs, soustraction successive et algorithme d'Euclide – en illustrant chacune avec l'exemple 21 et 15, puis montre que l'algorithme d'Euclide est la plus simple et la plus rapide. Il conçoit ensuite un algorithme détaillé en pseudo‑code : validation des entrées avec des boucles de type Répéter/While, mise en place de variables a, b, x, y, r, conditionnement pour que x soit le dividende et y le diviseur, et boucle TantQue qui répète les divisions successives jusqu’à ce que le reste soit nul. Enfin, il traduit cet algorithme en Python, en adaptant la structure Do‑While par une boucle While, en gérant la conversion de types pour l’affichage, et il montre le programme fonctionner avec différents ordres d’entrée (21‑15 et 15‑21), affichant toujours le PGCD égal à 3. La vidéo se conclut par un rappel du principe et une invitation à la prochaine leçon.
Chapters
Bonjour à tous et bienvenue dans cette nouvelle vidéo d'algorithmique où nous allons traiter l'exercice suivant: Calculer le PGCD de 2 entiers positifs entrés par l'utilisateur en utilisant la méthode la plus simple possible. Le PGCD signifie le plus grand commun diviseur. Il s'agit de l'entier le plus grand qui est à la fois diviseur de tous les nombres spécifiés. Dans l'énoncé, on se contente de 2 nombres, donc l'objectif est de trouver l'entier le plus grand qui divise les 2 nombres saisis par l'utilisateur. Par exemple, si ce dernier entre les nombres 21 et 15, alors on affichera: le PGCD vaut 3, car 3 est le plus grand nombre entier qui divise à la fois 21 et 15. Pour calculer le PGCD de 2 entiers, on peut dénombrer 3 méthodes populaires à savoir: l'exposition de la liste de leurs diviseurs, la méthode des différences ou soustractions successives, l'algorithme d'Euclide ou divisions successives. En appliquant la première méthode aux 2 nombres 21 et 15, allons trouver la liste de leurs diviseurs individuels établis dans l'ordre croissant comme ceci: 1, 3, 7 et 21 pour le nombre 21 et 1, 3, 5 et 15 pour le nombre 15. Les 2 nombres ont 2 diviseurs communs qui sont 1 et 3. Le plus grand des 2 est 3. Donc le PGCD des nombres 21 et 15 vaut 3. Avec la 2ème méthode qui consiste à la soustraction successive, on part du principe que si un nombre est un diviseur de 2 autres nombres, on alors il est aussi diviseur de leur différence. Si on applique ceci aux nombres 21 et 15, alors leurs 2 diviseurs communs 1 et 3 vus précédemment sont aussi diviseurs de leur différence qui vaut 6. Pour exécuter cette méthode on procède de la manière suivante: on calcule la différence des nombres 21 et 15, ce qui donne 6. Ensuite, on continue en calculant la différence entre le résultat calculé qui vaut 6 et le plus petit opérande de l'opération précédente qui vaut 15, ce qui donne 9. On recommence de la même manière en calculant 9- 6, ce qui donne 3, 6- 3 qui donne 3 encore, et 3- 3 qui donne 0. Quand le résultat vaut 0, on arrête et on retient le résultat de l'opération précédente. C'est ce résultat-là, dont la valeur est 3, qui est le PGCD des 2 nombres initiaux 21 et 15. La 3e méthode connue sous le nom d'algorithme d'Euclide consiste à faire des divisions successives comme ceci: on divise le plus grand nombre par le plus petit. Dans ce cas, on divise 21 par 15. On obtient 1 et le reste 6. On recommence en divisant le diviseur de l'opération précédente par le reste. Autrement dit, on divise 15 par 6, on obtient 2 et le reste 3. On recommence de la même manière et on divise 6 par 3. On obtient 2 et le reste 0. L'opération prend fin car le reste est nul. Le PGCD des 2 nombres initiaux vaut alors la valeur du diviseur de la dernière division, c'est-à-dire 3. On constate que l'algorithme d'Euclide constitue la solution la plus simple, nous allons donc l'adopter dans notre algorithme. Il est clair que l'on aura affaire à un traitement itératif, et vu que le nombre de divisions successives à effectuer n'est pas connu à l'avance, alors on va opter pour la boucle TantQue. Notez que l'on se servira aussi de la structure Répéter afin de filtrer les entrées de l'utilisateur de telle sorte à n'accepter que les entiers positifs. Dans cet algorithme, nous aurons besoin des variables suivantes: a et b qui constituent les nombres entrés par l'utilisateur et dont on veut calculer le PGCD. x et y qui constituent respectivement le dividende et le diviseur de chacune des divisions successives que l'on effectuera. Bien entendu, ces 2 variables changeront de valeur à chaque opération comme on l'a vu précédemment, mais au début ils seront initialisés respectivement avec la valeur de a et de b. R qui est le reste de chaque nouvelle division effectuée. Toutes les variables de cet algorithme seront de type entier. Je propose l'algorithme suivant: On commence par demander à l'utilisateur de saisir les valeurs de A et B que l'on récupère juste après. Ces deux traitements sont placés dans deux structures itératives Répéter. Ces dernières tourneront jusqu'à ce que l'utilisateur saisisse des entiers positifs. Vu que ce dernier n'est pas obligé d'entrer les nombres de telle sorte à ce que A soit supérieur à B, alors il faut veiller à ce que le dividende soit d'entier supérieur et le diviseur d'entier inférieur. Nous allons donc procéder à un traitement conditionnel qui consiste à vérifier si A est supérieur à B. Si c'est le cas, alors on initialise les variables X et Y respectivement avec les valeurs de A et de B. Sinon, c'est-à-dire si A est inférieur à B, dans ce cas on initialise X avec la valeur de B et Y avec la valeur de A. Ce traitement fait en sorte que X soit supérieur à Y avant d'entamer le traitement suivant. Maintenant que X et Y sont initialisés correctement, il est temps de procéder au traitement d'Euclide qui va exécuter les divisions successives. On va donc exécuter un traitement itératif à l'aide de la boucle TantQue qui tournera tant que le reste de la division de X par Y est différent de 0. Dans ce bloc, nous allons calculer la nouvelle valeur du reste que l'on stockera dans la variable R. Ensuite on change les valeurs de X et Y avant de faire la division suivante, en affectant à X la valeur de Y et à Y la valeur du reste R. À la sortie de la boucle on aura calculé le PGCD des entiers 1 et B qui vaut la valeur du diviseur de la dernière division. On affiche alors le PGCD calculé et l'algorithme prend fin. Notez que la méthode des différences qui consiste aux soustractions successives donnera aussi un algorithme assez optimisé, mais il est conventionnel que l'algorithme d'Euclide est la méthode la plus simple et la plus rapide qui permet de calculer le PGCD. Maintenant nous allons implémenter notre algorithme en Python pour voir comment il va réagir. On commence par le premier bloc qui demande la valeur de A. Vu que le langage Python ne dispose pas de la structure Do While ou bien Répéter, alors j'ai opté pour la structure While. Dans ce cas, cette structure va tourner indéfiniment jusqu'à ce que la valeur de A saisie par l'utilisateur soit supérieure à 0. On fait la même chose pour b, je vais juste copier ça. Maintenant on va initialiser x et y. Alors si a est supérieur à b, dans ce cas on initialise x avec a et y avec b. Sinon on fait l'inverse. Maintenant on va procéder au calcul du PGCD. On utilise la boucle while. Tant que le reste de la division de x par y est différent de 0, on fait le traitement. On commence par calculer le reste de la division et on l'affecte à la variable r. Ensuite on va modifier les valeurs de x et y. La dernière opération c'est l'affichage. L'opérateur+ dans ce cas sert à la concaténation. Il y a juste un souci, c'est que les variables a, b et y sont des entiers, alors on peut pas les concaténer dans une chaîne de caractères. On va donc les caster, c'est-à-dire qu'on va changer leur type provisoirement en chaîne de caractères juste pour l'affichage. Comme ceci, exécutons. Entrez la valeur de a. Je vais entrer une valeur négative par exemple. On voit que le programme insiste, il faut bien que j'entre une valeur positive. Même une valeur nulle n'est pas acceptée. Bon, je vais entrer 21. Pour le b, c'est le même traitement, alors je mets directement la valeur 15. Et ça m'affiche le PGCD de 21 et 15 vaut 3. Maintenant, je vais entrer les nombres dans l'ordre inverse. Je commence par 15 puis 21. Et ça donne toujours 3. Alors j'espère que vous avez compris le principe. Merci pour votre attention et à la vidéo prochaine.
