Znajdź sumę Fibonacciego Series

Question

dałem Set A muszę znaleźć sumę Fibonacciego sumę wszystkich podzbiorów A.

Fibonacci(X) - Czy X th Element Fibonacciego serii
Na przykład dla A = {1,2,3} :

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

Czy istnieje sposób, aby znaleźć sumę bez genów erytowanie podzbioru?

Ponieważ uważam, że suma wszystkich podzbioru łatwo
tj Sum of All Subset - (1+2+3)*(pow(2,length of set-1))

Answer 1

Nie

pewno jest.

Najpierw przypomnieć, że n-ta liczba jest równa Fibonacciego

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

gdzie φ = (√ 5 + 1)/2 (złoty stosunek) i (-φ)^(- 1) = (1-√5)/2. Ale żeby było to krótsze, oznaczam φ jako A i (-φ)^(- 1) jako B.

Następnie zwróćmy uwagę, że suma liczb Fibonacciego jest sumą mocy A i B:

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

teraz, co jest wystarczające do Obliczono (w przykładzie {1,2,3}) jest

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

Ale hej, jest to prostsze wyrażenie na to:

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

Teraz nadszedł czas aby uzyskać cały wynik.

Niech nasz zestaw będzie {n1, n2, ..., nk}. Wtedy nasza suma będzie równa

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

myślę, matematycznie, jest to „najprostsza” formą odpowiedzi jak nie ma relacja pomiędzy n_i. Jednak może być trochę miejsca na optymalizację komputerową tego wyrażenia. Właściwie to nie jestem pewien, czy to (używając liczb rzeczywistych) będzie działało szybciej niż "proste" podsumowanie, ale pytanie dotyczyło unikania generowania podzbiorów, więc oto odpowiedź.

Answer 2

Testowałem odpowiedź od YakovL używając Pythona 2.7. Działa bardzo dobrze i jest szybki. Nie mogę sobie wyobrazić, że sumowanie wartości sekwencji byłoby szybsze. Oto implementacja.

_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 

A oto niektóre wyniki badań:

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]