IPython Notebook

 Le facteur Last saved: Oct 29 10:47 AM
In [1]:
 
%pylab inline
Welcome to pylab, a matplotlib-based Python environment [backend: module://IPython.zmq.pylab.backend_inline].
For more information, type 'help(pylab)'.

Les produits, version brute non ordonnée

In [2]:
 
def TriFacteur(n):
    L=[]
    for a in range(n+1):
        for b in range(n+1):
            for c in range(n+1):
                if a*b*c==n:
                    L.append((a,b,c))
    return L
In [3]:
 
TriFacteur(36)
Out[3]:
[(1, 1, 36),
 (1, 2, 18),
 (1, 3, 12),
 (1, 4, 9),
 (1, 6, 6),
 (1, 9, 4),
 (1, 12, 3),
 (1, 18, 2),
 (1, 36, 1),
 (2, 1, 18),
 (2, 2, 9),
 (2, 3, 6),
 (2, 6, 3),
 (2, 9, 2),
 (2, 18, 1),
 (3, 1, 12),
 (3, 2, 6),
 (3, 3, 4),
 (3, 4, 3),
 (3, 6, 2),
 (3, 12, 1),
 (4, 1, 9),
 (4, 3, 3),
 (4, 9, 1),
 (6, 1, 6),
 (6, 2, 3),
 (6, 3, 2),
 (6, 6, 1),
 (9, 1, 4),
 (9, 2, 2),
 (9, 4, 1),
 (12, 1, 3),
 (12, 3, 1),
 (18, 1, 2),
 (18, 2, 1),
 (36, 1, 1)]

Les produits, version brute ordonnée

In [4]:
 
def TriFacteur2(n):
    L=[]
    for a in range(n+1):
        for b in range(a,n+1):
            for c in range(b,n+1):
                if a*b*c==n:
                    L.append((a,b,c))
    return L
In [5]:
 
TriFacteur2(36)
Out[5]:
[(1, 1, 36),
 (1, 2, 18),
 (1, 3, 12),
 (1, 4, 9),
 (1, 6, 6),
 (2, 2, 9),
 (2, 3, 6),
 (3, 3, 4)]

La clef de la résolution : (1,6,6) et (2,2,9) ont même somme.

In [7]:
 
[[x,sum(x)] for x in TriFacteur2(36)]
Out[7]:
[[(1, 1, 36), 38],
 [(1, 2, 18), 21],
 [(1, 3, 12), 16],
 [(1, 4, 9), 14],
 [(1, 6, 6), 13],
 [(2, 2, 9), 13],
 [(2, 3, 6), 11],
 [(3, 3, 4), 10]]

Amélioration du temps

In [8]:
 
def TriFacteur3(n):
    L=[]
    A=int(n**(1.0/3.0))
    B=int(n**0.5)
    for a in range(1,A+1):
        for b in range(a,B+1):
            if n%(a*b)==0:
                c=n//(a*b)
                if c>=b:
                    L.append((a,b,c))
    return L
In [9]:
 
import time
def temps(f,L):
    tps=[]# contiendra une liste de temps de calcul
    for j in L:
        start = time.time()
        f(j)
        dureeCalcul=time.time() - start # dureeCalcul=temps de calcul de f(j)
        tps.append(dureeCalcul)
    return tps
In [24]:
 
X=range(50,500,50) 
 
Y2=temps(TriFacteur2,X) 
Y3=temps(TriFacteur3,X) 
axis([min(X),max(X), -0.2,max(Y2)])
plot(X,Y2,'r--') #   rouge tireté
plot(X,Y3,'b*')#   bleu étoilé
show()
In [28]:
 
X=range(10,20**5,10**4) 
 
  
Y3=temps(TriFacteur3,X) 
axis([min(X),max(X), -0.2,max(Y2)])
 
plot(X,Y3,'b*')#   bleu étoilé
show()
In [ ]: