Home > Project Euler, python > Project euler #39

Project euler #39

If p is the perimeter of a right angle triangle  with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.
{20,48,52}, {24,45,51}, {30,40,50}
For which value of p ≤ 1000, is the number of solutions maximised?

Con un approccio BruteForce ERRATO, purtroppo i tempi di esecuzione si rivelano esageratamente alti.
In pratica il primo tentativo voleva ciclare sui possibili valori del perimetro, ciclare sui valori possibili del primo cateto, poi su quelli del secondo cateto, poi calcolare l’ipotenusa e controllare che il perimetro risultante fosse uguale al valore del perimetro del primo ciclo for. Per rallentare il tutto, controllavo
anche che il valore del perimetro fosse intero.
Tempi di esecuzione: 70sec circa.
Oltre ad essere un tempo pazzesco, è anche maggiore del minuto di decenza richiesto da project euler…

Poi mi sono armato di google e mi sono fatto una ricerca…

Analisi:

I criteri di semplificazione sono i seguenti:

Innanzi tutto per non dover ciclare su 3 incognite (p, a e b) dobbiamo cercare di ridurre la ricerca a due sole incognite.
Per fare questo sfruttiamo le due equazioni che conosciamo:

p = a + b + c

e come insegna pitagora:

a**2 + b**2 = c**2

Dalla prima equazione ricaviamo l’ipotenusa (c):

c = p - a - b

e sostituiamo ‘c’ nella seconda equazione:

a**2 + b**2 = (p - a - b)**2
a**2 + b**2 = p**2 + a**2 + b**2 - 2pa – 2pb + 2ab

ricaviamo b:

b = (p**2 -2pa) / (2p-2a)

Con questa formula sappiamo che per tutti i valori di perimetro ‘p’ e di cateto ‘a’, dove ‘b’ è un intero, abbiamo trovato la nostra “tripletta pitagorica”.
Si tratta quindi di controllare che ‘b’ sia un intero.
Basta semplicemente controllare che (p**2 -2pa) / (2p-2a) non dia resto, quindi usiamo il modulo.

Altra semplificazione:

considerando l’equazione

a + b + c = p

1- se ‘a’ e ‘b’ sono pari, allora ‘c’ e quindi ‘p’ lo sono.
2- se ‘a’ o ‘b’ (ma non entrambi) sono dispari, allora ‘c’ è dispari quindi ‘p’ diventa pari.
3- se ‘a’ e ‘b’ sono dispari, allora ‘c’ è pari, quindi ‘p’ è pari

Se ne deduce che cicleremo solo sui valori pari di ‘p’, che di per sè dimezza già i tempi.

Ultima semplificazione:

Considerando

a <= b 

per non avere valori duplicati ({20, 48, 52} e {48, 20, 52}) e

b < c 

dato che l’ipotenusa è il lato più lungo, ne consegue che

a <= b < c

Possiamo quindi semplificare che SICURAMENTE

a <= p/3

Tutto questo, in python, risulta in:

import time
import math

ts = time.time()
maxc = 0
p = 0
for x in xrange(2, 1000, 2): # solo perimetri pari
    count = 0
    for a in range(1, x/3): # a < perimetro/3
        if (x*(x-2*a) % (2*(x-a))) == 0: # controllo che b sia intero
            count += 1 # numero di combinazioni per perimetro = x
        if count > maxc: maxc, p = count, x
print 'Comb max: {} perimeter: {}'.format(maxc, p)
print time.time() - ts

tempi di esecuzione:

Comb max: 9 perimeter: 840
0.088635921478
Categorie:Project Euler, python
  1. Non c'è ancora nessun commento.
  1. No trackbacks yet.

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: