Discussion :

[Iloyd]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 !

[VinsS]

Salut,

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[tyrtamos]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Sve@r]

Bonjour

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)

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

[Iloyd]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 .

[Iloyd]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Iloyd]

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

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

[Iloyd]

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.

[Sve@r]

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

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.

[tyrtamos]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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!

[Sve@r]

Ce qui affiche comme résultat:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Iloyd]

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 !

[Sve@r]

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

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.

[Dguillau]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[wiztricks]

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