Pages: 1 [2]   Go Down
Print
Author Topic: output terza gara  (Read 3502 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #15 on: 16-04-2011, 21:37:40 »

tempi?
Mediamente 2.08073216E8ns ...come ti sembra? Io credo un pò altino  I
P.S. Calcolato con System.nanoTime()

EDIT: Trasformando un algoritmo da ricorsivo ad iterativo ora raggiunge vali massimali di 1.82713984E8ns. Per il resto non credo sia possibile renderlo più veloce  boh
« Last Edit: 16-04-2011, 23:18:41 by zElOtO » Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
Chuck_son
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.583



WWW
« Reply #16 on: 17-04-2011, 10:40:58 »

AHAH quindi in MS dovrebbero essere un 180?
Logged

Aliens Exist
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #17 on: 17-04-2011, 10:59:07 »

AHAH quindi in MS dovrebbero essere un 180?
come valore massimo
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
FReddy
Apprendista Forumista
**
Offline Offline

Posts: 367



« Reply #18 on: 17-04-2011, 11:07:57 »

Quote
si hai ragione che in linea teorica e' quello, ma secondo me c'e' 1 aspetto pratico: i tempi di esecuzione diventerebbero proibitivi gia' dopo la quindicina di ingredienti, qualunque super strategia uno riesca ad inventarsi!!

Pensadoci meglio non è proprio così:
nel caso in cui tutti gli ingredienti valessero 1 anche se ci fossero 44! (o anche meno) permutazioni, se quella tavoletta soddisfa l'equazione la soddisferà per ogni permutazione e quindi al primo colpo. Questo ragionamento vale per ogni tavoletta in cui gli ingredienti hanno tutti lo stesso numero.

Ora, non mi aspetto che nel file di input ci sia una tavoletta tipo di 30-40 ingredienti che non soddisfa l'equazione (sennò buonanotte  ), ma ritengo più che giusto considerare l'eventualità di possibili tavolette di questa lunghezza che la soddisfano, messe apposta per testare questo vincolo.
Logged

Il presente è ora,
Il passato era ora,
Il futuro sarà ora.
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #19 on: 17-04-2011, 12:51:44 »

E poi in generale basta che almeno 1 permutazione soddisfa l'espressione 1..non c'è nemmeno bisogno di calcolarsi le restanti 
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
callo
Forumista
***
Offline Offline

Gender: Male
Posts: 564


"Quanto manca alla vetta?";"Tu sali e non pensare"


« Reply #20 on: 17-04-2011, 23:12:20 »

Ragazzi io ho cercato in internet il modo per evitare permutazioni inutili e ho trovato qualcosa di veramente interessante: Disuguaglianza del riarrangiamento  . Grazie a questa disuguaglianza si capisce a priori quali sono le righe  "papabili" e quali no!!su quelle si facevano le permutazioni fino a trovare il valore di k!In termini pratici su 1000righe di file le papabili erano un centinaio(mooolto meno della metà!) e questo riduceva i tempi di esecuzione in modo drastico!!
Logged

"A cavallina....a cavallina.....a chi era bedda quannu  curreva" [Cit.  Dal Tenerissimo via plebiscito]
Chuck_son
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.583



WWW
« Reply #21 on: 18-04-2011, 11:32:42 »

io avevo pensato all'equazione DIOFANTEA
Logged

Aliens Exist
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #22 on: 18-04-2011, 15:10:38 »

io avevo pensato all'equazione DIOFANTEA
Utilizzata come? 
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
Chuck_son
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.583



WWW
« Reply #23 on: 18-04-2011, 15:18:22 »

io avevo pensato all'equazione DIOFANTEA
Utilizzata come? 

non saprei.. è molto simile alla risoluzione del nostro problema.. ma non ho saputo implementarla
Logged

Aliens Exist
Pages: 1 [2]   Go Up
Print
Jump to: