Algorithme de calcul du PGCD de deux entiers par la méthode d’Euclide
Plan de tutoriel
1- Principe de l'algorithme
2- Algorithme de calcul du PGCD
3- Programme Python
Principe de l'algorithme
Le PGCD (Plus Grand Commun Diviseur) de deux entiers positifs a et b est le plus grand entier qui divise à la fois a et b. Cet algorithme permet de déterminer rapidement le PGCD de deux entiers en utilisant la méthode d’Euclide.
Dans un premier temps, le programme demande à l’utilisateur de saisir deux entiers positifs a et b. La fonction saisie() vérifie que chaque valeur saisie est supérieure à 1. La saisie est répétée jusqu’à obtenir une valeur valide.
Ensuite, la fonction pgcd(a,b) applique successivement la méthode d’Euclide. Elle calcule le reste r de la division de a par b à l’aide de l’opérateur %. Les valeurs sont ensuite remplacées : a prend la valeur de b et b prend la valeur du reste r.
Cette opération est répétée tant que b est différent de zéro. À chaque étape, le problème est ainsi réduit à la recherche du PGCD de deux nombres plus petits. Lorsque b devient égal à zéro, la valeur de a correspond au PGCD des deux entiers initiaux.
Enfin, le programme principal affiche le résultat obtenu. Par exemple, pour a = 48 et b = 18, les restes successifs sont 12, puis 6, puis 0. Le dernier reste non nul est donc 6, qui est le PGCD de 48 et 18.
Algorithme de calcul du PGCD
Algorithme du programme Principal
L’algorithme principal PGCD_Euclidienne assure l’enchaînement des différentes étapes nécessaires pour calculer le PGCD (Plus Grand Commun Diviseur) de deux entiers positifs.
1- Il appelle la fonction saisie() une première fois afin de demander et récupérer le premier entier a supérieur à 0.
2- Il appelle ensuite saisie() une deuxième fois pour demander et récupérer le deuxième entier b supérieur à 0.
3- Il appelle la fonction pgcd(a, b) afin de calculer le PGCD des deux entiers selon la méthode d’Euclide.
4- Enfin, il affiche le résultat obtenu sous la forme : « Le PGCD de a et b est … ».
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Algorithme PGCD_Euclidienne Debut # Appeler la fonction saisie() pour demander # et récupérer le premier entier a supérieur à 1. a <-- saisie() # Appeler la fonction saisie() pour demander # et récupérer le deuxième entier b supérieur à 1. b <-- saisie() # Appeler la fonction pgcd(a, b) pour calculer # le PGCD des deux entiers a et b. # Afficher ensuite le résultat obtenu. Ecrire("Le PGCD de a et b est ", pgcd(a, b)) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| a | entier |
| b | entier |
La fonction saisie
La fonction saisie() permet de saisir et de contrôler un entier n. Elle oblige l’utilisateur à entrer une valeur strictement supérieure à 1.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Fonction saisie():entier Début # La variable test permet de contrôler # la validité de la valeur saisie par l'utilisateur. test <-- Faux # Répéter la saisie tant que la valeur de n # n'est pas supérieure à 1. Tant que test = Faux faire # Demander à l'utilisateur de saisir un entier n. Ecrire("donner n>1 : ")) Lire(n) # Vérifier que la valeur saisie est supérieure à 1. Si n > 1 alors # La valeur saisie est correcte. # On change test à True pour arrêter la boucle. test <-- True Fin si Fin Tant que # Retourner la valeur de n au programme principal. Retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction pgcd
La fonction pgcd(a, b) a pour rôle de calculer le Plus Grand Commun Diviseur (PGCD) de deux entiers a et b en utilisant la méthode d’Euclide.
Elle répète les calculs tant que b est différent de 0.
1- À chaque étape, elle calcule le reste r de la division entière de a par b à l’aide de MOD.
2- Elle remplace ensuite a par b et b par r afin de poursuivre le calcul avec le nouveau couple de valeurs.
3- Lorsque b devient égal à 0, la valeur contenue dans a correspond au PGCD recherché.
Enfin, la fonction retourne a, qui représente le résultat du calcul.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Fonction pgcd(a,b:entier):entier Début # Répéter les opérations tant que b est différent de 0. # Cette boucle permet d'appliquer successivement # la méthode d'Euclide. Tant que b != 0 faire # Calculer le reste de la division entière # de a par b. r <-- a MOD b # Remplacer a par b. # Cette étape permet de poursuivre # l'algorithme avec les nouvelles valeurs. a <-- b # Remplacer b par le reste r. # Le nouveau couple devient (b, r). b <-- r Fin tant que # Lorsque b devient égal à 0, # a contient le PGCD des deux entiers. retourner a Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| r | entier |
Programme en Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
# ========================================================== # Fonction de saisie # ========================================================== def saisie(): # La variable test permet de contrôler # la validité de la valeur saisie par l'utilisateur. test = False # Répéter la saisie tant que la valeur de n # n'est pas supérieure à 1. while test == False: # Demander à l'utilisateur de saisir un entier n. n = int(input("donner n>1 : ")) # Vérifier que la valeur saisie est supérieure à 1. if n > 0: # La valeur saisie est correcte. # On change test à True pour arrêter la boucle. test = True # Retourner la valeur de n au programme principal. return n # ========================================================== # Fonction pgcd # ========================================================== def pgcd(a, b): # Répéter les opérations tant que b est différent de 0. # Cette boucle permet d'appliquer successivement # la méthode d'Euclide. while b != 0: # Calculer le reste de la division entière # de a par b. r = a % b # Remplacer a par b. # Cette étape permet de poursuivre # l'algorithme avec les nouvelles valeurs. a = b # Remplacer b par le reste r. # Le nouveau couple devient (b, r). b = r # Lorsque b devient égal à 0, # a contient le PGCD des deux entiers. return a # ========================================================== # Programme principal # ========================================================== # Appeler la fonction saisie() pour demander # et récupérer le premier entier a supérieur à 1. a = saisie() # Appeler la fonction saisie() pour demander # et récupérer le deuxième entier b supérieur à 1. b = saisie() # Appeler la fonction pgcd(a, b) pour calculer # le PGCD des deux entiers a et b. # Afficher ensuite le résultat obtenu. print("Le PGCD de a et b est ", pgcd(a, b)) |
Exécution du programme :
0 commentaire
laisser un commentaire
Passion de robotique
Tutoriels récents
Atelier robotique
Tutoriels populaires
Construction des robots
Tutoriels plus commentés
Bras robotique
Categories
Maison intelligente
