30 maggio 2024 - esercizio 4

[Elia-Belli]

[Elia-Belli]

Programmazione Dinamica (circa)

Non conoscendo una formula finita utilizziamo un approccio ricorsivo per calcolare $c_n$ a partire da problemi più piccoli.

Notiamo che è possibile partizionare le stringhe lunghe $n$ che seguono il nostro criterio in stringhe costituite da:

1. un $1$ iniziale $+$ una stringa lunga $n-1$ che rispetta il criterio
2. uno $0$ iniziale $+$ una stringa lunga $n-1$ che inizia per $1$ e rispetta il criterio (se iniziasse per $0$ ci sarebbe 2 zeri consecutivi)

Indichiamo con $a_n, b_n$ il numero di stringhe rispettivamente del primo e del secondo tipo, segue banalmente che $c_n = a_n + b_n$.
Adesso vorremmo cercare una relazione che ci permetta di calcolare $c_{i+1}$ a partire da $c_i$, osserviamo che:

• Le stringhe del tipo 2 sono costituite in parte da stringhe lunghe $n-1$ che iniziano per $1$, quindi $b_i = a_{i-1}$
• Le stringhe del tipo 1 non hanno vincoli sull'iniziale della sottostringa lunga $n-1$, quindi $a_i = a_{i-1} + b_{i-1}$

Allora partendo dal caso base $a_1 = 1$ e $b_1 = 1$ possiamo realizzare un algoritmo che calcola $c_n$.

def no_00(n):
    i = 1
    a = 1
    b = 1
    c = 1

    while(i <= n):
        b = a       # b_i = a_(i-1)
        a = c       # a_i = c_(i-1) = a_(i-1) + b_(i-1)
        c = a + b   # c_i = a_i + b_i
        i += 1

    return c

[CiottoloMaggico]

Approccio differente, si possono tenere solo gli ultimi 2 elementi dell'array per evitare di usare O(n) memoria

[CarloDaRomadev]