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

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

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

Comparaison expérimentale

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
 

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

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

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

Petites améliorations sur les bornes

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

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 [ ]: