Problem:
Jeder neue Ausdruck in der Fibonacci-Sequenz wird durch Hinzufügen der vorherige zwei Begriffe.
Wenn Sie mit 1 und 2 beginnen, werden die ersten 10 Begriffe angezeigt sei:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...Unter Berücksichtigung der Terme in der Fibonacci-Sequenz, deren Werte dies nicht tun Überschreiten Sie vier Millionen, finden Sie die Summe der gleichwertigen Begriffe.
Mein Code: (funktioniert gut)
%Vor%Ich suche nach einem effizienteren Algorithmus, um diese Frage zu beantworten. Irgendwelche Hinweise?
Wenn folgende Regeln berücksichtigt werden:
gerade + gerade = gerade
gerade + ungerade = ungerade
ungerade + gerade = ungerade
ungerade + ungerade = gerade
Die Parität der ersten Fibonacci-Zahlen lautet:
o o o o o o o e ...
Im Grunde genommen müssen Sie nur drei Schritte machen. Was ist:
%Vor% Gegeben (a,b,c) Dies ist (b+c,b+2*c,2*b+3*c) .
Das bedeutet, dass wir nur die letzten zwei Zahlen speichern und die angegebene (a,b) , (a+2*b,2*a+3*b) berechnen müssen.
Also (1,2) -> (5,8) -> (21,34) -> ... und immer die letzte zurückgeben.
Dies wird schneller als ein "Filter" -Ansatz arbeiten, da dies die if-Anweisung verwendet, die das Pipelining reduziert.
Der resultierende Code lautet:
%Vor%Oder der jdoodle (mit Benchmarking, dauert 5 Mikrosekunden mit Kaltstart und durchschnittlich 50 Nanosekunden, basierend auf dem Durchschnitt von 1M mal). Natürlich ist die Anzahl der Anweisungen in der Schleife größer. Aber die Schleife wird ein Drittel der Male wiederholt.
Sie können es nicht viel besser verbessern, jede Verbesserung, die Sie vornehmen, ist vernachlässigbar und hängt von dem Betriebssystem ab, auf dem Sie arbeiten.
Beispiel:
Laufen Sie Ihren Code in einer Schleife 1M mal auf meinem Mac auch 73-75ms (lief es ein paar Mal).
Ändern der Bedingung:
zu:
%Vor%und es ein paar Mal wieder laufen, habe ich 51-54ms.
Wie ich in meinem Kommentar erwähnt habe, besteht keine Notwendigkeit für weitere Verbesserungen. Ich habe ein paar Messungen gemacht
so sind einzelne Durchlaufzeiten [ns] diese:
der letzte gewinnt klar auf meiner Maschine (obwohl ich erwarten würde, dass der erste der Beste sein wird)
App ohne Threads 32-Bit-Compiler BDS2006 Trubo C ++
1,2 sind hier in Answers schon schön erwähnt, also kommentiere ich nur 3:
%Vor%(a ^ 1) negiert das liebste Bit
OK, hier ist der Code ( lese nicht weiter, wenn du es selbst codieren willst ):
%Vor%[edit1] schneller Code hinzufügen
[edit2] Noch schneller Code hinzufügen - nur einige Variablen und Operationen für mehr Geschwindigkeit neu anordnen - [76 ns] verringerte die Anzahl der Operanden, um den Overhead und den Heap-Abfall zu verringern
Wenn Sie die Fibonacci-Reihe überprüfen, können Sie für gerade Zahlen 2 8 34 144 610 sehen, dass es eine fantastische Beziehung zwischen geraden Zahlen gibt, zum Beispiel:
%Vor%dies bedeutet, dass als nächstes sogar in Fibonacci wie folgt ausgedrückt werden kann
%Vor%in Java
%Vor%Die Antwort für das Projekt Euler Problem 2 ist (in Java):
%Vor%Dies ist die einfachste Antwort.
F (n) sei die n-te Fibonnaci-Zahl, d. h. F (n) = F (n-1) + F (n-2)
Sagen wir, dass F (n) gerade ist, und dann
F (n) = F (n-1) + F (n-2) = F (n-2) + F (n-3) + F (n-2)
F (n) = 2F (n-2) + F (n-3)
- Dies beweist den Punkt, dass jeder dritte Term gerade ist (wenn F (n-3) gerade ist, dann muss F (n) auch gleich sein)
F (n) = 2 [F (n-3) + F (n-4)] + F (n-3)
= 3F (n-3) + 2F (n-4)
= 3F (n-3) + 2F (n-5) + 2F (n-6)
Aus Gl. 1:
F (n-3) = 2F (n-5) + F (n-6)
2F (n-5) = F (n-3) - F (n-6) -
F (n) = 3F (n-3) + [F (n-3) - F (n-6)] + 2F (n-6)
= 4F (n-3) + F (n-6)
Wenn die Folge gerader Zahlen aus jeder dritten Zahl besteht (n, n-3, n-6, ...)
Sogar Fibonacci-Sequenz:
public static long findEvenFibSum(long n){
long term1=0;
long term2=2;
long curr=0;
long sum=term1+term2;
while((curr=(4*term2+term1))<=n){
sum+=curr;
term1=term2;
term2=curr;
}
return sum;
}