ProjectEuler - Problema 5

30 marzo del 2010

Ecco qua con il mio primo vero post.. e come non poteva riguardare una delle mie ultime passioni.. PYTHON.
Partiamo quindi con il problema 5.. parto dal 5 in quanto i problemi 1-2-3 sono già stati affrontati su stacktrace.it, e il 4 non mi ha dato nulla di "nuovo"..
Ma partiamo dall'enunciato:

2520 è il più piccolo numero che può essere diviso da tutti i numeri da 1 a 10, senza alcun resto.
Qual'è il più piccolo numero che è divisibile allo stesso modo da tutti i numeri da 1 a 20?

Prendendo spunto dall'articolo di Daniele riguardande il Problema3, ho voluto anch'io entrare nello specifico del mio problema.
Come si può subito capire facilmente dall'enunciato, la soluzione si può trovare calcolando il Minimo Comune Multiplo dei numeri che vanno da 1 a 20. Ma come si calcola?

Il Minimo Comune Multiplo(mcm)
Da Wikipedia, l'enciclopedia libera.

In matematica il minimo comune multiplo (mcm) di due interi a e b è il più piccolo intero positivo che è multiplo sia di a che di b.
Se non esiste un intero positivo con queste proprietà, cioè se a = 0 o b = 0, allora mcm(a, b) è definito uguale a zero.

l minimo comune multiplo è uno strumento utile per determinare la somma o sottrazione di due frazioni: in questo caso il denominatore della frazione risultante è il minimo comune multiplo delle due date. Ad esempio, nella somma

${2\over21}+{1\over6}={4\over42}+{7\over42}={11\over42},$

il denominatore è mcm(21, 6) = 42.

Se a e b non sono entrambi nulli, il minimo comune multiplo può essere calcolato usando il massimo comun divisore (MCD) di a e b e la formula seguente:

$\operatorname{mcm}(a,b)=\frac{a\cdot b}{\operatorname{MCD}(a,b)}.$

Quindi, l'algoritmo di Euclide per il MCD fornisce anche un veloce algoritmo per il calcolo del mcm. Ritornando all'esempio precedente,

$\operatorname{mcm}(21,6) ={21\cdot6\over\operatorname{MCD}(21,6)} ={21\cdot 6\over 3}={21\cdot 2}=42.$

Poiché (ab)/c = a(b/c) = (a/c)b, è possibile calcolare il mcm usando la formula precedente in modo più efficiente, dapprima utilizzando il fatto che b/c o a/c sono più semplici da calcolare rispetto al divisione tra il prodotto ab e c: il fatto che c sia multiplo sia di a che di b consente di semplificare completamente il fattore c dalla frazione a/c oppure da b/c, prima di effettuare il prodotto ab.

La formula

$\operatorname{mcm}(a,b)=\frac{a\cdot b}{\operatorname{MCD}(a,b)}$

è adeguata per calcolare il mcm per piccoli numeri.
Allora il mcm si può calcolare o così:

$\operatorname{mcm}(a,b)=\left({a\over\operatorname{MCD}(a,b)}\right)\cdot b$

oppure così:

$\operatorname{mcm}(a,b)=a\cdot\left({b\over\operatorname{MCD}(a,b)}\right).\,$

Ma.. cosa è MCD(Massimo Comune Divisore)??

Il Massimo Comune Divisore(MCD)
Da Wikipedia, l'enciclopedia libera.

In matematica, il massimo comune divisore (M.C.D.) di due numeri interi, che non siano entrambi uguali a zero, è il numero naturale più grande per il quale possono entrambi essere divisi.

Il massimo comun divisore tra i due numeri a e b viene indicato con MCD(a, b), o più semplicemente (a, b). Ad esempio, MCD(12, 18) = 6, MCD(−4, 14) = 2 e MCD(5, 0) = 5.
Due numeri si dicono coprimi o primi tra loro se il loro massimo comun divisore è uguale a 1. Per esempio, i numeri 9 e 28 sono primi tra loro (ma non sono primi).
Il massimo comun divisore è utile per ridurre una frazione ai minimi termini. Per esempio nella seguente frazione:

${42 \over 56}={3 \cdot 14 \over 4 \cdot 14}={3 \over 4}$

è stato semplificato il fattore 14, il massimo comun divisore tra 42 e 56.

Il massimo comune divisore può essere calcolato, in linea di principio, determinando la scomposizione in fattori primi dei due numeri dati e moltiplicando i fattori comuni, considerati una sola volta con il loro minimo esponente. Per esempio, per calcolare il MCD(18,84) si scompongono dapprima i due numeri in fattori primi, ottenendo 18 = 2·3² e 84 = 2²·3·7, e poi si considerano i fattori comuni ai due numeri, 2 e 3: entrambi compaiono con esponente minimo uguale a 1, e quindi si ottiene che MCD(18,84)=6. Non trovando fattori primi comuni, il MCD è 1, così ad esempio MCD(242,375)=1.

Questo metodo è utilizzabile, nella pratica, solo per numeri molto piccoli: la scomposizione in fattori primi di un numero richiede in generale troppo tempo.
Un metodo molto più efficiente è fornito dall'algoritmo di Euclide: si divide 84 per 18 ottenendo un quoziente di 4 e un resto di 12. Poi si divide 18 per 12 ottenendo un quoziente di 1 e un resto di 6. Infine si divide 12 per 6 ottenendo un resto di 0, il che significa che 6 è il massimo comun divisore.

Detto ciò.. andiamo a vedere un po' di codice

Iniziamo, utilizzando l'algoritmo di Euclide, a creare la funzione per calcolare il MCD:

def mcd(a, b):
if b == 0:return a
return mcd(b, a % b)

Ed infine, definiziamo la funzione per calcolare il mcm (usando la formula "migliorata" citata sopra):

def mcm(a,b):
return (a*(b/mcd(a,b)))

Ora abbiamo tutto per risolvere il nostro problema..
Mah.. noi abbiamo 20 numeri e non 2 (come la nostra funzione).. come facciamo?
Semplice.. useremo il calcolo mcm tra due numeri (esempio 1 e 2) come input da passare alla nostra funzione mcm

tmp = 1
for i in range(2,20):
tmp=mcm(i, tmp)
print tmp

Ho provato a testare il tempo di risoluzione del nostro script, utilizzando la funzione time di Unix..
Ecco il risultato:

real   0m0.033s
user   0m0.008s
sys   0m0.020s

Direi un tempo accettabile.. no??
Si accettano comunque idee per migliorarlo ulteriormente

1 Responses to "ProjectEuler - Problema 5"

Fab
30 marzo 11:03:42 del 2010

from random import randint
from time import clock

def gcd(a, b):
    ''' iterative '''
    while b:
        a, b = b, a%b
    return a

def gcd_rec(a, b):
    ''' recursive '''
    if b == 0:
        return a
    return gcd_rec(b, a%b)

def test(f, v):
    t = clock()
    for vv in v:
        r = f(vv[0], vv[1])
    t = clock() - t
    print('{0} took {1:.7f} seconds'.format(f.__name__, t))

n = 10**5
mx = 10**8
v = [(randint(0, mx), randint(0, mx)) for x in xrange(n)]

test(gcd, v)

test(gcd_rec, v)
'''
gcd took 0.2916580 seconds
gcd_rec took 0.6686202 seconds
'''

Grazie della dritta.. hai ragione!!