O forse intendi questo ordine???BlaisorBlade ha scritto:Beh, Mind, sei sicuro che quello non vada in tempo ottimo?
Ma quell'algoritmo, che esplorerà tutte le possibili combinazioni, ovvero tutti i sottoinsiemi di tartarughe, non sarà di ordine O(2^n)? O forse no... forse sei stato eccessivamente sintetico ma hai già detto quello giusto.
[...]
Fermo restando il fatto che rimango dubbioso su come lo si possa dimostrare "rigorosamente", io vedrei necessario memorizzare un vettore di lunghezze massime e uno dei pesi raggiunti fino a quel momento, con un elemento per tartaruga; dopodiche' si ripete n volte, ed al piu' su n elementi, una procedura che (qualora la sequenza di tartarughe selezionata non si sia gia' interrotta precendentemente, il che' e' verificabile cofrontando la lunghezza raggiunta con il numero di iterazioni gia' effettuate) controlla se la capacita' della tartaruga successiva (che ha indice k-i, se k e' l'indice della sequenza in questione e i e' il numero di iterazioni gia' effettuate) e' maggiore del peso raggiunto e che in base al risultato del confronto aggiorna i vettori. Alla fine l'elemento con lunghezza massima vince. Non va?MindFlyer ha scritto:Un'altra cosa: bisognerebbe anche dimostrare che l'algoritmo di BlaisorBlade funziona, che è un fatto non ovvio (e del quale non sono nemmeno convinto)...
Bisognerebbe dimostrare che, aggiungendo una nuova tartaruga "dal basso", la sequenza massimale che parte con questa tartaruga si ottiene a partire dalle sequenze massimali finora trovate per le altre tartarughe.
Allora BlaisorBlade, come lo dimostri?
Per induzione (due volte)?MindFlyer ha scritto:L'algoritmo è chiaro.
Come dimostri che funziona??
Ciau Pyv, e benvenuto nel forum!Pyv ha scritto:P.S.: visto che ci sto vi propongo un problemino informatico/matematico: dato un numero 1<=n<=10^9, determinare la cifra piu' significativa di n^n.
Io veramente intendevo memorizzare, per ciascuna tartaruga, la lunghezza della sequenza più lunga che ha sopra tutte le altre quella determinata tartaruga, aggiungendo le successive poi una alla volta dal basso; quando non ce la si può più fare, perchè la nuova tartaruga di base non regge il peso della pila, allora la pila precedente era la più lunga, con quella determinata tartaruga posta alla sommità... siccome poi la pila massima dovrà avere alla sommità una delle tartarughe, e io per ogni tartaruga ho calcolato la pila massima con essa in cima, il massimo lo trovo tra quelli calcolati...MindFlyer ha scritto:Sarò breve: se sono riuscito a capire quello che avete detto, voi memorizzate ad ogni passo soltanto la lunghezza della sequenza più lunga che ha per base ciascuna tartaruga, ed il relativo peso. Poi aggiungete una nuova tartaruga sotto tutte le altre (non sopra, come mi sembra di capire dal discorso di gip), e vedete se può estendere le pile trovate precedentemente. E ok.
Ma la mia domanda è: se voi non considerate tutte le sequenze che si possono formare a partire da una pila non massima nell'iterazione precedente, come garantite di trovare ugualmente il massimo? Insomma, voi usate un algoritmo "greedy", supponendo che dei passaggi localmente ottimi ottimizzino anche il risultato finale. Ma non mi pare ovvio che funzioni, in questo caso.
Oooooh, esatto!!!gip ha scritto:P.S.: un dubbio atroce pervade ora la mia mente: non è che si intendesse sequenze nell'ordine dato, ma formate anche da tartarughe non adiacenti nella configurazione di partenza??????? Se sì ritiro tutto quanto, poiché avevo inteso il contrario...
Amen. Ma qual è il modo banale per avere O(n)?MindFlyer ha scritto:Oooooh, esatto!!!gip ha scritto:P.S.: un dubbio atroce pervade ora la mia mente: non è che si intendesse sequenze nell'ordine dato, ma formate anche da tartarughe non adiacenti nella configurazione di partenza??????? Se sì ritiro tutto quanto, poiché avevo inteso il contrario...
Altrimenti il problema sarebbe banalmente O(n), senza programmazione dinamica e altre diavolerie.