PGCD de deux entiers

Bonsoir à toutes et à tous,

J'ai pour travail de calculer le PGCD de deux nombres entiers à partir de la décomposition de deux entiers.
Je vous mets le code que j'ai fait ci-dessous :
Code:

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 def decompose(n): T = [] while n != 1: i = 2 while n%i != 0: i = i+1 if n%i ==0 and premier(i) == True: T = T + [i] n = n//i return T def PGCD(n,m): T = decompose(m) T1 = decompose(n) Tt = [] i = 0 j = 0 if len(T) > len(T1): while i < len(T1) and T[i] != "": if T[i] == T1[j]: Tt = Tt + T[i] else: i = i+1 j = j+1 if len(T) < len(T1): while i < len(T) and T1[i] != "": if T[i] == T1[j]: Tt = Tt + T[i] else: i = i+1 j = j+1 print(Tt)
J'ai réussi à faire la première fonction pour pouvoir décomposer un nombre.

Je vous explique ce que j'essaye de faire :
Je veux appeler cette fonction, afin qu'elle puisse me décomposer dans deux différentes listes les entiers "n" et "m".
Ensuite, je compare les deux listes, si il y a similitude, je concatène la valeur d'une des deux listes à une liste vide.
Et enfin, je renvoie la liste qui me montre le PGCD des deux nombres.

Mais je ne comprends pas ma faute.

Merci d'avance pour vos réponses ! :D

Salut,

Citation:

J'ai réussi à faire la première fonction pour pouvoir décomposer un nombre.

Ben non justement.
Que fait la fonction premier(i) ? On va supposer qu'elle retourne True si i est premier.
Voyons ça avec n = 16
Code:

1 2 3 4 5 6 7 8 9 10 11 12 def decompose(16): T = [] while 16 != 1: i = 2 while 16%2 != 0: i = i+1 # 16 % 2 == 0 donc fin de la boucle if 16%2 ==0 and premier(2) == True: # 2 est premier T = T + [i] # T == [2] n = n//i # Ne sert à rien return T # return [2]
Tu obtiens donc toujours une liste d'un seul diviseur si celui-ci est premier sinon une liste vide.

Donc, réécris cette boucle pour qu'avec n = 16 elle te retourne [2, 4, 8], pour la suite on verra.

Bonjour,

Quelques remarques concernant la fonction decompose:

Quand on a une difficulté de mise au point, on ajoute des "print" aux endroits qu'il faut et on essaie sur un nombre dont on connait le résultat. Cela permet de comprendre et donc de corriger l'algorithme.

Sinon:
- il n'y a pas de raison de repartir à chaque boucle while avec i=2: remonte cette ligne au dessus du while n != 1:.
- quand on a trouvé un diviseur qui marche, il faut essayer plusieurs fois jusqu'à ce qu'il ne marche plus. Le 2ème while est donc while n%i == 0:.
- la ligne if n%i ==0 and premier(i) == True: est complètement inutile, et le test concernant la fonction premier(i) n'a rien à faire ici puisqu'on essaie tous les diviseurs à partir de 2 du plus petit au plus grand: ils sont forcements premiers!
- à chaque diviseur trouvé, on enregistre le résultat dans la liste, et on recalcule le nouveau n, mais il ne faut pas incrémenter ce diviseur tout de suite, mais seulement quand celui-ci ne marche plus. Il faut donc mettre le i+=1 au même niveau d'indentation que le 2ème while.

Cela donnerait quelque chose comme ça:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 def decompose(n): T = [] i = 2 while n != 1: #i = 2 #while n%i != 0: while n%i == 0: #i = i+1 #if n%i ==0 and premier(i) == True: T = T + [i] n = n//i i = i+1 return T
Le résultat est bon, mais l'algorithme utilisé est vraiment rustique. Il suffira peut-être pour ton exercice, mais pour ton info, on pourrait l'améliorer au moins sur les points suivants:
- il faut épuiser dès le départ tous les facteurs 2, puisque 2 est premier, ce qui permettra ensuite de n'essayer que les diviseurs impairs à partir de 3 (on divise ainsi par 2 le nombre d'essais).
- si on n'a pas trouvé de diviseurs inférieurs à racine de n, on n'en trouvera plus après! On peut donc arrêter les essais de division plus tôt.

