Qual è un buon risultato in termini di tempo?

A
Alessio22 (340 points)
2 8 13
asked Oct 19, 2017 in Es1 by Alessio22 (340 points)
closed Oct 20, 2017 by Alessio22
Ho notato che molti hanno tempi di esecuzioni veramente molto bassi. Io sono partito da 14 secondi e sono sceso a 2, ma molti hanno anche 4ms. Ovviamente il problema è sui numeri grandi, il mio programma scompone il numero in fattori primi e ovviamente si ferma se ha già trovato k divisori. Li trova dividendo il numero per un numero che parte da 2 e poi diventa 2*n+1 con n che incrementa ogni volta. In questo modo genero tutti i primi che mi servono per effettuare la divisione e anche qualche composto. Nonostante questo non scendo sotto i 2 secondi, mi interessava sapere come avete fatto voi e  se 2 secondi è più che accettabile. Grazie.
402 views
closed with note: risolto grazie ad una risposta

2 Answers

Best answer
answered Oct 19, 2017 by Anon1 (9,920 points)
selected Oct 20, 2017 by Alessio22
Ciao, un consiglio è quello di sfruttare la radice quadrata, è spesso usata per cercare i numeri primi. Ti spiego brevemente il funzionamento, anche se su Internet trovi molte più informazioni spiegate meglio: prendi il numero 15, la radice quadrata approssimata per difetto è 3. Ora comincia il famoso ciclo, e fermalo quando arrivi a 3 (compreso). Vedrai che il 15 non è divisibile per 2, però lo è per 3 (infatti 15 / 3 fa 5). Ora sai che 3 è un divisore di 15, ma anche 15/3, ossia 5, è un divisore di 15.
Auron (15880 points)
32 126 194
commented Oct 19, 2017 by Auron (15,880 points)
Non diciamo troppo, un pochino di pepe e di sana competizione deve restare :)
Comunque Alessio... Se capisci come implementare bene quello che hai detto sulla radice quadrata, è esattamente quello che bisogna fare :)
M
Maryam1372 (1270 points)
10 32 38
commented Oct 20, 2017 by Maryam1372 (1,270 points)
Chiedo scusa x ignoranza innanzitutto. Il mio primo esercizio risponde a tutti e 3 test in un tempo inferiore ai 30 secondi però nella pagina di risultati vedo 5334 MS x il primo esercizio! Ma questo che vuol dire? Visto che avete scritto 2 secondi posso sapere a cosa si riferisce? Il mio programma ci mette circa 12 secondi in totale.
A
Alessio22 (340 points)
2 8 13
commented Oct 20, 2017 by Alessio22 (340 points)
2 secondi è il tempo che ci mette il mio programma a svolgere tutte le istruzioni per i valori dati dal tester, espresso in ms 2000 (ms=millisecondi, nb non voglio insultare esplicitandolo è solo per togliere qualsiasi dubbio, sui risultati globali è tutto espresso in ms). Quindi da come dici tu mi sembra di capire che il tuo programma dell'es 1 ci mette 5334ms ovvero 5, 3 secondi. Il 12 mi viene da pensare che l'elaboratore che esegue i testi sul sito sia più potente del tuo, oppure sia la somma dei tempi di tutte e tre i programmi.
Auron (15880 points)
32 126 194
answered Oct 19, 2017 by Auron (15,880 points)
Suggerimento: Radice quadrata :P
Non ti dico di più altrimenti ti tolgo il gusto della scoperta :D
Internet è il tuo migliore amico su questo :)
Auron (15880 points)
32 126 194
commented Oct 19, 2017 by Auron (15,880 points)
Io per esempio ho un tempo che varia da 1,20 a 1,70 ms sull'esercizio 1, ma non riesco ad abbassare ulteriormente il mio tempo di 0,5 (circa) ms sul 3°, quando c'è gente che lo fa in (circa) 0,1 ms :P
A
Angelo9787 (3670 points)
6 32 51
commented Oct 19, 2017 by Angelo9787 (3,670 points)
Quoto il suggerimento sulla radice quadrata
A
Alessio22 (340 points)
2 8 13
commented Oct 19, 2017 by Alessio22 (340 points)
Radice quadrata così non capisco a cosa vi riferiate. Posso pensare che non serva dividere per numeri più grandi della radice quadrata. Ma non è vero, ad esempio 15 la sua radice è circa 3.87 e 5 è un suo divisore .