Algorithme de calcul du PGCD de deux entiers par la méthode d’Euclide

Bac SC 21-09-26

12 0

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 pour calculer le factoriel d’un entier

Algorithme du programme Principal

L’algorithme principal Factoriel assure l’exécution générale du programme.

Il commence par appeler la fonction saisie() afin de demander à l’utilisateur une valeur n supérieure à 1 et de la mémoriser dans la variable n.

Ensuite, il appelle la fonction factoriel(n) en lui transmettant la valeur saisie. Cette fonction calcule le factoriel de n.

Enfin, l’algorithme principal affiche le résultat obtenu à l’aide de l’instruction Ecrire.

Algorithme PGCD_Euclidienne
Debut  
     # Appeler la fonction saisie() pour demander
     # et récupérer le premier entier a supérieur à 0.
     a <-- saisie()
     # Appeler la fonction saisie() pour demander
     # et récupérer le deuxième entier b supérieur à 0.
     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

Algorithme PGCD_Euclidienne

Debut

# Appeler la fonction saisie() pour demander

# et récupérer le premier entier a supérieur à 0.

a <-- saisie()

# Appeler la fonction saisie() pour demander

# et récupérer le deuxième entier b supérieur à 0.

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

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.

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

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
ch	chaîne des caractères

La fonction fact

La fonction fact(n) permet de calculer le factoriel de l’entier n.

Elle initialise la variable f à 1, puis parcourt les entiers de 2 jusqu’à n. À chaque étape, elle multiplie f par l’entier courant i. À la fin de la boucle, f contient le résultat du calcul du factoriel de n.

Fonction fact(n:entier):entier
Début
    # Initialiser la variable f à 1.
    # f contiendra progressivement le résultat du factoriel.
    f <-- 1
    # Parcourir les entiers de 2 jusqu'à n.
    # Le dernier entier n est inclus grâce à n+1.
    Pour i de 2 à n  faire
        # Multiplier le résultat précédent par i.
        # À chaque étape, f contient le produit des entiers
        # parcourus jusqu'à présent.
        f <-- f * i
    Fin pour
    # Retourner la valeur finale de f,
    # qui représente le factoriel de n.
    Retourner f
Fin

Fonction fact(n:entier):entier

Début

# Initialiser la variable f à 1.

# f contiendra progressivement le résultat du factoriel.

f <-- 1

# Parcourir les entiers de 2 jusqu'à n.

# Le dernier entier n est inclus grâce à n+1.

Pour i de 2 à n faire

# Multiplier le résultat précédent par i.

# À chaque étape, f contient le produit des entiers

# parcourus jusqu'à présent.

f <-- f * i

Fin pour

# Retourner la valeur finale de f,

# qui représente le factoriel de n.

Retourner f

Fin

Déclaration des objets

Objet	Type / Nature
i	entier
f	entier

Programme en Python

# ==========================================================
# 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 > 1:

            # 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 factoriel
# ==========================================================

def factoriel(n):

    # Initialiser la variable f à 1.
    # f contiendra progressivement le résultat du factoriel.
    f = 1

    # Parcourir les entiers de 2 jusqu'à n.
    # Le dernier entier n est inclus grâce à n+1.
    for i in range(2, n + 1):

        # Multiplier le résultat précédent par i.
        # À chaque étape, f contient le produit des entiers
        # parcourus jusqu'à présent.
        f = f * i

    # Retourner la valeur finale de f,
    # qui représente le factoriel de n.
    return f


# ==========================================================
# Programme principal
# ==========================================================

# Appeler la fonction saisie() pour demander
# et récupérer une valeur n supérieure à 1.
n = saisie()

# Appeler la fonction factoriel(n) pour calculer
# le factoriel de n, puis afficher le résultat.
print("Le factoriel est ", factoriel(n))