Algorithme de calcul du PPCM de deux entiers

Bac SC 23-09-26

0 0

Plan de tutoriel

1- Principe de l'algorithme

2- Algorithme de calcul du PPCM

3- Programme Python

Principe de l'algorithme

Le PPCM (Plus Petit Commun Multiple) de deux entiers positifs a et b est le plus petit entier positif qui est un multiple de a et de b.

Dans cet algorithme, on commence par saisir les deux entiers a et b. La fonction saisie() vérifie que chaque valeur entrée est positive avant de la retourner au programme principal.

La fonction ppcm(a, b) détermine d'abord le plus grand et le plus petit des deux nombres. Le plus grand nombre est utilisé comme valeur initiale pour rechercher un multiple commun.

Ensuite, l'algorithme utilise une boucle Tant que. Tant que le nombre courant n'est pas divisible par le plus petit nombre, sa valeur est augmentée afin de rechercher le prochain multiple commun.

Lorsque la condition de divisibilité est satisfaite, la boucle s'arrête. La valeur obtenue correspond au PPCM de a et b, qui est ensuite affiché par le programme principal.

Algorithme de calcul de PPCM

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 … ».

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
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.

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
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.

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

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

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