Finden Sie die Summe der Fibonacci-Reihe

Question

ich gegeben habe, ein Set A ich die Summe von Fibonacci Summe aller Teilmengen von A.

Fibonacci(X) finden habe - Ist das X-te Element der Fibonacci-Reihe
Zum Beispiel für 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

Gibt es einen Weg, wie ich die Summe ohne Gen finden kann die Teilmenge erraten?

Da ich die Summe aller Teilmenge finden leicht
heißt Sum of All Subset - (1+2+3)*(pow(2,length of set-1))

Answer 1

Es ist sicherlich.

Zuerst lassen Sie uns daran erinnern, dass die n-te Fibonacci-Zahl ist gleich

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

wo φ = (√ 5 + 1)/2 (Goldenes Verhältnis) und (-φ)^(- 1) = (1 - √5)/2. Aber um das kürzer zu machen, lassen Sie mich φ als A und (-φ)^(- 1) als B bezeichnen. Als nächstes bemerken wir, dass eine Summe von Fibonacci-Zahlen eine Summe von Potenzen von A und B ist:

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

Nun, was zu calc genug ist (in dem {1,2,3} Beispiel)

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

Aber hey, es ist ein einfacher Ausdruck dafür:

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

Jetzt ist es an der Zeit um das ganze Ergebnis zu bekommen.

Lassen Sie unser Set {n1, n2, ..., nk} sein. Dann ist unsere Summe gleich sein wird

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

denke ich, mathematisch, das ist die „einfachste“ Form der Antwort, da es keine Beziehung zwischen n_i ist. Es könnte jedoch Spielraum für eine rechnerische Optimierung dieses Ausdrucks geben. In der Tat bin ich überhaupt nicht sicher, ob dies (mit reellen Zahlen) schneller funktioniert als die "einfache" Summierung, aber die Frage war, die Erzeugung von Teilmengen zu vermeiden, also hier ist die Antwort.

Answer 2

Ich habe die Antwort von YakovL mit Python 2.7 getestet. Es funktioniert sehr gut und ist sehr schnell. Ich kann mir nicht vorstellen, dass das Summieren der Sequenzwerte schneller wäre. Hier ist die Implementierung.

_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 

Und hier sind einige Testergebnisse:

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]