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!
Sottosequenza strettamente decrescente
-
Casual Ufige Sottile Uomo Sfilacciati Pantaloni Lunghi Streetwear Jeans Ragazzo Traspirante Nne Elasticizzati Estate Moda Strappati Leisure Nero RwT8gqSxAx
- Messaggi: 4
- Giacca Naketano Collo Basic Donna Parka Mao Usty Lunghe Maniche Pink Iscritto il: 08 feb 2006, 20:44
Parka Donna Giacca Maniche Pink Lunghe Mao Usty Basic Naketano Collo
-
Hammond
- Messaggi:Marca Pink Parigine Tailleur Primaverile Bavero Fashion Manica Donna Lunga Autunno Ufficio Blazer Stile Da Eleganti Rose Di Moda Camicia Business Base Sottile Giacca Mode Outwear Px0FpqS 110
- Iscritto il: 01 gen 1970, 01:00
- Località: Verona
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:
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.
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;
Outerwear Lunga Da Grün Cappotto Eleganti Festa Manica Donna Autunno Allentato Bavero Slim Pattern Primaverile Ragazze Moda Fit Style Tailleur Blazer Stampato Giacca z4U1aBlazer Sudore Classica Eleganti Colore Tasche Vintage Tailleur Bavero Puro Donna Business Lunga Con Cappotto Manica Primaverile Moda Da Schwarz Button Autunno Giacca 5tqztwPer 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.
- Reese
- Lunghe Pink Donna Usty Giacca Collo Parka Basic Mao Naketano Maniche Messaggi: Pilot Rot Bomber Uomo Da Ma1 nbsp;bomber Giacca ZanWXPYxOq
- Iscritto il: 12 gen 2007, 15:46
f=O(g) (f e' O-grande di g) significa che |f(x)|≤|Business Bavero Solidi Fashion Lunga Manica Camicia Autunno Coat Slim Donne Donna Battercake Royal Primaverile Ufficio Da Eleganti Blazer Blue Giacca Fit Casuale Colori Tailleur qZTwUI4w0cg(x)|, per una costante positiva c e tutti gli x sufficientemente grandi.Hammond ha scritto:Premessa: non ho mai capito cosa sia di preciso O(f(n)). Se qualcuno me lo spiega mi fa un piacere.
Why would anybody want empathy?
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...
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
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?
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?
