Project Euler - Problema 53

8 febbraio del 2011

Erano ormai mesi e mesi che non mi concedevo un paio d'ore di svago davanti a Python; finalmente dopo un lungo periodo di completo digiuno da Python, sono riuscito a riprenderlo in mano. Destino volle che il giorno stesso in cui mi misi nuovamente a giocare con Python, lo staff di ThinkCode.TV decise di fare una superofferta nel suo corso di Python a cura di "Marco Beri" (no, non quello delle iene ;)).. decisi quindi di prendere il corso ed iniziare da capo Python.. Che dire.. non mi ricordavo fosse così efficiente e così divertente programmare in Python; dopo alcune ore di studio "full immersion", ripresi in mano una mia vecchia passione: "Project Euler". Ordinando i problemi in ordine di difficoltà mi ritrovai ad affrontare il problema numero 53, il cui enunciato diceva:

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, ⁵C₃ = 10.

In general,

ⁿC_r =

n!
r!(nr)!

,where r

n, n! = n

(n

...

1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: ²³C₁₀ = 1144066.

How many, not necessarily distinct, values of ⁿC_r, for 1 n 100, are greater than one-million?

Il problema non mi sembrava difficile, ma pensavo (sbagliandomi) :"Dubito che facendo due cicli for, possa risolvermi velocemente il tutto! Vabbè proviamo..."

import math
numero_elementi=0
for n in range(1,101):
    for r in range(1,n+1):
        if math.factorial(n) / (math.factorial(r) * math.factorial(n-r)) > 1000000:
            numero_elementi+=1

print "Numero elementi trovati:" , numero_elementi

Il tutto funzionava e la risoluzione impiegava pochissimo..decisi di provare a ridurre ulteriormente la mia riga di codice e mi ritrovai ad una soluzione di un unica riga..

print sum(1 for n in range(1, 101) for r in range(1, n+1) if math.factorial(n) / (math.factorial(r) * math.factorial(n-r)) > 1000000)

Questo Python è davvero COOL

Penso che prossimamente mi ritaglierò un po' di tempo per proseguire con Project Euler. L'obiettivo è raggiungere il Livello 4 di Project Euler per fine anno! Diamoci dentro...

ferro

0 Comments

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