M3.1011 PyGame[5]

Sono esclusi tutti quelli che hanno già risolto un problema.

2520 è il più piccolo numero divisibile per tutti i numeri da 1 a 10.

Trovare il più piccolo numero divisibile per tutti i numeri da 1 a 20.

valore: 2 crediti

valore algoritmo ottimo: 3 crediti

Questa voce è stata pubblicata in Algoritmi, Informatica, M3, M3.1011, Programmazione e contrassegnata con , , . Contrassegna il permalink.

22 risposte a M3.1011 PyGame[5]

  1. Daniele Roiter ha detto:

    programma messo in dropbox (sotto il nome di pygame_ver5.3.pyw) con tempo di esecuzione pari a 15 sec…

  2. bobcarr ha detto:

    aggiornamenti:

    la soluzione carta e penna di E. Bastianetto è corretta (anche se la spiegazione non è chiarissima; ma, lo sappiamo, sapere non è lo stesso che spiegare); quindi crediti accordati

    la soluzione di Roiter è ancora in attesa di miglioramento; quanto dobbiamo aspettare ancora?

  3. Edoardo Bastianetto ha detto:

    Se si moltiplicano tutti i numeri dal 1 al 20 si ottiene un numero superiore al più piccolo numero divisibile per tutti i numeri scelti, perchè per esempio se il numero è divisibile per il 2 e per il 3 non serve moltiplicarlo anche per il 6.
    Quindi si fa prima la scomposizione a numeri primi e poi il minimo comune multiplo e si ottiene il risultato.
    Metto i calcoli ?

    • Davide Mattiuzzo ha detto:

      Te li metto io per far prima, ma non penso sia la soluzione che intendeva il prof, perchè questa è la soluzione più ovvia!

      2^4*3^2*5*7*11*13*17*19 = 232792560

        • edoardobastianetto ha detto:

          Per accelerare il procedimento invece di effettuare la fattorizzazione di ogni numero si può fare cosi :

          -Si trovano i numeri primi minori del numero massimo* (20)

          1,2,3,5,7,11,13,17

          – Dei numeri primi inferiori al quadrato del numero massimo** (4,4)

          2,3

          si trova quale sia il loro quadrato più grande inferiore del numero massimo

          2->16-2^4,3->9->3^2

          Infine si moltiplicano le potenze dei numeri primi appena trovati e gli altri numeri primi quindi :

          2^4*3^2*5*7*11*13*17

          E si ottiene il numero minore divisibile per tutti i numeri minori o uguali al numero massimo.

          *Basta trovare i numeri primi e non gli altri numeri perchè gli altri numeri o sono quadrati di numeri primi e saranno calcolati dopo o perchè sono dati dal prodotto di numeri primi e quei numeri primi sono già stati presi.

          (Se un numero è divisibile per 2 e per 3 lo è anche per 6, perchè 2*3=6)

          **Inferiori al quadrato perchè se il numero fosse maggiore della radice quadrata del numero massimo allora elevato alla seconda sara maggiore del numero massimo.

  4. bobcarr ha detto:

    Aggiornamento:

    il problema si può risolvere con carta e penna. 3 crediti al risolutore.

  5. bobcarr ha detto:

    @mattiuzzo

    bello. peccato che era il prob. n.5 e non il n.5*

    • Davide Mattiuzzo ha detto:

      Ma lei mi ha detto che potevamo partecipare alla parte del miglioramento dell’algoritmo no? E il problema era già stato risolto a quanto avevo capito..
      Nel caso mi sbagliassi sono fiero di essermi presuntuosamente preso la libertà di essere al centro dell’attenzione^^ Viva gli esaltati!

      • bobcarr ha detto:

        Il problema è stato risolto ma il tempo di esecuzione non è soddisfacente, aspetto ancora un miglioramento dall’autore.
        Essere al centro dell’attenzione non è sempre salutare, si è un buon bersaglio.

  6. Davide Mattiuzzo ha detto:

    Programma migliorato.. La soluzione è su dropbox, tempo di rispluzione: 0 millisecondi

  7. bobcarr ha detto:

    la soluzione in J:

    */ ((>./”1@(+/@(E.&>)/) # [)~ ~.@;) <@q: 1+i.20

    tempo: 0

  8. bobcarr ha detto:

    il programma roiter è corretto ma molto lento
    inoltre non si capisce bene perchè incrementi di 20 il contatore

    • Daniele Roiter ha detto:

      aumenta di venti perchè so già che se il numero non è divisibile per venti non va bene all’esercizio per cui ho eliminato molto conti inutili!!!!!!
      Comunque prof io non ho molto capito questa storia del j e quello che ha scritto lei è abbastanza arabo per me….

  9. Daniele Roiter ha detto:

    Su dropbox c’è il programma finale che ci impega molto meno tempo in esecuzione…
    è sotto il nome di pygame_ver5.1

  10. Daniele Roiter ha detto:

    Sono riuscito anche in python con lo stesso risultato però ci impiega molto più tempo che in pascal…
    Non so…..

    • bobcarr ha detto:

      non capisco il numero 2521, da dove sbuca?

      l’estensione dei file python deve essere .pyw

      • Daniele Roiter ha detto:

        Perchè volevo evitare di calcolare già un pò di numeri siccome il programma è molto lungo.
        Però adesso sto pensando di far partire il programma da un numero piccolo multiplo di 20 e poi tentare sommando sempre 20 cos’ ci sono un sacco di conti in meno che la CPU non deve fare… Ora provo e posto su dropbox.

  11. Daniele Roiter ha detto:

    prof io ho fatto il programma però è fatti in TP perchè non riesco ancora a destreggiarmi bene in python.
    Comunque il risultato secondo il mio programma è 232792560!!!!!
    spero sia giusto..
    intanto metto il TP in dropbox e ora provo a fare in python di nuovo…

Lascia un commento

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