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)'.
. . .
x
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)]
. . .
x
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)]
. . .
x
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]]
. . .
x
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 [ ]:
. . .