Discussion :

[djahn]

Voilà, qqu'un pourrait-il m'aider, merci :
#!usr/bin/env python

'''Décomposition d'un nombre'''

n=int(input('Donner un nombre : '))
dep=n
p2=0
p3=0
p5=0
p7=0
while(n%2==0):
n=n/2
p2 +=1
n2=n

while(n2%3==0):
n2=n2/3
p3 +=1
n3=n2

while(n3%5==0):
n3=n3/5
p5 +=1
n5=n3

while(n5%7==0):
n5=n5/7
p7 +=1
n7=n5

print(dep, '=',p2,'*',n2,' +',p3,'*',n3,' +', p5,'*',n5,' +',p7,'*',n7)

[Sve@r]

Voilà, qqu'un pourrait-il m'aider, merci :

Oui, bonjour à toi aussi

#!usr/bin/env python

Même pas fichu de connaitre son arborescence Unix

Code python :

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

#!/usr/bin/env python

'''Décomposition d'un nombre'''

n=int(input('Donner un nombre : '))
dep=n
p2=0
p3=0
p5=0
p7=0
while(n%2==0):
n=n/2
p2 +=1
n2=n

while(n2%3==0):
n2=n2/3
p3 +=1
n3=n2

while(n3%5==0):
n3=n3/5
p5 +=1
n5=n3

while(n5%7==0):
n5=n5/7
p7 +=1
n7=n5

print(dep, '=',p2,'*',n2,' +',p3,'*',n3,' +', p5,'*',n5,' +',p7,'*',n7)

Mouais Déjà

Ensuite ben tu cherches à décomposer un nombre en facteurs premiers si je ne me trompe pas (parce que si je devais compter avec tes explications pour comprendre...). As-tu d'abord réfléchi à un algorithme ??? N'as-tu pas réalisé qu'il suffit d'instancier une boucle de i variant de 2 à n et regarder si i divise n (on s'en fout que i soit premier ou pas parce que s'il n'est pas premier, alors il sera préempté par le premier qui le divise lui-même => explications: si n est divisible par 6 ça veut dire qu'il est divisible par 2 et par 3 donc quand 2 et 3 passeront l'algo, ils rendront n tel qu'ensuite il ne sera plus divisible par 6

Donc algo

Code :

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

1
2
3
4
5
6
7
8
9
10
11
i=2
tant que i <= n
faire
    tant que (n modulo i) == 0
    faire
        ajouter i au tableau des facteurs
        n=n/i
    fin faire
    i=i+1
fin faire
afficher tableau

Ensuite tu peux optimiser un peu. Par exemple si i devient plus grand que n/i alors inutile de continuer. Enfin déjà essaye de faire ça...

[djahn]

Bonjour, d'abord pour ne vexer personne. Etant autodidacte en info mais courageux dans l'effort je poursuis mon aventure de programmation.... D'abord merci pour ta réponse même un peu sèche Sev@r.
1.Je veux bien que l'on m'indique quelques sites sur l'algorithmique (Intéressant! Pour ne pas perdre mon temps ou un livre), merci d'avance .
2. voilà, j'ai corrigé et la décomposition MERCI ça marche bien ( surement à améliorer!)
3. Après pour ma façon de chercher le pgcd, on n'obtient pas le pgcd car il s'arrête avant le dernier i et j, je ne vois pas comment corriger?


#!/usr/bin/env python

'''Décomposition d'un nombre, PGCD et PPCM'''
# Décomposition des 2 nombres
n1=int(input('Donner un nombre : '))
n2=int(input('Donner un autre nombre : '))
decomp1 = []
decomp2=[]

i=2
while(i<=n1 ):
while(n1%i==0):
decomp1.append(i)
n1=n1/i
i=i+1
j=2
while(j<=n2 ):
while(n2%j==0):
decomp2.append(j)
n2=n2/j
j=j+1
print(decomp1)
print(decomp2)

#PGCD
# En prenant un i dans la + grande liste d'abord, je parcours la + petite
pgcd=1
i=0
j=0
if (len(decomp1)<len(decomp2)):#decomp1 est plus grand que decomp2
decomp1,decomp2=decomp2,decomp1
len1=len(decomp1)
len2=len(decomp2)
print(len1,len2)
while(i<len1):
while( j < len2):
if(decomp1[i]==decomp2[j]):
pgcd *=decomp1[i]
j=j+1
i =i +1
print('PGCD =',pgcd)

[tyrtamos]

Bonjour,

C'est trop pénible d'éplucher ton code sans indentation: reprend ton message précédent, et entoure le code Python avec les tags de code: le '#' en haut et à gauche de la fenêtre d'édition.

A part ça, le pgcd existe déjà dans le système Python: fonction 'gcd' du module 'fractions'. Tu peux examiner ce module écris en python comme source d'inspiration.

[djahn]

Bonsoir merci pour l'info et voilà un peu plus de lisibilité (sauf pour les couleurs du code , comme tout était rouge alors j'ai mis tout noir, désolé,) :
C'est de la ligne 37 à 42 que...je n'ai pas le compte, il s'arrête un pas avant.
Bien sûr je vais regarder ce que fait le module fraction pour voir, merci.

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

#!/usr/bin/env python

'''Décomposition d'un nombre, PGCD et PPCM'''
# Décomposition des 2 nombres
n1=int(input('Donner un nombre : '))
n2=int(input('Donner un autre nombre : '))
decomp1 = []
decomp2=[]
       
i=2
while(i<=n1 ):
     while(n1%i==0):
          decomp1.append(i)
          n1=n1/i
     i=i+1
j=2
while(j<=n2 ):
     while(n2%j==0):
          decomp2.append(j)
          n2=n2/j
     j=j+1
print(decomp1)     
print(decomp2)

#PGCD
# En prenant un i dans la + grande liste puis on parcours la + petite, on ré-itère
pgcd=1
i=0
j=0
#decomp1 sera plus grand que decomp2
if (len(decomp1)<len(decomp2)):
      decomp1,decomp2=decomp2,decomp1
len1=len(decomp1)
len2=len(decomp2)
print(len1,len2)
while(i<len1):
     while( j < len2):
          if(decomp1[i]==decomp2[j]):
                    pgcd *=decomp1[i]
          j=j+1
     i =i +1 
print('PGCD =',pgcd)
    

[tyrtamos]

Bonjour,

Bon. Passer par une décomposition en facteurs premier pour calculer le PGCD n'est pas très efficace depuis qu'on connait l'algorithme d'Euclide, c'est à dire depuis environ 2300 ans...

Mais ça a au moins le mérite de coller à la définition! J'ai corrigé un peu ton code pour exploiter un peu mieux ce que Python sait faire:

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
n1 = 56
n2 = 84
 
# décomposition de n1 en facteurs premiers
decomp1 = []
i=2
n = n1
while i*i<=n1:
    if n%i==0:
        decomp1.append(i)
        n = n//i
    else:
        i += 1
print "n1 =", n1,  " decomposition de n1:", (decomp1)
 
# décomposition de n2 en facteurs premiers
decomp2 = []
i=2
n = n2
while i*i<=n2 :
    if n%i==0:
        decomp2.append(i)
        n=n//i
    else:
        i += 1
print "n2 =", n2,  " decomposition de n2:", (decomp2)
 
# calcul du PGCD de n1 et n2
fcom = [] # liste des facteurs communs à trouver
for i in decomp1:
    if i in decomp2 and i not in fcom:
        # ici: i est un facteur commun entre decomp1 et decomp2, et n'a pas encore été traité
        c1 = decomp1.count(i) # nb de fois où le facteur i apparait dans decomp1
        c2 = decomp2.count(i) # nb de fois où le facteur i apparait dans decomp2
        fcom += [i]*min(c1,c2) # on ajoute le facteur i, autant de fois qu'il faut
# multiplier tous les facteurs communs pour trouver le PGCD
pgcd = 1
for i in fcom:
    pgcd *= i
print "PGCD =", pgcd, " <=>", fcom

NB: dans la décompositions de n en facteurs premiers, il n'est pas nécessaire de dépasser racine de n: d'où la condition while i*i<=n.

Appliqué à n1=56 et n2=84, cela donne:

n1 = 56 decomposition de n1: [2, 2, 2, 7]
n2 = 84 decomposition de n2: [2, 2, 3, 7]
PGCD = 28 <=> [2, 2, 7]

Et voilà un code qui calcule le PGCD en utilisant l'algorithme d'Euclide:

Code :

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

1
2
3
4
5
6
n1=56
n2=84
while n2<>0:
    n1, n2 = n2, n1%n2
print "PGCD =", n1
28

Merci Euclide!

[djahn]

Bonjour et merci pour ce rectificatif Tyrtamos, ,
Je commence à jouer avec Python alors faut pas m'en vouloir si je ne suis pas les chemins les plus courts. C'est peut-être volontaire, Merci encore,

[Sve@r]

D'abord merci pour ta réponse même un peu sèche Sev@r.

Oui, c'est effectivement ce qui se passe quand on arrive en commençant par "voilà qqun..."

1.Je veux bien que l'on m'indique quelques sites sur l'algorithmique (Intéressant! Pour ne pas perdre mon temps ou un livre), merci d'avance .

http://algo.developpez.com/livres (le 6°)
http://algo.developpez.com/cours/
Sinon pour le reste Tyrtamos a tout dit.

[wiztricks]

Salut,

Discuter de l'algorithme d'Euclide est un sujet intéressant.

Comme vous débutez, la difficulté est plutôt "pourquoi le Python ne fait pas ce que je souhaite". Et changer d'algo ne vous donnera pas d'indication sur ce qui coince dans la mise en oeuvre de celui que vous avez choisi...

Reprenons, votre calcul de PGCD:

Code :

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

1
2
3
4
5
6
while(i<len1):
     while( j < len2):
          if(decomp1[i]==decomp2[j]):
                    pgcd *=decomp1[i]
          j=j+1
     i =i +1

Lorsque decomp1[i]==decomp2[j] vous avez un facteur "commun", il s'accumule dans le PGCD. le soucis est dans le "else".
L'incrément du "j" aboutit à trouver un decomp2[j] qui ne sera pas ou plus decomp1[i], il faut donc faire avancer "i" et éviter d'avancer "j".

Ré-écrivons cela:

Code :

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

1
2
3
4
5
while  i < len1 and j < len2:
          if(decomp1[i] == decomp2[j]):
                    pgcd  *= decomp1[i]
                    j += 1
     i += 1

Quitte à passer par cet algo, l'idée de Tyrtamos (compter les occurrences de...) est intéressante. On peut pousser un peu en structurant la décomposition non plus comme la liste croissante des diviseurs premiers qui se répète en une liste de (p, r) ou p est le nombre premier et r la répétition.

- W