Trova la somma di Fibonacci Serie

Question

ho dato un Set A devo trovare la somma di Fibonacci somma di tutti i sottoinsiemi di A.

Fibonacci(X) - è l'X Elemento di Fibonacci Serie
Ad esempio, per A = {1,2,3} :

Fibonacci (1) + Fibonacci (2) + Fibonacci (3) + Fibonacci (1 + 2) + Fibonacci (2 + 3) + Fibonacci (1 + 3) + Fibonacci (1 + 2 + 3) 1 + 1 + 2 + 2 + 5 + 3 + 8 = 22

C'è un modo per trovare la somma senza gen erating il sottoinsieme?

poiché trovo la somma di tutte sottoinsieme facilmente
cioè Sum of All Subset - (1+2+3)*(pow(2,length of set-1))

Answer 1

Ci

è sicuramente.

In primo luogo, cerchiamo di ricordare che il numero di Fibonacci n-esimo è uguale

φ (n) = [φ^n - (-φ)^(- n)]/√5

dove φ = (√ 5 + 1)/2 (Golden Ratio) e (-φ)^(- 1) = (1-√5)/2. Ma per renderlo più breve, denoti φ come A e (-φ)^(- 1) come B.

Poi, notiamo che una somma di numeri di Fibonacci è una somma di potenze di A e B:

[φ (n) + φ (m)] * √5 = a^n + a^m - B^n - B^m

Ora, ciò che è sufficiente per calc (nell'esempio {1,2,3}) è

A^1 + A^2 + A^3 + A^{1 + 2} + A^{1 + 3} + A^{2 + 3} + A^{1 + 2 + 3}.

Ma hey, c'è un'espressione più semplice per questo:

(A^1 + 1) (A^2 + 1) (A^3 + 1) - 1

Ora, è il momento per ottenere l'intero risultato.

Lasciate che il nostro set sia {n1, n2, ..., nk}. Allora la nostra somma sarà pari a

Sum = 1/√5 * [(A^n1 + 1)(A^n2 + 1)...(A^nk + 1) - (B^n1 + 1)(B^n2 + 1)...(B^nk + 1)]

Credo che, matematicamente, questa è la forma della risposta "più semplice", come non c'è alcuna relazione tra n_i. Tuttavia, potrebbe esserci spazio per l'ottimizzazione computativa di questa espressione. In effetti, non sono affatto sicuro se questo (usando numeri reali) funzionerà più velocemente del sommario "diretto", ma la domanda era di evitare la generazione di sottoinsiemi, quindi ecco la risposta.

Answer 2

Ho testato la risposta di YakovL utilizzando Python 2.7. Funziona molto bene ed è molto veloce. Non riesco a immaginare che sommando i valori della sequenza sarebbe più veloce. Ecco l'implementazione.

_phi = (5.**0.5 + 1.)/2. 

A = lambda n: _phi**n 
B = lambda n: (-_phi)**(-n) 
prod = lambda it: reduce(lambda x, y: x*y, it) 
subset_sum = lambda s: (prod(A(n)+1 for n in s) - prod(B(n)+1 for n in s))/5**0.5 

e qui ci sono alcuni risultati dei test:

print subset_sum({1, 2, 3}) 
# 22.0 
# [Finished in 0.1s] 

print subset_sum({1, 2, 4, 8, 16, 32, 64, 128, 256, 512}) 
# 7.29199318438e+213 
# [Finished in 0.1s]