Ich versuche, die Grundlagen von C ++ zu lernen, indem ich einige Projekt Euler Probleme durchlaufe. Ich habe es geschafft ... # 2.
Jeder neue Ausdruck im Fibonacci Sequenz wird durch Hinzufügen der vorherige zwei Begriffe. Mit 1 anfangen und 2 sind die ersten 10 Begriffe:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Finde die Summe aller geraden Werte Begriffe in der Reihenfolge, die nicht mehr als vier Millionen.
Meine Logik:
%Vor%Das obige führt durch:
%Vor%Mein Code:
%Vor% Das gibt 4613788 aus
Die richtige Antwort ist jedoch 4613732 .
Ich weiß nicht, was los ist. = /.
Sie verwenden y sowohl als Schleifenvariable als auch als zweiten Term in der Sequenz.
Was Sie vorhaben, ist:
%Vor% Beachten Sie, dass Sie wahrscheinlich auch sum initialisieren sollten.
Der for-Schleife-Codeblock sollte etwas wie
sein %Vor%Grundsätzlich sollten Sie y nicht erhöhen.
So können wir in einer minimalen Anzahl von Schleifen arbeiten. Wenn wir die Fibonacci-Reihe in Bezug auf die ersten beiden Zahlen schreiben, lautet sie:
a, b , (a + b), (a + 2b), (2a+3b) , (3a + 5b), (5a + 8b), (8a+13b) , (13a + 21b), (21a + 34b), (34a+55b) ....
In der obigen Reihe a ist 1 und b ist 2, hervorgehobene Zahlen sind gerade Zahlen. In der Fibonacci-Reihe ist jede dritte Zahl eine gerade Zahl, die Reihenfolge ist EVEN-ODD-ODD-EVEN-. Wenn wir also gerade Zahlen schreiben, ist das folgende Serie:
b, (2a+3b), (8a+13b), (34a+55b), (144a+233b)...
Wenn wir Muster in dieser Serie beobachten, ist coefficient_of_next_a 4*(coefficient_of_current_a)+(coefficient_of_previous_a) .
Und coefficient_of_next_b ist (coefficient_of_current_a)+(coefficient_of_current_b)+(coefficient_of_next_a) .
Python-Code:
%Vor%Ausgabe ist:
%Vor%Hier ist ein Weg, um dieses Problem in O zu lösen (log (N)) - Zeit gegen die langsamere O (N) Implementierung (O (log (N)) kommt von der Notwendigkeit, die pow () -Funktion zu verwenden) .
Zunächst müssen Sie in der Lage sein, die N-te Fibonacci-Zahl in O (log (N)) Zeit zu berechnen:
%Vor%wo PHI = 1,6180339 ... und PSI = -0,61803398 ... (siehe Wiki für weitere Informationen)
Zweitens müssen Sie den nächsten Index für Ihr Ziellimit berechnen (im Fall von Problem 2 wären das 4.000.000):
%Vor%Drittens werden Sie die B & amp; Q-Identität # 25 verwenden (mehr Informationen hier ) für die Berechnung der Summe der geraden Fibonacci-Zahlen:
%Vor%Berechnen Sie schließlich die Summe:
%Vor%Wir brauchen nur jedes dritte Element, um die Summe der geraden Fibonacci-Zahlen zu berechnen.
Hoffe, das hilft! Will
Ich habe kürzlich begonnen, die arkane Kunst von Perl zu studieren ... (LIEBE ES!)
aber ich werde es erklären ... wir brauchen drei Variablen, die wir verschieben unsere 2 Werte, die wir brauchen, um den nächsten Schritt in der Sequenz zu finden (die der dritten Var wie dieser $c=$a;$a=$b;$b=$c; zugewiesen wird) . $a und $b werden im Voraus deklariert, weil wir wissen, dass der fibo damit beginnt ( $a,$b=(0,1) ). Von dort werden wir eine Weile Schleife rollen, solange unsere Variable, die wir in unserem Boot verwenden, weniger als 4mil ( while($a<4*10**6) ) ist. Jede Iteration, die wir auf gerade Zahlen ( $a%2==0 ) mit Modulus und Plus überprüfen, entspricht diesen unserer $ sum-Variablen ( $sum+=$a ). Nach dem Mischen der Variablen (wie bereits erwähnt) ist es nur "Drucken und fertig".
Ich weiß, dass du das in C / C ++ machen wolltest (Perl ist in C geschrieben), aber ich habe nur mit den Euler-Problemen in Perl herumgespielt und dachte, dass dies einen Einblick geben könnte.
Wenn es überhaupt nicht hilft (abgesehen davon, dass Sie nicht die richtige Sprache sind), sagen Sie mir bitte, wie ich meine Antwort verbessern kann, damit ich in Zukunft bessere Antworten geben kann. Am wichtigsten, einen schönen Tag!
Golf irgendjemand?
Versuchen, dem Problem wenig Hilfe hinzuzufügen. Das folgende Programm zeigt alle geraden Fibonacci-Seriennummern für eine gegebene Länge der Reihe, die vom Benutzer eingegeben wird.
%Vor%Tags und Links c++