Sottosequenza strettamente decrescente

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Casual Ufige Sottile Uomo Sfilacciati Pantaloni Lunghi Streetwear Jeans Ragazzo Traspirante Nne Elasticizzati Estate Moda Strappati Leisure Nero RwT8gqSxAx
Messaggi: 4
Da Montane Blu Marina Donna Montagna Giacca Prism Iscritto il: 08 feb 2006, 20:44

Goosecraft Giacca Black super Donna Schwarz qrHwdq7xS

Lunghi Ragazzi Casual Uomo Slim Blau1 Jeans Neri Blu Tasche Con Strappati Classiche Fit Pantaloni 78ddq0 da Casual Ufige Sottile Uomo Sfilacciati Pantaloni Lunghi Streetwear Jeans Ragazzo Traspirante Nne Elasticizzati Estate Moda Strappati Leisure Nero RwT8gqSxAx » 05 mar 2007, 01:54

Data una sequenza di interi positivi A = (a1, a2,..., an), descrivere ed analizzare un algoritmo che in tempo O(n^2) determini la lunghezza della sua più lunga sottosequenza strettamente decrescente. Si determini poi anche una sottosequenza di tale lunghezza.

Ringrazio chiunque per l'aiuto!

Ciao!

Prism Giacca Marina Montagna Montane Da Donna Blu
Hammond
Messaggi:Jeans Yan Slimjeans Blu Cotone Simmon Uomo HAqaP1 110
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Messaggio da Hammond » 05 mar 2007, 13:08

Premessa: non ho mai capito cosa sia di preciso O(f(n)). Se qualcuno me lo spiega mi fa un piacere.

Comunque cosi' dovrebbe funzionare:
creo gli array a[n] e max[n]. In a ci metto gli elementi della sequenza, mentre max lo riempio di 1. Poi:

Codice: Seleziona tutto

for (i = n; i; i--)
    for (j = i; j < n; j++)
        if ( (a[j] < a[i - 1]) && (max[i - 1] <= max[j]) )
            max[i - 1] = max[j] + 1;
Jeans Blu Up232ds0192t21t800 Dondup Cotone Uomo qXRzzwCnUp232ds0196t26t800 Uomo Dondup Jeans Blu Cotone EzW4BqWS
in pratica max[k] contiene il valore della massima sottosequenza decrescente che parte da a[k] (valore che parte da 1 e si aggiorna di volta in volta). Alla fine il risultato e' dato dal massimo valore presente in max.
Per costruire la sottosequenza, non so se e' il modo migliore, ma si potrebbe fare un array che indichi per ogni elemento il suo successore nella "massima sottosequenza provvisoria", da aggiornare insieme con max.

rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 05 mar 2007, 16:08

Esiste anche un algoritmo classico di complessità O(n log n) che mi pare sia stato già discusso in un topic di questo di forum.

Reese
Marina Donna Montagna Giacca Da Blu Prism Montane Messaggi: Pilot Rot Bomber Uomo Da Ma1 nbsp;bomber Giacca ZanWXPYxOq
Iscritto il: 12 gen 2007, 15:46

Bianca Casuale Slim Formale A color Tuxedo Fit Capispalla Maniche V Giubbotto Monopetto Emmala S Uomo Scollo Tuta Size Senza Vest Jacket Giacche txFEq6HIw da Reese » Jacob Nero Uomo Jeans Cotone Jcu01j69600947black Cohen FqYwzF08 mar 2007, 12:45

Hammond ha scritto:Premessa: non ho mai capito cosa sia di preciso O(f(n)). Se qualcuno me lo spiega mi fa un piacere.
f=O(g) (f e' O-grande di g) significa che |f(x)||Cotone Uomo Blu Jeans 37pcjupa15xd00581d470 Jeckerson 67w8BqWcg(x)|, per una costante positiva c e tutti gli x sufficientemente grandi.
Why would anybody want empathy?

Hammond
Messaggi: 110
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Messaggio da Hammond » 08 mar 2007, 14:12

Grazie Reese, ma come si applica agli algoritmi?
Qui intuitivamente posso pensare che f(n) sia data dal numero di 'passi' che l'algoritmo compie quando ha come input una sequenza di n interi, ma se per esempio non c'e' un dato solo?
Senza contare che non ho idea di cosa siano i 'passi', ne' di come si contino...

lupotresto
Messaggi: 1
Iscritto il: 18 apr 2007, 00:33

Xpression Donna Fashion Donna Fashion Blue Jeans Jeans Xpression twwf67

Messaggio da lupotresto » 18 apr 2007, 00:40

raga auitatemi ho trovato questa soluzione:



c[1]=1
for i=2 to n
max=0
for j=1 to i-1 do
if(x^y>x^i)
then max=c[y]
endif
endfor
c =1+max
endfor
return c


che ne pensate???questo è un esercizio di ptogrammazione dinamica vero?

Rispondi

Torna a “Informatica”