-
.
Ho modificato leggermente il problema originale per renderlo più interessante. CITAZIONESe elenchiamo tutti i numeri naturali minori di 10 che sono multipli di 3 o 5, otteniamo 3, 5, 6, 9. La somma di questi multipli è 23.
Trova la somma di tutti i multipli di 3 o 5 minore di 1.000.000.
Quello del progetto eulero la richiede sino a 1.000, ma in questo modo è risolvibile facilmente anche con un brute force.
. -
walter4991.
User deleted
Con un brute force in C: CODICE#include <stdio.h>
#define MAX 1000000
void main()
{
int i, tot=0;
for(i=0;i<MAX;i++)
if(i%3==0||i%5==0) tot+=i;
printf("\n %d", tot);
tot=0;
}
Output con un milione di numeri:CODICE1404932684
Più tardi vedo di trovare una soluzione più ottimizzata.
. -
.
Non ricordo se il risultato è corretto, tuttavia suppongo di si.
Quanto ci ha impiegato?. -
meliture.
User deleted
SPOILER (clicca per visualizzare)CODICEpublic class ExSoloPc{
public static void main(String s[]){
int n=0,N=1000000;
double cinq=0,tre=0;
while(n<N){
tre+=n;
n+=3;
}
n=0;
while(n<N){
cinq+=n;
n+=5;
}
double somma = tre +cinq;
System.out.println(somma);
}
ho provato con 10 e mi viene 23...
con 1kk a me da questo risutato che non so se sia giusto o no 2.66666333333E11 .... -
walter4991.
User deleted
Non ricordo se il risultato è corretto, tuttavia suppongo di si.
Quanto ci ha impiegato?
A fare cosa? Il programma l'ho fatto in meno di 30 secondi...
Il tempo di esecuzione è relativo alla cpu che si ha, quindi non è un buon strumento di valutazione.
Al massimo possiamo prendere in considerazione il numero di iterazioni per raggiungere il risultato, in questo caso sarebbero 1.000.000 perchè si tratta di un brute force.. -
lumo.
User deleted
Una soluzione meno ingenua(python) CODICEdef sumOfMultiplesUpTo(limit, multiple):
numberOfMultiples = limit // multiple
return multiple*( numberOfMultiples*(numberOfMultiples+1))/2
limit = 1000000 - 1
result = 0
result += sumOfMultiplesUpTo(limit,3)
result += sumOfMultiplesUpTo(limit,5)
result -= sumOfMultiplesUpTo(limit,15)
print result
L'algoritmo di meliture è sbagliato perchè riconta due volte i multipli di 15, mentre quello di walter è giusto ma un int è troppo piccolo per contenere il risultato.
Il risultato dovrebbe essere 233333166668. ( E in fatti 233333166668 modulo 2^31 fa 1404932684 ).
1000000 è troppo piccolo per non funzionare con un bruteforce asd.. -
.
Il risultato è il seguente: 1404932684
@Walter: mi riferivo al tempo di esecuzione, ovviamente.
@lumo: il mio scopo era far notare la lentezza di una soluzione ingenua (come l'hai definita tu), rispetto ad un brute force con un numero relativamente basso come 1 milione.
Comunque posto la mia soluzione, in C:CODICE#include<stdio.h>
int sum(int n, int max);
int get_sum(int n1, int n2, int m);
int sum(int n, int max) {
int temp = (max-1) / n;
return (temp*(temp+1) / 2) * n;
}
int get_sum(int n1, int n2, int m) {
int diff = ((n1 * n2) < m) ? (sum(n1*n2, m)) : 0;
return (sum(n1,m) + sum(n2,m))-diff;
}
int main() {
int n1, n2, m;
printf("Inserisci il primo numero:");
scanf("%d",&n1);
printf("Inserisci il secondo numero:");
scanf("%d",&n2);
printf("Inserisci il limite massimo:");
scanf("%d",&m);
printf("La somma dei multipli dei valori inseriti e': %d",get_sum(n1, n2, m));
return 0;
}
Anche con 10.000.000 non ci impiega molto più di un secondo ("a naso" direi tra 1s e 1.5s, magari meno).
Ho guardato meglio il tuo codice ora lumo, e mi sono accorto che hai dato la mia soluzione. lol. -
lumo.
User deleted
Il risultato è il seguente: 1404932684
@Walter: mi riferivo al tempo di esecuzione, ovviamente.
@lumo: il mio scopo era far notare la lentezza di una soluzione ingenua (come l'hai definita tu), rispetto ad un brute force con un numero relativamente basso come 1 milione.
Comunque posto la mia soluzione, in C:CODICE#include<stdio.h>
int sum(int n, int max);
int get_sum(int n1, int n2, int m);
int sum(int n, int max) {
int temp = (max-1) / n;
return (temp*(temp+1) / 2) * n;
}
int get_sum(int n1, int n2, int m) {
int diff = ((n1 * n2) < m) ? (sum(n1*n2, m)) : 0;
return (sum(n1,m) + sum(n2,m))-diff;
}
int main() {
int n1, n2, m;
printf("Inserisci il primo numero:");
scanf("%d",&n1);
printf("Inserisci il secondo numero:");
scanf("%d",&n2);
printf("Inserisci il limite massimo:");
scanf("%d",&m);
printf("La somma dei multipli dei valori inseriti e': %d",get_sum(n1, n2, m));
return 0;
}
Anche con 10.000.000 non ci impiega molto più di un secondo ("a naso" direi tra 1s e 1.5s, magari meno).
Ho guardato meglio il tuo codice ora lumo, e mi sono accorto che hai dato la mia soluzione. lol
Già però anche tu hai fatto lo stesso errore di walter. Usa un long long int.. -
Wextum.
User deleted
CODICEprint sum(range(1,999999,3))+sum(range(1,999999,5))CITAZIONE266665866667
Questo è l'out, quindi penso sia sbagliato..
. -
lumo.
User deleted
CODICEprint sum(range(1,999999,3))+sum(range(1,999999,5))CITAZIONE266665866667
Questo è l'out, quindi penso sia sbagliato..
Con quel codice riconti due volte i multipli sia di 3 che 5.. -
Wextum.
User deleted
CODICEprint sum(range(1,999999,3 or 5))CITAZIONE166666166667CODICE>>> print sum(range(1,999999,3))+sum(range(1,999999,5))-sum(range(1,999999,15))
233332633335
Nessuno dei due... -
lumo.
User deleted
CODICEprint sum(range(1,999999,3 or 5))CITAZIONE166666166667CODICE>>> print sum(range(1,999999,3))+sum(range(1,999999,5))-sum(range(1,999999,15))
233332633335
Nessuno dei due..
Il primo multiplo di un numero è lo 0, quindi devi cominciare il range da 0, non da 1. -
.
@lumo: anche in un int ci sta comunque. Ovvio, se viene inserito un numero un poco più grande, esce dal range e diventa negativo.
Ripeto la soluzione per i meno attenti: 1404932684. -
Wextum.
User deleted
CITAZIONEIl primo multiplo di un numero è lo 0, quindi devi cominciare il range da 0, non da 1
In un sum, lo zero è inutile.. dato che
166666166667 + 0 = 166666166667CITAZIONERipeto la soluzione per i meno attenti: 1404932684
Appunto, e non capisco perchè non la trovo..
. -
lumo.
User deleted
CITAZIONEIl primo multiplo di un numero è lo 0, quindi devi cominciare il range da 0, non da 1
In un sum, lo zero è inutile.. dato che
166666166667 + 0 = 166666166667CITAZIONERipeto la soluzione per i meno attenti: 1404932684
Appunto, e non capisco perchè non la trovo..
Ma siccome il range parte da 1 con step 3, allora avrai una lista così:
[1,4,7,10,...]
Questi NON sono i multipli di tre lol.
Quello che serve a te è [0,3,6,9,...].
SoloPC [Tutto sui PC, Programmazione, Hacking, News, Grafica, e molto altro ancora!] 
Esercizi di programmazione
Trova la somma dei multipli di 3 o 5, minore di 1.000.000Modifica al Project Euler. |
Contacts
Web