Objectif

Réaliser un programme permettant de calculer le Plus Grand Commun Diviseur en utilisant l'algorithme d'Euclide avec l'IDE Thonny.

Pour comprendre Euclide, liens vers une vidéo décrivant son fonctionnement: https://youtu.be/EVQY8DG5_es

Un exemple:

>>> %Run pgcd1.py
Saisir le premier nombre entier: 5120
Saisir le second nombre entier: 785
Le PGCD entre  5120  et  785 est donc  5
Les diviseurs de  5120  sont  [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5]
Les diviseurs de  785  sont  [1, 5, 157]

Procédure

Etape 1 - Algorigrammer

Réaliser un schéma logique de votre programme. Pour vous aidez:

• document vous présentant les symboles dans un algorigramme
  https://ipa-troulet.fr/cours/attachments/article/466/cours_algorithmique_algorigramme.pdf
• OpenOffice Draw et sa barre d'outils Dessin vous propose les formes ad hoc et les connecteurs qui vont bien

Mon schéma logique ressemble à cela:

#saisie des paramètres grand nbre et petit nombre
gdnbre= 525
ptnbre=390

#
#Rappel:
# dividende  |  diviseur 
#            |-----------
#            |  quotient
#    reste   |
#
#initialisation des listes
compteur i=0
quotient
reste
diviseur
dividende
#

#boucle de calcul - tant que le reste diff de 0
calcul du quotient => // division entière
ajouter le quotient calculé dans la liste quotient
calcul du reste => % modulo
ajouter le reste calculé dans la liste reste

affectation des nouvelles valeurs pour la division suivante:
le dernier diviseur devient le prochain dividende
le dernier reste devient le prochain diviseur

#Afficher 
PGCD = le dernier des dividendes

Etape 2 - Scripter

L'idée est de réaliser ici un premier jet. Priorité aux boucles et aux variables. Vous noterez l'usage des listes sous python. Pour vous aider voir ici: https://www.courspython.com/introduction-python.html#quelques-bases-rapides-en-python

# PGCD
#saisie des nbres
gnbre=525
pnbre=390

# declaration des listes pour garder une trace
dividende=[]
diviseur=[]
quotient=[]
reste=[]


# initialisation
i=0
r=1
dividende.append(gnbre)
diviseur.append(pnbre)


# boucle
while r!=0:
    q=dividende[i]//diviseur[i]
    r=dividende[i]%diviseur[i]

    quotient.append(q)
    reste.append(r)

    dividende.append(diviseur[i])
    diviseur.append(r)
    i=i+1



# Affichage
print("Le PGCD entre est donc ",dividende[-1])

Etape 3 - Améliorer et commenter

Tout est perfectible, pour ici je dirais:

• Améliorer les impressions et les commentaires
• Faire en sorte que le gnbre soit vraiment le gnbre
• Permettre le choix des 2 nombres (Input)

# PGCD
# Version 2

#saisie des 2 nbres
a=int(input("Saisir le premier nombre entier: "))
b=int(input("Saisir le second nombre entier: "))


# classement et definition de gnbre et pnbre
if a<b:
    gnbre=b
    pnbre=a
else:
    gnbre=a
    pnbre=b

# declaration des listes pour garder une trace
dividende=[]
diviseur=[]
quotient=[]
reste=[]


# initialisation
i=0
r=1
dividende.append(gnbre)
diviseur.append(pnbre)


# boucle
while r!=0:
    q=dividende[i]//diviseur[i]
    r=dividende[i]%diviseur[i]

    quotient.append(q)
    reste.append(r)

    dividende.append(diviseur[i])
    diviseur.append(r)
    i=i+1



# Affichage
print("Le PGCD entre ",a," et ",b, "est donc ",dividende[-1])

Etape 4 - Affichage complémentaire

Pour mieux comprendre le PGCD, afficher aussi la liste des diviseurs de a et de b.

Prenez par exemple a= 4 277 700 et b=52 500 (ne pas saisir les espaces!)

# PGCD
# Version 3

#saisie des 2 nbres
a=int(input("Saisir le premier nombre entier: "))
b=int(input("Saisir le second nombre entier: "))


# classement et definition de gnbre et pnbre
if a<b:
    gnbre=b
    pnbre=a
else:
    gnbre=a
    pnbre=b

# declaration des listes pour garder une trace
dividende=[]
diviseur=[]
quotient=[]
reste=[]


# initialisation
i=0
r=1
dividende.append(gnbre)
diviseur.append(pnbre)


# boucle
while r!=0:
    q=dividende[i]//diviseur[i]
    r=dividende[i]%diviseur[i]

    quotient.append(q)
    reste.append(r)

    dividende.append(diviseur[i])
    diviseur.append(r)
    i=i+1



# Affichage
print("Le PGCD entre ",a," et ",b, "est donc ",dividende[-1])



# Pour  vérif, affichage des diviseurs de a et de b
i=2
aini=a
diviseura=[1]

while i<=a:
    if a%i ==0:
        diviseura.append(i)
        a=a/i
    else:
        i=i+1
print("Les diviseurs de ",aini," sont ",diviseura)





i=2
bini=b
diviseurb=[1]

while i<=b:
    if b%i ==0:
        diviseurb.append(i)
        b=b/i
    else:
        i=i+1
print("Les diviseurs de ",bini," sont ",diviseurb)