Pagina 1 di 1
Sottosequenza strettamente decrescente
Inviato: 05 mar 2007, 01:54
da etxyz
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!
Inviato: 05 mar 2007, 13:08
da Hammond
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;
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.
Inviato: 05 mar 2007, 16:08
da rand
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.
Inviato: 08 mar 2007, 12:45
da Reese
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 $ \displaystyle |f(x)|\le |cg(x)| $, per una costante positiva c e tutti gli x sufficientemente grandi.
Inviato: 08 mar 2007, 14:12
da Hammond
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...
Inviato: 18 apr 2007, 00:40
da lupotresto
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?