Ho sempre trovato l’enigmistica un simpatico passatempo. Ricordo con divertimento le ore passate in spiaggia a risolvere indovinelli o parole crociate in compagnia.
I tempi per andare al mare ormai sono maturi ma non tutti possono godersi la fresca brezza serale e gli interminabili bagni. Quello che però si può fare è mantenere fresca ed allenata la propria mente.
In questo articolo però non vi proporrò come farebbero altri sudoku o rebus vari. Quello che vi voglio segnalare è il Progetto Eulero.
Il Progetto Eulero consiste in una serie di problemi matematici risolvibili attraverso algoritmi da implementare al computer. Nella pagina del progetto viene esplicitamente evidenziato che per risolvere i vari quesiti è necessario saper programmare.
I quesiti proposti sono 299 in ordine di difficoltà crescente e rappresentano un’occasione sia per imparare ad approcciare problemi complessi che per rimanere allenati. Per farvi un’idea di quello che vi troverete di fronte vi propongo il primo quesito:
Se elenchiamo tutti i numeri naturali più piccoli di 10 che sono multipli di 3 o 5, otteniamo 3, 5, 6 e 9. La somma di questi multipli è 23.
Trova la somma di tutti i multipli di 3 o 5 più piccoli di 1000.
Il primo esercizio è estremamente semplice (quantomeno scrivere l’algoritmo corretto, altro discorso per quanto riguarda un algoritmo più efficiente) ma non fatevi ingannare… andando avanti le cose diventano decisamente più difficili.
Una volta inserita la risposta corretta sbloccherete la possibilità di scaricare un documento PDF che spiega bene tutti gli approcci possibili al problema (e vi assicuro che ne vedrete delle belle) e l’accesso ad una sezione del forum per discutere le possibili soluzioni. Naturalmente per raggiungere l’obbiettivo potete utilizzare qualsiasi linguaggio di programmazione.
Personalmente consiglio python :P ma c’è qualcuno che preferisce, per esempio, dilettarsi con java, c o addirittura Assembly.
Per darvi un idea di come si possa raggiungere lo scopo utilizzando i linguaggi più disparati date un occhiata alla pagina delle statistiche.
Tutti i quesiti sono pensati per impiegare al massimo 1 minuto di tempo macchina… quindi se vedete che il vostro algoritmo tiene il computer occupato per parecchio tempo probabilmente è il caso di ripensare la soluzione.
Ovviamente vi invito a condividere nei commenti le vostre soluzioni al primo quesito e ad iscrivervi a questo fantastico sito.
Se poi il caldo di questi giorni non vi permette nemmeno di completare “Unisci i puntini”…
…e “Annerisci gli spazi” vi sembra una montagna insormontabile allora è arrivato il momento di staccare la spina e cercare un po’ di fresco lontano dal PC.
di getto!
count=0;
for (int i=0; i < 1000; i++){
if( i%3 == 0 || i % 5 == 0){
count+=i;
}
}
System.out.println("La somma dei primi numeri naturali multipli di 3 o 5 < 1000 e' "+count);
Ora mi vado a guardare gli altri
Questo era facile… anche se c’è una soluzione molto più efficiente. A cui sinceramente non avrei mai pensato. ;-)
pensata al momento:
int a = 1000 – 1;
int b = a / 3;
int c = a / 5;
int d = a / 15;
return 3*(b*(b+1)/2) + 5*(c*(c+1)/2) – 15*(d*(d+1)/2);
Il primo premio va a Dubbioso :D
Complimenti!
C’avrei scommesso che si poteva fare in maniera costante derivando la formula da Gauss :D.
proverò a risolverli in matlab.. devo imparare a usarlo ù__ù
Anche a me la prima cosa venuta in mente è stata la formula di Gauss, il calcolo è fattibile anche in meno di un minuto di tempo uomo… immagino che molti problemi si risolvano prima per via matematica che computazionale.
In realtà certe volte quando non mi viene nulla in mente per problemi tradizionali, il risolverli per via computazionale mi fa venire l’idea giusta per risolverlo anche per via matematica.
Ci voleva proprio un passatempo del genere ;)
Ecco li una nuova droga sintetica.
Effetti collaterali … arrivato a 100 inizi a sentirti vicino a Dio :D
bellissimo!!!! ci sto provando, ma la maggior parte dei problemi sono matematica pura XDDD
P.S.
L’autore dell’articolo declina ogni responsabilità per i possibili danni dovuti ad accanimento nel tentativo di risoluzione dei problemi.
In soldoni se vi parte qualche rotella e avete voglia di infliggervi del male o farlo al prossimo non mandate il conto dei danni a casa mia! :P
non ci provo neanche, son sempre stato duro a matematica ^_-
Bellissimo sito, sono contenta che si diffonda!
E come è stato detto, inizialmente i quesiti sono piuttosto semplici, cosa che mi portò a raggiungere il 1° livello (25 quesiti risolti) di corsa, per poi perdere un po’ più di tempo con i successivi.
Comunque, “scontrarsi” con le difficoltà aiuta ad imparare un sacco di cose. E approvo la scelta del Python! :)
@Lisa
Per caso frequenti il canale irc di Arch Linux con nick “shainer”? :D
@ Lisa
[OT] Che fantascienza leggi? :D
@Rampichini, mi pareva che il tuo nome non fosse nuovo… ora mi ricordo dove l’ho visto (ho una memoria un po’ bucata per queste cose, mi avevi pure trovata sul blog mi sa, o no?)! Sì sono io.
@Pleg, che c’entra la fantascienza? :D
C’e’ scritto sul tuo sito :) ero curioso di sapere se leggevi la roba \giusta\ per un’informatica :)
(Speriamo non mi caccino per via dell’OT…) Diciamo che la fantascienza mi piace un po’ tutta: fra i preferiti ho i libri di Simak e di Philip Dick, ma anche Asimov o Vonnegut.
Poi mi piace anche il fantasy, ma solo se è “strano” (uno per tutti: Mondo Disco). Te?
Gli OT sui libri (soprattutto quelli di fantascienza :D) sono fortemente incoraggiati. Si legge talmente poco che sarebbe un delitto bloccare un commento che può portare lettori del blog a conoscenza di piccoli o grandi capolavori letterari.
Il genere fantasy non ha mai entusiasmato… ho una sorta di allergia per qualsiasi cosa riguardi Nani,Elfi,Troll e compagnia bella. :D
Roba classica, insomma :) Tra quelli che citi direi che Simak e’ il mio preferito (“City”, vari racconti).
Come cose “giuste” per qualcuno col tuo background, nel caso tu non abbia gia; letto, consiglierei:
scienza dura-dura-dura: Egan (“Axiomatic” su tutti, uan raccolta di racconti con una densita’ di idee spettacolari talmente alta da essere pericolosa; poi “Distress” e “Permutation city”)
information technology: naturalmente Neal Stephenson, che per me e’ un semidio da adorare e riverire (in ordine di gustosita’ hackereggiante metterei “Cryptonomicon”, “Snowcrash” e “The diamond age: A young lady’s illustrated primer”). “Cryptonomicon”, come puoi immaginare dal nome, e’ molto gustoso se sai qualcosa di crittografia (o almeno ti interessa l’argomento); “Snowcrash” e’ una spassossima presa in giro del cyberpunk tra hacker, mondi virtuali, virus per computer e cervelli e antichi Dei sumeri :D
Ma di fantascienza leggo un po’ di tutto. Tra i mie preferiti (oltre a quelli citati) metterei Heinlein per i bei vecchi tempi andati, e Banks e Vinge tra quelli piu’ recenti.
Project Euler è bello e ben fatto. E’ un pò che non lo frequento… quando ci giocavo io non c’era sta cosa del PDF con i vari approcci :( fico!
Altri siti ottimi, ma decisamente più impegnativi sono:
http://www.spoj.pl/
http://www.topcoder.com/
SPOJ in particolare mi ha rubato un sacco di tempo libero :)
@Pleg, grazie dei consigli! Snowcrash l’ho letto, con la storia della consegna della pizza stavo per morire dalle risate. Heinlein non lo apprezzo tanto, gli altri non li conosco e ci farò un pensierino. Axiomatic c’è in italiano (così lo cerco in biblioteca) o solo in lingua originale? Pare interessante!
@Emanuele, per questo ti consiglio il Mondo Disco. Ci sono nani, troll, streghe, maghi, tutta questa roba qua, ma generalmente sono fuori di testa e il tutto è una grande satira dei difetti umani (fatta in modo divertente) :)
Si’ il “Deliverator” e’ geniale :)
C’e’ in italiano, e credo si chiami proprio “Assiomatico”.
#include
main(){
int sum=0,i;
for(i=0;i<1000;i++){
if(!(i%3)||!(i%5)) sum=sum+i;
}
printf("%d", sum);
fflush(stdin);
getchar();
}
Finalmente roba un po più seria (anche se il problemino proposto nell’articolo è abbastanza semplice) per quanto concerne la programmazione, saper programmare non significa conoscere la sintassi di un dato linguaggio (io figurati pur conoscendo C/C++, Basic, Python, Java, Iava script, Pascal ecc. ecc. ho una confusione mentale sulle sintassi e se non ricorro ai manuali faccio una frittata dei vari linguaggi) significa sviluppare gli algoritmi più efficienti per arrivare ai risultati perché ovviamente un qualsiasi problema può essere risolto in diversi modi ma esiste sempre il modo più efficiente. Chi vuole saper programmare si deve concentrare piuttosto sulla logica degli algoritmi insomma deve affrontare un dato problema piuttosto da matematico (io sono pienamente convinto che i migliori programmatori sono matematici) poi con il manualetto dello specifico linguaggio è uno scherzo tradurre in codice.
Per chi è interessato c’è il seguente libro sulla programmazione, esso si appoggia al linguaggio C++ ma punta soprattutto alla logica generale per creare gli algoritmi quindi è adatto per la programmazione con qualsisi linguaggio di alto livello (è un testo utilizzato nell’università soprattuto nelle facoltà di matematica ed in alcune facoltà di ingegneria ma comunque salvo qualche capitolo il resto è alla portata di tutti anche dei semplici diplomati, bisogna sola far frullare il cervello nel leggerlo).
MARCO CADOLI, MAURIZIO LENZERINI, PAOLO NAGGAR, ANDREA SHAERF
FONDAMENTI DELLA PROGETTAZIONE DEI PROGRAMMI
PRINCIPI, TECNICHE E LORO APPLICAZIONI IN C++
CITTA’STUDIEDIZIONI
Vi propongo quest’altro problemino che punta piuttosto alla logica perché la soluzione è banalmente una formula.
Scrivere un programma che dato in input un numero intero n restituisca come risultato il numero minimo di mosse per risolvere una torre di Hanoi costituita da tre colonne ed n dischi. Ma prima di scrivere il programma dimostrare il funzionale n –> numero minimo di mosse (n)
(è un tipo esercizio proposto al primo anno della facoltà di matematica nell’esame di algebra ma la dimostrazione del funzionale non richiede neanche le conoscenze dell’algebra studiata alle superiori è pura logica quindi anche un diplomato dovrebbe essere capace ad affrontare il problema tocca solo far frullare il cervello).
Pert chi si cimenta buon divertimento!!!
Ovviamente mi aspetto che qualcuno posti qui la dimostrazione generale della torre di Hanoi
@Fede
Se non sbaglio si dimostra per induzione. Ho fatto da poco un listato in prolog per risolverla con algoritmo di search (sia bredth-first che depth first ). :D
Per la gioia di fede ecco la dimostrazione:
per completare la torre di hanoi con 1 solo disco serve 1 mossa,
per completare la torre di hanoi con 2 dischi servono 3 mosse,
per completare la torre di hanoi con 3 dischi servono 7 mosse.
Quindi intuitivamente servono m mosse con m=(2^n) – 1
i) abbiamo che m(0) è vera,
ii) supponiamo vera m(n-1) = (2^(n-1)) – 1
basta provare m(n)=(2^n)-1
considerando che bisognerà spostare ad un certo punto del gioco l’anello più grande dal primo piolo (passaggio obbligato del gioco) al terzo piolo avremo una situazione di questo tipo:
nel piolo 1 l’anello più grande nel piolo 2 i restanti (n-1) anelli nel terzo piolo niente.
Tale stato può essere considerato come un gioco di hanoi con (n-1) anelli in cui l’obbiettivo consiste nel portarli nella seconda colonna.
Avendo supposto vera ii) sappiamo che per arrivare a tale stato serviranno 2^(n-1)-1 passi.
Bisognerà spostare poi il disco grande dal piolo 1 al 3 (quindi aggiungo un altro passo).
A questo punto ho un altro problema di hanoi con n-1 dischi e obbiettivo terzo piolo quindi ulteriori 2^(n-1)-1 passi.
Sommando si ottiene:
m(n) = 2^(n-1) +2^(n-1) -2 + 1 = (2^n) -1
q.e.d.
:D
Non ho più l’età per queste cose ;)
Io invece avevo pensato ad una soluzione molto simile a quella di ‘Dubbioso’.
Supponiamo che ‘N’ sia l’ultimo multiplo di un numero (nel caso di 5 è 1000 e nel caso di 3 è 999).
La seguente formula calcola la somma dei multipli di 3:
N*(N+3)/6
dove N = 999.
La seguente formula calcola la somma dei multipli di 5 (incluso 1000):
N*(N+5)/10
dove N = 1000…
ma per escludere 1000 (perchè vogliamo calcolare la somma dei multipli di 5 minori di 1000) dobbiamo sottrarre alla formula N (cioè 1000) e quindi diventa:
N*(N+5)/10 – N = N*[(N+5)/10 – 1]
Se vogliamo scrivere la formula completa assumendo che M = 999 e N = 1000 allora avremo:
S = M*(M+3)/6 + N*[(N+5)/10 – 1]
Ho sbagliato una cosa nella formula. Potete anche cancellare i miei post
Scusate la mia domanda, ma non sono una cima in matematica, mi spieghereste come avete risolto il primo problema: il risultato e il procidemento.Grazie