Bonjour

Citation:

Envoyé par Iloyd

Ensuite, je compare les deux listes, si il y a similitude, je concatène la valeur d'une des deux listes à une liste vide.

Méfie toi du cas [2, 2, 3] vs [2, 2, 2, 7] car la liste devra être [2, 2] (il ne faudra ni en rajouter, ni en oublier)

Citation:

Envoyé par Iloyd

Et enfin, je renvoie la liste qui me montre le PGCD des deux nombres.

Ca te montrera plutôt les diviseurs communs qu'il faudra multiplier les uns aux autres pour avoir le pgcd (reduce() pourra te le faire en une instruction ex reduce(lambda x, y: x*y, (2, 2, 3, 3)) donne 36).

Bonjour !

Je m'excuse, j'ai omis de mettre la fonction premier que j'ai fait, donc forcément ça ne renvoie pas le bon résultat :

Donc ça donnerait cela :

Code:

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
from math import*
 
 
def premier(n):
 
    if n == 0 or n == 1:
        return False
 
    for i in range(2,int(sqrt(n))+1):
        if n%i == 0:
            return False
    return True
 
 
def decompose(n):
    T = []
    i = 2
    while n != 1:
        while n%i == 0:    
            T = T + [i]
            n = n//i
        i = i+1
    return T
 
def PGCD(n,m):
 
    T = decompose(m)
    T1 = decompose(n)
    Tt = []
    i = 0
    j = 0
    if len(T) > len(T1):
 
        while i < len(T1) and T[i] != "":           
            if T[i] == T1[j]:
                Tt = Tt + T[i]
 
            else:
                i = i+1
            j = j+1
 
 
    if len(T) < len(T1):
        while i < len(T) and T1[i] != "":
            if T[i] == T1[j]:
                Tt = Tt + T[i]
            else:
                i = i+1 
        j = j+1
    print(Tt)

J'ai pris en compte vos commentaires et j'ai modifié le premier code afin qu'il puisse être plus lisible (Il était en quelque sorte "rustique" x) ).
Mais vu que je l'ai modifié, la fonction premier ne me sert plus à grand chose .

Citation:
Envoyé par VinsS
Salut,

Ben non justement.
Que fait la fonction premier(i) ? On va supposer qu'elle retourne True si i est premier.
Voyons ça avec n = 16
Code:

1 2 3 4 5 6 7 8 9 10 11 12 def decompose(16): T = [] while 16 != 1: i = 2 while 16%2 != 0: i = i+1 # 16 % 2 == 0 donc fin de la boucle if 16%2 ==0 and premier(2) == True: # 2 est premier T = T + [i] # T == [2] n = n//i # Ne sert à rien return T # return [2]
Tu obtiens donc toujours une liste d'un seul diviseur si celui-ci est premier sinon une liste vide.

Donc, réécris cette boucle pour qu'avec n = 16 elle te retourne [2, 4, 8], pour la suite on verra.
Bonjour, alors je ne pense que que n = 16 me retournera [2,4,8] parce que ce n'est pas le bon résultat.
Pour n = 16 je trouve [2,2,2,2] et ça me semble correct (2*2*2*2 = 2^4 = 16)
Pour n = 90 je trouve [2,3,3,5] (2*3*3*5 = 6*3*5 = 18*5 = 90)

J'ai fait plusieurs tests

Citation:

Envoyé par Sve@r

Bonjour

Méfie toi du cas [2, 2, 3] vs [2, 2, 2, 7] car la liste devra être [2, 2] (il ne faudra ni en rajouter, ni en oublier)

Ca te montrera plutôt les diviseurs communs qu'il faudra multiplier les uns aux autres pour avoir le pgcd (reduce() pourra te le faire en une instruction ex reduce(lambda x, y: x*y, (2, 2, 3, 3)) donne 36).

