di  -  martedì 6 Luglio 2010

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.

30 Commenti »

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.

  • # 1
    io80gioia
     scrive: 

    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

  • # 2
    Emanuele Rampichini (Autore del post)
     scrive: 

    Questo era facile… anche se c’è una soluzione molto più efficiente. A cui sinceramente non avrei mai pensato. ;-)

  • # 3
    Dubbioso
     scrive: 

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

  • # 4
    Emanuele Rampichini (Autore del post)
     scrive: 

    Il primo premio va a Dubbioso :D
    Complimenti!

  • # 5
    Giulio85
     scrive: 

    C’avrei scommesso che si poteva fare in maniera costante derivando la formula da Gauss :D.

  • # 6
    v1
     scrive: 

    proverò a risolverli in matlab.. devo imparare a usarlo ù__ù

  • # 7
    Massive
     scrive: 

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

  • # 8
    sirhaplo
     scrive: 

    Ecco li una nuova droga sintetica.
    Effetti collaterali … arrivato a 100 inizi a sentirti vicino a Dio :D

  • # 9
    Nicola
     scrive: 

    bellissimo!!!! ci sto provando, ma la maggior parte dei problemi sono matematica pura XDDD

  • # 10
    Emanuele Rampichini (Autore del post)
     scrive: 

    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

  • # 11
    carletto
     scrive: 

    non ci provo neanche, son sempre stato duro a matematica ^_-

  • # 12
    Lisa
     scrive: 

    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! :)

  • # 13
    Emanuele Rampichini (Autore del post)
     scrive: 

    @Lisa
    Per caso frequenti il canale irc di Arch Linux con nick “shainer”? :D

  • # 14
    Pleg
     scrive: 

    @ Lisa

    [OT] Che fantascienza leggi? :D

  • # 15
    Lisa
     scrive: 

    @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

  • # 16
    Pleg
     scrive: 

    C’e’ scritto sul tuo sito :) ero curioso di sapere se leggevi la roba \giusta\ per un’informatica :)

  • # 17
    Lisa
     scrive: 

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

  • # 18
    Emanuele Rampichini (Autore del post)
     scrive: 

    Speriamo non mi caccino per via dell’OT…

    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.

    Poi mi piace anche il fantasy, ma solo se è “strano” (uno per tutti: Mondo Disco).

    Il genere fantasy non ha mai entusiasmato… ho una sorta di allergia per qualsiasi cosa riguardi Nani,Elfi,Troll e compagnia bella. :D

  • # 19
    Pleg
     scrive: 

    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.

  • # 20
    shinya
     scrive: 

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

  • # 21
    Lisa
     scrive: 

    @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) :)

  • # 22
    Pleg
     scrive: 

    Si’ il “Deliverator” e’ geniale :)

    C’e’ in italiano, e credo si chiami proprio “Assiomatico”.

  • # 23
    abbathrulez
     scrive: 

    #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();
    }

  • # 24
    Fede
     scrive: 

    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

  • # 25
    Emanuele Rampichini (Autore del post)
     scrive: 

    @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

  • # 26
    Emanuele Rampichini (Autore del post)
     scrive: 

    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

  • # 27
    Giovanni
     scrive: 

    Non ho più l’età per queste cose ;)

  • # 28
    seymourbeta
     scrive: 

    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]

  • # 29
    seymourbeta
     scrive: 

    Ho sbagliato una cosa nella formula. Potete anche cancellare i miei post

  • # 30
    un povero alunno
     scrive: 

    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

Scrivi un commento!

Aggiungi il commento, oppure trackback dal tuo sito.

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.