K-Bonacci

[xxalenicxx]

Ciao a tutti, mi sono appena iscritto e questo è il mio primo post nel forum. Volevo proporvi un problema che a me è sembrato abbastanza carino:

Definiamo il numero n-esimo di K-Bonacci nel seguente modo:

F_{n} = F_{n-1} + F_{n-2} + F_{n-3} + ... + F_{n-k}

F_{1} = 1
F_{2} = 1
F_{3} = 1
.
.
F_{k} = 1

Con F_{0} = 0.

Trovare un algoritmo che calcoli l' n-esimo numero di K-Bonacci in tempo O(log(n)).

[CUCU]

Per 2-Bonacci (Fibonacci classico):
Si consideri la matrice A:
0 1
1 1

Dimostriamo per induzione che l'n-esima potenza di A contiene il (n-1)-esimo numero di Fibonacci in prima posizione, l'n-esimo in seconda ed in terza, e l'(n+1)-esimo in quarta.
La base è verificata dalla definizione di A.
Sia A^n=A^(n-1)A.
Per semplicità sia B=A^n e C=A^(n-1).
Si ha dall'ipotesi induttiva: C1=F(n-2), C2=C3=F(n-1), C4=F(n).
B1=C1*A1+C2*A3=F(n-2)*0+F(n-1)*1=F(n-1)
B2=C1*A2+C2*A4=F(n-2)*1+F(n-1)*1=F(n)
B3=C3*A1+C4*A3=F(n-1)*0+F(n)*1=F(n)
B4=C3*A2+C4*A4=F(n-1)*1+F(n)*1=F(n+1).
Ciò conclude la dimostrazione.

Pertanto per calcolare l'n-esimo numero di fibonacci basta eseguire il susseguente algoritmo:

fib(n)
{

matrici 2x2 A,B,C;
A=
0 1
1 1;
C=B=matrice identità 2x2;
integer i;
if (n==0) return 0;

if (la prima posizione nella rappresentazione binaria di n è 1) C=A;

for (i=2; i<= (la base di log2(n))+1;i=i+1)
if (l'i-esima posizione nella rappresentazione binaria di n contiene 1 (e supponiamo che le posizioni iniziano da 1))
{ C=C*B=B*(A^2); }

print seconda posizione di C;

}

Si può dare una generalizzazione per k-bonacci.
Ne parleremo nei prossimi giorni.

[CUCU]

Ieri notte ero stanco e ho commesso degli errori.
L'algoritmo corretto è il susseguente:

fib(n)
{

matrici 2x2 A,C;
A=
0 1
1 1;
C=matrice identità 2x2;
integer i;

for (i=1; i<= (la base di log2(n))+1;i=i+1)
{
if (l'i-esima posizione nella rappresentazione binaria di n contiene 1 (e supponiamo che le posizioni iniziano da 1))
{ C=C*A; }

A=A^2;
}


print seconda posizione di C;
}

in pratica vogliamo calcolare A^n.
Se n è 2^(i1-1)*2^(i2-1)*...2^(ik-1)
dove i1,i2...ik sono le posizioni nella rappresentazione binaria di n che valgono 1 (e stiamo supponendo che la prima posizione sia la numero 1 (e non 0))
allora calcoliamo C come C=A^(2^(i1-1))*A^(2^(i2-1))*...A^(2^(ik-1))

Dal momento che abbiamo dimostrato che la seconda posizione di A^n conterrà Fib(n)
ciò mostra la correttezza dell'algoritmo.

[xxalenicxx]

Per k = 2 il tuo ragionamento è corretto. Adesso prova ad estendere il ragionamento per k generico, se vogliamo essere più precisi l'upper bound dell'algoritmo è O(log n) se consideriamo k una costante, altrimenti sarà O(k^3 log n).

[CUCU]

Per k = 2 il tuo ragionamento è corretto. Adesso prova ad estendere il ragionamento per k generico, se vogliamo essere più precisi l'upper bound dell'algoritmo è O(log n) se consideriamo k una costante, altrimenti sarà O(k^3 log n).

ma prima rileggi il testo dell'esercizio.
Forse hai sbagliato qualcosa.
Perché non ha senso definire k+1 numeri iniziali, dal momento che F(0) non verrà mai usato.
Rivedi la definizione e poi ne riparliamo.

[xxalenicxx]

Ops scusa hai ragione:
ridefiniamo i casi base:

F_0 = 0

F_1 = 1

F_ 2 = 1
.
.
.
F_{k-1} = 1

Adesso sono k casi base.

[CUCU]

Ops scusa hai ragione:
ridefiniamo i casi base:

F_0 = 0

F_1 = 1

F_ 2 = 1
.
.
.
F_{k-1} = 1

Adesso sono k casi base.

La generalizzazione è immediata:
consideriamo il vettore riga Rk= <0 1 1 .... 1> (con k-1 volte 1)
Consideriamo la matrica di dimensioni kxk
Ak=
0...0 1 (k-1 volte 0 seguito da 1)
I(k-1) U(K-1)

DOVE I(k-1) è la matrice identità (k-1)x(k-1)
e M(k-1) è un vettore colonna di lunghezza k-1 contenente tutti 1

Per esempio per k=4
Ak=
0 0 0 1
1 0 0 1
0 1 0 1
0 0 1 1

Allora per calcolare l'n-esimo numero di K-bonacci:
se n<= k restituiamo l'n-esimo elemento di Rk
altrimenti
{ calcola in maniera analoga a quanto mostrato nell'algoritmo precedente B=A^(n-k+1)
calcola il vettore riga V=R*B
restituisci l'ultimo elemento di V (ossia il (k-1)-esimo)
}

La correttezza di questo algoritmo è evidente:
Se Rk è un vettore che contiene gli elementi F(n-k+1) F(n-k+2)...F(n-1) F(n)
R*Ak= F(n-k+2) F(n-k+3) ... F(n) F(n+1).
il tempo d'esecuzione dell'algoritmo è Theta(f(k)*log(n))
dove f(k) è il tempo d'esecuzione del più veloce algoritmo per la moltiplicazione di matrici kxk

Inoltre si può generalizzare l'algoritmo a qualsiasi relazione di ricorrenza lineare

[xxalenicxx]

Esatto! E' vera anche la tua ultima affermazione, in quanto si può sempre costruire la matrice A per qualsiasi relazione di ricorrenza lineare. Corretta anche la generalizzazione di f(k), io avevo usato f(k) = k^3 per rendere le cose un pò più semplici.

[CUCU]

Esatto! E' vera anche la tua ultima affermazione, in quanto si può sempre costruire la matrice A per qualsiasi relazione di ricorrenza lineare. Corretta anche la generalizzazione di f(k), io avevo usato f(k) = k^3 per rendere le cose un pò più semplici.

Sì, per una generica relazione di ricorrenza LINEARE la matrice Ak sarà come nel precedente post con la sola differenza che l'ultima colonna
sarà il vettore colonna<a_1 a_2 a_3 ... a_k> dove a1, a2,... ak sono i fattori della ricorrenza.

ed ovviamente il vettore Rk conterrà i prim k termini di tale ricorrenza.