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
Recherche des triangles entiers de Pythagore de périmètre donné
In [2]:
def triangle_rect_de_perimetre3(p):
L=[] # L : liste vide
for a in range(1,p+1):
for b in range(1,p+1):
for c in range(1,p+1):
if a+b+c==p and a**2+b**2==c**2 :
L.append((a,b,c))
return L
. . .
In [3]:
triangle_rect_de_perimetre3(40)
Out[3]:
[(8, 15, 17), (15, 8, 17)]
. . .
x
Petite amélioration de la complexité
In [4]:
def triangle_rect_de_perimetre2(p):
L=[] # L : liste vide
for a in range(1,p+1):
for b in range(1,p+1):
c=p-a-b
if a**2+b**2==c**2 :
L.append((a,b,c))
return L
. . .
In [5]:
triangle_rect_de_perimetre2(40)
Out[5]:
[(8, 15, 17), (15, 8, 17)]
. . .
x
Comparaison expérimentale
x
Fonction temps
In [6]:
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
. . .
x
Affichage simultané des deux courbes du temps
In [7]:
X=range(50,500,50)
Y3=temps(triangle_rect_de_perimetre3,X)
Y2=temps(triangle_rect_de_perimetre2,X)
axis([min(X),max(X),-0.05*(max(Y3)-min(Y3)),max(Y3)])# paramètres d'ouverture pour fenêtre graphique
plot(X,Y3,'r--') # rouge tireté
plot(X,Y2,'b*')# bleu étoilé
show()
. . .
x
Temps pour triangle_rect_de_perimetre2 : fonction du second degré en n
In [*]:
XX=range(10,3000,200)
YY2=temps(triangle_rect_de_perimetre2,XX)
p=polyfit(XX,YY2,2) # approche de la courbe par une fonction du second degré
YY=[p[0]*x**2+p[1]*x+p[2] for x in XX]
plot(XX,YY2,'b*',XX,YY,'r')
show()
. . .
x
Temps pour triangle_rect_de_perimetre3 : fonction de degré 3 en n
In [9]:
XX=range(10,700,50)
YY3=temps(triangle_rect_de_perimetre3,XX)
p=polyfit(XX,YY3,3) # approche de la courbe par une fonction degré 3
YY=[p[0]*x**3+p[1]*x**2+p[2]*x+p[3] for x in XX]
plot(XX,YY3,'b*',XX,YY,'r')
show()
. . .
In [10]:
YY2=temps(triangle_rect_de_perimetre3,XX)
p=polyfit(XX,YY2,2) # approche de la courbe par une fonction du second degré
YY=[p[0]*x**2+p[1]*x+p[2] for x in XX]
plot(XX,YY2,'b*',XX,YY,'r')
show()
. . .
x
Petites améliorations sur les bornes
x
Textes des programmes
In [11]:
def trp1(p):
L=[]
for a in range(1,p/3+1):
for b in range(a,p/2+1):
c=p-a-b
if a**2+b**2==c**2:L.append((a,b,c))
return L
. . .
In [12]:
def trp2(p):
L=[]
for a in range(1,p/3+1):
for b in range(a,p-a):
c=p-a-b
if a**2+b**2==c**2:L.append((a,b,c))
return L
. . .
x
Comparaison expérimentale des temps
In [15]:
X=range(50,5000,150)
Ytrp1=temps(trp1,X)
Ytrp2=temps(trp2,X)
plot(X,Ytrp1,'r--') # rouge tireté
plot(X,Ytrp2,'b*')# bleu étoilé
show()
. . .
In [ ]:
. . .