Le PGCD (plus grand commun diviseur) de deux nombres entiers, différents de 0, est le plus grand nombre entier qui les divise tous les deux. Par exemple, le PGCD de 1028 et de 160 est 32, puisque leurs diviseurs communs sont 1, 2, 4, 9, 16 et 32. La notion de PGDC permet de simplifier les calculs de factions (a/b) en divisant a et b par leur PGCD.

La fonction math.gcd ( ), de la bibliothèque standard de Python, retourne le PGCD des 2 int ( ) passés en arguments, mais cette facilité n'est pas disponible avec tous les langages de programmation. Pourrez-vous trouver un algorithme qui sera capable de suppléer à cette absence ?

Il existe plusieurs méthodes pour calculer le PGCD de 2 nombres, dans cette présentation, nous utiliserons la méthode dite des soustractions successives. Cette méthode consiste à : 

- soustraire le plus petit des deux nombres du plus grand nombre

- on remplace la valeur du plus grand des deux nombres par le résultat

. on recommence tant que les deux nombres ne sont pas égaux.

- quand les 2 nombres sont égaux, il s'agit du PGCD recherché.

Par exemple avec les nombres entiers 782 et 221 on obtient : 782 - 221 = 561, 

on remplace donc 782 par 561 --> 561 - 221 = 340

on remplace donc 561 par 340 --> 340 - 221 = 119

on remplace donc 340 par 119 --> 221 - 119 = 102

on remplace donc 782 par 561 --> 119 - 102 = 17

on remplace donc 119 par 17 --> 102 - 17 = 85 

on remplace donc 102 par 85 -->  85 - 17 = 68

on remplace donc 85 par 68 --> 68 - 17 = 51 

on remplace donc 68 par 51 --> 51 - 17 = 34

on remplace donc 51 par 34 --> 34 - 17 = 17 

on remplace donc 34 par 17 --> 17 - 17 = 0 

donc 17 est le PGDC de 782 et 221.

Le programme doit :

1. demander à l'utilisateur de saisir 2 nombres entiers ;

2. vérifier la validités des saisies (nombres entiers non nul) ;

3. calculer le PGCD ;

4. afficher les 2 nombres saisies et leur PGCD ;

5. recommencer ou sortir du programme selon le choix de l'utilisateur.

D'abord, faite-le fonctionner. Ensuite, faite-le beau. Enfin, faite-le performant.

Amusez-vous bien !

Télécharger RETROGICIEL - PGCD par soustractions.

Cette présentation nécessite que Python 3 soit installé sur votre machine.

Après avoir téléchargé le fichier Pgcd par soustractions.7z, décompressez-le dans le répertoire de votre choix.

Ouvrez le répertoire qui vient d'être créé.

Lancez le fichier Retrogiciel.py.

Cliquez sur l'onglet RUN et testez le programme.

Créez votre propre script dans un des langages proposés ou un autre de votre choix.

Le répertoire contient aussi : 

- Python.py, l'exemple en PYTHON sans tkinter ;

- Tkinter.py, l'exemple en PYTHON avec tkinter ;

- Qb84.bas, l'exemple en QBASIC avec qb64 ;

- Bbc.bas, l'exemple en BBC BASIC avec bbc sdl.

# --- Origine Nerd ---

# --- RETROGICIEL - PYTHON ---

# --- PGCD par soustractions ---

# -*- coding: utf-8 -*-

# --- PRESENTATION ---

print ( "CALCULER LE PGCD DE DEUX NOMBRES ENTIERS" )

print ( "PAR LA METHODE DES SOUSTRACTIONS SUCCESSIVES." )

# --- BOUCLE PRINCIPALE ---

while True :

# --- Saisies et controles des 2 nombres entiers ---

kpremier = input ( "\nEntrez le premier nombre entier ... " )

ksecond = input ( "Entrez le second nombre entier ... " )

kvalide = True

# --- Controle de la validité des nombres ---

try :

kpremier = int ( kpremier )

ksecond = int ( ksecond )

except :

print ( "\nERREUR DE SAISIES.\nVeuillez saisir 2 nombres entiers.\n" )

kvalide = False

# --- Recheche et affichage du PGCD ---

if kvalide :

print ( f"le PGCD de { kpremier } et { ksecond } est" , end = " " )

while True :

if ksecond > kpremier : kpremier , ksecond = ksecond , kpremier 

kdifference = kpremier - ksecond

kpremier = kdifference

if kpremier == ksecond : break

print ( f"{ kpremier }.\n" )

# --- Choix du bouclage du programme ---

kchoix = input ( "Voulez-vous calculer un autre PGCD (O ou N) ? " )

if kchoix.upper ( ) == "N" : break

# --- FIN DU PROGRAMME ---

print ( "Au revoir" )

# --- Programme : JFB ---

# --- Juin 2024 ---

# --- Fin ---

Pour mieux comprendre l'exemple en PYTHON sans tkinter.

# --- Origine Nerd ---

# --- RETROGICIEL - TKINTER ---

# --- PGCD par soustractions ---

# -*- coding: utf-8 -*-

# --- IMPORTATION DES MODULES ---

# --- Modules de la bibliothèque standard ---

import tkinter

# --- DÉFINITION DES FONCTIONS PERSONNALISEES ---

# --- Calcul du PGCD des deux termes saisis ---

def FNC_Calculer ( ) :

# --- Convertion et compatibilité des saisies ---

LAB_Pgcd [ "text" ] = ""

try :

kpremier = int ( ENT_Premier.get ( ) )

ksecond = int ( ENT_Second.get ( ) )

except :

LAB_Pgcd [ "text" ] = "ERREUR DE SAISIES.\nVeuillez saisir 2 nombres entiers."

return

# --- Recheche du PGDC ---

while True :

if ksecond > kpremier : kpremier , ksecond = ksecond , kpremier 

kdifference = kpremier - ksecond

kpremier = kdifference

if kpremier == ksecond : break

# --- affichage du PGCD ---

LAB_Pgcd [ "text" ] = f"Le PGCD de { ENT_Premier.get ( ) } et { ENT_Second.get ( ) } \nest : { kpremier }."    

# --- CREATION DE L'INTERFACE GRAPHIQUE ---

# --- Création de la fenêtre principale ---

TKI_Principal = tkinter.Tk ( )

TKI_Principal.title ( "RETROGICIEL - pgcd par divisions" )

# --- Création des controles nommées ---

ENT_Premier = tkinter.Entry ( TKI_Principal , width = 7 )

ENT_Second = tkinter.Entry ( TKI_Principal , width = 7 )

LAB_Pgcd = tkinter.Label ( TKI_Principal , fg = "blue" , font = ( None , 10 , "bold" ) , height = 3 )

# --- Mise en place des controles (anonymes et nommés) dans la fenêtre principale ---

tkinter.Label ( TKI_Principal , text = "CALCULER LE PGCD DE 2 NOMBRES." ).grid ( row = 0 , column = 0 , columnspan = 2 , sticky = "nesw" )

tkinter.Label ( TKI_Principal , text = "Premier nombre :" , justify = "right" ).grid ( row = 1 , column = 0 , sticky = "e" )

ENT_Premier.grid ( row = 1 , column = 1 , sticky = "w" )

tkinter.Label ( TKI_Principal , text = "Second nombre :" , justify = "right" ).grid ( row = 2 , column = 0 , sticky = "e" )

ENT_Second.grid ( row = 2 , column = 1 , sticky = "w" )

tkinter.Button ( TKI_Principal , text = "Calculer le PGDC." , command = FNC_Calculer ).grid ( row = 3 , column = 0 , columnspan = 2 , sticky = "nesw" )

LAB_Pgcd.grid ( row = 4 , column = 0 , columnspan = 2 , sticky = "nesw" )

tkinter.Button ( TKI_Principal , text = "Quitter" , command = TKI_Principal.destroy ).grid ( row = 5 , column = 0 , columnspan = 2 , sticky = "nesw" )

# --- DEBUT DU PROGRAMME ---

TKI_Principal.mainloop ( )

# --- Programme : JFB ---

# --- Juin 2024 ---

# --- Fin ---

Pour mieux comprendre l'exemple en PYTHON avec tkinter.

' --- Origine Nerd propose pour ---

' --- RETROGICIEL - QB64 ---

' --- PGCD par soustractions ---

' --- DEBUT DU PROGRAMME ---

PRINT "CALCULER LE PGCD DE DEUX NOMBRES ENTIERS"

PRINT "PAR LA METHODE DES SOUSTRACTIONS SUCCESSIVES."

' --- BOUCLE PRINCIPALE ---

DO

' --- Saisie des deux nombres entiers ---

INPUT "Entrez le premier nombre entier ", kpremier&

INPUT "Entrez le second nombre entier ", ksecond&

PRINT "Le PGCD de "; kpremie&; " et "; ksecond&; " est ";

' --- Calcul du pgcd ---

DO

IF kpremier& < ksecond& THEN SWAP kpremier& , ksecond&

kdifference& = kpremier& - ksecond&

kpremier& = ksecond&

ksecond& = kdifference&

LOOP UNTIL kdifference& = 0

' --- Affichage du pgcd, si existe, des deux nombres saisis ---

PRINT kpremier&

' --- Bouclage du programme ---

PRINT

INPUT "Voulez-vous recommencer [ O ou N ] "; kchoix$

LOOP UNTIL UCASE$(kchoix$) = "N"

' --- FIN DU PROGRAMME ---

PRINT "Au revoir."

END

' --- Programme : JFB ---

' --- Juin 2024 ---

' --- Fin ---

Pour mieux comprendre l'exemple en QB64.

REM --- Origine Nerd propose pour ---

REM --- RETROGICIEL - BBC BASIC ---

REM --- PGCD par soustractions ---

REM --- DEBUT DU PROGRAMME ---

PRINT "CALCULER LE PGCD DE DEUX NOMBRES ENTIERS"

PRINT "PAR LA METHODE DES SOUSTRACTIONS SUCCESSIVES."

REM --- BOUCLE PRINCIPALE ---

REPEAT

REM --- Saisie des deux nomvres par l'utilisateur ---

INPUT "Entrez le premier nombre entier ", kpremier

INPUT "Entrez le second nombre entier ", ksecond

PRINT "Le PGCD de "; kpremier; " et "; ksecond; " est ";

REM --- Calcul du pgcd ---

REPEAT

IF kpremier < ksecond THEN SWAP kpremier , ksecond

kdifference = kpremier - ksecond

kpremier = ksecond

ksecond = kdifference

UNTIL kdifference = 0

REM --- Affichage du pgcd ---

PRINT STR$(kpremier)

REM --- Bouclage du programme ---

PRINT

INPUT "Voulez-vous recommencer [ O ou N ] "; kchoix$

UNTIL kchoix$ = "N" OR kchoix$ = "n"

REM --- FIN DU PROGRAMME ---

PRINT "Au revoir."

END

REM --- Programme : JFB ---

REM --- Juin 2024 ---

REM --- Fin ---

Pour mieux comprendre l'exemple en BBC BASIC.