Pages: [1]   Go Down
Print
Author Topic: Esercizio LCS pag.302 15.4-4  (Read 1178 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
havoc
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 224


« on: 10-12-2009, 20:13:26 »

Il professore a lezione aveva proposto questo esercizio.
Ecco la mia soluzione (script python):
http://galileo.dmi.unict.it/utenti/havoc/lcs_length.py

Spero sia abbastanza comprensibile... l'ho fatta un po' di corsa nei ritagli di tempo!
Logged

havoc
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 224


« Reply #1 on: 11-12-2009, 11:39:38 »

Premessa: risparmiando spazio si elimina la possibilità di conoscere le LCS.
Riscrivo per comodità la formula della ricorsione:
c[i,j] = 0                                      se i = 0 oppure j = 0
c[i,j] = c[i-1,j-1]+1                      se Xi = Yj
c[i,j] = max(c[i,j-1], c[i-1,j])         altrimenti

Ragionando per righe e guardando la formula ci accorgiamo che per ogni riga ci serve conoscere solo la riga precedente. Sfruttando ciò riusciamo a costruire un algoritmo che conserva soltanto 2*min(m,n) locazioni usando due righe "a turno".

La spiegazione del punto successivo alla prossima puntata! (Cioè appena riesco a trovare un modo per spiegarlo bene)
Logged

havoc
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 224


« Reply #2 on: 12-12-2009, 20:37:31 »

Non sono riuscito a trovare un modo per spiegarlo bene, magari poi provo a fare qualche disegnino... questo è quanto sono riuscito a fare.

Nella precedente versione avevamo due righe: una utilizzata esclusivamente per consultazione e l'altra veniva invece riempita.
Ora invece utilizziamo un singolo array sia per consultazione che per memorizzazione.
Pensando alla tabella dell'algoritmo classico per ogni cella ci può servire il valore in alto, il valore a sinistra e il valore in alto a sinistra, che chiamerò rispettivamente val_n, val_w, val_nw (north, west, north-west).
All'inizio di ogni ciclo esterno l'array conterrà i valori "della riga precedente" e ad ogni iterazione del ciclo interno conserveremo ciò che ci servirà alla successiva iterazione così da poter sovrascrivere le locazioni.
Logged

Pages: [1]   Go Up
Print
Jump to: