[Algo] Esercizio Programmazione Dinamica

[Pablitos23]

Dare lo pseudocodice di un algoritmo che dato l'intero n, restituisce il numero di stringhe binarie lunghe n in cui compaiono mai uni consecutivi in tempo O(n).
Es. n=4 restituisce 8
0000 1000 0100 0010 0001 1010 1001 0101

La mia idea.

Nstr(n:lunghezza)  -> n
   Z: array dimensione n
   Z[1] = 1
   Z[2] = 2
   for i=3 to n do
      Z[i] = Z[i-1] + Z[i-2]
   return Z[n]

La complessità è banalmente O(n) e l'algoritmo semrbra funzionante dopo 3/4 prove sperimentali anche se non so il perchè.
Potreste darci un'occhiatina per validarmelo o meno??

Grazie e buona serata

[vict85]

Scriviamo con \(\displaystyle Z_n \) il numero di stringhe che cerchi e con \(\displaystyle Z_n^0 \) e \(\displaystyle Z_n^1 \) i numeri di stringhe di lunghezza \(\displaystyle n \) che finiscono rispettivamente con \(\displaystyle 0 \) e \(\displaystyle 1 \) (e rispettano la proprietà in questione). Hai che \(\displaystyle Z_n = Z_n^0 + Z_n^1 \).

Osserva che \(\displaystyle Z_n^0 = Z_{n-1} \) perché qualsiasi elementi di lunghezza \(\displaystyle n-1 \) valido ne forma uno di lunghezza \(\displaystyle n \) valido se si aggiunge uno \(\displaystyle 0 \) alla fine.

Per quanto riguarda \(\displaystyle Z_n^1 \) invece si deve avere che la sottostringa dei primi \(\displaystyle n-1 \) elementi deve finire con uno 0. Pertanto si ha \(\displaystyle Z_n^1 = Z_{n-1}^0 = Z_{n-2} \) per quanto detto prima per \(\displaystyle Z_n^0 \).

[Pablitos23]

Grazie mille chiarissimo

[vict85]

Però direi che \(\displaystyle Z_1 = 2 \) ("0" e "1") e \(\displaystyle Z_2 = 3 \) ("00", "01" e "10").

[Pablitos23]

Si scusa è un refuso.