Bonjour, j'ai bien pris en compte le premier commentaire, mais au niveau du conseil avec l'outil ''reduce()'' le professeur d'algorithmique nous contraint à utiliser la fonction decompose pour pouvoir trouver le PGCD de deux nombres entiers

Hum, quel est l'utilité que decompose(16) te retourne [2, 2, 2, 2] ? Tu es censé en tirer quoi ?

Si decompose(24) --> [2, 3, 4, 6, 8, 12] et decompose(16) --> [2, 4, 8] leur plus grand diviseur commun 8 n'est guère difficile à trouver.
Par contre je ne vois pas en quoi [2, 2, 2, 2] est une réponse utile.

Citation:

Envoyé par VinsS

Hum, quel est l'utilité que decompose(16) te retourne [2, 2, 2, 2] ? Tu es censé en tirer quoi ?

Si decompose(24) --> [2, 3, 4, 6, 8, 12] et decompose(16) --> [2, 4, 8] leur plus grand diviseur commun 8 n'est guère difficile à trouver.
Par contre je ne vois pas en quoi [2, 2, 2, 2] est une réponse utile.

En fait, ça permet de décomposer un entier en facteurs de nombres premiers.
Mais maintenant que tu le dis, je ne vois pas où est - ce que mon professeur veut en venir x) .
Je vais faire le PGCD de plusieurs entiers à la main, et ensuite voir ce que j'obtiens avec la fonction pour pouvoir avancer.

Citation:

Envoyé par Iloyd

Bonjour, j'ai bien pris en compte le premier commentaire, mais au niveau du conseil avec l'outil ''reduce()'' le professeur d'algorithmique nous contraint à utiliser la fonction decompose pour pouvoir trouver le PGCD de deux nombres entiers

Pas de souci. Si c'est imposé alors tu fais comme il te le demande. Et pour toi tu te note "reduce()" dans un coin de ta tête pour le réutiliser quand tu y seras autorisé.

Citation:

Envoyé par VinsS

Si decompose(24) --> [2, 3, 4, 6, 8, 12] et decompose(16) --> [2, 4, 8] leur plus grand diviseur commun 8 n'est guère difficile à trouver.
Par contre je ne vois pas en quoi [2, 2, 2, 2] est une réponse utile.

C'est comme ça qu'on apprend le pgcd au secondaire (en France). On décompose les deux nombres en produit de nombres premiers et le pgcd est la multiplication des nombre premiers communs aux deux affectés du plus petit exposant de chacun
Ainsi 72=2^3*3^2 et 48=2^4*3^1 donc le pgcd sera 2^3*3^1 soit 24. Ce n'est peut-être pas la meilleure des méthodes mais c'en est une et c'est probablement celle qu'a choisie son prof de Python pour lui apprendre à manipuler les listes.
Accessoirement ta fonction "decompose()" telle que tu la montres ne décompose rien, elle liste juste les diviseurs ce qui n'est pas la définition d'une décomposition de nombres.

Bonjour,

Dans le cadre de l'exercice, il est effectivement nécessaire de faire une décomposition en facteurs premiers pour identifier les facteurs communs.

Voilà un petit code qui fait ça:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n1 = 30420 F1 = decompose(n1) print(n1, F1) n2 = 1280 F2 = decompose(n2) print(n2, F2) R = [] for e1 in F1: for i in range(0, len(F2)): if e1==F2[i]: R.append(F2.pop(i)) break print(R)
Ce qui affiche comme résultat:
Code:

1 2 3 30420 [2, 2, 3, 3, 5, 13, 13] 1280 [2, 2, 2, 2, 2, 2, 2, 2, 5] [2, 2, 5]
Ici, [2, 2, 5] est bien la liste des facteurs premiers communs aux 2 nb pris en exemple. Le PGCD sera donc: 2*2*5 = 20. Et on aura bien 30420//20= 1521 et 1280//20=64

On peut le vérifier avec la fonction gcd du module fractions: gcd(30420, 1280)=20.

Voilà d'autres exemples avec des nombres tirés au hasard:
Code:

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 25482 [2, 3, 31, 137] 11517 [3, 11, 349] [3] 47735 [5, 9547] 99473 [11, 9043] [] 64237 [64237] 71575 [5, 5, 7, 409] [] 99636 [2, 2, 3, 19, 19, 23] 84183 [3, 11, 2551] [3] 94206 [2, 3, 7, 2243] 33384 [2, 2, 2, 3, 13, 107] [2, 3] 62231 [13, 4787] 59308 [2, 2, 14827] [] 35382 [2, 3, 5897] 49992 [2, 2, 2, 3, 2083] [2, 3] 48644 [2, 2, 12161] 87706 [2, 43853] [2] 56426 [2, 89, 317] 90202 [2, 7, 17, 379] [2] 64057 [7, 9151] 35254 [2, 17627] [] 13053 [3, 19, 229] 39509 [39509] [] 37238 [2, 43, 433] 25726 [2, 19, 677] [2]
Il reste que cette méthode, qui permet de bien comprendre ce qu'est la PGCD, n'est pas efficace: on lui préfère l'algorithme d'Euclide qui est plus simple et plus rapide!

Citation:
Envoyé par tyrtamos
Ce qui affiche comme résultat:
Code:

1 2 3 30420 [2, 2, 3, 3, 5, 13, 13] 1280 [2, 2, 2, 2, 2, 2, 2, 2, 5] [2, 2, 5]
Pas mal de "popper" la liste des diviseurs. Ca permet d'éliminer les nombres utilisés au fur et à mesure et gère facilement le souci [2, 2, 3] vs [2, 2, 2, 7] :applo:
Mon idée initiale était de partir sur set() qui permet de trouver facilement les éléments communs mais je me suis vite heurté au souci de la redondance des diviseurs...

Oh je vois, je ne connaissais pas l'outil "append()", ça facilite tellement la chose x).
Je vais chercher ce que signifie l'outil "pop()" parce que je vois pas du tout son utilité.
Je vais prendre vos remarques en compte. De mon côté, je vais re - faire le code, et vous l'envoyez pour pouvoir voir si ma structure et bonne ou non.

Et en effet, je préfère aussi la méthode d'Euclide qui est plus simple et plus compréhensible à faire !

Merci beaucoup ! :D

Citation:

Envoyé par Iloyd

Oh je vois, je ne connaissais pas l'outil "append()"

Euh... C'est une des bases des tableaux tout de même. Parce que sans ça, impossible de rajouter une valeur dans ton tableau !!! On ne peut pas voir les tableaux sans voir aussi append() quoi...

Citation:

Envoyé par Iloyd

Je vais chercher ce que signifie l'outil "pop()" parce que je vois pas du tout son utilité.

Ca a un double effet: 1) ça te renvoie la valeur du tableau (par défaut la dernière) et 2) ça supprime cette valeur du tableau => comme je le disais, ça permet de supprimer du tableau les valeurs traitées.

on trouve sur le net une méthode qui semble beaucoup plus simple (mais qui utilise une fonction récursive) :

Code:

1
2
3
4
5
6
7
8
9
10
def pgcd(a,b):
    """pgcd(a,b): calcul du 'Plus Grand Commun Diviseur' entre les 2 nombres entiers a et b"""
    if b==0:
        return (a)
    else:
        r=a%b
        return (pgcd(b,r))
 
# Exemple d'utilisation:
print (pgcd(156,1242)) # =>  affiche 6

ou encore plus concise, et non récursive

Code:

1
2
3
4
5
6
7
def pgcd(a,b):
    """pgcd(a,b): calcul du 'Plus Grand Commun Diviseur' entre les 2 nombres entiers a et b"""
    while b!=0:
        a,b=b,a%b
    return (a)
 
print (pgcd (50, 375)) # affiche 25

Citation:

Envoyé par Dguillau

on trouve sur le net une méthode qui semble beaucoup plus simple (mais qui utilise une fonction récursive) :

Oui, c'est l'algorithme d'Euclide (2300 BC!) mais on veut ici coder une méthode différente.

- W