Problemi, gare e algoritmi

Non ci posso credere ma esiste veramente un sito in cui si gareggia e ci si confronta con utenti da tutto il mondo su problemi di matematica utilizzando computer e intelligenza.

Si tratta del Project Eulero: in poche parole, sul sito trovate problemi di matematica, principalmente aritmetici, risolubili con carta e penna o con un computer e un programma di calcolo o un linguaggio di programmazione.

Sembra proprio fatto per noi. Per partecipare (e vedere anche le statistiche e altri dati interessanti) bisogna registrarsi con login e password come al solito.

L’unico ostacolo (ma non per noi, ovviamente) è che tutto è in lingua inglese.

Dopo essersi registrati si può incominciare a risolvere i problemi proposti e dopo un certo numero si sarà ammessi nell’elenco dei risolutori ufficiali (con vari gradi di abilità).

Nella sezione statistiche si vede il numero dei partecipanti distinti per nazione e l’Italia si colloca dopo paesi come Germania,Francia,Olanda, Svezia,Norvegia e vicino a paesi come Messico, Romania, Belgio. Ma vi pare accettabile? non credo proprio.

Dunque diamoci da fare: attualmente i risolutori italiani sono 354; vediamo se riusciamo a passare i 400 entro fine anno. Intanto mi iscrivo.

Per capire subito di cosa si tratta vi ripropongo uno dei problemi proposti con relativa soluzione da me trovata; bisogna anche dire che tipo di programmi si sono usati: nel mio caso uso SAGE, un software di cui vi parlerò presto, ma si può anche usare Maxima o un linguaggio di programmazione.

Problema n. 1 5 Ottobre 2001

Se elenchiamo i numeri naturali minori di 10 che sono multipli di 3 o di 5 otteniamo: 3,5,6,9 la cui somma è 23.

Trovare la somma di tutti i multipli di 3 o 5 minori di 1000.

Risposta: 233168

Codice usato:

def mu(n):
tot=0
for k in range(n):
if mod(k,3)==0 or mod(k,5)==0:
tot=tot+k
print tot

Come dicevo, il programma usato  si chiama Sage che contiene tutti gli ambienti OpenSource per la matematica nonchè alcuni linguaggi di programmazione, tipo Python.

L’algoritmo sopraesposto è banale e si può tradurre in qualsiasi altro linguaggio di vostro gradimento.

Per chi volesse cimentarsi subito senza registrarsi, ecco il problema n.56 7 Novembre 2003

Un googol \displaystyle (10^{100}) è un numero grandissimo, 1 seguito da cento zeri; \displaystyle (100^{100}) è inimmaginabile: 1 seguito da 2 cento zeri. Nonostante la loro grandezza, la somma delle cifre di questi numeri è sempre 1.

Considerando numeri naturali della forma \displaystyle a^b con \displaystyle a,b < 100, qual’è il massimo della somma delle cifre?

Coraggio.

Annunci
Questa voce è stata pubblicata in Aritmetica, Informatica, Matematica, Matematica.curiosa e contrassegnata con , . Contrassegna il permalink.

16 risposte a Problemi, gare e algoritmi

  1. bobcarr ha detto:

    non sapevo che sqr fosse il quadrato: ok, bene. E ora il problema 220!

    Sia D_0 la stringa “Fa”

    D_n si ottiene da D_{n-1} sostittuendo ‘a’ con la stringa ‘aRbFR’ e ‘b’ con la stringa ‘LFaLb’

    Quindi:
    D_0 = ‘Fa’
    D_1 = ‘FaRbFR’
    D_2 = ‘FaRbFRRLFaLbFR’ ecc.

    Se interpretiamo F come avanti di 1, R gira a destra di 90 gradi, L gira a sinistra di 90 gradi, a e b ignorati e partiamo, in un sistema di coordinate cartesiane, dal punto (0,0) origine con direzione verso l’alto (asse y), allora la stringa rappresenterà un certo percorso nel piano cartesiano. Ovviamente il punto mobile si troverà sempre su un punto di coordinate intere.
    Considerando D_{50}, dove si troverà il punto dopo 500 passi?

  2. cavaliere ha detto:

    @bobcarr

    si viene giusto.. qsomma:=sqr(somma) mi da il quadrato la radice è sqrt se è questo che intende

  3. cavaliere ha detto:

    @bobcarr

    si viene giusto.. qsomma:=sqr(domma) mi da il quadrato la radice è sqrt se è questo che intende

  4. bobcarr ha detto:

    @cavaliere ma hai inserito il risultato?

    credo che ci sia un erroretto -> “qsomma:=sqr(somma);”

  5. cavaliere ha detto:

    @bobcarr

    ed ecco a lei la risoluzione del problema (sempre in pascal)

    var i, n, k, somma, sommq, qsomma : longint;

    begin
    readln(n);
    somma:=0;
    sommaq:=0
    for i:=1 to n do
    begin
    somma:=somma+i;
    sommaq:=sommaq+(i*i);
    end;
    qsomma:=sqr(somma);
    k:=qsomma-sommaq;
    writeln(somma);
    writeln(sommaq);
    writeln(k);
    readln
    end.

    un po’ alla volta li faccio tutti!!!

  6. bobcarr ha detto:

    @cavaliere bravo

    ora il problema n.6

    la somma dei quadrati dei primi dieci numeri è:

    1^2 + 2^2 + \dots + 10^2 = 385

    il quadrato della somma è:

    (1+2+3+ \dots + 10)^2 = 3025

    la differenza è 3025-385 = 2640

    trovare la stessa differenza per i primi 100 numeri naturali

  7. cavaliere ha detto:

    grazie prof.. ce l’ho fatta!!!
    ecco il programma in pascal

    var a, b, k, n, tot : longint;

    begin
    readln(n);
    tot:=0;
    a:=1;
    b:=1;
    k:=0;
    repeat
    k:=a+b;
    a:=b;
    b:=k;
    if b mod 2=0 then tot:=tot+b
    until b > n;
    writeln(tot)
    end.

    grazie ancora!!!

  8. bobcarr ha detto:

    A gentile richiesta: il problema n. 2

    la successione di Fibonacci si ottiene partendo dai numeri 1,1 e sommando successivamente i due numeri precedenti, quindi:

    1,1,2,3,5,8,13,21,34,….

    trovare la somma dei termini pari della sequenza minori di 4 000 000

    soluzione mia (python)

    def p2(n):
    …tot=0
    …a, b = 1,1
    …while b < n:
    ……a=b
    ……b=a+b
    ……if b%2==0:
    ………tot=tot+b
    …print “ris. “, tot

    p2(4000000)

    in un prossimo commento, la soluzione di qualche guru della programmazione

  9. bobcarr ha detto:

    Un problemino facilmente risolubile con maxima:

    quali sono le ultime 10 cifre del numero 28433 \cdot 2^{7830457} +1 ?

    in Pascal, che problemi incontrereste?

  10. bobcarr ha detto:

    Nessuno scrive su sto post, quindi continuo io.

    Il problema proposto nel testo : “Un googol \displaystyle (10^{100}) è un numero grandissimo, 1 seguito da cento zeri; \displaystyle (100^{100}) è inimmaginabile: 1 seguito da 2 cento zeri. Nonostante la loro grandezza, la somma delle cifre di questi numeri è sempre 1.

    Considerando numeri naturali della forma \displaystyle a^b con \displaystyle a,b < 100, qual’è il massimo della somma delle cifre?”

    La mia soluzione in python:

    def p56(a,b):
    …max = 0
    …for x in range(2,a+1):
    ……for y in range(1,b+1):
    ………k=x^y
    ………z=sommacifre(k)
    ………if max > z : max = z
    …print x,y,k,max
    …………….
    def sommacifre(n):
    …p=n
    …tot=0
    …while p > 0:
    ……tot=tot+p%10
    ……p=p//10
    …return tot

    note: range(n,m) attiva un ciclo for che va da n a m-1
    % mi ritorna il resto della divisione intera
    // mi ritorna il quoziente della divisione intera

    spero che siate in grado di scrivere una vostra versione migliore e più efficiente della mia;
    aspetto fiducioso

    scusate i puntini ma non riesco a fare le tabulazioni (qualcuno esperto di hml potrebbe darmi un suggerimento?)

  11. Igor R. ha detto:

    la soluzione che mi viene in mente è la stessa di elia…quindi è superfluo postarla penso…

  12. elllia ha detto:

    L’odiato maxima… Di gran lunga meglio il phyton… Comunque non le sembra di aver già fornito un pseudo soluzione?

    Io le propongo la mia…

    const n = 1000;
    var tot,i : integer;
    begin
    tot=0;
    for i:=1 to n do
    begin
    if (i mod 3=0) or (i mod 5=0) then
    tot=tot+i;
    end;
    writeln(tot)
    end.

    Perdoni il Pscal un pò arruginito…

  13. Ciccio Pompelmo ha detto:

    sisi sono io, volevo firmarmi ma sapevo che mi avrebbe riconosciuto quindi ho evitato comqunque se g5radisce di piu mi firmo d’ora in poi..comunque di che programma si tratta??

    Malacrea Marco

  14. bobcarr ha detto:

    @ciccio se non erro, tu sei Malacrea, ricordati di firmarti, noi non amiamo l’anonimato.

    il problema è semplice e ci puoi arrivare anche tu; se il problema è la pigrizia allora non so cosa dire.

    consiglierei un piccolo programmino in pascal senza scomodare il maxima, con il quale le difficoltà sarebbero nettamente superiori

  15. Ciccio Pompelmo ha detto:

    oddio bobcarr non esageriamo, noi di 3a non siamo così intelligenti..o almeno…lo siamo ma siamo anche pigri comunque ora scarico maxima e ci provo..

  16. bobcarr ha detto:

    Visto lo scarso successo di questo post, ritorniamo alla carica riproponendo un problema (di programmazione) molto facile:

    Problema n. 1 5 Ottobre 2001

    Se elenchiamo i numeri naturali minori di 10 che sono multipli di 3 o di 5 otteniamo: 3,5,6,9 la cui somma è 23.

    Trovare la somma di tutti i multipli di 3 o 5 minori di 1000.

    Risposta: 233168

    Quello che vorrei è un commento (anzi molti commenti) che contenesse un programma o una funzione che risolve il problema; il linguaggio o il programma (maxima p.es. o pascal o assembly o php o java) usato non ha alcuna importanza.
    Tutti gli studenti sono in grado di risolverlo, anche quelli di 3a.
    Ricchi premi per la soluzione più brillante.

Rispondi

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...